Abstract
We study a dynamic non-bipartite matching problem. There is a fixed set of agent types, and agents of a given type arrive and depart according to type-specific Poisson processes. The value of a match is determined by the types of the matched agents. We present an online algorithm that is (1/8)-competitive with respect to the value of the optimal-in-hindsight policy, for arbitrary weighted graphs. This is the first result to achieve a constant competitive ratio when both arrivals and departures are random and unannounced. Our algorithm treats agents heterogeneously, interpolating between immediate and delayed matching in order to thicken the market while still matching valuable agents opportunistically.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We discuss Poisson processes more formally in Sect. 2.1.
- 2.
Note for an online policy, \(\tau (T)\subseteq \tau (T')\) whenever \(T\le T'\); however this need not hold for a policy with hindsight.
- 3.
Taking the limit as the time horizon grows allows us to ignore lower-order terms.
- 4.
Recall that if Z and \(Z'\) are two (random) point processes, then Z stochastically dominates \(Z'\) if there is a coupling of Z and \(Z'\) such that \(\Pr [ Z' \subseteq Z ] = 1\).
- 5.
Recall by the definition of available, such an agent is also present.
References
Akbarpour, M., Li, S., Gharan, S.O.: Thickness and information in dynamic matching markets. J. Polit. Econ. 128(3), 783–815 (2020)
Alaei, S., Hajiaghayi, M., Liaghat, V.: Online prophet-inequality matching with applications to Ad allocation. In: Proceedings of the 13th ACM Conference on Electronic Commerce, EC 2012, pp. 18–35. Association for Computing Machinery, New York (2012). https://doi.org/10.1145/2229012.2229018
Anderson, R., Ashlagi, I., Gamarnik, D., Kanoria, Y.: Efficient dynamic barter exchange. Oper. Res. 65(6), 1446–1459 (2017). https://doi.org/10.1287/opre.2017.1644
Aouad, A., Saritaç, O.: Dynamic stochastic matching under limited time. In: Proceedings of the 21st ACM Conference on Economics and Computation, EC 2020, pp. 789–790. Association for Computing Machinery, New York (2020). https://doi.org/10.1145/3391403.3399524
Ashlagi, I., Burq, M., Dutta, C., Jaillet, P., Saberi, A., Sholley, C.: Edge weighted online windowed matching. In: Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, pp. 729–742. ACM, New York (2019). https://doi.org/10.1145/3328526.3329573
Ashlagi, I., Burq, M., Jaillet, P., Manshadi, V.: On matching and thickness in heterogeneous dynamic markets. Oper. Res. 67(4), 927–949 (2019)
Baccara, M., Lee, S., Yariv, L.: Optimal dynamic matching. CEPR Discussion Paper No. DP12986 (2018)
Dickerson, J.P., Sankararaman, K.A., Srinivasan, A., Xu, P.: Assigning tasks to workers based on historical data: online task assignment with two-sided arrivals. In: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pp. 318–326. International Foundation for Autonomous Agents and Multiagent Systems (2018)
Feldman, J., Mehta, A., Mirrokni, V., Muthukrishnan, S.: Online stochastic matching: Beating 1–1/e. In: 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 117–126. IEEE (2009)
Gravin, N., Wang, H.: Prophet inequality for bipartite matching: merits of being simple and non adaptive. In: Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, pp. 93–109. Association for Computing Machinery, New York (2019). https://doi.org/10.1145/3328526.3329604
Haeupler, B., Mirrokni, V.S., Zadimoghaddam, M.: Online stochastic weighted matching: improved approximation algorithms. In: Chen, N., Elkind, E., Koutsoupias, E. (eds.) WINE 2011. LNCS, vol. 7090, pp. 170–181. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25510-6_15
Huang, Z., Kang, N., Tang, Z.G., Wu, X., Zhang, Y., Zhu, X.: How to match when all vertices arrive online. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 17–29 (2018)
Huang, Z., Peng, B., Tang, Z.G., Tao, R., Wu, X., Zhang, Y.: Tight competitive ratios of classic matching algorithms in the fully online model. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2875–2886. SIAM (2019)
Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (1990)
Mahdian, M., Yan, Q.: Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC 2011, pp. 597–606. ACM, New York (2011). https://doi.org/10.1145/1993636.1993716
Mehta, A., Panigrahi, D.: Online matching with stochastic rewards. In: Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, FOCS 2012, pp. 728–737. IEEE Computer Society, Washington (2012). https://doi.org/10.1109/FOCS.2012.65
Mehta, A., Saberi, A., Vazirani, U.V., Vazirani, V.V.: Adwords and generalized on-line matching. In: 46th Annual IEEE Symposium on Foundations of Computer Science (2005)
Mehta, A., Waggoner, B., Zadimoghaddam, M.: Online stochastic matching with unequal probabilities. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, pp. 1388–1404. Society for Industrial and Applied Mathematics, Philadelphia (2015). http://dl.acm.org/citation.cfm?id=2722129.2722221
Truong, V.A., Wang, X.: Prophet inequality with correlated arrival probabilities, with application to two sided matchings (2019)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Collina, N., Immorlica, N., Leyton-Brown, K., Lucier, B., Newman, N. (2020). Dynamic Weighted Matching with Heterogeneous Arrival and Departure Rates. In: Chen, X., Gravin, N., Hoefer, M., Mehta, R. (eds) Web and Internet Economics. WINE 2020. Lecture Notes in Computer Science(), vol 12495. Springer, Cham. https://doi.org/10.1007/978-3-030-64946-3_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-64946-3_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-64945-6
Online ISBN: 978-3-030-64946-3
eBook Packages: Computer ScienceComputer Science (R0)