Identifying optimal strategies in kidney exchange games is \(\varSigma_2^p\)-complete. (English) Zbl 1537.91065
Summary: In kidney exchange games, agents (e.g. hospitals or national organizations) have control over a number of incompatible recipient-donor pairs whose recipients are in need of a transplant. Each agent has the opportunity to join a collaborative effort which aims to maximize the total number of transplants that can be realized. However, the individual agent is only interested in maximizing the number of transplants within the set of recipients under its control. Then, the question becomes: which recipient-donor pairs to submit to the collaborative effort? We model this situation by introducing the Stackelberg kidney exchange game, a game where an agent, having perfect information, needs to identify a strategy, i.e., to decide which recipient-donor pairs to submit. We show that even in this simplified setting, identifying an optimal strategy is \(\varSigma_2^p\)-complete, whenever we allow exchanges involving at most a fixed number \(K \geq 3\) pairs. However, when we restrict ourselves to pairwise exchanges only, the problem becomes solvable in polynomial time.
MSC:
| 91A65 | Hierarchical games (including Stackelberg games) |
| 91B68 | Matching models |
| 90C60 | Abstract computational complexity for mathematical programming problems |
References:
| [1] | Abraham, David J., Blum, Avrim, Sandholm, Tuomas: Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges. In Proceedings of the eighth ACM Conference on Economic Commerce, pages 295-304. ACM, (2007) |
| [2] | Agarwal, N., Ashlagi, I., Azevedo, E., Featherstone, C.R., Karaduman, Ö.: Market failure in kidney exchange. Am. Econ. Rev. 109(11), 4026-4070 (2020) |
| [3] | Arora, S., Barak, B.: Computational complexity: a modern approach. Technical report, Cambridge University Press (2009) · Zbl 1193.68112 |
| [4] | Ashlagi, I.; Roth, AE, Free riding and participation in large scale, multi-hospital kidney exchange, Theor. Econ., 9, 3, 817-863 (2014) · Zbl 1395.91337 · doi:10.3982/TE1357 |
| [5] | Ashlagi, I.; Fischer, F.; Kash, IA; Procaccia, AD, Mix and match: a strategyproof mechanism for multi-hospital kidney exchange, Games Econom. Behav., 91, 284-296 (2015) · Zbl 1318.91143 · doi:10.1016/j.geb.2013.05.008 |
| [6] | Berge, C., Two theorems in graph theory, Proc. Natl. Acad. Sci. USA, 43, 9, 842-844 (1957) · Zbl 0086.16202 · doi:10.1073/pnas.43.9.842 |
| [7] | Biró, P., Haase-Kromwijk, B., Andersson, T., Ásgeirsson, E.I., Baltesová, T., Boletis, I., Bolotinha, C., Bond, G., Böhmig, G., Burnapp, L., Cechlárová, K., Di Ciaccio, P., Fronek, J., Hadaya, K., Hemke, A., Jacquelinet, C., Johnson, R., Kieszek, R., Kuypers, D., Leishman, R., Macher, M.-A., Manlove, D., Menoudakou, G., Salonen, M., Smeulders, B., Sparacino, V., Spieksma, F., de la Oliva Valentín Muñoz, M., Wilson, N., van de Klundert, J.: Building kidney exchange programmes in Europe – an overview of exchange practice and activities. Transplantation, 103:1514-1522 (2019) |
| [8] | Biró, P., Kern, W., Pálvölgyi, D., Paulusma, D.: Generalized matching games for international kidney exchange. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems, pp. 413-421. International Foundation for Autonomous Agents and Multiagent Systems (2019) |
| [9] | Biró, P., Gyetvai, M., Klimentova, X., Pedroso, J.P., Pettersson, W., Viana: Compensation scheme with Shapley value for multi-country kidney exchange programmes, Ana (2020) |
| [10] | Biró, Péter., van de Klundert, Joris, Manlove, David, Pettersson, William, Andersson, Tommy, Burnapp, Lisa, Chromy, Pavel, Delgado, Pablo, Dworczak, Piotr, Haase, Bernadette, et al, Eur. J. Oper. Res., 291, 447-456 (2021) |
| [11] | Blum, A., Caragiannis, I., Haghtalab, N., Procaccia, A.D., Procaccia, E.B., Vaish, R.: Opting into optimal matchings. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2351-2363. SIAM (2017) · Zbl 1410.05160 |
| [12] | Caragiannis, I.; Filos-Ratsikas, A.; Procaccia, AD, An improved 2-agent kidney exchange mechanism, Theoret. Comput. Sci., 589, 53-60 (2015) · Zbl 1318.91144 · doi:10.1016/j.tcs.2015.04.013 |
| [13] | Carvalho, M., Lodi, A.: Game theoretical analysis of kidney exchange programs. arXiv preprint arXiv:1911.09207 (2019) |
| [14] | Carvalho, M., Lodi, A., Pedroso, J.P., Viana, A.: Nash equilibria in the two-player kidney exchange game. Math. Program. 161(1-2), 389-417 (2017) · Zbl 1414.91289 |
| [15] | Hajaj, C., Dickerson, J.P., Hassidim, A., Sandholm, T., Sarne, D.: Strategy-proof and efficient kidney exchange using a credit mechanism. In Twenty-Ninth AAAI Conference on Artificial Intelligence (2015) |
| [16] | Johannes, B.: New classes of complete problems for the second level of the polynomial hierarchy. Technical report, PhD thesis of TU Berlin (2011) |
| [17] | Klimentova, X., Viana, A., Pedroso, J.P., Santos, N.: Fairness models for multi-agent kidney exchange programmes. Omega 102333 (2020) |
| [18] | Lodi, A.; Ralphs, T.; Woeginger, G., Bilevel programming and the separation problem, Math. Program., 146, 1-2, 437-458 (2014) · Zbl 1401.90128 · doi:10.1007/s10107-013-0700-x |
| [19] | Reese, P.; Boudville, N.; Garg, A., Living kidney donation: outcomes, ethics, and uncertainty, The Lancet, 385, 2003-2013 (2015) · doi:10.1016/S0140-6736(14)62484-3 |
| [20] | Smeulders, B., Blom, D.A.M.P., Spieksma, F.C.R.: The Stackelberg kidney exchange problem is \({\Sigma }_2^p\)-complete. In Proceedings of SAGT 2020, p. 342. Springer (2020) |
| [21] | Toulis, P.; Parkes, DC, Design and analysis of multi-hospital kidney exchange mechanisms using random graphs, Games Econom. Behav., 91, 360-382 (2015) · Zbl 1318.91148 · doi:10.1016/j.geb.2015.01.001 |
| [22] | Valentín, MO; Garcia, M.; Costa, AN; Bolotinha, C.; Guirado, L.; Vistoli, F.; Breda, A.; Fiaschetti, P.; Dominguez-Gil, B., International cooperation for kidney exchange success, Transplantation, 103, 6, e180-e181 (2019) · doi:10.1097/TP.0000000000002664 |
| [23] | Woeginger, G.J.: The trouble with the second quantifier. 4OR, 1-25 (2021) |
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.
