דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

תכנון מכרז תחת ערכים תלויים הדדית וסאב-מודולריים: קירוב משופר
event speaker icon
עמיר עאמר, הרצאה סמינריונית למגיסטר
event date icon
יום רביעי, 3.11.2021, 12:30
event location icon
Zoom Lecture: 92257427664
event speaker icon
מנחה:  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.
[בחזרה לאינדקס האירועים]