Back to search

Georgia Institute of Technology

Algorithmic Game Theory

Abstract

dc:description.abstract

The 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.

Degree

thesis:*
Department dc:contributor.department
Computing
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2005

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Mehta, Aranyak
Advisors dc:contributor.advisor
  • Lipton, Richard J.
  • Vazirani, Vijay V.
Committee members dc:contributor.committeemember
  • Mihail, Milena
  • Tovey, Craig
  • Vigoda, Eric

Subjects

dc:subject × 11

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/7220

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Mehta, Aranyak. Algorithmic Game Theory. Georgia Institute of Technology, 2005. http://hdl.handle.net/1853/7220