EC 2017 Tutorial

Pricing in Combinatorial Markets: Equilibria and Prophet Inequalities

Organizers: Michal Feldman (Tel Aviv University and MSR Herzliya) and Brendan Lucier (Microsoft)

Description:

The focus of this tutorial is efficient resource allocation through posted pricing. In practical combinatorial markets – such as markets for cloud resources and online advertising – simple pricing schemes may be preferable to more general mechanisms due to their transparency, learnability, and robustness. We survey recent lines of work investigating the power of posted prices to resolve combinatorial markets.  The tutorial will be self-contained, and aims to develop useable frameworks for designing price-based mechanisms for allocation problems.

In the first half of the tutorial, we explore a natural connection between pricing under uncertainty and prophet inequalities.  In the traditional prophet inequality setup, a protagonist is presented a sequence of rewards drawn from independent distributions. Whenever a reward is revealed it must either be rejected and lost forever, or accepted irrevocably. The goal is to maximize the expected reward.  In the pricing analogy, the rewards are buyers who arrive sequentially, and the protagonist is a seller who must decide whether to trade with each buyer as he or she arrives.

Recent work has extended prophet inequalities to multiple-choice scenarios, such as accepting many rewards subject to a feasibility constraint (cardinality, matroid, etc.), and choosing among multiple rewards each round (as in matching and combinatorial auctions). These extensions have led to exciting developments in mechanism design for increasingly complex allocation problems.  We will survey this line of work, emphasizing recent developments and open problems.

In the second half of the tutorial, we turn to notions of market equilibrium prices. We take the perspective of a central market-maker who wishes to find prices that (approximately) clear a fully specified, non-stochastic market.  We will survey the classic theory of Walrasian equilibria, which describes market-clearing prices under reasonable but strong assumptions about buyer preferences.  We then describe a spectrum of relaxations: bundle prices, imperfect market clearing, and robustness to tie-breaking.  In many cases, these relaxations extend the applicability of market equilibrium, while simultaneously increasing their robustness to miscoordinated buyer behavior.

Biographies:

Michal Feldman is an Associate Professor in the Blavatnik School of Computer Science at Tel Aviv University and a researcher at Microsoft Research (MSR) Herzliya. Her research focuses on the intersection of computer science, game theory and microeconomics. She received her Ph.D. from the University of California at Berkeley in 2005, and did her postdoc at the Hebrew University (2005-07). She was a faculty member in the School of Business Administration and the Center for the study of rationality at the Hebrew University (2007-13), and a visiting professor at Harvard University and Microsoft Research New England (2011-13). She serves on the editorial board of various journals, including JCSS, MOR and ACM TEAC. She is the vice chair of ACM SIGEcom, and served as the PC chair of ACM Conference on Economics and Computation 2015. She is the recipient of various grants and fellowships, including ERC (European Research Council), Marie Curie IOF, Alon, and ISF. She is a member of the Israeli Young Academy and an alumna of the Global Young Academy.

Brendan Lucier is a Researcher at Microsoft Research, New England. Prior to joining Microsoft, he received his Ph.D. in Computer Science from the University of Toronto. His research interests lie in the intersection of theoretical Computer Science and Economics, and include algorithmic market design, algorithmic pricing, and social processes on networks. He is especially interested in the tradeoffs between simplicity, robustness, and optimality in markets for complex goods and services.

Format: Two lecture-style parts, 1.5 hours each, with a 30-minute break in between.

Related tutorials: The second half of this tutorial is closely related to the tutorial at WINE 2016 on pricing and prophet inequalities.

Related papers: The tutorial will lead up to covering results and open problems from the following papers. This is not an exhaustive list – much of the tutorial will be spent surveying the prior literature discussed in these papers.

· Vincent Cohen-Addad, Alon Eden, Michal Feldman, Amos Fiat, “The Invisible Hand of Dynamic Market Pricing,” EC 2016

· Paul Duetting, Michal Feldman, Thomas Kesselheim, Brendan Lucier, “Posted Prices, Smoothness, and Combinatorial Prophet Inequalities,” working paper: https://arxiv.org/abs/1612.03161

· Michal Feldman, Nick Gravin, Brendan Lucier, “Combinatorial Walrasian Equilibrium,” STOC 2013.

· Michal Feldman, Nick Gravin, Brendan Lucier, “Combinatorial Auctions via Posted Prices,” SODA 2015

· Michal Feldman, Nick Gravin, Brendan Lucier, “On Welfare Approximation and Stable Pricing,” working paper: https://arxiv.org/abs/1511.02399

· Justin Hsu, Jamie Morgenstern, Ryan Rogers, Aaron Roth, Rakesh Vohra. “Do Prices Coordinate Markets?” STOC 2016