Stability and Efficiency in the General-Priority-Based Assignment

Aytek Erdil; Taro Kumano

Auctions, Market Mechanisms, and Their Applications. Second International ICST Conference, AMMA 2011, NewYork, NY, USA, August 22-23, 2011, Revised Selected Papers

Research Article

Stability and Efficiency in the General-Priority-Based Assignment

Download

369 downloads

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.1007/978-3-642-30913-7_18,
    author={Aytek Erdil and Taro Kumano},
    title={Stability and Efficiency in the General-Priority-Based Assignment},
    proceedings={Auctions, Market Mechanisms, and Their Applications. Second International ICST Conference, AMMA 2011, NewYork, NY, USA, August 22-23, 2011, Revised Selected Papers},
    proceedings_a={AMMA},
    year={2012},
    month={10},
    keywords={Stability Efficiency Generalized deferred acceptance algorithm Substitutability Indifferences Stable agent improving cycle Equal treatment of equal agents Acyclicity},
    doi={10.1007/978-3-642-30913-7_18}
}

Aytek Erdil
Taro Kumano
Year: 2012
Stability and Efficiency in the General-Priority-Based Assignment
AMMA
Springer
DOI: 10.1007/978-3-642-30913-7_18

Aytek Erdil¹^,*, Taro Kumano²^,*

1: University of Cambridge
2: Washington University in St. Louis

*Contact email: nae25@cam.ac.uk, tkumano@wustl.edu

Abstract

We introduce a general class of priority orders over sets, which captures both indifferences and substitutability. Our notion of substitutability ensures the existence of stable assignment. The characterization of efficient priority structures implies that there is usually a conflict between efficiency and stability. Thus we turn to the problem of finding a constrained efficient assignment, and give an algorithm which solves the problem for any priority structure that falls into our class. As an important application, gender equality or racial equality in school choice can be captured by our model, but not previous models in the literature.

Keywords: Stability Efficiency Generalized deferred acceptance algorithm Substitutability Indifferences Stable agent improving cycle Equal treatment of equal agents Acyclicity

Published: 2012-10-08

: http://dx.doi.org/10.1007/978-3-642-30913-7_18