Approximation guarantees for game-theoretic equilibria
Abstract/Contents
- Abstract
- Game-theoretic equilibria model natural outcomes of selfish behavior. The concept of the "Price of Anarchy (POA)" captures how well game-theoretic equilibria approximate the socially optimal outcome. In this dissertation, we consider the POA in three different models, as a function of different design parameters and equilibrium concepts. We first consider weighted congestion games where players compete to share resources. The cost of a resource depends on the total weight of the players using that resource and players are allowed to use only certain subsets of the resources. Routing games are a canonical example of such games. We provide a precise characterization of the POA as a function of the resource cost functions. We also explore how the POA is affected by the structure of the permitted strategies for the players. Our bounds apply to pure Nash, mixed Nash, correlated, and coarse-correlated equilibria. We next consider opinion formation games, where players in a social network choose opinions to express to minimize the cost of disagreement with their neighbors' opinions and their own intrinsic beliefs. We obtain bounds on the POA with respect to the pure Nash, mixed Nash, and correlated equilibria. We show that the POA is always at most 2 when the cost functions are convex. We provide a more detailed characterization of the the Price of Anarchy as a function of the costs of disagreement. Finally, we consider combinatorial auctions with item bidding. In this model, several goods are sold simultaneously in independent auctions to buyers who have different values for different bundles of goods. We bound the pure Nash and the Bayes-Nash POA when the individual single-item auctions are second price auctions and buyers' valuations over the bundles are subadditive. We provide the first explicit gap between the worst case pure Nash and Bayes-Nash POA. We also consider how the pure Nash POA varies as a function of the payment rule in the underlying single-item auction.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2013 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Bhawalkar, Kshipra |
|---|---|
| Associated with | Stanford University, Department of Computer Science. |
| Primary advisor | Roughgarden, Tim |
| Thesis advisor | Roughgarden, Tim |
| Thesis advisor | Goel, Ashish |
| Thesis advisor | Shoham, Yoav |
| Advisor | Goel, Ashish |
| Advisor | Shoham, Yoav |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Kshipra Bhawalkar. |
|---|---|
| Note | Submitted to the Department of Computer Science. |
| Thesis | Ph.D. Stanford University 2013 |
| Location | electronic resource |
Access conditions
- Copyright
- © 2013 by Kshipra Uday Bhawalkar
Also listed in
Loading usage metrics...