Abstract:

The talk will begin with a quick (and, inevitably, partial) overview of algorithmic game theory and computational social choice. These are two exciting research agendas that lie at the interface of computer science (in particular, the subfields of TCS and AI that study the design and analysis of algorithms and the foundations of AI systems, respectively) and economics (mostly micro-economics, and in particular game theory and social choice). In this firstpart of the talk, I will give brief snapshots of my related research on topics like sponsored search auctions, matchings with applications to kidney exchanges, interactive democracy, and more. The second and largest part will focus on computing fair allocations of indivisible items among agents with additive valuations for the items. After defining the fairness concept of envy-freeness and the efficiency measure of Nash social welfare, we will present trade-offs between fairness and efficiency. In particular, we will show how to obtain allocations that have high Nash social welfare and are as close to envy-freeness as possible. En route, we will discuss several challenging open problems.