Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01bv73c356g
 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 theoryAuctionsMechanism designPersuasionRevenueSocial 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. URI: http://arks.princeton.edu/ark:/88435/dsp01bv73c356g Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog: catalog.princeton.edu Type of Material: Academic dissertations (Ph.D.) Language: en Appears in Collections: Computer Science