Simplicity and Optimality in Algorithmic Economics: Multi-Item Auctions and Social Learning

Abstract

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 \emph{simplicity} in algorithmic game theory and when simplicity results in \emph{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 $n$ items to a single unit-demand buyer. Unfortunately, optimal auctions for selling multiple items can be unreasonably 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 \emph{computation} and \emph{menu size}. Our main result is a mechanism that gets a $(1-\varepsilon)$-approximation to the optimal revenue in time quasi-polynomial in $n$. We also study how information aggregates in networks through simple \emph{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 \emph{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 \emph{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.