On Computing Pareto Stable Assignments

Author Ning Chen



PDF
Thumbnail PDF

File

LIPIcs.STACS.2012.384.pdf
  • Filesize: 0.64 MB
  • 12 pages

Document Identifiers

Author Details

Ning Chen

Cite AsGet BibTex

Ning Chen. On Computing Pareto Stable Assignments. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 384-395, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
https://doi.org/10.4230/LIPIcs.STACS.2012.384

Abstract

Assignment between two parties in a two-sided matching market has been one of the central questions studied in economics, due to its extensive applications, focusing on different solution concepts with different objectives. One of the most important and well-studied ones is that of stability, proposed by Gale and Shapley, which captures fairness condition in a model where every individual in the market has a preference of the other side. When the preferences have indifferences (i.e., ties), a stable outcome need not be Pareto efficient, causing a loss in efficiency. The solution concept Pareto stability, which requires both stability and Pareto efficiency, offers a refinement of the solution concept stability in the sense that it captures both fairness and efficiency. We study the algorithmic question of computing a Pareto stable assignment in a many-to-many matching market model, where both sides of the market can have multiunit capacities (i.e., demands) and can be matched with multiple partners given the capacity constraints. We provide an algorithm to efficiently construct an assignment that is simultaneously stable and Pareto efficient; our result immediately implies the existence of a Pareto stable assignment for this model.
Keywords
  • Algorithm
  • stable matching
  • Pareto efficiency

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
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