Strategic multiway cut and multicut games. (English) Zbl 1314.91049
Jansen, Klaus (ed.) et al., Approximation and online algorithms. 8th international workshop, WAOA 2010, Liverpool, UK, September 9–10, 2010. Revised papers. Berlin: Springer (ISBN 978-3-642-18317-1/pbk). Lecture Notes in Computer Science 6534, 1-12 (2011).
Summary: We consider cut games where players want to cut themselves off from different parts of a network. These games arise when players want to secure themselves from areas of potential infection. For the game-theoretic version of Multiway Cut, we prove that the price of stability is 1, i.e., there exists a Nash equilibrium as good as the centralized optimum. For the game-theoretic version of Multicut, we show that there exists a 2-approximate equilibrium as good as the centralized optimum. We also give poly-time algorithms for finding exact and approximate equilibria in these games.
For the entire collection see [Zbl 1206.68011].
For the entire collection see [Zbl 1206.68011].
MSC:
| 91A43 | Games involving graphs |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68M10 | Network design and communication in computer systems |
| 91A10 | Noncooperative games |
