Dynamics for network formation games
Abstract/Contents
- Abstract
- Modern communication networks operate at a scale that makes the use of centralized policies/protocols challenging. At the same time, nodes in the network are self-interested strategic agents. It is therefore natural to model the formation of modern communication networks as the result of interactions between self-interested agents; and to consider the observed networks as its equilibrium outcomes. The aim of such modeling is to predict some macroscopic observable, here efficiency. If we want to make the best prediction possible, how should one model the strategic interactions of the agents, and what equilibrium concept should be used? In this thesis, we assume the network is the outcome of a network formation game. The network formation game considered captures two conflicting objectives of self-interested nodes in a network. On one hand, such a node wishes to be able to reach all other nodes in the network; on the other hand, it wishes to minimize its cost of participation. We focus on myopic local best response dynamics for such games, where nodes can only deviate to form links with others in a restricted neighborhood. For two general classes of costs of participating in the network, we show that a static analysis of the network formation game does not provide useful predictions about efficiency. To do so, we identify extrema outcomes, with respect to efficiency, in the equilibrium set and show they correspond to the extrema of all reasonable outcomes. In some cases, this holds true even when using strong stability as equilibrium concept. In terms of efficiency loss, we show the efficiency loss can be linear in the number of nodes. We then show that, for myopic local best response dynamics, if we allow a single node a "one step look-ahead'', the dynamics converge almost surely, and the efficiency loss can be constant. In some cases, our dynamics converge to efficient outcomes. Thus the prediction about efficiency can be as precise as possible, with one unique value predicted, and full efficiency achieved.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Copyright date | 2010 |
| Publication date | 2009, c2010; 2009 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Arcaute Aizpuru, Esteban Daniel |
|---|---|
| Associated with | Stanford University, Institute for Computational and Mathematical Engineering. |
| Primary advisor | Johari, Ramesh, 1976- |
| Thesis advisor | Johari, Ramesh, 1976- |
| Thesis advisor | Jackson, Matthew O |
| Thesis advisor | Mannor, Shie |
| Advisor | Jackson, Matthew O |
| Advisor | Mannor, Shie |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Esteban Daniel Arcaute Aizpuru. |
|---|---|
| Note | Submitted to the Institute for Computational and Mathematical Engineering. |
| Thesis | Ph.D. Stanford University 2010 |
| Location | electronic resource |
Access conditions
- Copyright
- © 2010 by Esteban Daniel Arcaute Aizpuru
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...