A dynamic model of barter exchange
We consider the problem of efficient operation of a barter exchange platform for indivisible goods. We introduce a dynamic model of barter exchange where in each period one agent arrives with a single item she wants to exchange for a different item. We study a homogeneous and stochastic environment:...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics (SIAM)
2017
|
| Online Access: | http://hdl.handle.net/1721.1/109184 https://orcid.org/0000-0003-2124-738X https://orcid.org/0000-0001-8898-8778 |
| _version_ | 1826208515371302912 |
|---|---|
| author | Kanoria, Yash Anderson, Ross Michael Ashlagi, Itai Gamarnik, David |
| author2 | Massachusetts Institute of Technology. Operations Research Center |
| author_facet | Massachusetts Institute of Technology. Operations Research Center Kanoria, Yash Anderson, Ross Michael Ashlagi, Itai Gamarnik, David |
| author_sort | Kanoria, Yash |
| collection | MIT |
| description | We consider the problem of efficient operation of a barter exchange platform for indivisible goods. We introduce a dynamic model of barter exchange where in each period one agent arrives with a single item she wants to exchange for a different item. We study a homogeneous and stochastic environment: an agent is interested in the item possessed by another agent with probability p, independently for all pairs of agents. We consider two settings with respect to the types of allowed exchanges: a) Only two-way cycles, in which two agents swap their items, b) Two or three-way cycles. The goal of the platform is to minimize the average waiting time of an agent.
Somewhat surprisingly, we find that in each of these settings, a policy that conducts exchanges in a greedy fashion is near optimal, among a large class of policies that includes batching policies. Further, we find that for small p, allowing three-cycles can greatly improve the waiting time over the two-cycles only setting. Specifically, we find that a greedy policy achieves an average waiting time of Θ(1/p2) in setting a), and Θ(1/p3/2) in setting b). Thus, a platform can achieve the smallest waiting times by using a greedy policy, and by facilitating three cycles, if possible.
Our findings are consistent with empirical and computational observations which compare batching policies in the context of kidney exchange programs. |
| first_indexed | 2024-09-23T14:06:34Z |
| format | Article |
| id | mit-1721.1/109184 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:06:34Z |
| publishDate | 2017 |
| publisher | Society for Industrial and Applied Mathematics (SIAM) |
| record_format | dspace |
| spelling | mit-1721.1/1091842022-10-01T19:16:55Z A dynamic model of barter exchange Kanoria, Yash Anderson, Ross Michael Ashlagi, Itai Gamarnik, David Massachusetts Institute of Technology. Operations Research Center Sloan School of Management Anderson, Ross Michael Ashlagi, Itai Gamarnik, David We consider the problem of efficient operation of a barter exchange platform for indivisible goods. We introduce a dynamic model of barter exchange where in each period one agent arrives with a single item she wants to exchange for a different item. We study a homogeneous and stochastic environment: an agent is interested in the item possessed by another agent with probability p, independently for all pairs of agents. We consider two settings with respect to the types of allowed exchanges: a) Only two-way cycles, in which two agents swap their items, b) Two or three-way cycles. The goal of the platform is to minimize the average waiting time of an agent. Somewhat surprisingly, we find that in each of these settings, a policy that conducts exchanges in a greedy fashion is near optimal, among a large class of policies that includes batching policies. Further, we find that for small p, allowing three-cycles can greatly improve the waiting time over the two-cycles only setting. Specifically, we find that a greedy policy achieves an average waiting time of Θ(1/p2) in setting a), and Θ(1/p3/2) in setting b). Thus, a platform can achieve the smallest waiting times by using a greedy policy, and by facilitating three cycles, if possible. Our findings are consistent with empirical and computational observations which compare batching policies in the context of kidney exchange programs. 2017-05-18T20:36:05Z 2017-05-18T20:36:05Z 2015 2015-01 Article http://purl.org/eprint/type/ConferencePaper 978-1-61197-374-7 978-1-61197-373-0 http://hdl.handle.net/1721.1/109184 Anderson, Ross; Ashlagi, Itai; Gamarnik, David and Kanoria, Yash. “A Dynamic Model of Barter Exchange.” Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (2015): 1925–1933. © 2015 Society for Industrial and Applied Mathematics (SIAM) https://orcid.org/0000-0003-2124-738X https://orcid.org/0000-0001-8898-8778 en_US http://dx.doi.org/10.1137/1.9781611973730.129 Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics (SIAM) SIAM |
| spellingShingle | Kanoria, Yash Anderson, Ross Michael Ashlagi, Itai Gamarnik, David A dynamic model of barter exchange |
| title | A dynamic model of barter exchange |
| title_full | A dynamic model of barter exchange |
| title_fullStr | A dynamic model of barter exchange |
| title_full_unstemmed | A dynamic model of barter exchange |
| title_short | A dynamic model of barter exchange |
| title_sort | dynamic model of barter exchange |
| url | http://hdl.handle.net/1721.1/109184 https://orcid.org/0000-0003-2124-738X https://orcid.org/0000-0001-8898-8778 |
| work_keys_str_mv | AT kanoriayash adynamicmodelofbarterexchange AT andersonrossmichael adynamicmodelofbarterexchange AT ashlagiitai adynamicmodelofbarterexchange AT gamarnikdavid adynamicmodelofbarterexchange AT kanoriayash dynamicmodelofbarterexchange AT andersonrossmichael dynamicmodelofbarterexchange AT ashlagiitai dynamicmodelofbarterexchange AT gamarnikdavid dynamicmodelofbarterexchange |