Cooperative games on simplicial complexes. (English) Zbl 1448.91016
Summary: In this work, we define cooperative games on simplicial complexes, generalizing the study of probabilistic values of R. J. Weber [“Probabilistic values for games”, in: The Shapley value: Essays in Honor of Lloyd S. Shapley. Cambridge: Cambridge University Press. 101–119 (1989; Zbl 0707.90100)] and quasi-probabilistic values of J. M. Bilbao et al. [Math. Methods Oper. Res. 53, No. 2, 333–348 (2001; Zbl 1062.91014)]. Applications to multi-touch attribution and the interpretability of the machine-learning prediction models motivate these new developments.
We deal with the axiomatization provided by the \(\lambda_i\)-dummy and the monotonicity requirements together with a probabilistic form of the symmetric and the efficiency axioms. We also characterize combinatorially the set of probabilistic participation influences as the facet polytope of the simplicial complex.
We deal with the axiomatization provided by the \(\lambda_i\)-dummy and the monotonicity requirements together with a probabilistic form of the symmetric and the efficiency axioms. We also characterize combinatorially the set of probabilistic participation influences as the facet polytope of the simplicial complex.
Software:
shapReferences:
| [1] | Adam, Lukáš; Kroupa, Tomáš, The intermediate set and limiting superdifferential for coalitional games: Between the core and the Weber set, Int. J. Game Theory, 46, 4, 891-918 (2017), MR:2847360 · Zbl 1411.91034 |
| [2] | Agatsuma, Yasushi; Funaki, Yukihiko; Yokote, Koji, Random reduction consistency of the Weber set, the core and the anti-core, Math. Methods Oper. Res., 85, 3, 389-405 (2017), MR:3684478 · Zbl 1411.91035 |
| [3] | Angel, Andrés; Borja, Jerson, Simplicial complexes and the evasiveness conjecture, Grad. J. Math., 1, 1, 1-8 (2016), MR:3848666 · Zbl 1498.05263 |
| [4] | Bach, Sebastian; Binder, Alexander; Montavon, Grégoire; Klauschen, Frederick; Müller, Klaus-Robert; Samek, Wojciech, On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation, PLoS ONE, 10, 7, 1-46 (2015) |
| [5] | Bilbao, J. M.; Driessen, T. S.H.; Jiménez Losada, A.; Lebrón, E., The shapley value for games on matroids: The static model, Math. Methods Oper. Res., 53, 2, 333-348 (2001), MR:2847360 · Zbl 1062.91014 |
| [6] | Bilbao, J. M.; Driessen, T. S.H.; Jiménez-Losada, A.; Lebrón, E., The shapley value for games on matroids: the dynamic model, Math. Methods Oper. Res., 56, 2, 287-301 (2002), MR:2847360 · Zbl 1071.91005 |
| [7] | Bilbao, J. M.; Ordóñez, M., The core and the weber set of games on augmenting systems, Discrete Appl. Math., 158, 3, 180-188 (2010), MR:2847360 · Zbl 1226.05178 |
| [8] | Björner, A., Topological Methods, HandBook of Combinatorics, Vol. 1, 2, 1819-1872 (1995), Elsevier Sci. B. V: Elsevier Sci. B. V Amsterdam, MR:1373690 · Zbl 0851.52016 |
| [9] | Björner, Anders; Vergnas, Michel Las; Sturmfels, Bernd; White, Neil; Ziegler, Günter M., Oriented matroids, (Encyclopedia of Mathematics and Its Applications, Vol. 46 (1999), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0944.52006 |
| [10] | Borzì, Alessio; Martino, Ivan, Set of independencies and tutte polynomial of matroids over a domain (2019), arXiv:1909.00332 |
| [11] | A. Datta, S. Sen, Y. Zick, Algorithmic transparency via quantitative input influence: Theory and experiments with learning systems, in: 2016 IEEE Symposium on Security and Privacy (SP), 2016, pp. 598-617. |
| [12] | Edmonds, Jack, Submodular functions, matroids, and certain polyhedra, (Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf. Calgary, Alta. 1969), Gordon and Breach, New York (1970)), 69-87, MR:0270945 · Zbl 0268.05019 |
| [13] | Faigle, Ulrich; Voss, Jan, A system-theoretic model for cooperation, interaction and allocation, Discrete Appl. Math., 159, 16, 1736-1750 (2011), MR:2847360 · Zbl 1244.91009 |
| [14] | Frank H. Lutz, Ulrich, Some results related to the evasiveness conjecture, J. Combin. Theory Ser. B, 81, 1, 110-124 (2001), MR:2847360 · Zbl 1040.05027 |
| [15] | Gillies, Donald B., Solutions to general non-zero-sum games, Contributions To the Theory of Games. Contributions To the Theory of Games, Ann. Math. Stud., IV, 40, 47-85 (1959), MR:0106116 · Zbl 0085.13106 |
| [16] | Greco, Ornella; Martino, Ivan, Ornella greco ivan martino syzygies of the veronese modules, Comm. Algebra, 44, 9, 3890-3906 (2016), MR:2847360 · Zbl 1365.13021 |
| [17] | Greco, Ornella; Martino, Ivan, Cohen-macaulay property and linearity of pinched veronese rings (2018), arXiv:1709.10461 |
| [18] | Ichiishi, Tatsuro, Super-modularity: Applications to convex games and to the greedy algorithm for LP, J. Econom. Theory, 25, 2, 283-286 (1981), MR:2847360 · Zbl 0478.90092 |
| [19] | Kahn, Jeff; Saks, Michael; Sturtevant, Dean, Sturtevant a topological approach to evasiveness, Combinatorica, 4, 4, 297-306 (1984), MR:2847360 · Zbl 0577.05061 |
| [20] | Kannai, Yakar, The core and balancedness, (Vol. I, HandBooks in Econom, Vol. 11 (1992), North-Holland: North-Holland Amsterdam), 355-395, MR:1202057 · Zbl 0968.91503 |
| [21] | Lipovetsky, Stan; Conklin, Michael, Stan lipovetsky michael conklin analysis of regression in game theory approach, Appl. Stoch. Models Bus. Ind., 17, 319-330 (2001) · Zbl 1008.62041 |
| [22] | Lundberg, Scott M.; Lee, Su-In, A unified approach to interpreting model predictions, (Guyon, I.; Luxburg, U. V.; Bengio, S.; Wallach, H.; Fergus, R.; Vishwanathan, S.; Garnett, R., Advances in Neural Information Processing Systems 30 (2017), Curran Associates, Inc.), 4765-4774 |
| [23] | Lutz, F. H., Examples of \(\mathbb{Z} \)-acyclic and contractible vertex-homogeneous simplicial complexes, vol. 27, (Geometric Combinatorics, San Francisco, CA/Davis, CA, 2000 (2002)), 137-154, MR:1871694 · Zbl 1011.52007 |
| [24] | Martino, Ivan, Vertex collapsing and cut ideals, Serdica Math. J., 41, 2-3, 229-242 (2015), MR:2847360 · Zbl 1488.14018 |
| [25] | Martino, Ivan, Face module for realizable \(\mathbb{Z} \)-matroids, Contrib. Discrete Math., 13, 2, 74-87 (2018), MR:2847360 · Zbl 1435.05044 |
| [26] | Martino, Ivan, Efficiency scenarios for fair division problems (2020), arXiv:2001.00779 |
| [27] | Martino, Ivan, Probabilistic values for simplicial complexes (2020), arXiv:2001.05820 |
| [28] | Meng, Fanyong; Tang, Jie; Ma, Beiling; Zhang, Qiang, Proportional coalition values for monotonic games on convex geometries with a coalition structure, J. Comput. Appl. Math., 348, 34-47 (2019) · Zbl 1418.91049 |
| [29] | Meng, Fanyong; Zhang, Qiang, The fuzzy core and shapley function for dynamic fuzzy games on matroids, Fuzzy Optim. Decis. Mak., 10, 4, 369-404 (2011), MR:2847360 · Zbl 1254.91024 |
| [30] | Nagamochi, Hiroshi; Zeng, Dao-Zhi; Kabutoya, Naohisa; Ibaraki, Toshihide, Complexity of the minimum base game on matroids, Math. Oper. Res., 22, 1, 146-164 (1997) · Zbl 0871.90121 |
| [31] | Oxley, James, Matroid theory, (Oxford Graduate Texts in Mathematics, Vol. 21 (2011), Oxford University Press: Oxford University Press Oxford), MR:2849819 · Zbl 1254.05002 |
| [32] | Ribeiro, Marco; Singh, Sameer; Guestrin, Carlos, “why should i trust you?”: Explaining the predictions of any classifier, 02, 97-101 (2016) |
| [33] | Robert James Weber, P., The Shapley Value, 101-119 (1988), Cambridge Univ. Press: Cambridge Univ. Press Cambridge, MR:989825 |
| [34] | Ronald L. Rivest, P.; Vuillemin, Jean. and, On the time required to recognize properties of graphs from their adjacency matrices, (Journées Algorithmiques (École Norm. Sup. Paris, 1975) (1976)), 213-227, Astérisque, No. 38-39. MR:0460172 · Zbl 0358.68078 |
| [35] | Lloyd S. Shapley, Cores of convex games, Int. J. Game Theory 1 (1971/72), 11-26, errata, ibid. 1 (1971/72), 199. MR:311338. · Zbl 0222.90054 |
| [36] | Shapley, L. S., Contributions To the Theory of Games. Contributions To the Theory of Games, Ann. Math. Stud., 2, 28, 307-317 (1953), MR:0053477 · Zbl 0050.14404 |
| [37] | Shrikumar, Avanti; Peyton, Greenside; Kundaje, Anshul, Learning important features through propagating activation differences (2017), arXiv:1704.02685 |
| [38] | Stanley, Richard P., An introduction to combinatorial commutative algebra, (Enumeration and Design (Waterloo, Ont. 1982) (1984), Academic Press: Academic Press Toronto, ON), 3-18, MR:782306 · Zbl 0569.05009 |
| [39] | Stanley, Richard P., Combinatorics and commutative algebra, (Progress in Mathematics, Vol. 41 (1996), Birkhäuser Boston, Inc: Birkhäuser Boston, Inc Boston, MA), MR:1453579 · Zbl 0838.13008 |
| [40] | Stanley, Richard P., Enumerative combinatorics, volume 1, (Cambridge Studies in Advanced Mathematics, Vol. 49 (2012), Cambridge University Press: Cambridge University Press Cambridge), MR:2868112 · Zbl 1247.05003 |
| [41] | Strumbelj, Erik; Kononenko, Igor, Explaining prediction models and individual predictions with feature contributions, Knowl. Inf. Syst., 41, 647-665 (2013) |
| [42] | Welker, Volkmar, Volkmar welker constructions preserving evasiveness and collapsibility, Discrete Math., 207, 1-3, 243-255 (1999) · Zbl 0938.06003 |
| [43] | Xu, Genjiu; Driessen, Theo S. H.; Su, Jun; Sun, Hao, Extreme points of the Harsanyi set and the Weber set, J. Math. Anal. Appl., 432, 2, 678-698 (2015), MR:2847360 · Zbl 1338.91017 |
| [44] | Yao, Andrew Chi-Chih, Andrew chi-chih yao monotone bipartite graph properties are evasive, SIAM J. Comput., 17, 3, 517-520 (1988), MR:2847360 · Zbl 0648.05028 |
| [45] | Zhao, Jingang, A necessary and sufficient condition for the convexity in oligopoly games, Math. Social Sci., 37, 2, 189-204 (1999), MR:2847360 · Zbl 0967.91005 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
