News & Events

Theory of Computation Seminars

Maximizing Gains From Trade in Two-Sided Markets

Kira Goldner, Columbia University

Sep 21, 2020
1:30 pm to 2:45 pm | ZOOM

In a two-sided market, we maximize the gains from trade: the sum over, for each buyer-seller pair that trades, the buyer's value minus the seller's cost.  Unfortunately, it is impossible to achieve the optimal gains from trade with a mechanism that satisfies the natural budget, truthfulness, and individual rationality constraints [Myerson Satterthwaite '83], so our goal is instead approximation.  Further, approximating the gains from trade objective is more difficult than both approximating welfare in a two-sided market and approximating revenue in a one-sided market.

In one approach, we use a simple mechanism on an augmented market in which we've recruited additional buyers to fully beat the optimal gains from trade in the original market.  In a second approach, we use simple mechanisms to obtain the first approximation in a multidimensional setting.  All of the mechanisms used are in fact quite simple.  We prove their guarantees with ideas from probability and optimization.

Joint work with (1) Moshe Babaioff and Yannai Gonczarowski and (2) Yang Cai, Steven Ma, and Mingfei Zhao.

Speaker Bio

Kira Goldner is a postdoctoral researcher at Columbia University hosted by Tim Roughgarden in the Computer Science department.  Specifically, she is an NSF Mathematical Sciences Postdoctoral Research Fellow and a Data Science Institute Postdoctoral Fellow.  Her research is in algorithmic mechanism design, with work ranging from relaxing traditional behavioral and informational assumptions, maximizing revenue in settings motivated by practice, and applying mechanism design to social good.  Kira also co-founded Mechanism Design for Social Good (MD4SG), an interdisciplinary initiative working to improve access to opportunity for historically disadvantaged communities.  She received her PhD in computer science and engineering from the University of Washington under the advisement of Anna Karlin, during which she was supported by a 2017-19 Microsoft Research PhD Fellowship and a 2016-17 Google Anita Borg Scholarship.


Carol Harlow