Exchange of indivisible goods and indifferences: the top trading absorbing sets mechanisms. (English) Zbl 1236.91106
Summary: There is a wide range of economic problems that involve the exchange of indivisible goods with no monetary transfers, starting from the housing market model of the seminal paper by L. Shapley and H. Scarf [J. Math. Econ. 1, 23–37 (1974; Zbl 0281.90014)] to problems such as the kidney exchange or the school choice problem. The classical solution to many of these models is to apply a mechanism called top trading cycles, attributed to David Gale, which satisfies good properties for the case of strict preferences. In this paper, we propose a family of mechanisms, called top trading absorbing sets mechanisms, which generalize the top trading cycles to the general case in which individuals are allowed to report indifferences, while preserving a maximal possible set of its desirable properties.
MSC:
| 91B68 | Matching models |
| 91B60 | Trade models |
| 91B32 | Resource and cost allocation (including fair division, apportionment, etc.) |
Citations:
Zbl 0281.90014References:
| [1] | Abdulkadiroğlu, A.; Sönmez, T., House allocation with existing tenants, J. Econ. Theory, 88, 233-260 (1999) · Zbl 0939.91068 |
| [2] | Abdulkadiroğlu, A.; Sönmez, T., School choice: a mechanism design approach, Amer. Econ. Rev., 93, 729-747 (2003) |
| [3] | Bird, C., Group incentive compatibility in a market with indivisible goods, Econ. Letters, 14, 309-313 (1984) |
| [4] | Ehlers, L., Coalitional strategy-proof house allocation, J. Econ. Theory, 105, 298-317 (2002) · Zbl 1021.91035 |
| [5] | Erdil, A.; Ergin, H., Whatʼs the matter with tie-breaking? Improving efficiency in school choice, Amer. Econ. Rev., 98, 669-689 (2008) |
| [6] | Gale, D.; Shapley, L., College admissions and the stability of marriage, Amer. Math. Mon., 69, 9-15 (1962) · Zbl 0109.24403 |
| [7] | Jaramillo, P., Manjunath, V., 2009. The difference indifference makes in strategy-proof allocation of objects. Mimeo.; Jaramillo, P., Manjunath, V., 2009. The difference indifference makes in strategy-proof allocation of objects. Mimeo. · Zbl 1247.91101 |
| [8] | Kalai, E.; Schmeidler, D., An admissible set occurring in various bargaining situations, J. Econ. Theory, 14, 402-411 (1977) · Zbl 0364.90146 |
| [9] | Konishi, H.; Quint, T.; Wako, J., On the Shapley-Scarf economy: the case of multiple types of indivisible goods, J. Math. Econ., 35, 1-15 (2001) · Zbl 1007.91036 |
| [10] | Ma, J., Strategy-proofness and the strict core in a market with indivisibilities, Int. J. Game Theory, 23, 75-83 (1994) · Zbl 0804.90014 |
| [11] | Quint, T.; Wako, J., On houseswapping, the strict core, segmentation, and linear programming, Math. Operations Res., 29, 861-877 (2004) · Zbl 1082.91021 |
| [12] | Roth, A. E., Incentive compatibility in a market with indivisibilities, Econ. Letters, 9, 127-132 (1982) · Zbl 0722.90009 |
| [13] | Roth, A. E.; Postlewaite, A., Weak versus strong domination in a market with indivisible goods, J. Math. Econ., 4, 131-137 (1977) · Zbl 0368.90025 |
| [14] | Roth, Alvin E.; Sönmez, T.; Ünver, M. U., Kidney exchange, Quart. J. Econ., 119, 457-488 (2004) · Zbl 1064.92029 |
| [15] | Shapley, L.; Scarf, H., On cores and indivisibility, J. Math. Econ., 1, 23-28 (1974) · Zbl 0281.90014 |
| [16] | Sönmez, T.; Ünver, M. U., Matching, Allocation, and Exchange of Discrete Resources. Handbook of Social Economics (2009), Elsevier |
| [17] | Tarjan, R., Depth-first search and linear graph algorithms, SIAM J. Comp., 2, 146-160 (1972) · Zbl 0251.05107 |
| [18] | Yılmaz, Ö., Random assignment under weak preferences, Games Econ. Behav., 65, 546-558 (2009) · Zbl 1161.91346 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
