Graphs and Path Equilibria

摘要

The quest for optimal/stable paths in graphs concerns a few practical or theoretical areas. Taking part in the quest, this paper adopts an abstract, general, equilibrium-oriented approach: it uses (quasi-arbitrary) arc-labelled digraphs, and assumes little about the structure of the sought paths and the definition of equilibrium, i. e. optimality/stability. The paper gives both a sufficient condition and a necessary condition for equilibrium existence for every "graph", pinpoints the difference between these conditions, and shows coincidence when optimality relates to a total order. These results are applied to network routing.