Show simple item record

dc.contributor.authorSyrgkanis, Vasileiosen_US
dc.identifier.otherbibid: 8793480
dc.description.abstractWe provide a unifying theory for the analysis and design of efficient simple mechanisms for allocating resources to strategic players, with guaranteed good properties even when players participate in many mechanisms simultaneously or sequentially and even when they use learning algorithms to identify how to play and have incomplete information about the parameters of the game. These properties are essential in large scale markets, such as electronic marketplaces, where mechanisms rarely run in isolation and the environment is too complex to assume that the market will always converge to the classic economic equilibrium or that the participants will have full knowledge of the competition. We propose the notion of a smooth mechanism, and show that smooth mechanisms possess all the aforementioned desiderata in large scale markets. We further give guarantees for smooth mechanisms even when players have budget constraints on their payments. We provide several examples of smooth mechanisms and show that many simple mechanisms used in practice are smooth (such as formats of position auctions, uniform price auctions, proportional bandwidth allocation mechanisms, greedy combinatorial auctions). We give algorithmic characterizations of which resource allocation algorithms lead to smooth mechanisms when accompanied by appropriate payment schemes and show a strong connection with greedy algorithms on matroids. Last we show how inefficiencies of mechanisms can be alleviated when the market grows large in a canonical manner.en_US
dc.subjecttheoretical computer scienceen_US
dc.subjectprice of anarchyen_US
dc.titleEfficiency Of Mechanisms In Complex Marketsen_US
dc.typedissertation or thesisen_US Science Universityen_US of Philosophy D., Computer Science
dc.contributor.chairTardos, Evaen_US
dc.contributor.committeeMemberSirer, Emin G.en_US
dc.contributor.committeeMemberBlume, Lawrence Edwarden_US
dc.contributor.committeeMemberKleinberg, Robert Daviden_US

Files in this item


This item appears in the following Collection(s)

Show simple item record