Adaptive decision making in information networks
Abstract/Contents
- Abstract
- The goal of this thesis is to develop techniques that enable us to analyze network precesses in which nodes of the network make decisions based on local and limited information. Such processes arise naturally in many information networks such as the World Wide Web (WWW), online social networks, and sensor networks. First we study a stochastic version of the online bipartite matching problem in which the sequence of arrivals are i.i.d samples of a given distribution. We use the ideas of offline statistics and adaptivity to give the first algorithm for this problem that improves the 1 − 1/e competitive ratio of the celebrated algorithm by Karp, Vazirani, and Vazirani, for the stochastic version in its general form. We also model and study the evolution of cooperation in populations with local interactions. Every node of the network corresponds on an individual choosing whether to cooperate or defect in a repeated prisoner's dilemma game. The players try to learn the best action by imitating those neighbors who have higher payoffs. We show that when the interactions take place on graphs with large girth, cooperation is more likely to emerge as a result of local clustering of cooperators. We also consider the practical problem of constructing well-connected sensor networks by locally moving the sensors. We design decentralized algorithms in which sensors identify the critical edges and then move in directions that improve connectivity in more critical regions. In our algorithms, nodes determine their movement direction only with local information exchange with their neighbors.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2011 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | HosseiniKhah Manshadi, Vahideh |
|---|---|
| Associated with | Stanford University, Department of Electrical Engineering |
| Primary advisor | Saberi, Amin |
| Thesis advisor | Saberi, Amin |
| Thesis advisor | Johari, Ramesh, 1976- |
| Thesis advisor | Montanari, Andrea |
| Advisor | Johari, Ramesh, 1976- |
| Advisor | Montanari, Andrea |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Vahideh H. Manshadi. |
|---|---|
| Note | Submitted to the Department of Electrical Engineering. |
| Thesis | Ph.D. Stanford University 2011 |
| Location | electronic resource |
Access conditions
- Copyright
- © 2011 by Vahideh HosseiniKhah Manshadi
- 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...