Skip navigation
Please use this identifier to cite or link to this item:
Title: Simplicity and Optimality in Algorithmic Economics: Multi-Item Auctions and Social Learning
Authors: Mohan, Divyarthi
Advisors: Weinberg, S. Matthew
Contributors: Computer Science Department
Keywords: Algorithmic game theory
Mechanism design
Social learning
Subjects: Computer science
Issue Date: 2021
Publisher: Princeton, NJ : Princeton University
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.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog:
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Computer Science

Files in This Item:
File Description SizeFormat 
Mohan_princeton_0181D_13820.pdf982.54 kBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.