zbMATH — the first resource for mathematics

Playing with the maximum-flow problem. (English) Zbl 1415.68158
Barthe, Gilles (ed.) et al., LPAR-22. 22nd international conference on logic for programming, artificial intelligence and reasoning, Awassa, Ethiopia, November 17–21, 2018. Selected papers. Manchester: EasyChair. EPiC Ser. Comput. 57, 18-25 (2018).
Summary: In the traditional maximum-flow problem, the goal is to transfer maximum flow in a network by directing, in each vertex in the network, incoming flow into outgoing edges. The problem has been extensively used in order to optimize the performance of networks in numerous application areas. The definition of the problem corresponds to a setting in which the authority has control on all vertices of the network. Today’s computing environment involves parties that should be considered adversarial. We survey recent studies on flow games, which capture settings in which the vertices of the network are owned by different and selfish entities. We start with the case of two players, max (the authority), which aims at maximizing the flow, and min (the hostile environment), which aims at minimizing the flow. We argue that such flow games capture many modern settings, such as partially-controlled pipe or road systems or hybrid software-defined communication networks. We then continue to the special case where all vertices are owned by min. This case captures evacuation scenarios, where the goal is to maximize the flow that is guaranteed to travel in the most unfortunate routing decisions. Finally, we study the general case, of multiple players, each with her own target vertex. In all settings, we study the problems of finding the maximal flows, optimal strategies for the players, as well as stability and equilibrium inefficiency in the case of multi-player games. We discuss additional variants and their applications, and point to several interesting open problems.
For the entire collection see [Zbl 1407.68021].
68R10 Graph theory (including graph drawing) in computer science
05C21 Flows in graphs
91A43 Games involving graphs
Full Text: DOI