Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Auctions with Interdependence and SOS: Improved Approximation
event speaker icon
Ameer Amer (M.Sc. Thesis Seminar)
event date icon
Wednesday, 03.11.2021, 12:30
event location icon
Zoom Lecture: 92257427664
event speaker icon
Advisor: Dr. Inbal Talgam-Cohen
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.