Speaker: Stefano Leonardi, Sapienza, University of Rome
Mechanism design for one-sided markets is an area of extensive research in economics and, since more than a decade, in computer science as well. Two-sided markets, on the other hand, have not received the same attention despite the many applications to Internet advertisement and to the sharing economy. We present algorithms and mechanisms for two-sided markets in which both buyers and sellers act strategically.
An ideal goal in two-sided markets is to maximize the social welfare of buyers and sellers with individually rational (IR), incentive compatible (IC) and budget-balanced mechanisms (BB), which requires that the mechanism does not subsidize the market or make an arbitrary profit from the exchange. Unfortunately, Myerson and Satterthwaite proved in 1983 that this goal cannot be achieved even in the bayesian setting and for the simple case of only one buyer and one seller. In this talk I’ll discuss meaningful trade-offs and algorithmic approximations of the above requirements. I’ll present simple two-sided sequential posted price mechanisms which provides a provable good approximation to the optimal social welfare while obeying the IR, IC and BB constraints. The mechanisms work for any number of buyers and sellers with arbitrary, independent distributions and matroid constraints for the case of unit supply buyers and sellers. These mechanisms can be extended to two-sided combinatorial auctions with additive and XOS valuations on subsets of items.
In the second part of the talk, I’ll present a model for reservation exchange of display ads based on establishing a two-sided market between buyer orders that request blocks of impressions for advertiser campaigns and seller orders that offer blocks of page views available in the future. I’ll discuss the computational problems related to the design of an efficient market featured with IC on the buyer side and a revenue sharing scheme that provides sellers with a fair distribution of the revenue collected from buyers.
 Riccardo Colini-Baldeschi, Bart de Keijzer, Stefano Leonardi, Stefano Turchetta.Approximately Efficient Double Auctions with Strong Budget Balance.ACM-SIAM Symposium on Discrete Algorithms, SODA 2016.
 Riccardo Colini-Baldeschi, Paul Goldberg, Bart de Keijzer, Stefano Leonardi, Tim Roughgarden and Stefano Turchetta.Approximately Efficient Two-Sided Combinatorial Auctions. http://arxiv.org/abs/1611.06395
 Gagan Goel, Stefano Leonardi, Vahab Mirrokni, Afshin Nikzad, Renato Paes-Leme.Reservation Exchange Markets for Internet Advertising.International Colloquium on Automata, Languages and Programming, ICALP 2016. http://drops.dagstuhl.de/opus/volltexte/2016/6286/