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.
| Identifer | oai:union.ndltd.org:GATECH/oai:smartech.gatech.edu:1853/7220 |
| Date | 19 July 2005 |
| Creators | Mehta, Aranyak |
| Publisher | Georgia Institute of Technology |
| Source Sets | Georgia Tech Electronic Thesis and Dissertation Archive |
| Language | en_US |
| Detected Language | English |
| Type | Dissertation |
| Format | 444799 bytes, application/pdf |
Page generated in 0.0143 seconds