×

zbMATH — the first resource for mathematics

Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value. (English) Zbl 07153696
Summary: The paper focuses on cooperative games where the worth of any coalition of agents is determined by the optimal value of a matching problem on (possibly weighted) graphs. These games come in different forms that can be grouped in two broad classes, namely of matching and allocation games, and they have a wide spectrum of applications, ranging from two-sided markets where buyers and sellers are encoded as vertices in a graph, to allocation problems where indivisible goods have to be assigned (matched) to agents in a fair way, possibly using monetary compensations.
The Shapley value and the related notion of Banzhaf value have often been identified as appropriate solution concepts for many applications of matching/allocation games, but their computation is intractable in general. It is known that these concepts can be computed in polynomial time for matching games on unweighted trees and on graphs having degree at most two. However, it was open whether or not such positive results could be extended to the more general case of graphs having bounded treewidth, and to the case of allocation problems on weighted graphs.
The paper provides a positive answer to these questions, by showing that computing the Shapley value and the Banzhaf value is feasible in polynomial time for the following classes of games: matching games over unweighted graphs having bounded treewidth, allocation games over weighted graphs having bounded treewidth, and allocation games over weighted graphs and such that each good is of interest for two agents at most. Without such structural restrictions, computing these solution concepts on allocation games is instead shown to be \(\#\)P-hard, even in the case of unweighted graphs.
MSC:
68T Artificial intelligence
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Chalkiadakis, G.; Elkind, E.; Wooldridge, M., Computational Aspects of Cooperative Game Theory (Synthesis Lectures on Artificial Intelligence and Machine Learning) (2011), Morgan & Claypool Publishers
[2] 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
[3] Iwasaki, A.; Ueda, S.; Hashimoto, N.; Yokoo, M., Finding core for coalition structure utilizing dual solution, Artif. Intell., 222, C, 49-66 (2015)
[4] Ågotnes, T.; van der Hoek, W.; Wooldridge, M., Reasoning about coalitional games, Artif. Intell., 173, 1, 45-79 (2009) · Zbl 1180.68271
[5] Wooldridge, M.; Dunne, P. E., On the computational complexity of qualitative coalitional games, Artif. Intell., 158, 1, 27-73 (2004) · Zbl 1085.68070
[6] Shehory, O.; Kraus, S., Methods for task allocation via agent coalition formation, Artif. Intell., 101, 1-2, 165-200 (1998) · Zbl 0908.68032
[7] Bistaffa, F.; Farinelli, A.; Chalkiadakis, G.; Ramchurn, S. D., A cooperative game-theoretic approach to the social ridesharing problem, Artif. Intell., 246, 86-117 (2017) · Zbl 1425.91029
[8] Bachrach, Y.; Parkes, D. C.; Rosenschein, J. S., Computing cooperative solution concepts in coalitional skill games, Artif. Intell., 204, 1-21 (2013) · Zbl 1334.91007
[9] Dunne, P. E.; Kraus, S.; Manisterski, E.; Wooldridge, M., Solving coalitional resource games, Artif. Intell., 174, 1, 20-50 (2010) · Zbl 1185.68752
[10] Wooldridge, M.; Dunne, P. E., On the computational complexity of coalitional resource games, Artif. Intell., 170, 10, 835-871 (2006) · Zbl 1131.91011
[11] Deng, X.; Papadimitriou, C. H., On the complexity of cooperative solution concepts, Math. Oper. Res., 19, 2, 257-266 (1994) · Zbl 0824.90146
[12] 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
[13] 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
[14] Aziz, H.; Brandt, F.; Seedig, H. G., Computing desirable partitions in additively separable hedonic games, Artif. Intell., 195, 316-334 (2013) · Zbl 1270.91010
[15] Deng, X.; Ibaraki, T.; Nagamochi, H., Algorithmic aspects of the core of combinatorial optimization games, Math. Oper. Res., 24, 3, 751-766 (1999) · Zbl 1064.91505
[16] Bilbao, J. M., Cooperative games on combinatorial structures, (Theory and Decision Library C, vol. 26 (2000), Kluwer Academinc Publishers: Kluwer Academinc Publishers Reading, MA, USA) · Zbl 0983.91013
[17] Deng, X., Ch. Combinatorial optimization games, (Floudas, C. A.; Pardalos, P. M., Encyclopedia of Optimization (2009), Springer US), 387-391
[18] Greco, G.; Malizia, E.; Palopoli, L.; Scarcello, F., Non-transferable utility coalitional games via mixed-integer linear constraints, J. Artif. Intell. Res., 38, 633-685 (2010) · Zbl 1203.91017
[19] Greco, G.; Malizia, E.; Palopoli, L.; Scarcello, F., The complexity of the nucleolus in compact games, ACM Trans. Comput. Theory, 7, 1, Article 3 pp. (2014), 52 pp · Zbl 1348.91073
[20] Faigle, U.; Kern, W.; Fekete, S. P.; Hochstättler, W., On the complexity of testing membership in the core of min-cost spanning tree games, Int. J. Game Theory, 26, 3, 361-366 (1997) · Zbl 0885.90123
[21] Bachrach, Y., The least-core of threshold network flow games, (Proc. of MFCS (2011)), 36-47 · Zbl 1343.91011
[22] Bachrach, Y.; Rosenschein, J. S., Power in threshold network flow games, Auton. Agents Multi-Agent Syst., 106-132 (2009)
[23] Deng, X.; Fang, Q.; Sun, X., Finding nucleolus of flow game, J. Comb. Optim., 18, 1, 64-86 (2009) · Zbl 1188.91024
[24] Bachrach, Y.; Porat, E.; Rosenschein, J. S., Sharing rewards in cooperative connectivity games, J. Artif. Intell. Res., 47, 281-311 (2013) · Zbl 1267.68244
[25] Bachrach, Y.; Porat, E., Path disruption games, (Proc. of AAMAS (2010)), 1123-1130
[26] Goemans, M. X.; Skutella, M., Cooperative facility location games, J. Algorithms, 50, 2, 194-214 (2004) · Zbl 1106.91009
[27] Faigle, U.; Fekete, S. P.; Hochstättler, W.; Kern, W., On approximately fair cost allocation in Euclidean tsp games, OR Spektrum, 20, 1, 29-37 (1998) · Zbl 0897.90199
[28] Fang, Q.; Kong, L., Core stability of vertex cover games, (Proc. of WINE (2007)), 482-490
[29] Shapley, L. S.; Shubik, M., The assignment game I: the core, Int. J. Game Theory, 1, 1, 111-130 (1971) · Zbl 0236.90078
[30] Roth, A. E.; Sotomayor, M., Two-sided matching, (Handbook of Game Theory with Economic Applications, vol. 1 (1992), Elsevier), 485-541 · Zbl 0968.91516
[31] Le Breton, M.; Weber, S., Stability of coalition structures and the principle of optimal partitioning, (Social Choice, Welfare and Ethics (1995), Cambridge University Press), 301-319 · Zbl 0924.90134
[32] Eriksson, K.; Karlander, J., Stable outcomes of the roommate game with transferable utility, Int. J. Game Theory, 29, 4, 555-569 (2001) · Zbl 1060.91037
[33] Fang, Q.; Li, B.; Sun, X.; Zhang, J.; Zhang, J., Computing the least-core and nucleolus for threshold cardinality matching games, Theor. Comput. Sci., 609, P2, 500-510 (2016) · Zbl 1334.91009
[34] Moulin, H., An application of the Shapley value to fair division with money, Econometrica, 60, 6, 1331-1349 (1992) · Zbl 0768.90100
[35] Demetrescu, C.; Lupia, F.; Mendicelli, A.; Ribichini, A.; Scarcello, F.; Schaerf, M., On the Shapley value and its application to the Italian VQR research assessment exercise, J. Informetr., 13, 1, 87-104 (2019)
[36] Mishra, D.; Rangarajan, B., Cost sharing in a job scheduling problem, Soc. Choice Welf., 29, 3, 369-382 (2007) · Zbl 1180.90132
[37] Maniquet, F., A characterization of the Shapley value in queueing problems, J. Econ. Theory, 109, 1, 90-103 (2003) · Zbl 1032.91020
[38] Greco, G.; Scarcello, F., Mechanisms for fair allocation problems: no-punishment payment rules in verifiable settings, J. Artif. Intell. Res., 49, 403-449 (2014) · Zbl 1286.68439
[39] Greco, G.; Scarcello, F., Fair division rules for funds distribution: the case of the Italian research assessment program (VQR 2004-2010), Intell. Artif., 7, 1, 45-56 (2013)
[40] Gillies, D. B., Solutions to general non-zero-sum games, (Tucker, A. W.; Luce, R. D., Contributions to the Theory of Games. Contributions to the Theory of Games, Annals of Mathematics Studies, vol. 40 (1959), Princeton University Press), 47-85 · Zbl 0085.13106
[41] Edgeworth, F. Y., Mathematical Psychics: an Essay on the Mathematics to the Moral Sciences (1881), C. Kegan Paul & Co.: C. Kegan Paul & Co. London · Zbl 0005.17402
[42] Alkan, A.; Gale, D., The core of the matching game, Games Econ. Behav., 2, 3, 203-212 (1990) · Zbl 0754.90072
[43] Biró, P.; Kern, W.; Paulusma, D., Computing solutions for matching games, Int. J. Game Theory, 41, 1, 75-90 (2012) · Zbl 1232.91026
[44] Schmeidler, D., The nucleolus of a characteristic function game, SIAM J. Appl. Math., 17, 6, 1163-1170 (1969) · Zbl 0191.49502
[45] Kern, W.; Paulusma, D., Matching games: the least core and the nucleolus, Math. Oper. Res., 28, 2, 294-308 (2003) · Zbl 1082.91016
[46] Shapley, L. S., A value for n-person games, (Kuhn, H. W.; Tucker, A. W., Contributions to the Theory of Games II (1953), Princeton University Press), 307-317 · Zbl 0050.14404
[47] Aziz, H.; de Keijzer, B., Shapley meets Shapley, (Proc. of STACS (2014)), 99-111 · Zbl 1359.68116
[48] Bousquet, N., The Shapley value of matching games on trees (2015), in
[49] Robertson, N.; Seymour, P., Graph minors. III. Planar tree-width, J. Comb. Theory, Ser. B, 36, 1, 49-64 (1984) · Zbl 0548.05025
[50] Banzhaf, J. F., Weighted voting doesn’t work: a mathematical analysis, Rutgers Law Rev., 19, 317-343 (1965)
[51] Courcelle, B., Graph rewriting: an algebraic and logic approach, (van Leeuwen, J., Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics (1990), The MIT Press), 193-242 · Zbl 0900.68282
[52] Langer, A., Fast Algorithms for Decomposable Graphs (2013), RWTH Aachen University, Ph.D. thesis
[53] Greco, G.; Lupia, F.; Scarcello, F., The tractability of the Shapley value over bounded treewidth matching games, (Proc. of IJCAI (2017)), 1046-1052
[54] Greco, G.; Lupia, F.; Scarcello, F., Structural tractability of Shapley and Banzhaf values in allocation games, (Proc. of IJCAI (2015)), 547-553
[55] Osborne, M. J.; Rubinstein, A., A Course in Game Theory (1994), The MIT Press: The MIT Press Cambridge, MA, USA · Zbl 1194.91003
[56] Gottlob, G.; Greco, G.; Scarcello, F., Treewidth and hypertree width, (Tractability: Practical Approaches to Hard Problems (2014), Cambridge University Press), 3-38
[57] Gottlob, G.; Leone, N.; Scarcello, F., Hypertree decompositions and tractable queries, J. Comput. Syst. Sci., 64, 3, 579-627 (2002) · Zbl 1052.68025
[58] Grohe, M.; Marx, D., Constraint solving via fractional edge covers, ACM Trans. Algorithms, 11, 1, Article 4 pp. (2014), 20 pp · Zbl 1398.68240
[59] Gottlob, G.; Miklós, Z.; Schwentick, T., Generalized hypertree decompositions: NP-hardness and tractable variants, J. ACM, 56, 6, Article 30 pp. (2009), 32 pp · Zbl 1325.68097
[60] 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
[61] Greco, G.; Scarcello, F., The power of local consistency in conjunctive queries and constraint satisfaction problems, SIAM J. Comput., 46, 3, 1111-1145 (2017) · Zbl 1371.68061
[62] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W. H. Freeman & Co.: W. H. Freeman & Co. New York, NY, USA · Zbl 0411.68039
[63] Elberfeld, M.; Jakoby, A.; Tantau, T., Logspace versions of the theorems of bodlaender and courcelle, (Proc. of FOCS (2010)), 143-152
[64] Langer, A.; Reidl, F.; Rossmanith, P.; Sikdar, S., Practical algorithms for MSO model-checking on tree-decomposable graphs, Comput. Sci. Rev., 13-14, 39-74 (2014) · Zbl 1302.68184
[65] Ieong, S.; Shoham, Y., Marginal contribution nets: a compact representation scheme for coalitional games, (Proc. of EC (2005)), 193-202
[66] Elkind, E.; Goldberg, L. A.; Goldberg, P. W.; Wooldridge, M., A tractable and expressive class of marginal contribution nets and its applications, Math. Log. Q., 55, 4, 362-376 (2009) · Zbl 1175.91022
[67] Ieong, S.; Shoham, Y., Multi-attribute coalitional games, (Proc. of EC (2006)), 170-179
[68] Conitzer, V.; Sandholm, T., Computing Shapley values, manipulating value division schemes, and checking core membership in multi-issue domains, (Proc. of AAAI (2004)), 219-225
[69] Michalak, T. P.; Aadithya, K. V.; Szczepanski, P. L.; Ravindran, B.; Jennings, N. R., Efficient computation of the Shapley value for game-theoretic network centrality, J. Artif. Intell. Res., 46, 1, 607-650 (2013) · Zbl 1280.91035
[70] P.L. Szczepanski, Fast algorithms for game-theoretic centrality measures, CoRR abs/1512.01764, 2015.
[71] Bhagat, S.; Kim, A.; Muthukrishnan, S.; Weinsberg, U., The Shapley value in knapsack budgeted games, (Proc. of WINE (2014)), 106-119 · Zbl 1404.91016
[72] Nagamochi, H.; Zeng, D.-Z.; Kabutoya, N.; Ibaraki, T., Complexity of the minimum base game on matroids, Math. Oper. Res., 22, 146-164 (1997) · Zbl 0871.90121
[73] Prasad, K.; Kelly, J. S., Np-completeness of some problems concerning voting games, Int. J. Game Theory, 19, 1, 1-9 (1990) · Zbl 0705.90103
[74] Zuckerman, M.; Faliszewski, P.; Bachrach, Y.; Elkind, E., Manipulating the quota in weighted voting games, Artif. Intell., 180-181, 1-19 (2012) · Zbl 1238.91056
[75] Fatima, S. S.; Wooldridge, M.; Jennings, N. R., A linear approximation method for the Shapley value, Artif. Intell., 172, 14, 1673-1699 (2008) · Zbl 1184.91029
[76] Liben-Nowell, D.; Sharp, A.; Wexler, T.; Woods, K., Computing Shapley value in supermodular coalitional games, (Proc. of COCOON (2012), Springer: Springer Berlin, Heidelberg), 568-579 · Zbl 1364.91022
[77] Papadimitriou, C. H., Computational Complexity (1993), Addison-Wesley · Zbl 0557.68033
[78] Colbourn, C. J.; Provan, J. S.; Vertigan, D., The complexity of computing the tutte polynomial on transversal matroids, Combinatorica, 15, 1, 1-10 (1995) · Zbl 0821.05011
[79] Aziz, H.; Lachish, O.; Paterson, M.; Savani, R., Power indices in spanning connectivity games, (Proc. of AAIM (2009)), 55-67 · Zbl 1246.91009
[80] Bareiss, E. H., Sylvester’s identity and multistep integer-preserving Gaussian elimination, Math. Comput., 22, 565 (1968) · Zbl 0187.09701
[81] Berge, C., Two theorems in graph theory, Proc. Natl. Acad. Sci. USA, 43, 9, 842-844 (1957) · Zbl 0086.16202
[82] Courcelle, B.; Makowsky, J.; Rotics, U., On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, Discrete Appl. Math., 108, 1-2, 23-52 (2001) · Zbl 0972.05023
[83] Lupia, F.; Mendicelli, A.; Ribichini, A.; Scarcello, F.; Schaerf, M., Computing the Shapley value in allocation problems: approximations and bounds, with an application to the Italian VQR research assessment program, J. Exp. Theor. Artif. Intell., 30, 4, 505-524 (2018)
[84] Dubey, P.; Neyman, A.; Weber, R. J., Value theory without efficiency, Math. Oper. Res., 6, 1, 122-128 (1981) · Zbl 0496.90096
[85] Myerson, R. B., Graphs and cooperation in games, Math. Oper. Res., 2, 3, 225-229 (1977) · Zbl 0402.90106
[86] Meir, R.; Zick, Y.; Elkind, E.; Rosenschein, J. S., Bounding the cost of stability in games over interaction networks, (Proc. of AAAI (2013)), 690-696
[87] Skibski, O.; Michalak, T. P.; Sakurai, Y.; Yokoo, M., A pseudo-polynomial algorithm for computing power indices in graph-restricted weighted voting games, (Proc. of IJCAI (2015)), 631-637
[88] Dagum, P.; Luby, M., Approximating the permanent of graphs with large factors, Theor. Comput. Sci., 102, 2, 283-305 (1992) · Zbl 0766.68056
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.