Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


oberlin1307994412.pdf (292.06 KB)

ETD Abstract Container

Abstract Header

Simple Games on Networks

Kimmel, Jason
http://rave.ohiolink.edu/etdc/view?acc_num=oberlin1307994412

Abstract Details

2011, BA, Oberlin College, Computer Science.
In the same way that traditional game theory captured the minds of economists and allowed complex problems to be studied using simple models, so have games on networks come to be used in computer science. In particular, previous work has focused on extending a two-player base game M over a network G by having each vertex in G chose a strategy from the base game and play it simultaneously against all adjacent nodes. Similarly, the utility for each vertex becomes the sum of the utility of that node in each of the games it plays against its neighbors. The resulting networked game is called M + G. This paper seeks to augment the body of existing work by studying a few similar networked games and finding key characteristics like the existence of Nash equilibria, the price of anarchy, the price of stability, the convergence speed of best response dynamic, and the difficulty of finding the optimal solution. We also reproduce the result that the class of exact potential games is isomorphic to the class of congestion games with a proof that is drastically more readable than the original. Co-authored by Tom Wexler.
Tom Wexler, PhD (Advisor)
17 p.
Computer Science; Mathematics
game theory; graphs; theoretical computer science

Recommended Citations

Citations

  • Kimmel, J. (2011). Simple Games on Networks [Undergraduate thesis, Oberlin College]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=oberlin1307994412

    APA Style (7th edition)

  • Kimmel, Jason. Simple Games on Networks. 2011. Oberlin College, Undergraduate thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=oberlin1307994412.

    MLA Style (8th edition)

  • Kimmel, Jason. "Simple Games on Networks." Undergraduate thesis, Oberlin College, 2011. http://rave.ohiolink.edu/etdc/view?acc_num=oberlin1307994412

    Chicago Manual of Style (17th edition)

oberlin1307994412
509
© 2011, all rights reserved.
This open access ETD is published by Oberlin College Honors Theses and OhioLINK.