Truth, Envy, and Profit.
Jason Hartline
Northwestern University
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.
This talk will not assume any background in mechanism design. Joint work with Qiqi Yan.