Divyarthi Mohan will present her FPO "Simplicity and Optimality in Algorithmic Economics: Multi-Item Auctions and Social Learning" on Wednesday, July 14, 2021 at 2:30PM via Zoom.

Zoom Link: https://princeton.zoom.us/j/94629442885?pwd=SURmMDBwYlg3YUp5YVVCMENvMEUrZz09

The members of Divya’s committee are as follows: Matt Weinberg ( Adviser), Readers: Mark Braverman, Nicole Immorlica (Microsoft Research);  Examiners: Bernard Chazelle, Ran Raz, Matt Weinberg

A copy of her thesis is available upon request.  Please email gradinfo@cs.princeton.edu if you would like a copy of the thesis.

Everyone is invited to attend her talk.

Abstract follows below:

Typically, algorithms are designed to find the best possible solution for a given input, while efficiently using resources. But in many settings, algorithms face an additional challenge: inputs are provided by strategic agents who may have different objectives than those of the algorithm designer. As a result, the field of algorithmic game theory emerged to understand and design algorithms in the presence of strategic agents. This thesis makes progress towards understanding simplicity in algorithmic game theory and when simplicity results in good outcomes; we focus on two main sub areas of algorithmic economics: multi-item auction theory and social learning. We consider the problem of revenue maximization when selling 𝑛 items to a single unit-demand buyer. Unfortunately, optimal auctions for selling multiple items can be un[1]reasonably complex and computationally intractable. Our work shows that simple mechanisms can achieve almost optimal revenue. We approach the tradeoffs of simplicity formally through the lens of computation and menu size. Our main result is a mechanism that gets a (1 − 𝜀)-approximation to the optimal revenue in time quasi-polynomial in 𝑛. We also study how information aggregates in networks through simple majority dynamics. We consider a model where agents make binary decisions, and each agent gets a private signal denoting which decision is better. Our main result proves that when the network is a tree formed according to the preferential attachment model, with high probability, the process stabilizes in a correct majority. Finally, we study a model of social learning between two Bayesian agents (a sender and a receiver) with limited/structured communication. In our model, to reflect real social exchanges, agents simply share a signal (or anecdote) they observed instead of sending arbitrary messages. A key result in our work shows that, when the agents have a fundamental difference, the optimal communication scheme can vary drastically (from sending the most representative anecdote to an extremely biased anecdote) depending on whether the receiver can observe the communication scheme used by the sender.