{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T14:43:27Z","timestamp":1780065807982,"version":"3.54.0"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2019,6,21]],"date-time":"2019-06-21T00:00:00Z","timestamp":1561075200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,6,21]],"date-time":"2019-06-21T00:00:00Z","timestamp":1561075200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"ANR","award":["14- CE24-0007-01- CoCoRICo-CoDec"],"award-info":[{"award-number":["14- CE24-0007-01- CoCoRICo-CoDec"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2019,9]]},"DOI":"10.1007\/s10458-019-09417-x","type":"journal-article","created":{"date-parts":[[2019,6,21]],"date-time":"2019-06-21T16:02:41Z","timestamp":1561132961000},"page":"591-627","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["Local envy-freeness in house allocation problems"],"prefix":"10.1007","volume":"33","author":[{"given":"Aur\u00e9lie","family":"Beynier","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yann","family":"Chevaleyre","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laurent","family":"Gourv\u00e8s","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ararat","family":"Harutyunyan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Julien","family":"Lesca","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4232-069X","authenticated-orcid":false,"given":"Nicolas","family":"Maudet","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ana\u00eblle","family":"Wilczynski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,6,21]]},"reference":[{"issue":"3","key":"9417_CR1","doi-asserted-by":"publisher","first-page":"689","DOI":"10.2307\/2998580","volume":"66","author":"A Abdulkadiro\u01e7lu","year":"1998","unstructured":"Abdulkadiro\u01e7lu, A., & S\u00f6nmez, T. (1998). Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica, 66(3), 689\u2013701.","journal-title":"Econometrica"},{"key":"9417_CR2","unstructured":"Abebe, R., Kleinberg, J., & Parkes, D. C. (2017). Fair division via social comparison. In Proceedings of the 16th international conference on autonomous agents and multiagent systems (AAMAS-17) (pp. 281\u2013289). ACM, S\u00e3o Paulo, Brazil."},{"key":"9417_CR3","doi-asserted-by":"crossref","unstructured":"Amanatidis, G., Birmpas, G., & Markakis, V. (2018). Comparing approximate relaxations of envy-freeness. In Proceedings of the 27th international joint conference on artificial intelligence (IJCAI-18) (pp. 42\u201348). International Joint Conferences on Artificial Intelligence, Stockholm, Sweden.","DOI":"10.24963\/ijcai.2018\/6"},{"issue":"3","key":"9417_CR4","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M. F., & Tarjan, R. E. (1979). A linear-time algorithm for testing the truth of certain quantified boolean formulas. Information Processing Letters, 8(3), 121\u2013123.","journal-title":"Information Processing Letters"},{"key":"9417_CR5","volume-title":"Complexity and approximation: Combinatorial optimization problems and their approximability properties","author":"G Ausiello","year":"2012","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., & Protasi, M. (2012). Complexity and approximation: Combinatorial optimization problems and their approximability properties. Berlin: Springer."},{"key":"9417_CR6","doi-asserted-by":"crossref","unstructured":"Aziz, H., Bouveret, S., Caragiannis, I., Giagkousi, I., & Lang, J. (2018). Knowledge, fairness, and social constraints. In Proceedings of the 32nd conference on artificial intelligence (AAAI-18) (pp. 4638\u20134645). AAAI Press, New Orleans, Louisiana, USA.","DOI":"10.1609\/aaai.v32i1.11590"},{"key":"9417_CR7","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.mathsocsci.2017.02.004","volume":"90","author":"H Aziz","year":"2017","unstructured":"Aziz, H., Hougaard, J. L., Moreno-Ternero, J. D., & \u00d8sterdal, L. P. (2017). Computational aspects of assigning agents to a line. Mathematical Social Sciences, 90, 93\u201399.","journal-title":"Mathematical Social Sciences"},{"key":"9417_CR8","unstructured":"Aziz, H., Schlotter, I., & Walsh, T. (2016). Control of fair division. In Proceedings of the 25th international joint conference on artificial intelligence (IJCAI-16) (pp. 67\u201373). IJCAI\/AAAI Press, New York, NY, USA."},{"key":"9417_CR9","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/j.jet.2018.12.004","volume":"180","author":"S Bade","year":"2019","unstructured":"Bade, S. (2019). Matching with single-peaked preferences. Journal of Economic Theory, 180, 81\u201399.","journal-title":"Journal of Economic Theory"},{"issue":"5439","key":"9417_CR10","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"AL Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si, A. L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286(5439), 509\u2013512.","journal-title":"Science"},{"key":"9417_CR11","doi-asserted-by":"crossref","unstructured":"Bei, X., Qiao, Y., & Zhang, S. (2017). Networked fairness in cake cutting. In Proceedings of the 26th international joint conference on artificial intelligence (IJCAI-17) (pp. 3632\u20133638). International Joint Conferences on Artificial Intelligence, Melbourne, Australia.","DOI":"10.24963\/ijcai.2017\/508"},{"key":"9417_CR12","unstructured":"Berman, P., Karpinski, M., & Scott, A. D. (2003). Approximation hardness of short symmetric instances of MAX-3SAT. Electronic Colloquium on Computational Complexity (ECCC) (49)."},{"key":"9417_CR13","unstructured":"Bil\u00f2, V., Caragiannis, I., Flammini, M., Igarashi, A., Monaco, G., Peters, et al. (2019). Almost envy-free allocations with connected bundles. In Proceedings of the 10th conference on innovations in theoretical computer science (ITCS-19), San Diego, California, USA."},{"issue":"1","key":"9417_CR14","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1086\/256633","volume":"56","author":"D Black","year":"1948","unstructured":"Black, D. (1948). On the rationale of group decision-making. Journal of Political Economy, 56(1), 23\u201334.","journal-title":"Journal of Political Economy"},{"key":"9417_CR15","volume-title":"The theory of committees and elections","author":"D Black","year":"1958","unstructured":"Black, D., Newing, R. A., McLean, I., McMillan, A., & Monroe, B. L. (1958). The theory of committees and elections. Berlin: Springer."},{"key":"9417_CR16","doi-asserted-by":"crossref","unstructured":"Bouveret, S., Cechl\u00e1rov\u00e1, K., Elkind, E., Igarashi, A., & Peters, D. (2017). Fair division of a graph. In Proceedings of the 26th international joint conference on artificial intelligence (IJCAI-17) (pp. 135\u2013141). International Joint Conferences on Artificial Intelligence, Melbourne, Australia.","DOI":"10.24963\/ijcai.2017\/20"},{"key":"9417_CR17","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1017\/CBO9781107446984.013","volume-title":"Handbook of computational social choice, Chap.\u00a012","author":"S Bouveret","year":"2016","unstructured":"Bouveret, S., Chevaleyre, Y., & Maudet, N. (2016). Fair allocation of indivisible goods. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, & A. D. Procaccia (Eds.), Handbook of computational social choice, Chap.\u00a012 (pp. 284\u2013310). Cambridge: Cambridge University Press."},{"issue":"2","key":"9417_CR18","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/s10458-015-9287-3","volume":"30","author":"S Bouveret","year":"2016","unstructured":"Bouveret, S., & Lema\u00eetre, M. (2016). Characterizing conflicts in fair division of indivisible goods using a scale of criteria. Autonomous Agents and Multi-Agent Systems, 30(2), 259\u2013290.","journal-title":"Autonomous Agents and Multi-Agent Systems"},{"key":"9417_CR19","unstructured":"Bredereck, R., Kaczmarczyk, A., & Niedermeier, R. (2018). Envy-free allocations respecting social networks. In Proceedings of the 17th international conference on autonomous agents and multiagent systems (AAMAS-18) (pp. 283\u2013291). ACM, Stockholm, Sweden."},{"key":"9417_CR20","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972238","volume-title":"Assignment problems","author":"R Burkard","year":"2012","unstructured":"Burkard, R., Dell\u2019Amico, M., & Martello, S. (2012). Assignment problems. Philadelphia: Society for Industrial and Applied Mathematics."},{"key":"9417_CR21","doi-asserted-by":"crossref","unstructured":"Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., & Kyropoulou, M. (2009). On low-envy truthful allocations. In Proceedings of the 1st international conference on algorithmic decision theory (ADT-09) (pp. 111\u2013119). Springer, Venice, Italy.","DOI":"10.1007\/978-3-642-04428-1_10"},{"issue":"3","key":"9417_CR22","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/j.mathsocsci.2010.01.002","volume":"59","author":"S Cato","year":"2010","unstructured":"Cato, S. (2010). Local strict envy-freeness in large economies. Mathematical Social Sciences, 59(3), 319\u2013322.","journal-title":"Mathematical Social Sciences"},{"key":"9417_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2016.09.005","volume":"242","author":"Y Chevaleyre","year":"2017","unstructured":"Chevaleyre, Y., Endriss, U., & Maudet, N. (2017). Distributed fair allocation of indivisible goods. Artificial Intelligence, 242, 1\u201322.","journal-title":"Artificial Intelligence"},{"key":"9417_CR24","unstructured":"Damamme, A., Beynier, A., Chevaleyre, Y., & Maudet, N. (2015). The power of swap deals in distributed resource allocation. In Proceedings of the 14th international conference on autonomous agents and multiagent systems (AAMAS-15) (pp. 625\u2013633). ACM, Istanbul, Turkey."},{"key":"9417_CR25","doi-asserted-by":"crossref","unstructured":"de\u00a0Keijzer, B., Bouveret, S., Klos, T., & Zhang, Y. (2009). On the complexity of efficiency and envy-freeness in fair division of indivisible goods with additive preferences. In Proceedings of the 1st international conference on algorithmic decision theory (ADT-09) (pp. 98\u2013110). Springer, Venice, Italy.","DOI":"10.1007\/978-3-642-04428-1_9"},{"key":"9417_CR26","doi-asserted-by":"crossref","unstructured":"Dickerson, J. P., Goldman, J. R., Karp, J., Procaccia, A. D., & Sandholm, T. (2014). The computational rise and fall of fairness. In Proceedings of the 28th conference on artificial intelligence (AAAI-14) (pp. 1405\u20131411). AAAI Press, Qu\u00e9bec City, Qu\u00e9bec, Canada.","DOI":"10.1609\/aaai.v28i1.8884"},{"issue":"6","key":"9417_CR27","first-page":"995","volume":"64","author":"A Feldman","year":"1974","unstructured":"Feldman, A., & Kirman, A. (1974). Fairness and envy. The American Economic Review, 64(6), 995\u20131005.","journal-title":"The American Economic Review"},{"issue":"8","key":"9417_CR28","doi-asserted-by":"publisher","first-page":"1075","DOI":"10.1109\/TPDS.2008.168","volume":"20","author":"M Feldman","year":"2009","unstructured":"Feldman, M., Lai, K., & Zhang, L. (2009). The proportional-share allocation market for computational resources. IEEE Transactions on Parallel and Distributed Systems, 20(8), 1075\u20131088.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"issue":"1","key":"9417_CR29","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"MR Fellows","year":"2009","unstructured":"Fellows, M. R., Hermelin, D., Rosamond, F., & Vialette, S. (2009). On the parameterized complexity of multiple-interval graph problems. Theoretical Computer Science, 410(1), 53\u201361.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"9417_CR30","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1177\/001872675400700202","volume":"7","author":"L Festinger","year":"1954","unstructured":"Festinger, L. (1954). A theory of social comparison process. Human Relations, 7(2), 117\u2013140.","journal-title":"Human Relations"},{"key":"9417_CR31","doi-asserted-by":"crossref","unstructured":"Flammini, M., Mauro, M., & Tonelli, M. (2018). On social envy-freeness in multi-unit markets. In Proceedings of the 32nd conference on artificial intelligence (AAAI-18) (pp. 1031\u20131038). AAAI Press, New Orleans, Louisiana, USA.","DOI":"10.1609\/aaai.v32i1.11438"},{"issue":"1","key":"9417_CR32","first-page":"45","volume":"7","author":"DK Foley","year":"1967","unstructured":"Foley, D. K. (1967). Resource allocation and the public sector. Yale Economic Essays, 7(1), 45\u201398.","journal-title":"Yale Economic Essays"},{"key":"9417_CR33","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. New York, NY: W. H. Freeman."},{"issue":"1","key":"9417_CR34","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/0022-0531(76)90063-6","volume":"13","author":"WV Gehrlein","year":"1976","unstructured":"Gehrlein, W. V., & Fishburn, P. C. (1976). The probability of the paradox of voting: A computable solution. Journal of Economic Theory, 13(1), 14\u201325.","journal-title":"Journal of Economic Theory"},{"key":"9417_CR35","doi-asserted-by":"crossref","unstructured":"Gourv\u00e8s, L., Lesca, J., & Wilczynski, A. (2017). Object allocation via swaps along a social network. In Proceedings of the 26th international joint conference on artificial intelligence (IJCAI-17) (pp. 213\u2013219). International Joint Conferences on Artificial Intelligence, Melbourne, Australia.","DOI":"10.24963\/ijcai.2017\/31"},{"key":"9417_CR36","unstructured":"Hagberg, A. A., Schult, D. A., & Swart, P. J. (2008). Exploring network structure, dynamics, and function using NetworkX. In Proceedings of the 7th python in science conference (SciPy-08) (pp. 11 \u2013 15). Pasadena, CA USA."},{"issue":"2","key":"9417_CR37","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1086\/260757","volume":"87","author":"A Hylland","year":"1979","unstructured":"Hylland, A., & Zeckhauser, R. (1979). The efficient allocation of individuals to positions. Journal of Political Economy, 87(2), 293\u2013314.","journal-title":"Journal of Political Economy"},{"key":"9417_CR38","doi-asserted-by":"crossref","unstructured":"Igarashi, A., & Peters, D. (2019). Pareto-optimal allocation of indivisible goods with connectivity constraints. In Proceedings of the 33rd conference on artificial intelligence (AAAI-19), Honolulu, Hawaii, USA (to appear).","DOI":"10.1609\/aaai.v33i01.33012045"},{"key":"9417_CR39","volume-title":"Algorithm design","author":"JM Kleinberg","year":"2006","unstructured":"Kleinberg, J. M., & Tardos, \u00c9. (2006). Algorithm design. Reading: Addison-Wesley."},{"key":"9417_CR40","unstructured":"Kondratev, A. Y., Nesterov, A. S. (2019). Minimal envy and popular matchings. CoRR arXiv:1902.08003."},{"key":"9417_CR41","doi-asserted-by":"crossref","unstructured":"Lipton, R. J., Markakis, E., Mossel, E., Saberi, A. (2004). On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM conference on electronic commerce (EC-04) (pp. 125\u2013131). ACM, New York, NY, USA.","DOI":"10.1145\/988772.988792"},{"key":"9417_CR42","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.dam.2014.09.010","volume":"179","author":"TT Nguyen","year":"2014","unstructured":"Nguyen, T. T., & Rothe, J. (2014). Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods. Discrete Applied Mathematics, 179, 54\u201368.","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"9417_CR43","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0020-0190(92)90248-T","volume":"44","author":"VT Paschos","year":"1992","unstructured":"Paschos, V. T. (1992). A ($\\Delta $\/2)-approximation algorithm for the maximum independent set problem. Information Processing Letters, 44(1), 11\u201313.","journal-title":"Information Processing Letters"},{"key":"9417_CR44","doi-asserted-by":"crossref","unstructured":"Saffidine, A., & Wilczynski, A. (2018). Constrained swap dynamics over a social network in distributed resource reallocation. In Proceedings of the 11th international symposium on algorithmic game theory (SAGT-18) (pp. 213\u2013225). Springer, Beijing, China.","DOI":"10.1007\/978-3-319-99660-8_19"},{"issue":"4","key":"9417_CR45","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1017\/S0963548399003867","volume":"8","author":"A Steger","year":"1999","unstructured":"Steger, A., & Wormald, N. C. (1999). Generating random regular graphs quickly. Combinatorics, Probability and Computing, 8(4), 377\u2013396.","journal-title":"Combinatorics, Probability and Computing"},{"key":"9417_CR46","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/j.dam.2019.01.036","volume":"260","author":"W Suksompong","year":"2019","unstructured":"Suksompong, W. (2019). Fairly allocating contiguous blocks of indivisible items. Discrete Applied Mathematics, 260, 227\u2013236.","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"9417_CR47","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/s003550050160","volume":"16","author":"LG Svensson","year":"1999","unstructured":"Svensson, L. G. (1999). Strategy-proof allocation of indivisible goods. Social Choice and Welfare, 16(4), 557\u2013567.","journal-title":"Social Choice and Welfare"},{"key":"9417_CR48","volume-title":"Approximation algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V. V. (2001). Approximation algorithms. Berlin: Springer."},{"issue":"1","key":"9417_CR49","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0022-0531(90)90070-Z","volume":"52","author":"L Zhou","year":"1990","unstructured":"Zhou, L. (1990). On a conjecture by Gale about one-sided matching problems. Journal of Economic Theory, 52(1), 123\u2013135.","journal-title":"Journal of Economic Theory"}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-019-09417-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10458-019-09417-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-019-09417-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,21]],"date-time":"2022-09-21T14:25:04Z","timestamp":1663770304000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10458-019-09417-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,21]]},"references-count":49,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["9417"],"URL":"https:\/\/doi.org\/10.1007\/s10458-019-09417-x","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"value":"1387-2532","type":"print"},{"value":"1573-7454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,21]]},"assertion":[{"value":"21 June 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}