Computing with Selfish Agents [1/2]

Опубликовано 6 сентября 2016, 5:19

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