Emergence of Small World Networks Network formation through link selection by selfish nodes
| dc.contributor.author | Börjesson, Martin | |
| dc.contributor.department | Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers) | sv |
| dc.contributor.department | Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers) | en |
| dc.date.accessioned | 2019-07-03T13:07:50Z | |
| dc.date.available | 2019-07-03T13:07:50Z | |
| dc.date.issued | 2013 | |
| dc.description.abstract | A game theoretic approach is taken to the Small World Phenomenon. A standard model for the algorithmic approach is generalised in a game theoretic framework, and the corresponding normal form game is de ned and analysed. The thesis shows that when nodes in the network select long range contacts based on incentives that promote participation in short message chains the game admits a potential function. This implies the existence and optimality of pure Nash equilibria as well as convergence of some known game dynamics. The structure of Nash equilibria is further characterised by showing, theoretically and experimentally, the existence of a symmetric equilibrium. Drawing on results in the literature allows the Price of Anarchy to be lower bounded by (log n). Thus showing that while there are globally optimal equilibrium points the sel sh actions of nodes have a large negative impact on the performance of the network. As an example of this, the convergence behaviour of regret minimizing agents in a fully dynamic version of the game is investigated experimentally. | |
| dc.identifier.uri | https://hdl.handle.net/20.500.12380/174174 | |
| dc.language.iso | eng | |
| dc.setspec.uppsok | Technology | |
| dc.subject | Data- och informationsvetenskap | |
| dc.subject | Computer and Information Science | |
| dc.title | Emergence of Small World Networks Network formation through link selection by selfish nodes | |
| dc.type.degree | Examensarbete för masterexamen | sv |
| dc.type.degree | Master Thesis | en |
| dc.type.uppsok | H |
Ladda ner
Original bundle
1 - 1 av 1
Hämtar...
- Namn:
- 174174.pdf
- Storlek:
- 696.84 KB
- Format:
- Adobe Portable Document Format
- Beskrivning:
- Fulltext