{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T11:58:25Z","timestamp":1780315105450,"version":"3.54.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,6,7]],"date-time":"2021-06-07T00:00:00Z","timestamp":1623024000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,7]],"date-time":"2021-06-07T00:00:00Z","timestamp":1623024000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100008001","name":"Universit\u00e4t zu K\u00f6ln","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008001","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2021,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In hedonic games, players form coalitions based on individual preferences over the group of players they could belong to. Several concepts to describe the stability of coalition structures in a game have been proposed and analysed in the literature. However, prior research focuses on algorithms with time complexity that is at least linear in the input size. In the light of very large games that arise from, e.g., social networks and advertising, we initiate the study of sublinear time property testing algorithms for existence and verification problems under several notions of coalition stability in a model of hedonic games represented by graphs with bounded degree. In graph property testing, one shall decide whether a given input has a property (e.g., a game admits a stable coalition structure) or is far from it, i.e., one has to modify at least an <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\epsilon$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03f5<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-fraction of the input (e.g., the game\u2019s preferences) to make it have the property. In particular, we consider verification of perfection, individual rationality, Nash stability, (contractual) individual stability, and core stability. While there is always a Nash-stable coalition structure (which also implies individually stable coalitions), we show that the existence of a perfect coalition structure is not tautological but can be tested. All our testers have one-sided error and time complexity that is independent of the input size.<\/jats:p>","DOI":"10.1007\/s10458-021-09505-x","type":"journal-article","created":{"date-parts":[[2021,6,7]],"date-time":"2021-06-07T07:04:57Z","timestamp":1623049497000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Testing stability prop\ufefferties in graphical hedonic games"],"prefix":"10.1007","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3246-5323","authenticated-orcid":false,"given":"Hendrik","family":"Fichtenberger","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7387-6853","authenticated-orcid":false,"given":"Anja","family":"Rey","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,6,7]]},"reference":[{"issue":"1","key":"9505_CR1","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1137\/060667177","volume":"39","author":"N Alon","year":"2009","unstructured":"Alon, N., Fischer, E., Newman, I., & Shapira, A. (2009). A combinatorial characterization of the testable graph properties: It s all about regularity. SIAM J. Comput., 39(1), 143.","journal-title":"SIAM J. Comput."},{"key":"9505_CR2","unstructured":"Aziz, H., & Savani, R. (2016). Hedonic games. In: Handbook of Computational Social Choice, Cambridge University Press."},{"key":"9505_CR3","doi-asserted-by":"crossref","unstructured":"Aziz, H., Brandt, F., & Seedig, H.G. (2013). Computing desirable partitions in additively separable hedonic games. Artificial Intelligence 195.","DOI":"10.1016\/j.artint.2012.09.006"},{"key":"9505_CR4","unstructured":"Aziz, H., Harrenstein, P., Lang, J., & Wooldridge, M. (2016). Boolean hedonic games. In: Proceedings of the 15th international conference on principles of knowledge representation and reasoning."},{"issue":"1","key":"9505_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.geb.2003.10.003","volume":"49","author":"C Ballester","year":"2004","unstructured":"Ballester, C. (2004). NP-completeness in hedonic games. Games Econom. Behavior, 49(1), 1\u201330.","journal-title":"Games Econom. Behavior"},{"key":"9505_CR6","doi-asserted-by":"crossref","unstructured":"Banerjee, S., Konishi, H., & S\u00f6nmez, T. (2001). Core in a simple coalition formation game. Social Choice and Welfare 18","DOI":"10.1007\/s003550000067"},{"issue":"6","key":"9505_CR7","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.ipl.2006.12.011","volume":"102","author":"O Ben-Zwi","year":"2007","unstructured":"Ben-Zwi, O., Lachish, O., & Newman, I. (2007). Lower bounds for testing euclidean minimum spanning trees. Inf. Process. Lett., 102(6), 219.","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9505_CR8","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1006\/game.2001.0877","volume":"38","author":"A Bogomolnaia","year":"2002","unstructured":"Bogomolnaia, A., & Jackson, M. O. (2002). The stability of hedonic coalition structures. Games Econom. Behavior., 38(2), 201.","journal-title":"Games Econom. Behavior."},{"key":"9505_CR9","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/S0166-218X(01)00230-X","volume":"116","author":"K Cechl\u00e1rov\u00e1","year":"2002","unstructured":"Cechl\u00e1rov\u00e1, K. (2002). On the complexity of exchange-stable roommates. Descrete Appl. Math., 116, 279.","journal-title":"Descrete Appl. Math."},{"key":"9505_CR10","doi-asserted-by":"crossref","unstructured":"Cechl\u00e1rov\u00e1, K., & Romero-Medina, A. (2001). Stability in coalition formation games. International Journal of Game Theory 29","DOI":"10.1007\/s001820000053"},{"key":"9505_CR11","doi-asserted-by":"publisher","DOI":"10.2200\/S00355ED1V01Y201107AIM016","volume-title":"Computational aspects of cooperative game theory","author":"G Chalkiadakis","year":"2011","unstructured":"Chalkiadakis, G., Elkind, E., & Wooldridge, M. J. (2011). Computational aspects of cooperative game theory. California: Morgan and Claypool Publishers."},{"issue":"3","key":"9505_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1367064.1367071","volume":"4","author":"A Czumaj","year":"2008","unstructured":"Czumaj, A., & Sohler, C. (2008). Testing euclidean minimum spanning trees in the plane. ACM Trans. Algorithms, 4(3), 1\u201323.","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"9505_CR13","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1002\/rsa.20462","volume":"45","author":"A Czumaj","year":"2014","unstructured":"Czumaj, A., Goldreich, O., Ron, D., Seshadhri, C., Shapira, A., & Sohler, C. (2014). Finding cycles and trees in sublinear time. Random Struct. Algorithm., 45(2), 139.","journal-title":"Random Struct. Algorithm."},{"key":"9505_CR14","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Peng, P., & Sohler, C. (2016). Relating two property testing models for bounded degree directed graphs. In: Proceedings of the 48th annual ACM symposium on theory of computing.","DOI":"10.1145\/2897518.2897575"},{"issue":"3","key":"9505_CR15","doi-asserted-by":"publisher","first-page":"767","DOI":"10.1007\/s00182-017-0596-4","volume":"47","author":"A Darmann","year":"2018","unstructured":"Darmann, A., Elkind, E., Kurz, S., Lang, J., Schauer, J., & Woeginger, G. J. (2018). Group activity selection problem with approval preferences. Int. J. Game Theor., 47(3), 767.","journal-title":"Int. J. Game Theor."},{"issue":"2","key":"9505_CR16","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/s00355-006-0104-4","volume":"26","author":"D Dimitrov","year":"2006","unstructured":"Dimitrov, D., Borm, P., Hendrickx, R., & Sung, S. C. (2006). Simple priorities and core stability in hedonic games. Soc. Choice Welfare, 26(2), 421.","journal-title":"Soc. Choice Welfare"},{"issue":"4","key":"9505_CR17","doi-asserted-by":"publisher","first-page":"987","DOI":"10.2307\/1912943","volume":"48","author":"JH Dr\u00e8ze","year":"1980","unstructured":"Dr\u00e8ze, J. H., & Greenberg, J. (1980). Hedonic coalitions: Optimality and stability. Econometrica, 48(4), 987.","journal-title":"Econometrica"},{"issue":"6","key":"9505_CR18","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1016\/0047-2484(92)90081-J","volume":"22","author":"R Dunbar","year":"1992","unstructured":"Dunbar, R. (1992). Neocortex size as a constraint on group size in primates. J. Hum. Evol., 22(6), 469.","journal-title":"J. Hum. Evol."},{"key":"9505_CR19","volume-title":"Grooming, Gossip, and the Evolution of Language","author":"R Dunbar","year":"1998","unstructured":"Dunbar, R., & Dunbar, R. I. M. (1998). Grooming, Gossip, and the Evolution of Language. Cambridge: Harvard University Press."},{"key":"9505_CR20","doi-asserted-by":"crossref","unstructured":"Eden, T., Ron, D., & Seshadhri, C. (2018). On approximating the number of k-cliques in sublinear time. In: Proceedings of the 50th annual ACM SIGACT symposium on theory of computing.","DOI":"10.1145\/3188745.3188810"},{"key":"9505_CR21","unstructured":"Elkind, E., & Wooldridge, M. (2009). Hedonic coalition nets. In: Proceedings of the 8th international conference on autonomous agents and multiagent systems."},{"key":"9505_CR22","unstructured":"Fichtenberger, H., Krivo\u0161ija, A., & Rey, A. (2019). Testing individual-based stability properties in graphical hedonic games. In: Proceedings of the 18th international conference on autonomous agents and multiAgent systems."},{"key":"9505_CR23","doi-asserted-by":"publisher","DOI":"10.1017\/9781108135252","volume-title":"Introduction to Property Testing","author":"O Goldreich","year":"2017","unstructured":"Goldreich, O. (2017). Introduction to property testing. Cambridge: Cambridge University Press."},{"key":"9505_CR24","doi-asserted-by":"crossref","unstructured":"Goldreich, O., & Ron, D. (2002). Property testing in bounded degree graphs. Algorithmica,32(2).","DOI":"10.1007\/s00453-001-0078-7"},{"issue":"2","key":"9505_CR25","doi-asserted-by":"publisher","first-page":"534","DOI":"10.1137\/100789646","volume":"40","author":"O Goldreich","year":"2011","unstructured":"Goldreich, O., & Ron, D. (2011). On proximity-oblivious testing. SIAM J. Comput., 40(2), 534.","journal-title":"SIAM J. Comput."},{"key":"9505_CR26","unstructured":"Google. (2020a). Prevent competing ads on a page with labels. Retrieved 18 May 2020 from https:\/\/support.google.com\/admanager\/answer\/190582?hl=en."},{"key":"9505_CR27","unstructured":"Google. (2020b). Prevent competitors from serving together. Retrieved 18 May 2020 from https:\/\/support.google.com\/admanager\/answer\/6145371?hl=en."},{"key":"9505_CR28","doi-asserted-by":"crossref","unstructured":"Hellweg, F., Schmidt, M., & Sohler, C. (2010). Testing euclidean spanners. In: Proceedings of the European symposium on algorithms.","DOI":"10.1007\/978-3-642-16367-8_24"},{"issue":"1","key":"9505_CR29","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1140\/epjb\/e2010-00216-1","volume":"76","author":"A Hernando","year":"2010","unstructured":"Hernando, A., Villuendas, D., Vesperinas, C., Abad, M., & Plastino, A. (2010). Unravelling the size distribution of social groups with information theory in complex networks. Eur. Phys. J. B, 76(1), 87.","journal-title":"Eur. Phys. J. B"},{"key":"9505_CR30","unstructured":"Igarashi, A., & Elkind, E. (2016). Hedonic games with graph-restricted communication. In: Proceedings of the 15th international conference on autonomous agents and multiagent systems."},{"key":"9505_CR31","unstructured":"Lang, J., Rey, A., Rothe, J., Schadrack, H., & Schend, L. (2015). Representing and solving hedonic games with ordinal preferences and thresholds. In: Proceedings of the 14th international conference on autonomous agents and multiagent systems."},{"key":"9505_CR32","unstructured":"Lee, H., & Shoham, Y. (2015). Stable invitations. In: Proceedings of the 29th AAAI conference on artificial intelligence."},{"key":"9505_CR33","unstructured":"Lee, H., & Williams, V. (2017). Complexity of the stable invitations problem. In: Proceedings of the 31th AAAI conference on artificial intelligence."},{"key":"9505_CR34","doi-asserted-by":"crossref","unstructured":"Ota, K., Barrot, N., Ismaili, A., Sakurai, Y., & Yokoo, M. (2017). Core stability in hedonic games among friends and enemies: Impact of neutrals. In: Proceedings of the 26th international joint conference on artificial intelligence.","DOI":"10.24963\/ijcai.2017\/51"},{"key":"9505_CR35","unstructured":"Peters, D. (2016). Grahical hedonic games of bounded treewidth. In: Proceedings of the 13th AAAI conference on artificial intelligence."},{"key":"9505_CR36","unstructured":"Peters, D., & Elkind, E. (2015). Simple causes of complexity in hedonic games. In: Proceedings of the 24th international joint conference on artificial intelligence."},{"key":"9505_CR37","doi-asserted-by":"crossref","unstructured":"Sliwinski, J., & Zick, Y. (2017). Learning hedonic games. In: Proceedings of the 26th international joint conference on artificial intelligence.","DOI":"10.24963\/ijcai.2017\/380"},{"issue":"3","key":"9505_CR38","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1016\/j.ejor.2009.09.004","volume":"203","author":"SC Sung","year":"2010","unstructured":"Sung, S. C., & Dimitrov, D. (2010). Computational complexity in additive hedonic games. Eur. J. Oper. Res., 203(3), 635.","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"9505_CR39","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.mathsocsci.2012.10.001","volume":"65","author":"GJ Woeginger","year":"2013","unstructured":"Woeginger, G. J. (2013). A hardness result for core stability in additive hedonic games. Math. Soc. Sci., 65(2), 101.","journal-title":"Math. Soc. Sci."}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-021-09505-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10458-021-09505-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-021-09505-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,24]],"date-time":"2021-09-24T13:27:45Z","timestamp":1632490065000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10458-021-09505-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,7]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["9505"],"URL":"https:\/\/doi.org\/10.1007\/s10458-021-09505-x","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"value":"1387-2532","type":"print"},{"value":"1573-7454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,7]]},"assertion":[{"value":"10 May 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"26"}}