My research focuses on algorithms, artificial intelligence, social choice, mechanism design and mechanism design. Below are some highlights. For a full list of publications see here. Also, here are links to my Google Scholar and DBLP pages.
Resource Allocation. Resource allocation is a fundamental problem that arises in a wide range of applications in computer science and operations research. Recently I've been especially interested in building algorithmic policy, as well as problems in dynamic fair division. Other representative papers in this space include our EC 2014 paper, joint with Ali Ghodsi and Eric Friedman, for fair strategyproof allocations in a realistic model of cloud computing centers, and our AAAI 2019 paper, joint with Eric Friedman, Vasilis Gkatzelis and Scott Shenker, where we study truthful and fair allocation of a shared memory.
Algorithmic Policy. Algorithms increasingly take governance and management roles in administrative and legal aspects of public and private decision-making. These algorithmic decisions can have a substantial impact on social welfare. How can we design algorithmic governance that is effective yet also moral, promotes overall social welfare, and balances the varying interests of different stakeholders? In the last year we have been working with a food bank called called 412 Food Rescue, an organization in Pittsburgh that matches food donations with non-profit organizations. The goal is to design and deploy a fair and efficient algorithm that would automatically make the decisions they most frequently face: given an incoming food donation, which recipient organization should receive it? We have collected data from each stakeholder (donors, recipients, volunteers and employees) that we used to learn a model of the preferences of each stakeholder. Every time a new dilemma arises, namely which recipient should a new donation go to, we predict a ranking for each stakeholder. Finally, we map these individuals' rankings into a single ranking over the alternatives by applying a voting rule. The voting rule we apply is the Borda count. See our recent paper (joint with Anson Kahng, Min Kyung Lee, Ritesh Noothigattu and Ariel D. Procaccia) for more details about why this is a good choice. Also, check out our other paper for more details about the implementation and stakeholder feedback.
Dynamic Fair Division. Fair division has attracted the attention of mathematicians, economists, political scientists and, more recently, computer scientists. A crucial element that has been left largely unexplored in the literature is the dynamic nature of the environment. In a series of papers we develop a theory of dynamic fair division. In particular, we explore two complementary paradigms: one in which the population of agents changes over time, but the resources shared are fixed; and the other in which the population of agents is fixed, but the resources arrive over time. In joint work with Eric Friedman and Shai Vardi (see our EC 2015 and EC 2017 papers) we develop a model for the dynamic fair division of computational resources among users that arrive and depart over time. A key element of our model is a constraint on the number of jobs the system is allowed to preempt when a new user arrives. We provide algorithms that almost never preempt, but provide surprisingly high fairness guarantees. In joint work with Gerdus Benadè, Aleksandr M. Kazachkov and Ariel D. Procaccia (EC 2018) we study a dynamic fair division problem, where indivisible goods arrive and must be allocated immediately and irrevocably to one of \(n\) agents, where the goal is to minimize the maximum envy between any two agents, after all the goods have been allocated. We give a polynomial-time, deterministic and asymptotically optimal algorithm with vanishing envy, i.e. the maximum envy divided by the number of items \(T\) goes to zero as \(T\) goes to infinity.
Mechanism Design. Mechanism design studies how to implement a desired objective in the presence of strategic behavior. In settings with monetary payments, like auctions, the celebrated VCG mechanism can be used to optimize social welfare and simultaneously incentivize the participants to behave honestly. Our understanding of other objectives, such as revenue optimization, is quite limited. Below I highlight my work in dynamic mechanism design. For some other representative papers on this topic see our STOC 2016 paper with Nikhil Devanur and Zhiyi Huang about sample complexity and revenue maximization, our EC 2017 paper with Nikhil Devanur and Nima Haghpanah about revenue optimal mechanisms in a multi-dimensional setting, and our recent paper with Jonah Brown-Cohen, Arvind Narayanan and Matt Weinberg about formal barriers to designing incentive compatible Proof-of-Stake cryptocurrencies (also see our EC 2018 tutorial on incentives in cryptocurrencies).
Dynamic Auctions. In mechanism design we typically study one-shot auctions. However, multi-stage environments are more common in the real world. My work in this space begins with the observation that restricting to static mechanisms results in significant losses in revenue. Why is it then that dynamic mechanisms are not more prevalent in practice? Surprisingly, in joint work with Christos Papadimitriou, George Pierrakos and Aviad Rubinstein, we prove that the problem of maximizing revenue from selling two items across two rounds using a deterministic mechanism, arguably the simplest meaningful dynamic mechanism design problem imaginable, is computationally intractable. On the other hand, in joint work with Siqi Liu we prove that introducing additional competition to the market and running a simple static mechanism in each round is better, in terms of revenue, than running the optimal dynamic auction. Combined, these results provide a partial answer to the above question. See our SODA 2016 (invited to the GEB Special Issue for best AGT papers from STOC/FOCS/SODA 2016-2017) and SODA 2018 papers for more details.