In a market with repeated sales of a single item to a single buyer, prior work has established the existence of a zero revenue perfect Bayesian equilibrium in the absence of a commitment device for the seller. This counter-intuitive outcome is the result of strategic purchasing decisions, where the buyer worries that the seller will update future prices in response to past purchasing behavior. We first show that in fact almost any revenue can be achieved in equilibrium, but the zero revenue equilibrium uniquely survives natural refinements. This establishes that single buyer markets without commitment are subject to market failure. However, our main result shows that this market failure depends crucially on the assumption of a single buyer. If there are multiple buyers, the seller can approximate the revenue that is possible with commitment. We construct an intuitive equilibrium for multiple buyers that survives our refinements, in which the seller learns from past purchasing behavior and obtains a constant factor of the per-round Myerson optimal revenue. Moreover, we describe a simple and computationally tractable pricing algorithm for the seller that achieves this approximation when buyers best-respond.
Joint work with Nicole Immorlica, Brendan Lucier, and Sam Taggart
Emmanouil Pountourakis is a PhD candidate in the Theory and Economics group of the Department of Electrical Engineering and Computer Science at Northwestern University, advised by Nicole Immorlica. Since 2014 he has been a long term visitor at Microsoft Research, New England. He holds an undergraduate and masters degree in Computer Science from the University of Athens. During Summer 2012 he completed a research internship at CWI, Amsterdam. He was a student visitor in the Institute of Advanced Studies at Hebrew University for the Special Semester in Algorithmic Game Theory in 2011. Emmanouil Pountourakis has a broad interest in algorithmic mechanism design. His current research focuses on revenue maximization in static and dynamic environments, and theoretical analysis of behavioral models of time-discounting. In the past he has worked on a variety of topics including cost-sharing, matching, and mechanism design without money.