**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