The interaction of theoretical computer science with game theory andeconomics has resulted in the emergence of two very interestingresearch directions. First, it has provided a new model for algorithmdesign, which is to optimize in the presence of strategicbehavior. Second, it has prompted us to consider the computationalaspects of various solution concepts from game theory, economics andauction design which have traditionally been considered mainly in anon-constructive manner. In this thesis we present progress along boththese directions. We first consider optimization problems that arisein the design of combinatorial auctions. We provide an onlinealgorithm in the important case of budget-bounded utilities. Thismodel is motivated by the recent development of the business of onlineauctions of search engine advertisements. Our algorithm achieves afactor of $1-1/e$, via a new linear programming based technique todetermine optimal tradeoffs between bids and budgets. We also providelower bounds in terms of hardness of approximation in more generalsubmodular settings, via a PCP-based reduction. Second, we considertruth-revelation in auctions, and provide an equivalence theorembetween two notions of strategy-proofness in randomized auctions ofdigital goods. Last, we consider the problem of computing anapproximate Nash equilibrium in multi-player general-sum games, forwhich we provide the first subexponential time algorithm.
PDF
download
878987797
028-85220240
