{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:19:23Z","timestamp":1750220363178,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":26,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,7,18]],"date-time":"2021-07-18T00:00:00Z","timestamp":1626566400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Science Foundation","award":["CCF-1733556"],"award-info":[{"award-number":["CCF-1733556"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,7,18]]},"DOI":"10.1145\/3465456.3467622","type":"proceedings-article","created":{"date-parts":[[2021,7,18]],"date-time":"2021-07-18T10:28:50Z","timestamp":1626604130000},"page":"138-156","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Incentive-Compatible Kidney Exchange in a Slightly Semi-Random Model"],"prefix":"10.1145","author":[{"given":"Avrim","family":"Blum","sequence":"first","affiliation":[{"name":"Toyota Technological Institute at Chicago, Chicago, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"G\u00f6lz","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,7,18]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2013.05.008"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"I. Ashlagi D. Gamarnik M. A. Rees and A. E. Roth. 2012. The Need for (Long) Chains in Kidney Exchange. Technical Report.  I. Ashlagi D. Gamarnik M. A. Rees and A. E. Roth. 2012. The Need for (Long) Chains in Kidney Exchange. Technical Report.","DOI":"10.3386\/w18202"},{"volume-title":"Proceedings of the 12th ACM Conference on Electronic Commerce. 321--322","author":"Ashlagi I.","key":"e_1_3_2_1_3_1","unstructured":"I. Ashlagi and A. E. Roth . 2011. Individual Rationality and Participation in Large Scale, Multi-Hospital Kidney Exchange . In Proceedings of the 12th ACM Conference on Electronic Commerce. 321--322 . I. Ashlagi and A. E. Roth. 2011. Individual Rationality and Participation in Large Scale, Multi-Hospital Kidney Exchange. In Proceedings of the 12th ACM Conference on Electronic Commerce. 321--322."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1257\/aer.102.3.354"},{"volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. 434--443","author":"Babaioff M.","key":"e_1_3_2_1_5_1","unstructured":"M. Babaioff , N. Immorlica , and R. Kleinberg . 2007. Matroids, Secretary Problems, and Online Mechanisms . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. 434--443 . M. Babaioff, N. Immorlica, and R. Kleinberg. 2007. Matroids, Secretary Problems, and Online Mechanisms. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. 434--443."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1142\/S1793830909000373"},{"volume-title":"Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms. 2351--2363","author":"Blum A.","key":"e_1_3_2_1_7_1","unstructured":"A. Blum , I. Caragiannis , N. Haghtalab , A. D. Procaccia , E. B. Procaccia , and R. Vaish . 2017. Opting into Optimal Matchings . In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms. 2351--2363 . A. Blum, I. Caragiannis, N. Haghtalab, A. D. Procaccia, E. B. Procaccia, and R. Vaish. 2017. Opting into Optimal Matchings. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms. 2351--2363."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1034"},{"volume-title":"Proceedings of the 25th Conference on Neural Information Processing Systems. 2204--2212","author":"Chen Y.","key":"e_1_3_2_1_9_1","unstructured":"Y. Chen , S. Sanghavi , and H. Xu . 2012. Clustering Sparse Graphs . In Proceedings of the 25th Conference on Neural Information Processing Systems. 2204--2212 . Y. Chen, S. Sanghavi, and H. Xu. 2012. Clustering Sparse Graphs. In Proceedings of the 25th Conference on Neural Information Processing Systems. 2204--2212."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1111\/ajt.14343"},{"key":"e_1_3_2_1_11_1","volume-title":"Optimizing Kidney Exchange with Transplant Chains: Theory and Reality. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems","volume":"2","author":"Dickerson J. P.","unstructured":"J. P. Dickerson , A. D. Procaccia , and T. Sandholm . 2012 . Optimizing Kidney Exchange with Transplant Chains: Theory and Reality. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems , Vol. 2 . 711--718. J. P. Dickerson, A. D. Procaccia, and T. Sandholm. 2012. Optimizing Kidney Exchange with Transplant Chains: Theory and Reality. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, Vol. 2. 711--718."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/3207692.3207706"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9801-4"},{"volume-title":"Beyond the Worst -Case Analysis of Algorithms","author":"Feige U.","key":"e_1_3_2_1_14_1","unstructured":"U. Feige . 202 0 (in press). Introduction to Semi -Random Models . In Beyond the Worst -Case Analysis of Algorithms , T. Roughgarden (Ed.). Cambridge University Press . U. Feige. 2020 (in press). Introduction to Semi -Random Models. In Beyond the Worst -Case Analysis of Algorithms, T. Roughgarden (Ed.). Cambridge University Press."},{"volume-title":"Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science. 674--683","author":"Feige U.","key":"e_1_3_2_1_15_1","unstructured":"U. Feige and J. Kilian . 1998. Heuristics for Finding Large Independent Sets, with Applications to Coloring Semi-Random Graphs . In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science. 674--683 . U. Feige and J. Kilian. 1998. Heuristics for Finding Large Independent Sets, with Applications to Coloring Semi-Random Graphs. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science. 674--683."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1097\/TP.0b013e3182a01311"},{"volume-title":"Beyond the Worst -Case Analysis of Algorithms","author":"Gupta A.","key":"e_1_3_2_1_18_1","unstructured":"A. Gupta and S. Singla . 2020 (in press). Random-Order Models . In Beyond the Worst -Case Analysis of Algorithms , T. Roughgarden (Ed.). Cambridge University Press . A. Gupta and S. Singla. 2020 (in press). Random-Order Models. In Beyond the Worst -Case Analysis of Algorithms, T. Roughgarden (Ed.). Cambridge University Press."},{"volume-title":"Proceedings of the 29th AAAI Conference on Artificial Intelligence.","author":"Hajaj C.","key":"e_1_3_2_1_19_1","unstructured":"C. Hajaj , J. P. Dickerson , A. Hassidim , T. Sandholm , and D. Sarne . 2015. Strategy-Proof and Efficient Kidney Exchange Using a Credit Mechanism . In Proceedings of the 29th AAAI Conference on Artificial Intelligence. C. Hajaj, J. P. Dickerson, A. Hassidim, T. Sandholm, and D. Sarne. 2015. Strategy-Proof and Efficient Kidney Exchange Using a Credit Mechanism. In Proceedings of the 29th AAAI Conference on Artificial Intelligence."},{"volume-title":"Proceedings of the 43rd Annual ACM Symposium on Theory of Computing. 587--596","author":"Karande C.","key":"e_1_3_2_1_20_1","unstructured":"C. Karande , A. Mehta , and P. Tripathi . 2011. Online Bipartite Matching with Unknown Distributions . In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing. 587--596 . C. Karande, A. Mehta, and P. Tripathi. 2011. Online Bipartite Matching with Unknown Distributions. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing. 587--596."},{"key":"e_1_3_2_1_21_1","volume-title":"Proceedings of the 7th Annual ACM -SIAM Symposium on Discrete Algorithms. 359--364","author":"Kenyon C.","year":"1996","unstructured":"C. Kenyon . 1996 . Best-Fit Bin-Packing with Random Order . In Proceedings of the 7th Annual ACM -SIAM Symposium on Discrete Algorithms. 359--364 . C. Kenyon. 1996. Best-Fit Bin-Packing with Random Order. In Proceedings of the 7th Annual ACM -SIAM Symposium on Discrete Algorithms. 359--364."},{"volume-title":"Proceeding of the 52nd Annual IEEE Symposium on Foundations of Computer Science. 443--452","author":"Kolla A.","key":"e_1_3_2_1_22_1","unstructured":"A. Kolla , K. Makarychev , and Y. Makarychev . 2011. How to Play Unique Games against a Semi-Random Adversary: Study of Semi-Random Models of Unique Games . In Proceeding of the 52nd Annual IEEE Symposium on Foundations of Computer Science. 443--452 . A. Kolla, K. Makarychev, and Y. Makarychev. 2011. How to Play Unique Games against a Semi-Random Adversary: Study of Semi-Random Models of Unique Games. In Proceeding of the 52nd Annual IEEE Symposium on Foundations of Computer Science. 443--452."},{"volume-title":"Proceedings of the 44th Annual ACM Symposium on Theory of Computing. 367--384","author":"Makarychev K.","key":"e_1_3_2_1_23_1","unstructured":"K. Makarychev , Y. Makarychev , and A. Vijayaraghavan . 2012. Approximation Algorithms for Semi-Random Partitioning Problems . In Proceedings of the 44th Annual ACM Symposium on Theory of Computing. 367--384 . K. Makarychev, Y. Makarychev, and A. Vijayaraghavan. 2012. Approximation Algorithms for Semi-Random Partitioning Problems. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing. 367--384."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1681\/ASN.2018101030"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2015.01.001"}],"event":{"name":"EC '21: The 22nd ACM Conference on Economics and Computation","sponsor":["SIGecom Special Interest Group on Economics and Computation"],"location":"Budapest Hungary","acronym":"EC '21"},"container-title":["Proceedings of the 22nd ACM Conference on Economics and Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465456.3467622","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465456.3467622","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465456.3467622","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:28Z","timestamp":1750191448000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465456.3467622"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,18]]},"references-count":26,"alternative-id":["10.1145\/3465456.3467622","10.1145\/3465456"],"URL":"https:\/\/doi.org\/10.1145\/3465456.3467622","relation":{},"subject":[],"published":{"date-parts":[[2021,7,18]]},"assertion":[{"value":"2021-07-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}