×

zbMATH — the first resource for mathematics

Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability. (English) Zbl 1419.68188
Summary: Coalition structure generation is the problem of partitioning the agents of a given environment into disjoint and exhaustive coalitions so that the whole available worth is maximized. While this problem has been classically studied in settings where all coalitions are allowed to form, it has been recently reconsidered in the literature moving from the observation that environments often forbid the formation of certain coalitions. By following this latter perspective, a model for coalition structure generation is proposed where constraints of two different kinds can be expressed simultaneously. Indeed, the model is based on the concept of valuation structure, which consists of a set of pivotal agents that are pairwise incompatible, plus an interaction graph prescribing that a coalition \(C\) can form only if the subgraph induced over the nodes/agents in \(C\) is connected.
It is shown that valuation structures can be used to model a number of relevant problems arising in real-world application domains. Then, the complexity of coalition structure generation over valuation structures is studied, by assuming that the functions associating each coalition with its worth are given as input according to some compact encoding – rather than explicitly listing all exponentially-many associations. In particular, islands of tractability are identified based on the topological properties of the underlying interaction graphs and on suitable algebraic properties of the given worth functions. Finally, stability issues over valuation structures are studied too, by considering the core as the prototypical solution concept.
MSC:
68T42 Agent technology and artificial intelligence
68Q25 Analysis of algorithms and problem complexity
91A12 Cooperative games
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arnborg, S.; Lagergren, J.; Seese, D., Easy problems for tree-decomposable graphs, J. Algorithms, 12, 2, 308-340, (1991) · Zbl 0734.68073
[2] Aziz, H.; de Keijzer, B., Complexity of coalition structure generation, (Proc. of AAMAS ’11, (2011)), 191-198
[3] Aziz, H.; de Keijzer, B., Shapley meets Shapley, (Proc. of STACS’14, (2014)), 99-111 · Zbl 1359.68116
[4] Bachrach, Y.; Kohli, P.; Kolmogorov, V.; Zadimoghaddam, M., Optimal coalition structure generation in cooperative graph games, (Proc. of AAAI’13, (2013)), 81-87
[5] Bachrach, Y.; Meir, R.; Jung, K.; Kohli, P., Coalitional structure generation in skill games, (Proc. of AAAI’10, (2010)), 703-708
[6] Bansal, N.; Blum, A.; Chawla, S., Correlation clustering, Mach. Learn., 56, 1-3, 89-113, (2004) · Zbl 1089.68085
[7] Basu, S.; Davidson, I.; Wagstaff, K., Constrained clustering: advances in algorithms, theory, and applications, (2008), Chapman & Hall/CRC
[8] Bentz, C., On the complexity of the multicut problem in bounded tree-width graphs and digraphs, Discrete Appl. Math., 156, 10, 1908-1917, (2008) · Zbl 1152.68038
[9] Bistaffa, F.; Farinelli, A.; Cerquides, J.; Rodríguez-Aguilar, J.; Ramchurn, S., Anytime coalition structure generation on synergy graphs, (Proc. of AAMAS’14, (2014)), 13-20
[10] Bodlaender, H. L., Dynamic programming on graphs with bounded treewidth, (Proc. of ICALP’88, (1988)), 105-118 · Zbl 0684.68047
[11] Bodlaender, H. L., A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25, 6, 1305-1317, (1996) · Zbl 0864.68074
[12] Bonchi, F.; Gionis, A.; Gullo, F.; Ukkonen, A., Chromatic correlation clustering, (Proc. of KDD’12, (2012)), 1321-1329
[13] Breton, M.; Owen, G.; Weber, S., Strongly balanced cooperative games, Int. J. Game Theory, 20, 4, 419-427, (1992) · Zbl 0763.90103
[14] Chalkiadakis, G.; Elkind, E.; Wooldridge, M., Computational aspects of cooperative game theory, Synth. Lect. Artif. Intell. Mach. Learn., 5, 6, 1-168, (2011)
[15] Chalkiadakis, G.; Greco, G.; Markakis, E., Characteristic function games with restricted agent interactions: core-stability and coalition structures, Artif. Intell., 232, 76-113, (2016) · Zbl 1351.68292
[16] Chopra, S.; Rao, M. R., On the multiway cut polyhedron, Networks, 21, 1, 51-89, (1991) · Zbl 0746.90077
[17] Conitzer, V.; Sandholm, T., Complexity of constructing solutions in the core based on synergies among coalitions, Artif. Intell., 170, 6-7, 607-619, (2006) · Zbl 1131.91305
[18] Costa, M.-C.; Billionnet, A., Multiway cut and integer flow problems in trees, Electron. Notes Discrete Math., 17, 105-109, (2004) · Zbl 1152.90353
[19] Courcelle, B., Graph rewriting: an algebraic and logic approach, (Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics, (1990), The MIT Press Cambridge, MA, USA), 193-242 · Zbl 0900.68282
[20] Cowans, P. J.; Szummer, M., A graphical model for simultaneous partitioning and labeling, (Proc. of AISTATS’05, (2005)), 73-80
[21] Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M., The complexity of multiterminal cuts, SIAM J. Comput., 23, 4, 864-894, (1994) · Zbl 0809.68075
[22] Dang, V. D.; Jennings, N. R., Generating coalition structures with finite bound from the optimal guarantees, (Proc. of AAMAS’04, (2004)), 564-571
[23] Dechter, R., Constraint processing, (2003), Morgan Kaufmann Publishers Inc. San Francisco, CA, USA
[24] Demange, G., Intermediate preferences and stable coalition structures, J. Math. Econ., 23, 1, 45-58, (1994) · Zbl 0791.90078
[25] Demange, G., On group stability in hierarchies and networks, J. Polit. Econ., 112, 4, 754-778, (2004)
[26] Demange, G., The strategy structure of some coalition formation games, Games Econ. Behav., 65, 1, 83-104, (2009) · Zbl 1165.91316
[27] Deng, X.; Papadimitriou, C. H., On the complexity of cooperative solution concepts, Math. Oper. Res., 19, 2, 257-266, (1994) · Zbl 0824.90146
[28] Edgeworth, F. Y., Mathematical psychics: an essay on the mathematics to the moral sciences, (1881), C. Kegan Paul & Co. London · Zbl 0005.17402
[29] Elkind, E.; Chalkiadakis, G.; Jennings, N. R., Coalition structures in weighted voting games, (Proc. of ECAI’08, (2008)), 393-397
[30] Elkind, E.; Goldberg, L. A.; Goldberg, P. W.; Wooldridge, M., On the computational complexity of weighted voting games, Ann. Math. Artif. Intell., 56, 2, 109-131, (2009) · Zbl 1185.91081
[31] Elkind, E.; Rahwan, T.; Jennings, N. R., Computational coalition formation, (Multiagent Systems, (2013), MIT Press), 329-380
[32] Gillies, D. B., Solutions to general non-zero-sum games, (Contributions to the Theory of Games, vol. IV, Ann. Math. Stud., vol. 40, (1959), Princeton University Press Princeton, NJ, USA), 47-85 · Zbl 0085.13106
[33] Giotis, I.; Guruswami, V., Correlation clustering with a fixed number of clusters, (Proc. of SODA’06, (2006)), 1167-1176 · Zbl 1194.62087
[34] Gottlob, G.; Greco, G., Decomposing combinatorial auctions and set packing problems, J. ACM, 60, 4, 24:1-24:39, (2013) · Zbl 1281.91088
[35] Gottlob, G.; Greco, G.; Leone, N.; Scarcello, F., Hypertree decompositions: questions and answers, (Proc. of PODS’16, (2016)), 57-74
[36] Gottlob, G.; Greco, G.; Scarcello, F., Treewidth and hypertree width, (Tractability: Practical Approaches to Hard Problems, (2013), Cambridge University Press), 1-38
[37] Gottlob, G.; Lee, S. T., A logical approach to multicut problems, Inf. Process. Lett., 103, 4, 136-141, (2007) · Zbl 1190.90032
[38] Greco, G.; Lupia, F.; Scarcello, F., Structural tractability of Shapley and Banzhaf values in allocation games, (Proc. of IJCAI’15, (2015)), 547-553
[39] Greco, G.; Malizia, E.; Palopoli, L.; Scarcello, F., On the complexity of core, kernel, and bargaining set, Artif. Intell., 175, 12-13, 1877-1910, (2011) · Zbl 1233.91018
[40] Greco, G.; Scarcello, F., Structural tractability of constraint optimization, (Proc. of CP’11, (2011)), 340-355
[41] Greco, G.; Scarcello, F., Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems, Inf. Comput., 252, 201-220, (2017) · Zbl 1355.68121
[42] Guo, J.; Hüffner, F.; Kenar, E.; Niedermeier, R.; Uhlmann, J., Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs, Eur. J. Oper. Res., 186, 2, 542-553, (2008) · Zbl 1138.90345
[43] Ieong, S.; Shoham, Y., Marginal contribution nets: a compact representation scheme for coalitional games, (Proc. of EC’05, (2005)), 193-202
[44] Johnson, D. S., A catalog of complexity classes, (Handbook of Theoretical Computer Science, Algorithms and Complexity, vol. A, (1990), The MIT Press Cambridge, MA, USA), 67-161 · Zbl 0900.68246
[45] Kalai, E.; Zemel, E., On totally balanced games and games of flow, (1980), Center for Mathematical Studies in Economics and Management Science, Northwestern University Evanston, IL, USA, Discussion Paper 413
[46] Keinänen, H., Simulated annealing for multi-agent coalition formation, (Proc. of KES-AMSTA’09, (2009)), 30-39
[47] Kleinberg, J.; Tardos, E., Algorithm design, (2005), Addison Wesley Boston, MA, USA
[48] Krentel, M. W., The complexity of optimization problems, (Proc. of STOC’86, (1986)), 69-76
[49] Megiddo, N., Computational complexity of the game theory approach to cost allocation for a tree, Math. Oper. Res., 3, 3, 189-196, (1978) · Zbl 0397.90111
[50] Michalak, T.; Sroka, J.; Rahwan, T.; Wooldridge, M.; McBurney, P.; Jennings, N. R., A distributed algorithm for anytime coalition structure generation, (Proc. of AAMAS’10, (2010)), 1007-1014
[51] Myerson, R. B., Graphs and cooperation in games, Math. Oper. Res., 2, 3, 225-229, (1977) · Zbl 0402.90106
[52] Ohta, N.; Conitzer, V.; Ichimura, R.; Sakurai, Y.; Iwasaki, A.; Yokoo, M., Coalition structure generation utilizing compact characteristic function representations, (Proc. of CP’09, (2009)), 623-638
[53] Osborne, M. J.; Rubinstein, A., A course in game theory, (1994), The MIT Press Cambridge, MA, USA · Zbl 1194.91003
[54] Papadimitriou, C. H., Computational complexity, (1994), Addison Wesley Reading, MA, USA · Zbl 0557.68033
[55] Pichler, R.; Rümmele, S.; Woltran, S., Multicut algorithms via tree decompositions, (Proc. of CIAC’10, (2010)), 167-179 · Zbl 1284.68303
[56] Rahwan, T.; Jennings, N. R., An algorithm for distributing coalitional value calculations among cooperating agents, Artif. Intell., 171, 8-9, 535-567, (2007) · Zbl 1168.68588
[57] Rahwan, T.; Jennings, N. R., An improved dynamic programming algorithm for coalition structure generation, (Proc. of AAMAS’08, (2008)), 1417-1420
[58] Rahwan, T.; Michalak, T. P.; Elkind, E.; Faliszewski, P.; Sroka, J.; Wooldridge, M.; Jennings, N. R., Constrained coalition formation, (Proc. of AAAI’11, (2011)), 719-725
[59] Rahwan, T.; Michalak, T. P.; Wooldridge, M.; Jennings, N. R., Coalition structure generation: a survey, Artif. Intell., 229, 139-174, (2015) · Zbl 1344.68249
[60] Rahwan, T.; Ramchurn, S. D.; Jennings, N. R.; Giovannucci, A., Anytime algorithm for optimal coalition structure generation, J. Artif. Intell. Res., 34, 521-567, (2009) · Zbl 1182.68264
[61] Robertson, N.; Seymour, P., Graph minors III: planar tree-width, J. Comb. Theory, Ser. B, 36, 1, 49-64, (1984) · Zbl 0548.05025
[62] Sandholm, T.; Larson, K.; Andersson, M.; Shehory, O.; Tohmé, F., Coalition structure generation with worst case guarantees, Artif. Intell., 111, 1-2, 209-238, (1999) · Zbl 0997.91004
[63] Schrijver, A., Theory of linear and integer programming, (1998), John Wiley & Sons New York, NY, USA · Zbl 0970.90052
[64] Sen, S.; Dutta, P. S., Searching for optimal coalition structures, (Proc. of ICMAS’00, (2000)), 287-292
[65] Shehory, O.; Kraus, S., Methods for task allocation via agent coalition formation, Artif. Intell., 101, 1-2, 165-200, (1998) · Zbl 0908.68032
[66] Ueda, S.; Iwasaki, A.; Yokoo, M.; Silaghi, M.-C.; Hirayama, K.; Matsui, T., Coalition structure generation based on distributed constraint optimization, (Proc. of AAAI’10, (2010)), 197-203
[67] Ueda, S.; Kitaki, M.; Iwasaki, A.; Yokoo, M., Concise characteristic function representations in coalitional games based on agent types, (Proc. of AAMAS’11, (2011)), 1271-1272
[68] Vazirani, V., Approximation algorithms, (2001), Springer-Verlag, Inc. New York, NY, USA · Zbl 1138.90417
[69] Voice, T.; Polukarov, M.; Jennings, N. R., Coalition structure generation over graphs, J. Artif. Intell. Res., 45, 1, 165-196, (2012) · Zbl 1253.68183
[70] Voice, T.; Ramchurn, S. D.; Jennings, N. R., On coalition formation with sparse synergies, (Proc. of AAMAS’12, (2012)), 223-230
[71] von Neumann, J.; Morgenstern, O., Theory of games and economic behavior, (1953), Princeton University Press Princeton, NJ, USA · Zbl 0053.09303
[72] Wagstaff, K.; Cardie, C.; Rogers, S.; Schrödl, S., Constrained k-means clustering with background knowledge, (Proc. of ICML’01, (2001)), 577-584
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.