Auctions with Interdependence and SOS: Improved Approximation

07/19/2021
by   Ameer Amer, et al.
0

Interdependent values make basic auction design tasks – in particular maximizing welfare truthfully in single-item auctions – quite challenging. Eden et al. recently established that if the bidders valuation functions are submodular over their signals (a.k.a. SOS), a truthful 4-approximation to the optimal welfare exists. We show existence of a mechanism that is truthful and achieves a tight 2-approximation to the optimal welfare when signals are binary. Our mechanism is randomized and assigns bidders only 0 or 0.5 probabilities of winning the item. Our results utilize properties of submodular set functions, and extend to matroid settings.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset