Graphs and Path Equilibria

Details Graphs and Path Equilibria Graphs and Path Equilibria

2007-12-10

arxiv.org/abs/0712.1521v1

Computer Science

Computer Science and Game Theory

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Graphs and Path Equilibria does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Graphs and Path Equilibria, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graphs and Path Equilibria will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-405699