Show simple item record

dc.contributor.advisorLipton, Richard
dc.contributor.advisorVazirani, Vijay
dc.contributor.authorMehta, Aranyaken_US
dc.date.accessioned2005-09-16T15:14:51Z
dc.date.available2005-09-16T15:14:51Z
dc.date.issued2005-07-19en_US
dc.identifier.urihttp://hdl.handle.net/1853/7220
dc.description.abstractThe interaction of theoretical computer science with game theory and economics has resulted in the emergence of two very interesting research directions. First, it has provided a new model for algorithm design, which is to optimize in the presence of strategic behavior. Second, it has prompted us to consider the computational aspects of various solution concepts from game theory, economics and auction design which have traditionally been considered mainly in a non-constructive manner. In this thesis we present progress along both these directions. We first consider optimization problems that arise in the design of combinatorial auctions. We provide an online algorithm in the important case of budget-bounded utilities. This model is motivated by the recent development of the business of online auctions of search engine advertisements. Our algorithm achieves a factor of $1-1/e$, via a new linear programming based technique to determine optimal tradeoffs between bids and budgets. We also provide lower bounds in terms of hardness of approximation in more general submodular settings, via a PCP-based reduction. Second, we consider truth-revelation in auctions, and provide an equivalence theorem between two notions of strategy-proofness in randomized auctions of digital goods. Last, we consider the problem of computing an approximate Nash equilibrium in multi-player general-sum games, for which we provide the first subexponential time algorithm.en_US
dc.format.extent444799 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectNash equilibriumen_US
dc.subjectCombinatorial auctions
dc.subjectOnline auctions
dc.subjectAconomics
dc.subjectAlgorithms
dc.subjectGame theory
dc.subject.lcshStrategic planning Economic aspectsen_US
dc.subject.lcshMathematical optimizationen_US
dc.subject.lcshInternet auctionsen_US
dc.subject.lcshGame theoryen_US
dc.subject.lcshEquilibrium (Economics)en_US
dc.subject.lcshAlgorithms Designen_US
dc.titleAlgorithmic Game Theoryen_US
dc.typeText
dc.description.degreePh.D.en_US
dc.contributor.departmentComputingen_US
dc.contributor.committeeMemberMihail, Milena
dc.contributor.committeeMemberTovey, Craig
dc.contributor.committeeMemberVigoda, Eric
dc.type.genreDissertation


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record