 | From the Series از مجموعه : Computing with Selfish Agents
Produced by تهيه كننده : Microsoft Research
Date تاريخ : 2005-01-28
Computing with Selfish Agentsdownload دانلود ,ويدئو و اسلايد Video & Slide , از گروه Computer Sience & Engineering كامپيوتر و مهندسی كتابخانه اينترنتي دانش گستران جوان You Research Description توضيح : Many complex systems of our day involve autonomous participants who act in their own self-interest and therefore might lie if it benefits them to do so. The goal in the field of mechanism design is to define rules in the system such that participants acting in their own self-interest will collectively act in a way that optimizes some system objective such as social welfare or revenue. In this talk, I will first present an overview of the basic notions mechanism design and survey some of my recent results in the field.
The focus of the talk will be based on a framework introduced by Goldberg et al. for maximizing revenue in auctions for a good of unlimited supply. Earlier work of Goldberg et al. introduced randomized auction mechanisms that, in the worst case, achieve close to the optimal revenue. We investigate the feasibility of high revenue deterministic auctions. In the process, we give an exponential-space construction for converting any randomized auction to a deterministic one with approximately the same revenue properties. We do so by first proving the existence of a deterministic solution to a related problem, the 'hat coloring problem', in which everyone at a party attempts to guess the color of his own hat by just observing the colors of his friends' hats. Our proof draws upon a seemingly unrelated set of techniques from the literature on network flows. We also present a polynomial-time deterministic construction of an auction with good revenue properties, using parity arguments. Our work bypasses an impossibility result of Goldberg et al. for deterministic symmetric auctions by introducing asymmetry into the allocation and pricing scheme, suggesting that in this setting asymmetry is essentially as powerful as randomness.
This talk is based on joint work with Gaggan Aggarwal, Amos Fiat, Andrew Goldberg, Jason Hartline, and Madhu Sudan.
Related Links لينك‌های مرتبط : -
Computing with Selfish Agentsdownload دانلود ,ويدئو و اسلايد Video & Slide , از گروه Computer Sience & Engineering كامپيوتر و مهندسی كتابخانه اينترنتي دانش گستران جوان You Research Speaker(s) اجرا : Nicole Immorlica, graduate student, Computer Science and Artificial Intelligence Laboratory (CSAIL), Massachusetts Institute of Technology
Runtime مدت زمان : 01:17:11
Video Size حجم ويدئو : 157 MB
Number of Slides تعداد اسلايد‌ها : 107 (15 MB)
Computing with Selfish Agentsdownload دانلود ,ويدئو و اسلايد Video & Slide , از گروه Computer Sience & Engineering كامپيوتر و مهندسی كتابخانه اينترنتي دانش گستران جوان You Research
|
