Document Open Access Logo

Maximum Votes Pareto-Efficient Allocations via Swaps on a Social Network

Authors Fu Li, Xiong Zheng

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.71.pdf
  • Filesize: 0.63 MB
  • 16 pages

Document Identifiers

Author Details

Fu Li
  • University of Texas at Austin, TX, USA
Xiong Zheng
  • University of Texas at Austin, TX, USA

Cite AsGet BibTex

Fu Li and Xiong Zheng. Maximum Votes Pareto-Efficient Allocations via Swaps on a Social Network. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 71:1-71:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.MFCS.2021.71

Abstract

In recent work, Gourv{è}s, Lesca, and Wilczynski (IJCAI 17) propose a variant of the classic housing markets model in which the matching between agents and objects evolves through Pareto-improving swaps between pairs of agents who are adjacent in a social network. To explore the swap dynamics of their model, they pose several basic questions concerning the set of reachable matchings, and investigate the computational complexity of these questions when the graph structure of the social network is a star, path, or tree, or is unrestricted. We are interested in how to direct the agents to swap objects with each other in order to arrive at a reachable matching that is both efficient and most agreeable. In particular, we study the computational complexity of reaching a Pareto-efficient matching that maximizes the number of agents who prefer their match to their initial endowments. We consider various graph structures of the social network: path, star, tree, or being unrestricted. Additionally, we consider two assumptions regarding preference relations of agents: strict (ties among objects not allowed) or weak (ties among objects allowed). By designing two polynomial-time algorithms and two NP-hardness reductions, we resolve the complexity of all cases not yet known. Our main contributions include a polynomial-time algorithm for path networks with strict preferences and an NP-hardness result in a star network with weak preferences.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory
Keywords
  • Housing markets
  • Distributed process
  • Algorithms
  • Complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Atila Abdulkadiroğlu, Yeon-Koo Che, and Yosuke Yasuda. Resolving conflicting preferences in school choice: The "Boston Mechanism" reconsidered. American Economic Review, 101(1):399-410, 2011. Google Scholar
  2. Atila Abdulkadiroğlu and Tayfun Sönmez. Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica, 66(3):689-701, 1998. Google Scholar
  3. Atila Abdulkadiroğlu and Tayfun Sönmez. House allocation with existing tenants. Journal of Economic Theory, 88(2):233-260, 1999. Google Scholar
  4. David J. Abraham, Katarína Cechlárová, David F. Manlove, and Kurt Mehlhorn. Pareto optimality in house allocation problems. In Proceedings of the 15th International Symposium on Algorithms and Computation, pages 3-15, 2004. Google Scholar
  5. David J. Abraham, Robert W. Irving, Telikepalli Kavitha, and Kurt Mehlhorn. Popular matchings. SIAM Journal on Computing, 37(4):1030-1045, 2007. Google Scholar
  6. Haris Aziz, Serge Gaspers, Simon Mackenzie, and Toby Walsh. Fair assignment of indivisible objects under ordinal preferences. Artificial Intelligence, 227:71-92, 2015. Google Scholar
  7. Matthias Bentert, Jiehua Chen, Vincent Froese, and Gerhard J. Woeginger. Good things come to those who swap objects on paths. arXiv, 2019. URL: http://arxiv.org/abs/1905.04219.
  8. Aurélie Beynier, Yann Chevaleyre, Laurent Gourvès, Ararat Harutyunyan, Julien Lesca, Nicolas Maudet, and Anaëlle Wilczynski. Local envy-freeness in house allocation problems. Autonomous Agents and Multi-Agent Systems, 33(5):591-627, 2019. Google Scholar
  9. Vittorio Bilò, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, and William S. Zwicker. Almost envy-free allocations with connected bundles. In Proceedings of the 10th Innovations in Theoretical Computer Science Conference, pages 14:1-14:21, 2018. Google Scholar
  10. Péter Biró and Jens Gudmundsson. Complexity of finding Pareto-efficient allocations of highest welfare. European Journal of Operational Research, 291(2):614-628, 2021. Google Scholar
  11. Ágnes Cseh. Trends in computational social choice. In U. Endriss, editor, Trends in Computational Social Choice, chapter 6, pages 105-122. lulu.com, 2017. Google Scholar
  12. Federico Echenique, Antonio Miralles, and Jun Zhang. Fairness and efficiency for probabilistic allocations with endowments. arXiv, 2019. URL: http://arxiv.org/abs/1908.04336.
  13. Laurent Gourvès, Julien Lesca, and Anaëlle Wilczynski. Object allocation via swaps along a social network. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, pages 213-219, 2017. Google Scholar
  14. Sen Huang and Mingyu Xiao. Object reachability via swaps along a line. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, pages 2037-2044, 2019. Google Scholar
  15. Sen Huang and Mingyu Xiao. Object reachability via swaps under strict and weak preferences. Autonomous Agents and Multiagent Systems, 34(2):51, 2020. Google Scholar
  16. Ayumi Igarashi and Dominik Peters. Pareto-optimal allocation of indivisible goods with connectivity constraints. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, pages 2045-2052, 2019. Google Scholar
  17. Telikepalli Kavitha, Julián Mestre, and Meghana Nasre. Popular mixed matchings. Theoretical Computer Science, 412(24):2679-2690, 2011. Google Scholar
  18. Telikepalli Kavitha, Meghana Nasre, and Prajakta Nimbhorkar. Popularity at minimum cost. Journal of Combinatorial Optimization, 27(3):574-596, 2014. Google Scholar
  19. Richard Matthew McCutchen. The least-unpopularity-factor and least-unpopularity-margin criteria for matching problems with one-sided preferences. In Proceedings of 8th Latin American Symposium on Theoretical Informatics, pages 593-604, 2008. Google Scholar
  20. Luis Müller and Matthias Bentert. On reachable assignments in cycles and cliques. arXiv, 2020. URL: http://arxiv.org/abs/2005.02218.
  21. Abdallah Saffidine and Anaëlle Wilczynski. Constrained swap dynamics over a social network in distributed resource reallocation. In Proceedings of the 11th International Symposium on Algorithmic Game Theory, pages 213-225, 2018. Google Scholar
  22. Lloyd Shapley and Herbert Scarf. On cores and indivisibility. Journal of Mathematical Economics, 1(1):23-37, 1974. Google Scholar
  23. Ryo Yoshinaka. Higher-order matching in the linear lambda calculus in the absence of constants is NP-complete. In Jürgen Giesl, editor, Proceedings of 16th International Conference on Term Rewriting and Applications, pages 235-249, 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact