Abstract
We study fairness and efficiency properties of randomized algorithms for barter exchanges with direct applications to kidney exchange problems. It is well documented that randomization can serve as a tool to ensure fairness among participants. However, in many applications, practical constraints often restrict the maximum allowed cycle-length of the exchange and for randomized algorithms, this imposes constraints of the cycle-length of every realized exchange in their decomposition. We prove that standard fairness properties such as envy-freeness or symmetry are incompatible with even the weakest notion of economic efficiency in this setting. On the plus side, we adapt some well-known matching mechanisms to incorporate the restricted cycle constraint and evaluate their performance experimentally on instances of the kidney exchange problem, showing tradeoffs between fairness and efficiency.
This work was supported by the National Basic Research Program of China Grant 2011CBA00300, 2011CBA00301, the Natural Science Foundation of China Grant 61033001, 61361136003, 61303077, a Tsinghua Initiative Scientific Research Grant and a China Youth 1000-talent program. Aris Filos-Ratsikas and Søren Kristoffer Stiil Frederiksen acknowledge support from the Danish National Research Foundation and The National Science Foundation of China (under the grant 61061130540) for the Sino-Danish Center for the Theory of Interactive Computation, within which this work was performed. The authors also acknowledge support from the Center for Research in Foundations of Electronic Markets (CFEM), supported by the Danish Strategic Research Council.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
- 2.
In this paper, we do not consider the use of altruistic chains, which may circumvent this requirement.
- 3.
- 4.
Balbuzanov [4] uses the term k-constrained to describe such assignments.
- 5.
This is true in particular because we consider all mechanisms, including cardinal mechanisms, i.e. mechanisms that can use the numerical values when outputting assignments.
- 6.
A simple example with two agents 1, 2 that have the same preference over items 1, 2 is sufficient to see this.
- 7.
This interpretation is very natural given that the proof in [2] uses a reduction from 3D-Matching.
References
Abdulkadiroğlu, A., Sönmez, T.: Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica 66(3), 689–701 (1998)
Abraham, D.J., Blum, A., Sandholm, T.: Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges. In: Proceedings of the 8th ACM Conference on Electronic Commerce, pp. 295–304. ACM (2007)
Ashlagi, I., Roth, A.: Individual rationality and participation in large scale, multi-hospital kidney exchange. In: Proceedings of the 12th ACM Conference on Electronic Commerce, pp. 321–322. ACM (2011)
Balbuzanov, I.: Short trading cycles: kidney exchange with strict ordinal preferences (2014)
Bogomolnaia, A., Moulin, H.: A new solution to the random assignment problem. J. Econ. Theor. 100(2), 295–328 (2001)
Dickerson, J.P., Goldman, J.R., Karp, J., Procaccia, A.D., Sandholm, T.: The computational rise and fall of fairness. In: Proceedings of the Twenty-eighth AAAI Conference on Artificial Intelligence, Québec City, Québec, Canada, 27–31 July 2014, pp. 1405–1411 (2014)
Dickerson, J.P., Procaccia, A.D., Sandholm, T.: Dynamic matching via weighted myopia with application to kidney exchange. In: AAAI (2012)
Dickerson, J.P., Procaccia, A.D., Sandholm, T.: Failure-aware kidney exchange. In: Proceedings of the Fourteenth ACM Conference on Electronic Commerce, pp. 323–340. ACM (2013)
Dickerson, J.P., Procaccia, A.D., Sandholm, T.: Price of fairness in kidney exchange. In: International Conference on Autonomous Agents and Multi-agent Systems, AAMAS 2014, Paris, France, 5–9 May 2014, pp. 1013–1020 (2014)
Goel, A., Kapralov, M., Khanna, S.: Perfect matchings in \(o(n\log n)\) time in regular bipartite graphs. SIAM J. Comput. 42(3), 1392–1404 (2013)
Katta, A.-K., Sethuraman, J.: A solution to the random assignment problem on the full preference domain. J. Econ. Theor. 131(1), 231–250 (2006)
Li, J., Liu, Y., Huang, L., Tang, P.: Egalitarian pairwise kidney exchange: fast algorithms vialinear programming and parametric flow. In: International Conference on Autonomous Agents and Multi-agent Systems, AAMAS 2014, Paris, France, 5–9 May 2014, pp. 445–452 (2014)
Roth, A.E., Sönmez, T., Ünver, M.: Kidney exchange. Q. J. Econ. 119(2), 457–488 (2004)
Roth, A.E., Sönmez, T., Ünver, M.U.: Pairwise kidney exchange. J. Econ. Theor. 125(2), 151–188 (2005)
Saban, D., Sethuraman, J.: The complexity of computing the random priority allocation matrix. In: Chen, Y., Immorlica, N. (eds.) WINE 2013. LNCS, vol. 8289, pp. 421–421. Springer, Heidelberg (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Fang, W., Filos-Ratsikas, A., Frederiksen, S.K.S., Tang, P., Zuo, S. (2015). Randomized Assignments for Barter Exchanges: Fairness vs. Efficiency. In: Walsh, T. (eds) Algorithmic Decision Theory. ADT 2015. Lecture Notes in Computer Science(), vol 9346. Springer, Cham. https://doi.org/10.1007/978-3-319-23114-3_32
Download citation
DOI: https://doi.org/10.1007/978-3-319-23114-3_32
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-23113-6
Online ISBN: 978-3-319-23114-3
eBook Packages: Computer ScienceComputer Science (R0)