Ignorance Is Almost Bliss: Near-Optimal Stochastic Matching with Few Queries

References

• Abraham DJ, Blum A, Sandholm T (2007) Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges. Proc. 8th ACM Conf. Electronic Commerce (EC) (ACM, New York), 295–304.Google Scholar
• Adamczyk M (2011) Improved analysis of the greedy algorithm for stochastic matching. Inform. Processing Lett. 111(15):731–737.Crossref, Google Scholar
• Akbarpour M, Li S, Gharan SO (2014) Dynamic matching market design. Proc. ACM Conf. Econom. Comput. (EC) (ACM, New York), 355.Google Scholar
• Anderson R, Ashlagi I, Gamarnik D, Kanoria Y (2015a) A dynamic model of barter exchange. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (ACM, New York), 1925–1933.Google Scholar
• Anderson R, Ashlagi I, Gamarnik D, Roth AE (2015b) Finding long chains in kidney exchange using the traveling salesman problem. Proc. Natl. Acad. Sci. USA 112(3):663–668.Crossref, Google Scholar
• Asadpour A, Nazerzadeh H, Saberi A (2008) Stochastic submodular maximization. Papadimitriou C, Zhang S, eds. Proc. 4th Internat. Workshop Internet Network Econom. (WINE) (Springer, Berlin, Heidelberg), 477–489.Google Scholar
• Ashlagi I, Roth A (2014) Free riding and participation in large scale, multi-hospital kidney exchange. Theoretical Econom. 9(2014): 817–863.Google Scholar
• Ashlagi I, Jaillet P, Manshadi VH (2013) Kidney exchange in dynamic sparse heterogenous pools. Proc. 14th ACM Conf. Electronic Commerce (EC) (ACM, New York), 25–26.Google Scholar
• Ashlagi I, Gamarnik D, Rees MA, Roth AE (2011a) The need for (long) chains in kidney exchange. NBER Working Paper No. w18202, National Bureau of Economic Research, Cambridge, MA.Google Scholar
• Ashlagi I, Gilchrist DS, Roth AE, Rees M (2011b) Nonsimultaneous chains and dominos in kidney-paired donation—Revisited. Amer. J. Transplantation 11(5):984–994.Crossref, Google Scholar
• Assadi S, Khanna S, Li Y (2016) The stochastic matching problem with (very) few queries. Proc. 17th ACM Conf. Electronic Commerce (EC) (ACM, New York), 43–60.Google Scholar
• Awasthi P, Sandholm T (2009) Online stochastic optimization in the large: Application to kidney exchange. Proc. 21st Internat. Joint Conf. Artificial Intelligence (IJCAI) (Morgan Kaufmann Publishers Inc., San Francisco), 405–411.Google Scholar
• Bansal N, Gupta A, Li J, Mestre J, Nagarajan V, Rudra A (2012) When LP is the cure for your matching woes: Improved bounds for stochastic matchings. Algorithmica 63(4):733–762.Crossref, Google Scholar
• Blum A, Gupta A, Procaccia AD, Sharma A (2013) Harnessing the power of two crossmatches. Proc. 14th ACM Conf. Electronic Commerce (EC) (ACM, New York), 123–140.Google Scholar
• Blum A, Dickerson JP, Haghtalab N, Procaccia AD, Sandholm T, Sharma A (2015) Ignorance is almost bliss: Near-optimal stochastic matching with few queries. Proc. 16th ACM Conf. Electronic Commerce (EC) (ACM, New York), 325–342.Google Scholar
• Bollobás, B (2001) Random Graphs, 2nd ed. (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Chen N, Immorlica N, Karlin AR, Mahdian M, Rudra A (2009) Approximating matches made in heaven. Albers S, Marchetti-Spaccamela A, Matias Y, Nikoletseas S, Thomas W, eds. Proc. 36th Internat. Colloquium Automata, Languages Programming (ICALP) (Springer, Berlin, Heidelberg), 266–278.Google Scholar
• Constantino M, Klimentova X, Viana A, Rais A (2013a) New insights on integer-programming models for the kidney exchange problem. Eur. J. Oper. Res. 231(1):57–68.Crossref, Google Scholar
• Costello KP, Tetali P, Tripathi P (2012) Matching with commitment. Czumaj A, Mehlhorn K, Pitts A, Wattenhofer R, eds. Proc. 39th Internat. Colloquium Automata, Languages Programming (ICALP) (Springer, Berlin, Heidelberg), 822–833.Google Scholar
• Dean BC, Goemans MX, Vondrak J (2004) Approximating the stochastic knapsack problem: The benefit of adaptivity. Math. Oper. Res. 33(4):945–964.Google Scholar
• Dickerson JP, Sandholm T (2015) FutureMatch: Combining human value judgments and machine learning to match in dynamic environments. Proc. 29th AAAI Conf. Artificial Intelligence (AAAI), Austin, TX, 622–628.Google Scholar
• Dickerson JP, Procaccia AD, Sandholm T (2012a) Dynamic matching via weighted myopia with application to kidney exchange. Proc. 26th AAAI Conf. Artificial Intelligence (AAAI), Toronto, Canada, 1340–1346.Google Scholar
• Dickerson JP, Procaccia AD, Sandholm T (2012b) Optimizing kidney exchange with transplant chains: Theory and reality. Proc. 11th Internat. Conf. Autonomous Agents Multi-Agent Systems (AAMAS) (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 711–718.Google Scholar
• Dickerson JP, Procaccia AD, Sandholm T (2019) Failure-aware kidney exchange. Management Sci. 65(4):1768–1791.Link, Google Scholar
• Dickerson JP, Manlove DF, Plaut B, Sandholm T, Trimble J (2016) Position-indexed formulations for kidney exchange. Proc. 17th ACM Conf. Electronic Commerce (EC) (ACM, New York), 25–42.Google Scholar
• Ding Y, Ge D, He S, Ryan C (2015) A non-asymptotic approach to analyzing kidney exchange graphs. Proc. 16th ACM Conf. Electronic Commerce (EC) (ACM, New York), 257–258.Google Scholar
• Fürer M, Yu H (2014) Approximate the k-set packing problem by local improvements. Fouilhoux P, Gouveia L, Mahjoub A, Paschos V, eds. Combinatorial Optimization (ISCO 2014), Lecture Notes in Computer Science, vol. 8596 (Springer, Cham, Switzerland).Google Scholar
• Glorie KM, van de Klundert JJ, Wagelmans APM (2014) Kidney exchange with long chains: An efficient pricing algorithm for clearing barter exchanges with branch-and-price. Manufacturing Service Oper. Management 16(4):498–512.Link, Google Scholar
• Goel G, Tripathi P (2012) Matching with our eyes closed. Proc. 53rd Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 718–727.Google Scholar
• Gupta A, Nagarajan V (2013) A stochastic probing problem with applications. Goemans M, Correa J, eds. Proc. 16th Conf. Integer Programming Combinatorial Optim. (IPCO) (Springer, Berlin, Heidelberg), 205–216.Google Scholar
• Gupta A, Krishnaswamy R, Nagarajan V, Ravi R (2012) Approximation algorithms for stochastic orienteering. Proc. 23rd Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 1522–1538.Google Scholar
• Hurkens CAJ, Schrijver A (1989) On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Discrete Math. 2(1):68–72.Crossref, Google Scholar
• Leishman R, Formica R, Andreoni K, Friedewald J, Sleeman E, Monstello C, Stewart D, Sandholm T (2013) The Organ Procurement and Transplantation Network (OPTN) Kidney Paired Donation Pilot Program (KPDPP): Review of current results. American Transplant Congress (ATC), talk abstract.Google Scholar
• Manlove D, O’Malley G (2015) Paired and altruistic kidney donation in the UK: Algorithms and experimentation. ACM J. Experiment. Algorithmics 19:2–6.Google Scholar
• Molinaro M, Ravi R (2011) The query-commit problem. Working paper, University of California, Berkeley, Berkeley.Google Scholar
• Roth AE, Sönmez T, Ünver MU (2004) Kidney exchange. Quart. J. Econom. 119(2):457–488.Crossref, Google Scholar
• Roth AE, Sönmez T, Ünver MU (2005) Pairwise kidney exchange. J. Econom. Theory 125(2):151–188.Crossref, Google Scholar
• Roth AE, Sönmez T, Ünver MU (2007) Efficient kidney exchange: Coincidence of wants in markets with compatibility-based preferences. Amer. Econom. Rev. 97(3):828–851.Crossref, Google Scholar
• Saidman SL, Roth AE, Sönmez T, Ünver MU, Delmonico FL (2006) Increasing the opportunity of live kidney donation by matching for two and three way exchanges. Transplantation 81(5):773–782.Crossref, Google Scholar
• Ünver MU (2010) Dynamic kidney exchange. Rev. Econom. Stud. 77(1):372–414.Crossref, Google Scholar
• U.S. Department of Health and Human Services (2018) Organ procurement and transplantation network. Accessed June 10, 2018, http://optn.transplant.hrsa.gov.Google Scholar