Best-Case and Strong Nash Equilibria

Tim RoughgardenCambridge 2016 · DOI · OpenAlex

Abstract

This lecture has two purposes. The first is to introduce a simple model of network formation that resembles atomic selfish routing games but has positive externalities, meaning that an agent prefers to share the edges of her path with as many other agents as possible. Such games generally have multiple PNE with wildly varying costs. The second purpose of the lecture is to explain two approaches for confining attention to a subset of “reasonable” PNE. Ideally, better worst-case approximation bounds should hold for such a subset than for all PNE, and there should also be a plausible narrative as to why PNE in the subset are more worthy of study than the others.
BibTeX
@inproceedings{roughgarden2016best,
  author = {Tim Roughgarden},
  title = {{Best-Case and Strong Nash Equilibria}},
  booktitle = {Cambridge},
  year = {2016},
  doi = {10.1017/cbo9781316779309.016},
}

Loading related content...

Figure