Divyarthi Mohan will present her Pre-FPO " Simplicity and Optimality in Algorithmic Economics: Multi-item Mechanism Auctions and Social Learning" on Wednesday, March 24 at 10.30am via Zoom. Zoom link: [ https://princeton.zoom.us/j/95620223131?pwd=SWJIOFhQOGd1djR2a0ZVWm8rQUJ0QT09 | https://princeton.zoom.us/j/95620223131?pwd=SWJIOFhQOGd1djR2a0ZVWm8rQUJ0QT09 ] Committee Members: Prof. Matt Weinberg (Advisor) Prof. Bernard Chazelle (Examiner) Prof. Ran Raz (Examiner) Prof. Mark Braverman (Reader) Dr. Nicole Immorlica (Reader) Title: " Simplicity and Optimality in Algorithmic Economics: Multi-item Mechanism Auctions and Social Learning" Abstract. Designing mechanisms to maximize revenue is a fundamental question in mathematical economics, motivated by numerous practical applications like pricing goods, online ad auctions, and spectrum auctions. In his seminal work, Myerson resolved the single-dimensional case by proving that simply posting a take-it-or-leave-it price is the optimal mechanism. Unfortunately, optimal auctions for selling multiple items can be unreasonably complex and computationally intractable. In response, the past decade has seen a long line of work in theoretical computer science studying simple and computationally-efficient auctions through the lens of approximation. These works study particular simple auctions and show that they can get approximately optimal revenue (usually a constant factor). More recently, there are works that move away from this binary take on simplicity and instead explore the trade-off between simplicity and optimality. In this talk, we consider a revenue-maximizing seller with n items facing a single unit-demand buyer. Our work shows that simple mechanisms can achieve almost optimal revenue. We approached the tradeoffs of simplicity formally through the lens of computation and "menu size". Our main result provides a mechanism that gets a (1 − ε)-approximation to the optimal revenue in time quasi-polynomial in n. We introduce the notion of symmetric menu complexity of a mechanism, which counts the number of distinct options the buyer may purchase, up to permutations of the items. We show that the above approximately optimal mechanism has quasi-polynomial symmetric menu complexity. Prior to our work, no sub-exponential upper bounds (or super-polynomial lower bounds) were known in any multi-dimensional setting, for either measure. I will also discuss recent work on social learning between two Bayesian agents with limited/simple communication. In our model, to reflect real social exchanges, agents simply share a signal/anecdote they observed instead of sending arbitrary messages. When the agents have a fundamental difference, we show that 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.