We consider the problem of fairly allocating resources that provide shared utility to agents. Examples include voting to elect a parliament, or deciding how to spend the local community budget, the so-called Participatory Budgeting problem. On the theoretical front, our main contributions are in reasoning about fair solutions that are agnostic to specification of sensitive demographics, and where no coalition of agents have incentive to deviate with their share of resources. On the applied front, we are working with cities to perform fair outreach for civic engagement.
- Advertising for demographically fair outcomes (with L. Gelauff, A. Goel, and S. Yandamuri).
- Approximately stable committee selection (with Zhihao Jiang, and Kangning Wang) STOC '20.
- Group fairness in committee selection (with Yu Cheng, Zhihao Jiang, and Kangning Wang) EC '19.
- Proportionally fair clustering (with Xingyu Chen, Brandon Fain, and Charles Lyu) ICML '19.
- Fair allocations of indivisible public goods (with Brandon Fain and Nisarg Shah) EC '18.
- The core of the Participatory Budgeting problem (with Brandon Fain and Ashish Goel), WINE '16.
Algorithms and Platforms for Collective Decision-making
On the analytic front, we have developed models and algorithms for several key problems in social choice, opinion formation, and preference aggregation in society. Our primary contribution is the design and analysis of "low-complexity" social choice schemes, where randomly chosen small groups of participants collectively make decisions. On the applied front, in collaboration with Ashish Goel and Jim Fishkin, we are building a platform for collaborative decision-making, where randomly chosen groups of people can deliberate policy issues in an automatically moderated video-chat room.
- Concentration of Distortion: The Value of Extra Voters in Randomized Social Choice (with B. Fain and W. Fan) IJCAI '20.
- Improved metric distortion for deterministic social choice rules (with Kangning Wang) EC '19.
- Iterative Local Voting for Collective Decision-making in Continuous Spaces (with N. Garg, V. Kamble, A. Goel, and D. Marn) JAIR '19 (also in WWW '17).
- Random dictatorship with random referee: Constant sample complexity mechanisms for social choice (with B. Fain, A. Goel, and N. Prabhu) AAAI '19.
- Metric distortion of social choice rules: Lower bounds and fairness properties (with A. K. Krishnaswamy and A. Goel) EC '17.
- Sequential deliberation for social choice (with Brandon Fain, Ashish Goel, and Sukolsak Sakshuwong), WINE '17.
Market Design and Scheduling
We develop models for allocation of resources, both one-shot and across time, and efficient algorithms for finding these allocations. We show applications of such algorithms for fair scheduling in data centers and multi-core architectures. A related theme is pricing resources and online allocations, and we design pricing mechanisms under various constraints such as budgets and search friction.
- Dynamic weighted fairness with minimal disruptions (with Sungjin Im, Ben Moseley, and Kirk Pruhs). SIGMETRICS '20.
- Predict and match: Prophet inequalities with uncertain supply. (with R. Alijani, S. Banerjee, S. Gollapudi, and K. Wang) SIGMETRICS '20.
- The segmentation-thickness tradeoff in online marketplaces (with R. Alijani, S. Banerjee, K. Kollias, and S. Gollapudi) SIGMETRICS '19.
- A simple mechanism for a budget constrained buyer (with Yu Cheng, Nick Gravin and Kangning Wang), WINE '18. (Best paper award)
- Competitive algorithms from competitive equilibria (with Sungjin Im and Janardhan Kulkarni) J. ACM '18. (Also in STOC '14 and FOCS '15)
- Segmenting two-sided markets (with Siddhartha Banerjee, Kostas Kollias, and Sreenivas Gollapudi), WWW '17.
Big-Data Processing and Geometric Applications
In collaboration with Pankaj Agarwal, we are exploring algorithms for massive geometric problems such as trajectory analysis and clustering. Our theme is finding properties in data that enable efficient computation, both sequentially and on parallel processors.
- Subtrajectory clustering: Models and algorithms. (with P. K. Agarwal, K. Fox, A. Nath, J. Pan, and E. Taylor) PODS '18.
- ROBUS: Fair cache allocation for data parallel workloads (with Mayuresh Kunjir, Brandon Fain, and Shivnath Babu) SIGMOD '17.
- Parallel algorithms for constructing range and nearest-neighbor search data structures (with P. K. Agarwal, K. Fox, and A. Nath) PODS '16.
- Massively parallel algorithms for computing TIN DEMs and contour trees for large terrains (with P. K. Agarwal, K. Fox, and A. Nath) ACM GIS '16.
- SELFISHMIGRATE: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors (with Sungjin Im, Jana Kulkarni, and Kirk Pruhs), FOCS '14.
- Modeling opinion dynamics in social networks (with Abhimanyu Das and Sreenivas Gollapudi), WSDM '14. Data sets used
- Stochastic regret minimization via Thompson sampling (with Sudipto Guha) COLT '14. See this related blog post on our conjecture.
- Coordination mechanisms from (almost) all scheduling policies (with Sayan Bhattacharya, Sungjin Im, and Janardhan Kulkarni) ITCS '14.
- Coevolutionary opinion formation games (with Kshipra Bhawalkar and Sreenivas Gollapudi), STOC '13.
- On the precision of social and information networks (with Reza Bosagh Zadeh, Ashish Goel, and Aneesh Sharma), COSN '13.
- Approximation algorithms for Bayesian multi-armed bandit problems (with Sudipto Guha) combines papers in STOC '07, ICALP '09, and APPROX '13.
- Adaptive uncertainty resolution in Bayesian combinatorial optimization (with Sudipto Guha) TALG '12 (also in SODA '07).
- Optimal auctions with positive network externalities (with Nima Haghpanah, Nicole Immorlica, and Vahab Mirrokni) EC '11.
- Approximation algorithms for restless bandit problems (with Sudipto Guha and Peng Shi) J. ACM '10 (also in FOCS '07 and SODA '09).
- Budget constrained auctions with heterogeneous items (with Sayan Bhattacharya, Gagan Goel, and Sreenivas Gollapudi) STOC '10.
- Incentive compatible budget elicitation in multi-unit auctions (with Sayan Bhattacharya, Vincent Conitzer, and Lirong Xia) SODA '10.
- Exceeding expectations and clustering uncertain data. (with Sudipto Guha), PODS '09.
- Hybrid keyword search auctions (with Ashish Goel) WWW '09. (Winner of best paper award)
- Optimization of continuous queries with shared expensive filters (with Utkarsh Srivastava and Jennifer Widom) PODS '07.
- Energy efficient monitoring of extreme values in sensor networks (with Adam Silberstein and Jun Yang) SIGMOD '06.
- Asking the right questions: Model driven optimization using probes (with Ashish Goel and Sudipto Guha), PODS '06.
- Adaptive ordering of pipelined stream filters (with Shivnath Babu, Rajeev Motwani, Itaru Nishizawa, and Jennifer Widom) SIGMOD '04.
- Cancer characterization and feature set extraction via discriminative margin clustering (with R. Tibshirani and P. O. Brown) BMC Bioinformatics 5:21, 2004.
- Constant factor approximation for the single sink edge installation problem (with Sudipto Guha and Adam Meyerson) STOC '01.
- Local search heuristics for k-medians and facility location problems (with V. Arya, N. Garg, R. Khandekar, A. Meyerson, and V. Pandit) STOC '01.
- Cost-Distance: Two metric network design (with Adam Meyerson and Serge Plotkin) FOCS '00.
- I/O-complexity of graph algorithms (with Abhiram Ranade) SODA '99.
Slides and Videos
- Talk on Stochastic Optimization at the Algorithms and Uncertainty Boot Camp, Simons Institute, 2016
- Talk on Multidimensional scheduling at the Optimization and Decision Making under Uncertainty Workshop, Simons Institute, 2016.
- Slides from my tutorial on Prophet Inequalities and Stochastic Optimization. Based on my joint work with Sudipto Guha.