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

אירועים

Theory Seminar: The Power of VCG: On Algorithms that are Maximal In Range
event speaker icon
שחר דובזינסקי, מדעי המחשב , האונ' העברית, י-ם
event date icon
יום ראשון, 3.2.2008, 11:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
Consider the following simple type of approximation algorithms: limit the set of possible outcomes, and completely optimize over the restricted subrange. In this talk we will study the power of this type of algorithms in two settings: multi-unit auctions, and combinatorial auctions with subadditive bidders.

From a game-theoretic point of view, our results provide a characterization of the power of the main positive result of mechanism design the VCG mechanism. Another motivation is that our lower bounds might play a crucial role towards setting lower bounds on the power of polynomial time truthful mechanisms. We will explain and discuss these issues.

Joint work with Noam Nisan.
[בחזרה לאינדקס האירועים]