{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,25]],"date-time":"2026-06-25T12:19:06Z","timestamp":1782389946645,"version":"3.54.5"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2024,8,3]],"date-time":"2024-08-03T00:00:00Z","timestamp":1722643200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,8,3]],"date-time":"2024-08-03T00:00:00Z","timestamp":1722643200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100015866","name":"Hezkuntza, Hizkuntza Politika Eta Kultura Saila, Eusko Jaurlaritza","doi-asserted-by":"publisher","award":["IT1456-22"],"award-info":[{"award-number":["IT1456-22"]}],"id":[{"id":"10.13039\/100015866","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["777778"],"award-info":[{"award-number":["777778"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003451","name":"Universidad del Pa\u00eds Vasco","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003451","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Queueing Syst"],"published-print":{"date-parts":[[2024,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the stochastic matching model on a non-bipartite compatibility graph and analyze the impact of adding an edge to the expected number of items in the system. One may see adding an edge as increasing the flexibility of the system, for example, asking a family registering for social housing to list fewer requirements in order to be compatible with more housing units. Therefore, it may be natural to think that adding edges to the compatibility graph will lead to a decrease in the expected number of items in the system and the waiting time to be assigned. In our previous work, we proved this is not always true for the First Come First Matched discipline and provided sufficient conditions for the existence of the performance paradox: despite a new edge in the compatibility graph, the expected total number of items can increase. These sufficient conditions are related to the heavy-traffic assumptions in queueing systems. The intuition behind this is that the performance paradox occurs when the added edge in the compatibility graph disrupts the draining of a bottleneck. In this paper, we generalize this performance paradox result to a family of so-called greedy matching policies and explore the type of compatibility graphs where such a paradox occurs. Intuitively, a greedy matching policy never leaves compatible items unassigned, so the state space of the system consists of finite words of item classes that belong to an independent set of the compatibility graph. Some examples of greedy matching policies are First Come First Match, Match the Longest, Match the Shortest, Random, Priority. We prove several results about the existence of performance paradoxes for greedy disciplines for some family of graphs. More precisely, we prove several results about the lifting of the paradox from one graph to another one. For a certain family of graphs, we prove that there exists a paradox for the whole family of greedy policies. Most of these results are based on strong aggregation of Markov chains and graph theoretical properties.\n<\/jats:p>","DOI":"10.1007\/s11134-024-09924-z","type":"journal-article","created":{"date-parts":[[2024,8,3]],"date-time":"2024-08-03T11:01:57Z","timestamp":1722682917000},"page":"257-293","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Performance paradox of dynamic matching models under greedy policies"],"prefix":"10.1007","volume":"107","author":[{"given":"Bu\u0161i\u0107","family":"Ana","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cadas","family":"Arnaud","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5552-9134","authenticated-orcid":false,"given":"Doncel","family":"Josu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fourneau","family":"Jean-Michel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,8,3]]},"reference":[{"issue":"1","key":"9924_CR1","first-page":"258","volume":"12","author":"D Braess","year":"1968","unstructured":"Braess, D.: \u00dcber ein paradoxon aus der verkehrsplanung. Unternehmensforschung 12(1), 258\u2013268 (1968)","journal-title":"Unternehmensforschung"},{"issue":"1","key":"9924_CR2","doi-asserted-by":"publisher","first-page":"155","DOI":"10.2307\/3215183","volume":"34","author":"NG Bean","year":"1997","unstructured":"Bean, N.G., Kelly, F.P., Taylor, P.G.: Braess\u2019s paradox in a loss network. J. Appl. Probab. 34(1), 155\u2013159 (1997)","journal-title":"J. Appl. Probab."},{"issue":"1","key":"9924_CR3","doi-asserted-by":"publisher","first-page":"134","DOI":"10.2307\/3215182","volume":"34","author":"B Calvert","year":"1997","unstructured":"Calvert, B., Solomon, W., Ziedins, I.: Braess\u2019s paradox in a queueing network with state-dependent routing. J. Appl. Probab. 34(1), 134\u2013154 (1997). https:\/\/doi.org\/10.2307\/3215182","journal-title":"J. Appl. Probab."},{"issue":"2","key":"9924_CR4","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1109\/90.588114","volume":"5","author":"JE Cohen","year":"1997","unstructured":"Cohen, J.E., Jeffries, C.: Congestion resulting from increased capacity in single-server queueing networks. IEEE\/ACM Trans. Netw. 5(2), 305\u2013310 (1997)","journal-title":"IEEE\/ACM Trans. Netw."},{"issue":"3","key":"9924_CR5","doi-asserted-by":"publisher","first-page":"730","DOI":"10.2307\/3214558","volume":"27","author":"JE Cohen","year":"1990","unstructured":"Cohen, J.E., Kelly, F.P.: A paradox of congestion in a queuing network. J. Appl. Probab. 27(3), 730\u2013734 (1990)","journal-title":"J. Appl. Probab."},{"key":"9924_CR6","doi-asserted-by":"crossref","unstructured":"Kameda, H.: How harmful the paradox can be in the Braess\/Cohen-Kelly-Jeffries networks. In: Proceedings. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 1, pp. 437\u2013445 (2002). IEEE","DOI":"10.1109\/INFCOM.2002.1019286"},{"issue":"3","key":"9924_CR7","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1145\/3529113.3529126","volume":"49","author":"A Cadas","year":"2022","unstructured":"Cadas, A., Doncel, J., Fourneau, J.-M., Busic, A.: Flexibility can hurt dynamic matching system performance. ACM SIGMETRICS Perform. Eval. Rev. 49(3), 37\u201342 (2022)","journal-title":"ACM SIGMETRICS Perform. Eval. Rev."},{"issue":"2","key":"9924_CR8","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1145\/2825236.2825265","volume":"43","author":"A Busic","year":"2015","unstructured":"Busic, A., Meyn, S.: Approximate optimality with bounded regret in dynamic matching models. SIGMETRICS Perform. Eval. Rev. 43(2), 75\u201377 (2015)","journal-title":"SIGMETRICS Perform. Eval. Rev."},{"key":"9924_CR9","doi-asserted-by":"publisher","unstructured":"Cadas, A., Busic, A., Doncel, J.: Optimal control of dynamic bipartite matching models. In: Proceedings of the 12th EAI International Conference on Performance Evaluation Methodologies and Tools. VALUETOOLS 2019, pp. 39\u201346. Association for Computing Machinery, New York, NY, USA (2019). https:\/\/doi.org\/10.1145\/3306309.3306317","DOI":"10.1145\/3306309.3306317"},{"issue":"4","key":"9924_CR10","doi-asserted-by":"publisher","first-page":"1064","DOI":"10.1017\/jpr.2016.65","volume":"53","author":"J Mairesse","year":"2016","unstructured":"Mairesse, J., Moyal, P.: Stability of the stochastic matching model. J. Appl. Probab. 53(4), 1064\u20131077 (2016). https:\/\/doi.org\/10.1017\/jpr.2016.65","journal-title":"J. Appl. Probab."},{"issue":"3","key":"9924_CR11","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1017\/jpr.2020.100","volume":"58","author":"P Moyal","year":"2021","unstructured":"Moyal, P., Bu\u0161i\u0107, A., Mairesse, J.: A product form for the general stochastic matching model. J. Appl. Probab. 58(3), 449\u2013468 (2021)","journal-title":"J. Appl. Probab."},{"issue":"1","key":"9924_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1080\/15326349.2021.1962352","volume":"38","author":"C Comte","year":"2022","unstructured":"Comte, C.: Stochastic non-bipartite matching models and order-independent loss queues. Stoch. Model. 38(1), 1\u201336 (2022). https:\/\/doi.org\/10.1080\/15326349.2021.1962352","journal-title":"Stoch. Model."},{"key":"9924_CR13","doi-asserted-by":"crossref","unstructured":"Begeot, J., Marcovici, I., Moyal, P., Rahme, Y.: A general stochastic matching model on multigraphs. ALEA Lat. Am. J. Probab. Math. Stat., 1325\u20131351 (2021)","DOI":"10.30757\/ALEA.v18-49"},{"key":"9924_CR14","unstructured":"Kaplan, E.H.: Managing the demand for public housing. Ph.D. thesis, Massachusetts Institute of Technology (1984)"},{"issue":"3","key":"9924_CR15","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1239\/aap\/1253281061","volume":"41","author":"R Caldentey","year":"2009","unstructured":"Caldentey, R., Kaplan, E.H., Weiss, G.: FCFS infinite bipartite matching of servers and customers. Adv. Appl. Probab. 41(3), 695\u2013730 (2009)","journal-title":"Adv. Appl. Probab."},{"issue":"2","key":"9924_CR16","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1239\/aap\/1370870122","volume":"45","author":"A Bu\u0161i\u0107","year":"2013","unstructured":"Bu\u0161i\u0107, A., Gupta, V., Mairesse, J.: Stability of the bipartite matching model. Adv. Appl. Probab. 45(2), 351\u2013378 (2013)","journal-title":"Adv. Appl. Probab."},{"issue":"1\u20132","key":"9924_CR17","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s11134-020-09668-6","volume":"96","author":"K Gardner","year":"2020","unstructured":"Gardner, K., Righter, R.: Product forms for fcfs queueing models with arbitrary server-job compatibilities: an overview. Queueing Syst. 96(1\u20132), 3\u201351 (2020)","journal-title":"Queueing Syst."},{"issue":"3\u20134","key":"9924_CR18","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/s11134-020-09676-6","volume":"96","author":"G Weiss","year":"2020","unstructured":"Weiss, G.: Directed FCFS infinite bipartite matching. Queueing Syst. Theory Appl. 96(3\u20134), 387\u2013418 (2020). https:\/\/doi.org\/10.1007\/s11134-020-09676-6","journal-title":"Queueing Syst. Theory Appl."},{"issue":"2","key":"9924_CR19","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1287\/opre.1110.1027","volume":"60","author":"I Adan","year":"2012","unstructured":"Adan, I., Weiss, G.: Exact FCFS matching rates for two infinite multitype sequences. Oper. Res. 60(2), 475\u2013489 (2012). https:\/\/doi.org\/10.1287\/opre.1110.1027","journal-title":"Oper. Res."},{"key":"9924_CR20","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/j.peva.2018.10.005","volume":"127\u2013128","author":"I Adan","year":"2018","unstructured":"Adan, I., Kleiner, I., Righter, R., Weiss, G.: FCFS parallel service systems and matching models. Perform. Eval. 127\u2013128, 253\u2013272 (2018). https:\/\/doi.org\/10.1016\/j.peva.2018.10.005","journal-title":"Perform. Eval."},{"issue":"3\u20134","key":"9924_CR21","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s11134-016-9485-y","volume":"83","author":"K Gardner","year":"2016","unstructured":"Gardner, K., Zbarsky, S., Doroudi, S., Harchol-Balter, M., Hyyti\u00e4, E., Scheller-Wolf, A.: Queueing with redundant requests: exact analysis. Queueing Syst. 83(3\u20134), 227\u2013259 (2016)","journal-title":"Queueing Syst."},{"key":"9924_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.peva.2017.07.001","volume":"116","author":"K Gardner","year":"2017","unstructured":"Gardner, K., Harchol-Balter, M., Hyyti\u00e4, E., Righter, R.: Scheduling for efficiency and fairness in systems with redundancy. Perform. Eval. 116, 1\u201325 (2017). https:\/\/doi.org\/10.1016\/j.peva.2017.07.001","journal-title":"Perform. Eval."},{"key":"9924_CR23","volume-title":"Finite Markov Chains","author":"JG Kemeny","year":"1960","unstructured":"Kemeny, J.G., Snell, J.L.: Finite Markov Chains. Van Nostrand, New York (1960)"},{"key":"9924_CR24","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139051705","volume-title":"Markov Chains and Dependability Theory","author":"G Rubino","year":"2014","unstructured":"Rubino, G., Sericola, B.: Markov Chains and Dependability Theory. Cambridge University Press, Cambridge (2014)"},{"key":"9924_CR25","doi-asserted-by":"crossref","unstructured":"Plateau, B., Stewart, W.J.: Stochastic automata networks. Computational Probability, 113\u2013151 (2000)","DOI":"10.1007\/978-1-4757-4828-4_5"},{"key":"9924_CR26","doi-asserted-by":"crossref","unstructured":"Busic, A., Cadas, A., Doncel, J., Fourneau, J.-M.: Product form solution for the steady-state distribution of a markov chain associated with a general matching model with self-loops. In: Computer Performance Engineering: 18th European Workshop, EPEW 2022, Santa Pola, Spain, September 21\u201323, 2022, Proceedings, pp. 71\u201385 (2023). Springer","DOI":"10.1007\/978-3-031-25049-1_5"},{"key":"9924_CR27","volume-title":"Denumerable Markov Chains","author":"JG Kemeny","year":"1969","unstructured":"Kemeny, J.G., Snell, J.L., Knapp, A.W.: Denumerable Markov Chains. Springer, New York (1969)"}],"container-title":["Queueing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11134-024-09924-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11134-024-09924-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11134-024-09924-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,16]],"date-time":"2024-08-16T12:21:26Z","timestamp":1723810886000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11134-024-09924-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,3]]},"references-count":27,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["9924"],"URL":"https:\/\/doi.org\/10.1007\/s11134-024-09924-z","relation":{},"ISSN":["0257-0130","1572-9443"],"issn-type":[{"value":"0257-0130","type":"print"},{"value":"1572-9443","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,3]]},"assertion":[{"value":"31 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 July 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 July 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 August 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}