Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Online Matching with Delays and Stochastic Arrival Times

Uproszczony widok
dc.abstract.enConsider a platform where independent agents arrive at random times and need to be matched into pairs, eventually after waiting for some time. This, for example, models job markets, gaming platforms, kidney exchange programs, etc. The role of the platform is to decide how to match agents together while optimizing two conflicting objectives: the quality of the matching produced, and the total waiting time of the agents. This can be modeled as an online problem called Min-cost Perfect Matching with Delays (MPMD), which has recently drawn a lot of attention. It is known that in the case when agents arrive in an adversarial order, no online algorithm can achieve a constant-competitive ratio. In this paper, we study the more realistic case where agents' arrival times follow some stochastic assumptions, and we present two matching mechanisms, which give constant-competitive solutions. The first one is a simple greedy algorithm in which agents act in a distributed manner requiring only local communication. The second one builds global analysis tools in order to obtain even better performance guarantees. This result is rather surprising as the greedy approach cannot achieve a competitive ratio better than O(mlog 1.5 + ) in the adversarial model, where m denotes the number of agents. Finally, we extend our results to the case where the delay cost corresponds to an arbitrary positive and non-decreasing function of the waiting time, as well as the case where the platform is allowed to pay a penalty cost to clear some agents' requests.
dc.affiliationUniwersytet Warszawski
dc.conference.countryWielka Brytania
dc.conference.datefinish2023-06-02
dc.conference.datestart2023-05-29
dc.conference.placeLondon
dc.conference.seriesInternational Joint Conference on Autonomous Agents and Multiagent Systems
dc.conference.seriesInternational Joint Conference on Autonomous Agents and Multiagent Systems
dc.conference.seriesshortcutAAMAS
dc.conference.shortcutAAMAS 2023
dc.conference.weblinkhttps://aamas2023.soton.ac.uk/
dc.contributor.authorSankowski, Piotr
dc.contributor.authorRen, Runtian
dc.contributor.authorPawłowski, Michał
dc.contributor.authorMari, Mathieu
dc.date.accessioned2024-01-25T15:44:21Z
dc.date.available2024-01-25T15:44:21Z
dc.date.issued2023
dc.description.financePublikacja bezkosztowa
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/114622
dc.identifier.weblinkhttps://dl.acm.org/doi/10.5555/3545946.3598737
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages976–984
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleOnline Matching with Delays and Stochastic Arrival Times
dc.typeJournalArticle
dspace.entity.typePublication