{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T19:41:12Z","timestamp":1771702872027,"version":"3.50.1"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,5,21]],"date-time":"2015-05-21T00:00:00Z","timestamp":1432166400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Technion-Micorsoft Electronic Commerce Research Center"},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["954\/11"],"award-info":[{"award-number":["954\/11"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2015,5,21]]},"abstract":"<jats:p>\n            Clustering, the partitioning of objects with respect to a similarity measure, has been extensively studied as a global optimization problem. We investigate clustering from a game-theoretic approach, and consider the class of\n            <jats:italic>hedonic clustering games<\/jats:italic>\n            . Here, a\n            <jats:italic>self-organized<\/jats:italic>\n            clustering is obtained via decisions made by independent players, corresponding to the elements clustered. Being a hedonic setting, the utility of each player is determined by the identity of the other members of her cluster. This class of games seems to be quite robust, as it fits with rather different, yet commonly used, clustering criteria. Specifically, we investigate hedonic clustering games in two different models:\n            <jats:italic>fixed clustering<\/jats:italic>\n            , which subdivides into\n            <jats:italic>k<\/jats:italic>\n            -median and\n            <jats:italic>k<\/jats:italic>\n            -center, and\n            <jats:italic>correlation clustering<\/jats:italic>\n            . We provide a thorough analysis of these games, characterizing Nash equilibria, and proving upper and lower bounds on the price of anarchy and price of stability. For fixed clustering we focus on the existence of a Nash equilibrium, as it is a rather nontrivial issue in this setting. We study it both for general metrics and special cases, such as line and tree metrics. In the correlation clustering model, we study both minimization and maximization variants, and provide almost tight bounds on both the price of anarchy and price of stability.\n          <\/jats:p>","DOI":"10.1145\/2742345","type":"journal-article","created":{"date-parts":[[2015,5,26]],"date-time":"2015-05-26T14:36:05Z","timestamp":1432650965000},"page":"1-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Hedonic Clustering Games"],"prefix":"10.1145","volume":"2","author":[{"given":"Moran","family":"Feldman","sequence":"first","affiliation":[{"name":"CS Department, Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liane","family":"Lewin-Eytan","sequence":"additional","affiliation":[{"name":"Yahoo Labs, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joseph (Seffi)","family":"Naor","sequence":"additional","affiliation":[{"name":"CS Department, Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,5,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comcom.2007.05.024"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of INFOCOM. 1713--1723","author":"Bandyopadhyay S."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003550000067"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033116.57574.95"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00182-010-0237-7"},{"key":"e_1_2_1_6_1","volume-title":"NIPS Workshop on Clustering Theory.","author":"Blum A.","year":"2009"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.2001.0877"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301257"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.012"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of APPROX. Springer","author":"Demaine E."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.2307\/1912943"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-5355-6"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of ESA. Springer","author":"Emanuel D."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1929237.1929253"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10841-9_62"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.2307\/1914085"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.10.2.180"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.2307\/2224214"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11235-010-9303-5"},{"key":"e_1_2_1_23_1","unstructured":"P. B. Mirchandani and R. L. Francis. 1990. Discrete Location Theory. Wiley Interscience New York NY.  P. B. Mirchandani and R. L. Francis. 1990. Discrete Location Theory. Wiley Interscience New York NY."},{"key":"e_1_2_1_24_1","volume-title":"NIPS Workshop on Clustering Theory.","author":"Pelillo M.","year":"2009"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220004"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(96)00021-1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","volume-title":"Approximation Algorithms","author":"Vazirani V.","DOI":"10.1007\/978-3-662-04565-7"},{"key":"e_1_2_1_28_1","first-page":"381","article-title":"Equilibrium points in polymatrix games (in Russian)","volume":"8","author":"Yanovskaya E. B.","year":"1968","journal-title":"Litovskii Matematicheskii Sbornik"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2742345","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2742345","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:00:33Z","timestamp":1750230033000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2742345"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,21]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,5,21]]}},"alternative-id":["10.1145\/2742345"],"URL":"https:\/\/doi.org\/10.1145\/2742345","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,21]]},"assertion":[{"value":"2013-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-05-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}