{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T19:41:19Z","timestamp":1742931679453,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030353889"},{"type":"electronic","value":"9783030353896"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-35389-6_8","type":"book-chapter","created":{"date-parts":[[2019,11,21]],"date-time":"2019-11-21T01:06:49Z","timestamp":1574298409000},"page":"100-113","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On the Convergence of Swap Dynamics to Pareto-Optimal Matchings"],"prefix":"10.1007","author":[{"given":"Felix","family":"Brandt","sequence":"first","affiliation":[]},{"given":"Ana\u00eblle","family":"Wilczynski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,12,3]]},"reference":[{"issue":"2","key":"8_CR1","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1006\/jeth.1999.2553","volume":"88","author":"A Abdulkadiro\u011flu","year":"1999","unstructured":"Abdulkadiro\u011flu, A., S\u00f6nmez, T.: House allocation with existing tenants. J. Econ. Theory 88(2), 233\u2013260 (1999)","journal-title":"J. Econ. Theory"},{"issue":"1","key":"8_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(94)00026-A","volume":"63","author":"H Abeledo","year":"1995","unstructured":"Abeledo, H., Rothblum, U.G.: Paths to marriage stability. Discrete Appl. Math. 63(1), 1\u201312 (1995)","journal-title":"Discrete Appl. Math."},{"key":"8_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/978-3-540-77105-0_48","volume-title":"Internet and Network Economics","author":"DJ Abraham","year":"2007","unstructured":"Abraham, D.J., et al.: The stable roommates problem with globally-ranked pairs. In: Deng, X., Graham, F.C. (eds.) WINE 2007. LNCS, vol. 4858, pp. 431\u2013444. Springer, Heidelberg (2007). \nhttps:\/\/doi.org\/10.1007\/978-3-540-77105-0_48"},{"issue":"1","key":"8_CR4","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1137\/090753498","volume":"40","author":"H Ackermann","year":"2011","unstructured":"Ackermann, H., Goldberg, P.W., Mirrokni, V.S., R\u00f6glin, H., V\u00f6cking, B.: Uncoordinated two-sided matching markets. SIAM J. Comput. 40(1), 92\u2013106 (2011)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"8_CR5","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/BF02716626","volume":"1","author":"J Alcalde","year":"1994","unstructured":"Alcalde, J.: Exchange-proofness or divorce-proofness? Stability in one-sided matching markets. Rev. Econ. Design 1(1), 275\u2013287 (1994)","journal-title":"Rev. Econ. Design"},{"issue":"4","key":"8_CR6","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.ipl.2008.10.003","volume":"109","author":"EM Arkin","year":"2009","unstructured":"Arkin, E.M., Bae, S.W., Efrat, A., Okamoto, K., Mitchell, J.S.B., Polishchuk, V.: Geometric stable roommates. Inf. Process. Lett. 109(4), 219\u2013224 (2009)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"8_CR7","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1016\/j.orl.2019.06.002","volume":"47","author":"H Aziz","year":"2019","unstructured":"Aziz, H.: Algorithms for Pareto optimal exchange with bounded exchange cycles. Oper. Res. Lett. 47(5), 344\u2013347 (2019)","journal-title":"Oper. Res. Lett."},{"key":"8_CR8","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1016\/j.geb.2013.08.006","volume":"82","author":"H Aziz","year":"2013","unstructured":"Aziz, H., Brandt, F., Harrenstein, P.: Pareto optimality in coalition formation. Games Econ. Behav. 82, 562\u2013581 (2013)","journal-title":"Games Econ. Behav."},{"key":"8_CR9","unstructured":"Aziz, H., Goldwaser, A.: Coalitional exchange stable matchings in marriage and roommate markets (extended abstract). In: Proceedings of 16th AAMAS Conference, pp. 1475\u20131477. IFAAMAS (2017)"},{"issue":"1","key":"8_CR10","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1086\/256633","volume":"56","author":"D Black","year":"1948","unstructured":"Black, D.: On the rationale of group decision-making. J. Polit. Econ. 56(1), 23\u201334 (1948)","journal-title":"J. Polit. Econ."},{"issue":"3","key":"8_CR11","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.: On the complexity of exchange-stable roommates. Discrete Appl. Math. 116(3), 279\u2013287 (2002)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20133","key":"8_CR12","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.dam.2005.06.003","volume":"152","author":"K Cechl\u00e1rov\u00e1","year":"2005","unstructured":"Cechl\u00e1rov\u00e1, K., Manlove, D.F.: The exchange-stable marriage problem. Discrete Appl. Math. 152(1\u20133), 109\u2013122 (2005)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"8_CR13","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1037\/h0060984","volume":"57","author":"CH Coombs","year":"1950","unstructured":"Coombs, C.H.: Psychological scaling without a unit of measurement. Psychol. Rev. 57(3), 145\u2013158 (1950)","journal-title":"Psychol. Rev."},{"key":"8_CR14","unstructured":"Damamme, A., Beynier, A., Chevaleyre, Y., Maudet, N.: The power of swap deals in distributed resource allocation. In: Proceedings of 14th AAMAS Conference, pp. 625\u2013633. IFAAMAS (2015)"},{"issue":"1","key":"8_CR15","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.geb.2003.05.003","volume":"48","author":"E Diamantoudi","year":"2004","unstructured":"Diamantoudi, E., Miyagawa, E., Xue, L.: Random paths to stability in the roommate problem. Games Econ. Behav. 48(1), 18\u201328 (2004)","journal-title":"Games Econ. Behav."},{"issue":"1","key":"8_CR16","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","volume":"69","author":"D Gale","year":"1962","unstructured":"Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Monthly 69(1), 9\u201315 (1962)","journal-title":"Am. Math. Monthly"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Gourv\u00e8s, L., Lesca, J., Wilczynski, A.: Object allocation via swaps along a social network. In: Proceedings of 26th IJCAI, pp. 213\u2013219. IJCAI (2017)","DOI":"10.24963\/ijcai.2017\/31"},{"key":"8_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/978-3-642-22012-8_8","volume-title":"Automata, Languages and Programming","author":"M Hoefer","year":"2011","unstructured":"Hoefer, M.: Local matching dynamics in social networks. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6756, pp. 113\u2013124. Springer, Heidelberg (2011). \nhttps:\/\/doi.org\/10.1007\/978-3-642-22012-8_8"},{"key":"8_CR19","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1016\/j.artint.2018.06.004","volume":"262","author":"M Hoefer","year":"2018","unstructured":"Hoefer, M., Vaz, D., Wagner, L.: Dynamics in matching and coalition formation games with structural constraints. Artif. Intell. 262, 222\u2013247 (2018)","journal-title":"Artif. Intell."},{"key":"8_CR20","doi-asserted-by":"crossref","unstructured":"Huang, S., Xiao, M.: Object reachability via swaps along a line. In: Proceedings of 33rd AAAI Conference, pp. 2037\u20132044. AAAI Press (2019)","DOI":"10.1609\/aaai.v33i01.33012037"},{"issue":"4","key":"8_CR21","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1016\/0196-6774(85)90033-1","volume":"6","author":"RW Irving","year":"1985","unstructured":"Irving, R.W.: An efficient algorithm for the \u201cstable roommates\u201d problem. J. Algorithms 6(4), 577\u2013595 (1985)","journal-title":"J. Algorithms"},{"key":"8_CR22","unstructured":"Klaus, B., Manlove, D.F., Rossi, F.: Matching under preferences. In: Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A.D. (eds.) Handbook of Computational Social Choice, Chap. 14. Cambridge University Press (2016)"},{"key":"8_CR23","unstructured":"Knuth, D.E.: Mariages stables. Les Presses de l\u2019Universit\u00e9 de Montr\u00e9al (1976)"},{"key":"8_CR24","doi-asserted-by":"crossref","unstructured":"Manlove, D.F.: Algorithmics of Matching Under Preferences. World Scientific Publishing Company (2013)","DOI":"10.1142\/8591"},{"issue":"5","key":"8_CR25","doi-asserted-by":"publisher","first-page":"1739","DOI":"10.1016\/j.jet.2010.02.003","volume":"145","author":"T Morrill","year":"2010","unstructured":"Morrill, T.: The roommates problem revisited. J. Econ. Theory 145(5), 1739\u20131756 (2010)","journal-title":"J. Econ. Theory"},{"issue":"6","key":"8_CR26","doi-asserted-by":"publisher","first-page":"1475","DOI":"10.2307\/2938326","volume":"58","author":"AE Roth","year":"1990","unstructured":"Roth, A.E., Vande Vate, J.H.: Random paths to stability in two-sided matching. Econometrica 58(6), 1475\u20131480 (1990)","journal-title":"Econometrica"},{"key":"8_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/978-3-319-99660-8_19","volume-title":"Algorithmic Game Theory","author":"A Saffidine","year":"2018","unstructured":"Saffidine, A., Wilczynski, A.: Constrained swap dynamics over a social network in distributed resource reallocation. In: Deng, X. (ed.) SAGT 2018. LNCS, vol. 11059, pp. 213\u2013225. Springer, Cham (2018). \nhttps:\/\/doi.org\/10.1007\/978-3-319-99660-8_19"},{"issue":"1","key":"8_CR28","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0304-4068(74)90033-0","volume":"1","author":"LS Shapley","year":"1974","unstructured":"Shapley, L.S., Scarf, H.: On cores and indivisibility. J. Math. Econ. 1(1), 23\u201337 (1974)","journal-title":"J. Math. Econ."}],"container-title":["Lecture Notes in Computer Science","Web and Internet Economics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-35389-6_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,12,2]],"date-time":"2019-12-02T19:04:17Z","timestamp":1575313457000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-35389-6_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030353889","9783030353896"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-35389-6_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"3 December 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WINE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Web and Internet Economics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"New York City, NY","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 December 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 December 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wine0","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/wine2019.cs.columbia.edu\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}