Computing Stable Solutions in Threshold Network Flow Games With Bounded Treewidth
Pages 2153 - 2155
Abstract
Network flow games are a prominent model for team formation, where a commodity can flow through a network whose edges are controlled by selfish agents. In Threshold Network Flow Games (TNFGs), an agent team is successful if the flow it can achieve between a source and target vertices meets or exceeds a certain threshold. Cooperative game theory allows predicting how agents are likely to share the the joint reward in such settings, by applying solution concepts such as the core, which characterizes stable reward distributions. When TNFGs have empty cores, every reward distribution is somewhat unstable, which requires using a relaxed solution such as the least-core to find the most stable distribution. Earlier work showed that computing the least-core in TNFGs is computationally hard, but tractable for very restricted graphs, such as layer graphs. We extend these results, presenting polynomial algorithms for the much larger class of bounded-treewidth graphs.
References
[1]
Samir Aknine, Suzanne Pinson, and Melvin F Shakun. 2004. An extended multi-agent negotiation protocol. Autonomous Agents and Multi-Agent Systems, Vol. 8, 1 (2004), 5--45.
[2]
Kenneth J Arrow, Amartya Sen, and Kotaro Suzumura. 2010. Handbook of social choice and welfare. Vol. 2. Elsevier.
[3]
Yoram Bachrach. 2011. The least-core of threshold network flow games. In International Symposium on Mathematical Foundations of Computer Science. Springer, 36--47.
[4]
Yoram Bachrach and Jeffrey S. Rosenschein. 2009. Power in threshold network flow games. Autonomous Agents and Multi-Agent Systems (2009).
[5]
Hans L Bodlaender. 1994. A tourist guide through treewidth. Acta cybernetica, Vol. 11, 1--2 (1994), 1.
[6]
Hans L. Bodlaender. 1997. Treewidth: Algorithmic Techniques and Results. Proceedings 22nd International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 1295 (1997), 29--36.
[7]
Felix Brandt, Vincent Conitzer, and Ulle Endriss. 2012. Computational social choice. Multiagent systems (2012), 213--283.
[8]
Mukun Cao, Xudong Luo, Xin Robert Luo, and Xiaopei Dai. 2015. Automated negotiation for e-commerce decision making: a goal deliberated agent architecture for multi-strategy selection. Decision Support Systems, Vol. 73 (2015), 1--14.
[9]
Georgios Chalkiadakis, Edith Elkind, and Michael Wooldridge. 2011. Computational aspects of cooperative game theory. Synthesis Lectures on Artificial Intelligence and Machine Learning, Vol. 5, 6 (2011), 1--168.
[10]
Georgios Chalkiadakis, Valentin Robu, Ramachandra Kota, Alex Rogers, and Nicholas R Jennings. 2011. Cooperatives of distributed energy resources for efficient virtual power plants. In The 10th International Conference on Autonomous Agents and Multiagent Systems-Volume 2. International Foundation for Autonomous Agents and Multiagent Systems, 787--794.
[11]
Yiling Chen, John K Lai, David C Parkes, and Ariel D Procaccia. 2013. Truth, justice, and cake cutting. Games and Economic Behavior, Vol. 77, 1 (2013), 284--297.
[12]
Yann Chevaleyre, Paul E Dunne, Ulle Endriss, Jérôme Lang, Michel Lemaitre, Nicolas Maudet, Julian Padget, Steven Phelps, Juan A Rodriguez-Aguilar, and Paulo Sousa. 2006. Issues in multiagent resource allocation. (2006).
[13]
Rodney G Downey and Michael Ralph Fellows. 2012. Parameterized complexity .Springer Science & Business Media.
[14]
Joan Feigenbaum, Christos H Papadimitriou, and Scott Shenker. 2001. Sharing the cost of multicast transmissions. J. Comput. System Sci., Vol. 63, 1 (2001), 21--41.
[15]
Donald Bruce Gillies. 1953. Some theorems on n-person games. Ph.D. Dissertation.
[16]
Joseph Greenberg. 1994. Coalition structures. Handbook of game theory with economic applications, Vol. 2 (1994), 1305--1337.
[17]
Robert H Guttman, Alexandros G Moukas, and Pattie Maes. 1998. Agent-mediated electronic commerce: A survey. The Knowledge Engineering Review, Vol. 13, 2 (1998), 147--159.
[18]
Nicholas R Jennings, Peyman Faratin, Alessio R Lomuscio, Simon Parsons, Michael J Wooldridge, and Carles Sierra. 2001. Automated negotiation: prospects, methods and challenges. Group Decision and Negotiation, Vol. 10, 2 (2001), 199--215.
[19]
Ehud Kalai and Eitan Zemel. 1982. Generalized Network Problems Yielding Totally Balanced Games. Operations Research, Vol. 30 (September 1982), 998--1008.
[20]
Ehud Kalai and Eitan Zemel. 1982. Totally balanced games and games of flow. Mathematics of Operations Research, Vol. 7, 3 (1982), 476--478.
[21]
Sven Koenig, Pinar Keskinocak, and Craig A Tovey. 2010. Progress on Agent Coordination with Cooperative Auctions. In AAAI, Vol. 10. 1713--1717.
[22]
Hideo Konishi and Debraj Ray. 2003. Coalition formation as a dynamic process. Journal of Economic theory, Vol. 110, 1 (2003), 1--41.
[23]
M. Maschler, B. Peleg, and L. S. Shapley. 1979. Geometric Properties of the Kernel, Nucleolus, and Related Solution Concepts. Math. Oper. Res. (1979).
[24]
David C Parkes and Michael P Wellman. 2015. Economic reasoning and artificial intelligence. Science, Vol. 349, 6245 (2015), 267--272.
[25]
James Pita, Manish Jain, Janusz Marecki, Fernando Ordó nez, Christopher Portway, Milind Tambe, Craig Western, Praveen Paruchuri, and Sarit Kraus. 2008. Deployed ARMOR protection: the application of a game theoretic model for security at the Los Angeles International Airport. Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems: industrial track. International Foundation for Autonomous Agents and Multiagent Systems, 125--132.
[26]
Neil Robertson and Paul D. Seymour. 1986. Graph minors. II Algorithmic aspects of Tree-width. J.Algorithms, Vol. 7(3) (1986), 309--322.
[27]
Tuomas W Sandhlom and Victor RT Lesser. 1997. Coalitions among computationally bounded agents. Artificial intelligence, Vol. 94, 1--2 (1997), 99--137.
[28]
Tuomas Sandholm. 2002. Algorithm for optimal winner determination in combinatorial auctions. Artificial intelligence, Vol. 135, 1--2 (2002), 1--54.
[29]
P. Scheffler. 1994. A practical linear time algorithm for disjoint paths in graphs with bounded tree--width. Technical Report 396 Berlin, Fachbereich 3 Mathematik 396 (1994).
[30]
Eric Shieh, Bo An, Rong Yang, Milind Tambe, Craig Baldwin, Joseph DiRenzo, Ben Maule, and Garrett Meyer. 2012. Protect: A deployed game theoretic system to protect the ports of the united states. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 1. International Foundation for Autonomous Agents and Multiagent Systems, 13--20.
[31]
Milind Tambe. 2011. Security and game theory: algorithms, deployed systems, lessons learned .Cambridge University Press.
[32]
Maksim Tsvetovat and Katia Sycara. 2000. Customer coalitions in the electronic marketplace. Proceedings of the fourth international conference on Autonomous agents. ACM, 263--264.
[33]
Lirong Xia. 2013. Designing social choice mechanisms using machine learning. In Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems. International Foundation for Autonomous Agents and Multiagent Systems, 471--474.
Index Terms
- Computing Stable Solutions in Threshold Network Flow Games With Bounded Treewidth
Recommendations
Monotone cooperative games and their threshold versions
AAMAS '10: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1 - Volume 1Cooperative games provide an appropriate framework for fair and stable resource allocation in multiagent systems. This paper focusses on monotone cooperative games, a class which comprises a variety of games that have enjoyed special attention within AI,...
Restricted space algorithms for isomorphism on bounded treewidth graphs
The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width are known to be solvable in polynomial time. We give restricted space algorithms for these problems proving the following results:*Isomorphism for ...
On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization)
Stable Marriage is a fundamental problem to both computer science and economics. Four well-known NP-hard optimization versions of this problem are the Sex-Equal Stable Marriage (SESMI), Balanced Stable Marriage (BSMI), max-Stable Marriage with Ties (max-...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2019
2518 pages
ISBN:9781450363099
- General Chairs:
- Edith Elkind,
- Manuela Veloso,
- Program Chairs:
- Noa Agmon,
- Matthew E. Taylor
Sponsors
Publisher
International Foundation for Autonomous Agents and Multiagent Systems
Richland, SC
Publication History
Published: 08 May 2019
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
AAMAS '19
Sponsor:
AAMAS '19: International Conference on Autonomous Agents and Multiagent Systems
May 13 - 17, 2019
Montreal QC, Canada
Acceptance Rates
AAMAS '19 Paper Acceptance Rate 193 of 793 submissions, 24%;
Overall Acceptance Rate 1,155 of 5,036 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 40Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 16 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in