Atomic Splittable Flow Over Time Games
| Autor: | Adamik, Antonia, Sering, Leon |
|---|---|
| Přispěvatelé: | Aspnes, James, Michail, Othon |
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
TheoryofComputation_MISCELLANEOUS Computer Science::Computer Science and Game Theory ComputingMilieux_PERSONALCOMPUTING TheoryofComputation_GENERAL Flows over time Theory of computation → Network flows 05C21 91A12 Cooperation Deterministic queuing Computer Science - Computer Science and Game Theory Optimization and Control (math.OC) Theory of computation → Network games FOS: Mathematics Traffic Atomic splittable games Equilibria Mathematics - Optimization and Control Mathematics of computing → Network flows Theory of computation → Quality of equilibria Computer Science and Game Theory (cs.GT) |
| Zdroj: | Leibniz International Proceedings in Informatics (LIPIcs), 221 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022) |
| ISSN: | 1868-8969 |
| Popis: | In an atomic splittable flow over time game, finitely many players route flow dynamically through a network, in which edges are equipped with transit times, specifying the traversing time, and with capacities, restricting flow rates. Infinitesimally small flow particles controlled by the same player arrive at a constant rate at the player's origin and the player's goal is to maximize the flow volume that arrives at the player's destination within a given time horizon. Here, the flow dynamics are described by the deterministic queuing model, i.e., flow of different players merges perfectly, but excessive flow has to wait in a queue in front of the bottle-neck. In order to determine Nash equilibria in such games, the main challenge is to consider suitable definitions for the players' strategies, which depend on the level of information the players receive throughout the game. For the most restricted version, in which the players receive no information on the network state at all, we can show that there is no Nash equilibrium in general, not even for networks with only two edges. However, if the current edge congestions are provided over time, the players can adapt their route choices dynamically. We show that a profile of those strategies always lead to a unique feasible flow over time. Hence, those atomic splittable flow over time games are well-defined. For parallel-edge networks Nash equilibria exists and the total flow arriving in time equals the value of a maximum flow over time leading to a price of anarchy of 1. Leibniz International Proceedings in Informatics, 221 ISSN:1868-8969 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022) ISBN:978-3-95977-224-2 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|