Graphs and Path Equilibria
| dc.creator | Roux, Stéphane Le | |
| dc.date | 2007-12-10 | |
| dc.date.accessioned | 2026-07-07T08:48:19Z | |
| dc.date.available | 2026-07-07T08:48:19Z | |
| dc.description | The quest for optimal/stable paths in graphs has gained attention in a few practical or theoretical areas. To take part in this quest this chapter adopts an equilibrium-oriented approach that is abstract and general: it works with (quasi-arbitrary) arc-labelled digraphs, and it assumes very little about the structure of the sought paths and the definition of equilibrium, \textit{i.e.} optimality/stability. In this setting, this chapter presents a sufficient condition for equilibrium existence for every graph; it also presents a necessary condition for equilibrium existence for every graph. The necessary condition does not imply the sufficient condition a priori. However, the chapter pinpoints their logical difference and thus identifies what work remains to be done. Moreover, the necessary and the sufficient conditions coincide when the definition of optimality relates to a total order, which provides a full-equivalence property. These results are applied to network routing. | |
| dc.identifier | https://arxiv.org/abs/0712.1521 | |
| dc.identifier | http://arxiv.org/abs/0712.1521 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/143903 | |
| dc.subject | Computer Science and Game Theory | |
| dc.title | Graphs and Path Equilibria | |
| dc.type | text |