Back to Search
Start Over
Randomized Assignments for Barter Exchanges: Fairness vs Efficiency
- Source :
- Fang, W, Filos-Ratsikas, A, Frederiksen, S K S, Tang, P & Zuo, S 2015, Randomized Assignments for Barter Exchanges: Fairness vs Efficiency . in T Walsh (ed.), Algorithmic Decision Theory : 4th International Conference, ADT 2015, Lexington, KY, USA, September 27-30, 2015, Proceedings . Springer VS, Lecture Notes in Computer Science, vol. 9346, pp. 537-552, International Conference on Algorithmic Decision Theory, Lexington, United States, 27/09/2015 . https://doi.org/10.1007/978-3-319-23114-3_32, Algorithmic Decision Theory ISBN: 9783319231136, ADT
- Publication Year :
- 2015
- Publisher :
- Springer VS, 2015.
-
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.
Details
- Language :
- English
- ISBN :
- 978-3-319-23113-6
- ISBNs :
- 9783319231136
- Database :
- OpenAIRE
- Journal :
- Fang, W, Filos-Ratsikas, A, Frederiksen, S K S, Tang, P & Zuo, S 2015, Randomized Assignments for Barter Exchanges: Fairness vs Efficiency . in T Walsh (ed.), Algorithmic Decision Theory : 4th International Conference, ADT 2015, Lexington, KY, USA, September 27-30, 2015, Proceedings . Springer VS, Lecture Notes in Computer Science, vol. 9346, pp. 537-552, International Conference on Algorithmic Decision Theory, Lexington, United States, 27/09/2015 . https://doi.org/10.1007/978-3-319-23114-3_32, Algorithmic Decision Theory ISBN: 9783319231136, ADT
- Accession number :
- edsair.doi.dedup.....c74eb3616c0c4f7cb040355168cc03dc