IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v65y2017i6p1446-1459.html
   My bibliography  Save this article

Efficient Dynamic Barter Exchange

Author

Listed:
  • Ross Anderson

    (Google, Mountain View, California 94043)

  • Itai Ashlagi

    (Management Science and Engineering, Stanford University, Stanford, California 94305)

  • David Gamarnik

    (Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

  • Yash Kanoria

    (Decision, Risk and Operations Division, Columbia Business School, New York, New York 10027)

Abstract

We study dynamic matching policies in a stochastic marketplace for barter, with agents arriving over time. Each agent is endowed with an item and is interested in an item possessed by another agent homogeneously with probability p , independently for all pairs of agents. Three settings are considered with respect to the types of allowed exchanges: (a) only two-way cycles, in which two agents swap items, (b) two-way or three-way cycles, (c) (unbounded) chains initiated by an agent who provides an item but expects nothing in return. We consider the average waiting time as a measure of efficiency and find that the cost outweighs the benefit from waiting to thicken the market. In particular, in each of the above settings, a policy that conducts exchanges in a greedy fashion is near optimal. Further, for small p , we find that allowing three-way cycles greatly reduces the waiting time over just two-way cycles, and conducting exchanges through a chain further reduces the waiting time significantly. Thus, a centralized planner can achieve the smallest waiting times by using a greedy policy, and by facilitating three-way cycles and chains, if possible.

Suggested Citation

  • Ross Anderson & Itai Ashlagi & David Gamarnik & Yash Kanoria, 2017. "Efficient Dynamic Barter Exchange," Operations Research, INFORMS, vol. 65(6), pages 1446-1459, December.
    • Handle: RePEc:inm:oropre:v:65:y:2017:i:6:p:1446-1459
    DOI: 10.1287/opre.2017.1644
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/opre.2017.1644
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2017.1644?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Ivo Adan & Gideon Weiss, 2012. "Exact FCFS Matching Rates for Two Infinite Multitype Sequences," Operations Research, INFORMS, vol. 60(2), pages 475-489, April.
    2. , & , E., 2014. "Free riding and participation in large scale, multi-hospital kidney exchange," Theoretical Economics, Econometric Society, vol. 9(3), September.
    3. Itai Ashlagi & David Gamarnik & Michael A. Rees & Alvin E. Roth, 2012. "The Need for (long) Chains in Kidney Exchange," NBER Working Papers 18202, National Bureau of Economic Research, Inc.
    4. Yu Wang & Aradhna Krishna, 2006. "Timeshare Exchange Mechanisms," Management Science, INFORMS, vol. 52(8), pages 1223-1237, August.
    5. Pycia, Marek & Unver, Utku, 2017. "Incentive compatible allocation and exchange of discrete resources," Theoretical Economics, Econometric Society, vol. 12(1), January.
    6. Roth, Alvin E. & Sonmez, Tayfun & Utku Unver, M., 2005. "Pairwise kidney exchange," Journal of Economic Theory, Elsevier, vol. 125(2), pages 151-188, December.
    7. Shapley, Lloyd & Scarf, Herbert, 1974. "On cores and indivisibility," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 23-37, March.
    8. Eric Budish & Peter Cramton & John Shim, 2015. "Editor's Choice The High-Frequency Trading Arms Race: Frequent Batch Auctions as a Market Design Response," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 130(4), pages 1547-1621.
    9. Roth, Alvin E., 1982. "Incentive compatibility in a market with indivisible goods," Economics Letters, Elsevier, vol. 9(2), pages 127-132.
    10. Roth, Alvin E. & Postlewaite, Andrew, 1977. "Weak versus strong domination in a market with indivisible goods," Journal of Mathematical Economics, Elsevier, vol. 4(2), pages 131-137, August.
    11. Mendelson, Haim, 1982. "Market Behavior in a Clearing House," Econometrica, Econometric Society, vol. 50(6), pages 1505-1524, November.
    12. Vahideh H. Manshadi & Shayan Oveis Gharan & Amin Saberi, 2012. "Online Stochastic Matching: Online Actions Based on Offline Statistics," Mathematics of Operations Research, INFORMS, vol. 37(4), pages 559-573, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Julien Combe & Vladyslav Nora & Olivier Tercieux, 2021. "Dynamic assignment without money: Optimality of spot mechanisms," Working Papers 2021-11, Center for Research in Economics and Statistics.
    2. Ali Aouad & Daniela Saban, 2023. "Online Assortment Optimization for Two-Sided Matching Platforms," Management Science, INFORMS, vol. 69(4), pages 2069-2087, April.
    3. Mohammad Akbarpour & Julien Combe & Yinghua He & Victor Hiller & Robert Shimer & Olivier Tercieux, 2020. "Unpaired Kidney Exchange: Overcoming Double Coincidence of Wants without Money," Post-Print halshs-02973042, HAL.
    4. Sönmez, Tayfun & Ünver, M. Utku & Yılmaz, Özgür, 2018. "How (not) to integrate blood subtyping technology to kidney exchange," Journal of Economic Theory, Elsevier, vol. 176(C), pages 193-231.
    5. Itai Ashlagi & Afshin Nikzad & Philipp Strack, 2018. "Matching in Dynamic Imbalanced Markets," Papers 1809.06824, arXiv.org, revised Jun 2019.
    6. Combe, Julien & Nora, Vladyslav & Tercieux, Olivier, 2025. "Dynamic assignment without money: optimality of spot mechanisms," Theoretical Economics, Econometric Society, vol. 20(1), January.
    7. Itai Ashlagi & Alvin E. Roth, 2021. "Kidney Exchange: An Operations Perspective," Management Science, INFORMS, vol. 67(9), pages 5455-5478, September.
    8. Yangyang Huang & Zhenyang Pi & Weiguo Fang, 2021. "Trade Credit with Barter in a Capital-Constrained Supply Chain," Sustainability, MDPI, vol. 13(20), pages 1-15, October.
    9. Tiago Monteiro & Xenia Klimentova & João Pedro Pedroso & Ana Viana, 2021. "A comparison of matching algorithms for kidney exchange programs addressing waiting time," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 29(2), pages 539-552, June.
    10. Itai Feigenbaum & Yash Kanoria & Irene Lo & Jay Sethuraman, 2020. "Dynamic Matching in School Choice: Efficient Seat Reassignment After Late Cancellations," Management Science, INFORMS, vol. 66(11), pages 5341-5361, November.
    11. Süleyman Kerimov & Itai Ashlagi & Itai Gurvich, 2024. "Dynamic Matching: Characterizing and Achieving Constant Regret," Management Science, INFORMS, vol. 70(5), pages 2799-2822, May.
    12. Hua, Guowei & Zhang, Yi & Cheng, T.C.E. & Wang, Shouyang & Zhang, Juliang, 2020. "The newsvendor problem with barter exchange," Omega, Elsevier, vol. 92(C).
    13. Itai Ashlagi & Maximilien Burq & Patrick Jaillet & Vahideh Manshadi, 2019. "On Matching and Thickness in Heterogeneous Dynamic Markets," Operations Research, INFORMS, vol. 67(4), pages 927-949, July.
    14. Loertscher, Simon & Muir, Ellen V. & Taylor, Peter G., 2022. "Optimal market thickness," Journal of Economic Theory, Elsevier, vol. 200(C).
    15. Nick Arnosti & Ramesh Johari & Yash Kanoria, 2021. "Managing Congestion in Matching Markets," Manufacturing & Service Operations Management, INFORMS, vol. 23(3), pages 620-636, May.
    16. Yifei Yu & Marc van den Berg & Devrim Murat Yazan, 2024. "Circular (de)construction matchmaking: A matter of space and time," Journal of Industrial Ecology, Yale University, vol. 28(4), pages 868-884, August.
    17. Irene Lo & Vahideh Manshadi & Scott Rodilitz & Ali Shameli, 2020. "Commitment on Volunteer Crowdsourcing Platforms: Implications for Growth and Engagement," Papers 2005.10731, arXiv.org, revised Jul 2021.
    18. Vahideh Manshadi & Sidhant Misra & Scott Rodilitz, 2020. "Diffusion in Random Networks: Impact of Degree Distribution," Operations Research, INFORMS, vol. 68(6), pages 1722-1741, November.
    19. Naonori Kakimura & Donghao Zhu, 2021. "Dynamic Bipartite Matching Market with Arrivals and Departures," Papers 2110.10824, arXiv.org.
    20. Kim, Jaehong & Li, Mengling & Xu, Menghan, 2021. "Organ donation with vouchers," Journal of Economic Theory, Elsevier, vol. 191(C).
    21. Milena Bieniek, 2021. "Bartering: Price-Setting Newsvendor Problem with Barter Exchange," Sustainability, MDPI, vol. 13(12), pages 1-22, June.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Nikhil Agarwal & Eric Budish, 2021. "Market Design," NBER Working Papers 29367, National Bureau of Economic Research, Inc.
    2. Morrill, Thayer & Roth, Alvin E., 2024. "Top trading cycles," Journal of Mathematical Economics, Elsevier, vol. 112(C).
    3. Anno, Hidekazu, 2015. "A short proof for the characterization of the core in housing markets," Economics Letters, Elsevier, vol. 126(C), pages 66-67.
    4. Alcalde-Unzu, Jorge & Molis, Elena, 2011. "Exchange of indivisible goods and indifferences: The Top Trading Absorbing Sets mechanisms," Games and Economic Behavior, Elsevier, vol. 73(1), pages 1-16, September.
    5. Zhiwei Cui & Yan-An Hwang, 2017. "House exchange and residential segregation in networks," International Journal of Game Theory, Springer;Game Theory Society, vol. 46(1), pages 125-147, March.
    6. Ivan Balbuzanov & Maciej H. Kotowski, 2019. "Endowments, Exclusion, and Exchange," Econometrica, Econometric Society, vol. 87(5), pages 1663-1692, September.
    7. Roth, Alvin E. & Sonmez, Tayfun & Utku Unver, M., 2005. "Pairwise kidney exchange," Journal of Economic Theory, Elsevier, vol. 125(2), pages 151-188, December.
    8. Yu, Jingsheng & Zhang, Jun, 2022. "Cores and mechanisms in restricted housing markets," Journal of Mathematical Economics, Elsevier, vol. 100(C).
    9. Ekici, Özgün, 2024. "Pair-efficient reallocation of indivisible objects," Theoretical Economics, Econometric Society, vol. 19(2), May.
    10. YIlmaz, Özgür, 2010. "The probabilistic serial mechanism with private endowments," Games and Economic Behavior, Elsevier, vol. 69(2), pages 475-491, July.
    11. Karakaya, Mehmet & Klaus, Bettina & Schlegel, Jan Christoph, 2019. "Top trading cycles, consistency, and acyclic priorities for house allocation with existing tenants," Journal of Economic Theory, Elsevier, vol. 184(C).
    12. Hidekazu Anno & Sui Takahashi, 2023. "A unified approach to strategy-proofness of the deferred-acceptance rule and the top-trading cycles rule," Review of Economic Design, Springer;Society for Economic Design, vol. 27(1), pages 133-137, February.
    13. Itai Ashlagi & Maximilien Burq & Patrick Jaillet & Vahideh Manshadi, 2019. "On Matching and Thickness in Heterogeneous Dynamic Markets," Operations Research, INFORMS, vol. 67(4), pages 927-949, July.
    14. Nicolò, Antonio & Rodríguez-Álvarez, Carmelo, 2017. "Age-based preferences in paired kidney exchange," Games and Economic Behavior, Elsevier, vol. 102(C), pages 508-524.
    15. Ekici, Özgün & Sethuraman, Jay, 2024. "Characterizing the TTC rule via pair-efficiency: A short proof," Economics Letters, Elsevier, vol. 234(C).
    16. Jaramillo, Paula & Manjunath, Vikram, 2012. "The difference indifference makes in strategy-proof allocation of objects," Journal of Economic Theory, Elsevier, vol. 147(5), pages 1913-1946.
    17. Atila Abdulkadiroglu & Parag A. Pathak & Alvin E. Roth & Tayfun Sönmez, 2006. "Changing the Boston School Choice Mechanism," Levine's Bibliography 122247000000001022, UCLA Department of Economics.
    18. , & , E., 2014. "Free riding and participation in large scale, multi-hospital kidney exchange," Theoretical Economics, Econometric Society, vol. 9(3), September.
    19. Tayfun Sönmez & M. Utku Ünver, 2006. "Kidney Exchange with Good Samaritan Donors: A Characterization," Boston College Working Papers in Economics 640, Boston College Department of Economics.
    20. Committee, Nobel Prize, 2012. "Alvin E. Roth and Lloyd S. Shapley: Stable allocations and the practice of market design," Nobel Prize in Economics documents 2012-1, Nobel Prize Committee.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:65:y:2017:i:6:p:1446-1459. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.