Truth or Envy?
Speaker: Jason Hartline , Northwestern University
Date: May 13 2011
Time: 10:30AM to 12:00PM
Location: 32-G449 Patil/Kiva
Host: Costis Daskalakis, CSAIL, MIT
Contact: Be Blackburn, 3-6098, imbe@mit.edu
Relevant URL: We consider (profit maximizing) mechanism design in general settings that include, e.g., position auctions (for selling advertisements on Internet search engines) and single-minded combinatorial auctions. We analyze optimal envy-free pricing in these settings and give economic justification for using optimal envy-free revenue as a benchmark for prior-free mechanism design and analysis. In addition to its economic justification, the envy-free revenue has a very simple structure and a strong connection to incentive compatibility (a.k.a., truthfulness) constraints in mechanism design.
As a first example of the connection between envy-free pricing and incentive compatible mechanism design, because the structures of optimal pricings and optimal mechanisms are similar, we give a mechanism design reduction from structurally rich environments including position auctions (and environments with a matroid structure) to multi-unit auction environments (i.e., auctioning $k$ identical units to $n$ unit-demand agents). For instance, via this reduction we are able to extend all prior-free digital good auctions to position auctions with a factor of two of loss in the approximation factor.
As a second example we extend a variant of the random sampling auction
to get constant approximations for general downward closed (i.e., if
we can serve a given set of agents, we can serve any subset) settings.
Joint work with Qiqi Yan.
See other events that are part of CIS Seminars 2010/2011
See other events happening in May 2011
