Document Open Access Logo

Flow Games

Authors Orna Kupferman, Gal Vardi, Moshe Y. Vardi

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2017.38.pdf
  • Filesize: 0.55 MB
  • 16 pages

Document Identifiers

Author Details

Orna Kupferman
Gal Vardi
Moshe Y. Vardi

Cite As Get BibTex

Orna Kupferman, Gal Vardi, and Moshe Y. Vardi. Flow Games. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FSTTCS.2017.38

Abstract

In the traditional maximal-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. While the problem has been extensively used in order to optimize the performance of networks in numerous application areas, it 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 introduce and study {\em flow games}, which capture settings in which the authority can control only part of the vertices. In these games, the vertices are partitioned between two players: the authority and the environment. While the authority aims at maximizing the flow, the environment need not cooperate. We argue that flow games capture many modern settings, such as partially-controlled pipe or road systems or hybrid software-defined communication networks. 
We show that the problem of finding the maximal flow as well as an optimal strategy for the authority in an acyclic flow game is $\Sigma_2^P$-complete, and is already $\Sigma_2^P$-hard to approximate. We study variants of the game: a restriction to strategies that ensure no loss of flow, an extension to strategies that allow non-integral flows, which we prove to be stronger, and a dynamic setting in which a strategy for a vertex is chosen only once flow reaches the vertex. 
We discuss additional variants and their applications, and point to several interesting open problems.

Subject Classification

Keywords
  • Flow networks
  • Two-player Games
  • Algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. Agarwal, M. S. Kodialam, and T. V. Lakshman. Traffic engineering in software defined networks. In Proc. 32nd IEEE International Conference on Computer Communications, pages 2211-2219, 2013. Google Scholar
  2. R.K. Ahuja, T.L. Magnanti, and J.B. Orlin. Network flows: Theory, algorithms, and applications. Prentice Hall Englewood Cliffs, 1993. Google Scholar
  3. B. Aminof, O. Kupferman, and R. Lampert. Rigorous approximated determinization of weighted automata. Theoretical Computer Science, 480:104-117, 2013. Google Scholar
  4. E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and T. Roughgarden. The price of stability for network design with fair cost allocation. SIAM J. Comput., 38(4):1602-1623, 2008. Google Scholar
  5. T. Bartnicki, J. A. Grytczuk, H. A. Kierstead, and X. Zhu. The map coloring game. AmericanMathematical Monthly, 114:793-803, 2007. Google Scholar
  6. A.K. Chandra, D.C. Kozen, and L.J. Stockmeyer. Alternation. Journal of the Association for Computing Machinery, 28(1):114-133, 1981. Google Scholar
  7. S.A. Cook. Path systems and language recognition. In Proc. 2nd ACM Symp. on Theory of Computing, pages 70-72, 1970. Google Scholar
  8. S.A. Cook. The complexity of theorem-proving procedures. In Proc. 3rd ACM Symp. on Theory of Computing, pages 151-158, 1971. Google Scholar
  9. T.H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms. MIT Press and McGraw-Hill, 1990. Google Scholar
  10. E.A. Dinic. Algorithm for solution of a problem of maximum flow in a network with power estimation. Soviet Math. Doll, 11(5):1277-1280, 1970. English translation by RF. Rinehart. Google Scholar
  11. J. Edmonds and R.M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19(2):248-264, 1972. Google Scholar
  12. S. Even, A. Itai, and A. Shamir. On the complexity of timetable and multicommodity flow problems. SIAM Journal on Computing, 5(4):691-703, 1976. Google Scholar
  13. J. Feigenbaum, C.H. Papadimitriou, R. Sami, and S. Shenker. A BGP-based mechanism for lowest-cost routing. Distributed Computing, 18(1):61-72, 2005. Google Scholar
  14. J. Ferrante and C. Rackoff. A decision procedure for the first order theory of real addition with order. SIAM Journal on Computing, 4(1):69-76, 1975. Google Scholar
  15. M.J. Fischer and M.O. Rabin. Super-exponential complexity of presburger arithmetic. In Quantifier Elimination and Cylindrical Algebraic Decomposition, pages 27-41, 1974. Google Scholar
  16. L.R. Ford and D.R. Fulkerson. Maximal flow through a network. Canadian journal of Mathematics, 8(3):399-404, 1956. Google Scholar
  17. L.R. Ford and D.R. Fulkerson. Flows in networks. Princeton Univ. Press, Princeton, 1962. Google Scholar
  18. Z. Füredi, D. Reimer, and A. Seress. Triangle-free game and extremal graph problems. Congressus Numerantium, 82:123-128, 1991. Google Scholar
  19. A.V. Goldberg, É. Tardos, and R.E. Tarjan. Network flow algorithms. Technical report, DTIC Document, 1989. Google Scholar
  20. A.V. Goldberg and R.E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM, 35(4):921-940, 1988. Google Scholar
  21. D. Hefetz, M. Krivelevich, A. Naor, and M. Stojaković. On saturation games. European Journal of Combinatorics, 41:315-335, 2016. Google Scholar
  22. D. Hefetz, O. Kupferman, A. Lellouche, and G. Vardi. Spanning-tree games. To appear, 2018. Google Scholar
  23. N. Immerman. Number of quantifiers is better than number of tape cells. Journal of Computer and Systems Science, 22(3):384-406, 1981. Google Scholar
  24. E. Kalai and E. Zemel. Totally balanced games and games of flow. Mathematics of Operations Research, 7(3):476-478, 1982. Google Scholar
  25. S. Keren, A. Gal, and E. Karpas. Goal recognition design for non optimal agents. In Proc. 29th AAAI conference, pages 3298-3304, 2015. Google Scholar
  26. D. Kozen. Lexicographic flow. Technical Report http://hdl.handle.net 13018, Computing and Information Science, Cornell University, June 2009. Google Scholar
  27. O. Lichtenstein and A. Pnueli. Checking that finite state concurrent programs satisfy their linear specification. In Proc. 12th ACM Symp. on Principles of Programming Languages, pages 97-107, 1985. Google Scholar
  28. N. Nisan, T. Roughgarden, E. Tardos, and V.V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007. Google Scholar
  29. M. J. Osborne and A. Rubinstein. A Course in Game Theory. The MIT Press, 1994. Google Scholar
  30. A. Pnueli and R. Rosner. On the synthesis of a reactive module. In Proc. 16th ACM Symp. on Principles of Programming Languages, pages 179-190, 1989. Google Scholar
  31. L. Qingsong, G. Betsy, and S. Shashi. Capacity constrained routing algorithms for evacuation planning: A summary of results. In International Symposium on Spatial and Temporal Databases, pages 291-307. Springer, 2005. Google Scholar
  32. B.L. Schwartz. Possible winners in partially completed tournaments. SIAM Review, 8(3):302-308, 1966. Google Scholar
  33. L.J. Stockmeyer. On the combinational complexity of certain symmetric boolean functions. Mathematical Systems Theory, 10:323-336, 1977. Google Scholar
  34. É. Tardos. A strongly polynomial minimum cost circulation algorithm. Combinatorica, 5(3):247-255, 1985. Google Scholar
  35. S. Vissicchio, L. Vanbever, and O. Bonaventure. Opportunities and research challenges of hybrid software defined networks. Computer Communication Review, 44(2):70-75, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact