×

zbMATH — the first resource for mathematics

Computing stable coalitions: approximation algorithms for reward sharing. (English) Zbl 1406.91122
Markakis, Evangelos (ed.) et al., Web and internet economics. 11th international conference, WINE 2015, Amsterdam, The Netherlands, December 9–12, 2015. Proceedings. Berlin: Springer (ISBN 978-3-662-48994-9/pbk; 978-3-662-48995-6/ebook). Lecture Notes in Computer Science 9470, 31-45 (2015).
Summary: Consider a setting where selfish agents are to be assigned to coalitions or projects from a set \(\mathcal {P}\). Each project \(k\in \mathcal {P}\) is characterized by a valuation function; \(v_k(S)\) is the value generated by a set \(S\) of agents working on project \(k\). We study the following classic problem in this setting: “how should the agents divide the value that they collectively create?”. One traditional approach in cooperative game theory is to study core stability with the implicit assumption that there are infinite copies of one project, and agents can partition themselves into any number of coalitions. In contrast, we consider a model with a finite number of non-identical projects; this makes computing both high-welfare solutions and core payments highly non-trivial.
The main contribution of this paper is a black-box mechanism that reduces the problem of computing a near-optimal core stable solution to the well-studied algorithmic problem of welfare maximization; we apply this to compute an approximately core stable solution that extracts one-fourth of the optimal social welfare for the class of subadditive valuations. We also show much stronger results for several popular sub-classes: anonymous, fractionally subadditive, and submodular valuations, as well as provide new approximation algorithms for welfare maximization with anonymous functions. Finally, we establish a connection between our setting and simultaneous auctions with item bidding; we adapt our results to compute approximate pure Nash equilibria for these auctions.
For the entire collection see [Zbl 1326.68026].
MSC:
91B15 Welfare economics
91A12 Cooperative games
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bachrach, Y., Elkind, E., Meir, R., Pasechnik, D., Zuckerman, M., Rothe, J., Rosenschein, J.S.: The cost of stability in coalitional games. In: Mavronicolas, M., Papadopoulou, V.G. (eds.) SAGT 2009. LNCS, vol. 5814, pp. 122–134. Springer, Heidelberg (2009) · Zbl 1262.91021 · doi:10.1007/978-3-642-04645-2_12
[2] 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 · doi:10.1016/j.artint.2013.07.005
[3] Bachrach, Y., Syrgkanis, V., Tardos, É., Vojnović, M.: Strong price of anarchy, utility games and coalitional dynamics. In: Lavi, R. (ed.) SAGT 2014. LNCS, vol. 8768, pp. 218–230. Springer, Heidelberg (2014) · Zbl 1403.91054 · doi:10.1007/978-3-662-44803-8_19
[4] Bejan, C., Gómez, J.C.: Theory Core extensions for non-balanced TU-games. Int. J. Game 38(1), 3–16 (2009) · Zbl 1211.91028 · doi:10.1007/s00182-008-0135-4
[5] Bhawalkar, K., Roughgarden, T.: Welfare guarantees for combinatorial auctions with item bidding. In: Proceedings of SODA (2011) · Zbl 1377.91102 · doi:10.1137/1.9781611973082.55
[6] Bousquet, N., Li, Z., Vetta, A.: Coalition games on interaction graphs: a horticultural perspective. In: Proceedings of EC (2015) · doi:10.1145/2764468.2764477
[7] Chalkiadakis, G., Elkind, E., Markakis, E., Polukarov, M., Jennings, N.R.: Cooperative games with overlapping coalitions. J. Artif. Intell. Res. (JAIR) 39, 179–216 (2010) · Zbl 1205.91020
[8] 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 · doi:10.1287/moor.24.3.751
[9] Dobzinski, S., Fu, H., Kleinberg, R.D.: On the complexity of computing an equilibrium in combinatorial auctions. In: Proceedings of SODA (2015) · Zbl 1318.91089 · doi:10.1137/1.9781611973730.9
[10] Dobzinski, S., Nisan, N., Schapira, M.: Approximation algorithms for combinatorial auctions with complement-free bidders. Math. Oper. Res. 35(1), 1–13 (2010) · Zbl 1216.68338 · doi:10.1287/moor.1090.0436
[11] Feige, U.: On maximizing welfare when utility functions are subadditive. SIAM J. Comput. 39(1), 122–142 (2009) · Zbl 1185.68855 · doi:10.1137/070680977
[12] Feldman, M., Friedler, O.: A unified framework for strong price of anarchy in clustering games. In: Halldórsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9135, pp. 601–613. Springer, Heidelberg (2015) · Zbl 1404.68078 · doi:10.1007/978-3-662-47666-6_48
[13] Feldman, M., Fu, H., Gravin, N., Lucier, B.: Simultaneous auctions are (almost) efficient. In: Proceedings of STOC (2013) · Zbl 1293.91081 · doi:10.1145/2488608.2488634
[14] Feldman, M., Lewin-Eytan, L., Naor, J.: Hedonic clustering games. In: Proceedings of SPAA (2012) · doi:10.1145/2312005.2312053
[15] Georgiou, K., Swamy, C.: Black-box reductions for cost-sharing mechanism design. Games and Economic Behavior (2013) · doi:10.1016/j.geb.2013.08.012
[16] Hoefer, M.: Strategic cooperation in cost sharing games. Int. J. Game Theory 42(1), 29–53 (2013) · Zbl 1282.91030 · doi:10.1007/s00182-011-0312-8
[17] Kleinberg, J.M., Oren, S.: Mechanisms for (mis)allocating scientific credit. In: Proceedings of STOC (2011) · Zbl 1288.91027 · doi:10.1145/1993636.1993707
[18] Lehmann, B., Lehmann, D., Nisan, N.: Combinatorial auctions with decreasing marginal utilities. Games Econ. Behav. 55(2), 270–296 (2006) · Zbl 1125.91043 · doi:10.1016/j.geb.2005.02.006
[19] Meir, R., Bachrach, Y., Rosenschein, J.S.: Minimal subsidies in expense sharing games. In: Kontogiannis, S., Koutsoupias, E., Spirakis, P.G. (eds.) SAGT 2010. LNCS, vol. 6386, pp. 347–358. Springer, Heidelberg (2010) · Zbl 1310.91024 · doi:10.1007/978-3-642-16170-4_30
[20] Myerson, R.B.: Graphs and cooperation in games. Math. Oper. Res. 2(3), 225–229 (1977) · Zbl 0402.90106 · doi:10.1287/moor.2.3.225
[21] Roughgarden, T., Sundararajan, M.: Quantifying inefficiency in cost-sharing mechanisms. J. ACM 56(4), 23 (2009) · Zbl 1325.91033 · doi:10.1145/1538902.1538907
[22] Vondrák, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: Proceedings of STOC (2008) · doi:10.1145/1374376.1374389
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.