## Abstract

In this paper, we study max-weight stochastic matchings on online bipartite graphs under both vertex and edge arrivals. We focus on designing polynomial time approximation algorithms with respect to the online benchmark, which was first considered by Papadimitriou, Pollner, Saberi, and Wajc [EC'21]. In the vertex arrival version of the problem, the goal is to find an approximate max-weight matching of a given bipartite graph when the vertices in one part of the graph arrive online in a fixed order with independent chances of failure. Whenever a vertex arrives we should decide, irrevocably, whether to match it with one of its unmatched neighbors or leave it unmatched forever. There has been a long line of work designing approximation algorithms for different variants of this problem with respect to the offline benchmark (prophet). Papadimitriou et al., however, propose the alternative online benchmark and show that considering this new benchmark allows them to improve the 0.5 approximation ratio, which is the best ratio achievable with respect to the offline benchmark. They provide a 0.51-approximation algorithm which was later improved to 0.526 by Saberi and Wajc [ICALP'21]. The main contribution of this paper is designing a simple algorithm with a significantly improved approximation ratio of (1-1/e) for this problem. We also consider the edge arrival version in which, instead of vertices, edges of the graph arrive in an online fashion with independent chances of failure. Designing approximation algorithms for this problem has also been studied extensively with the best approximation ratio being 0.337 with respect to the offline benchmark. This paper, however, is the first to consider the online benchmark for the edge arrival version of the problem. For this problem, we provide a simple algorithm with an approximation ratio of 0.5 with respect to the online benchmark.

Original language | English (US) |
---|---|

Title of host publication | EC 2022 - Proceedings of the 23rd ACM Conference on Economics and Computation |

Publisher | Association for Computing Machinery, Inc |

Pages | 967-985 |

Number of pages | 19 |

ISBN (Electronic) | 9781450391504 |

DOIs | |

State | Published - Jul 12 2022 |

Event | 23rd ACM Conference on Economics and Computation, EC 2022 - Boulder, United States Duration: Jul 11 2022 → Jul 15 2022 |

### Publication series

Name | EC 2022 - Proceedings of the 23rd ACM Conference on Economics and Computation |
---|

### Conference

Conference | 23rd ACM Conference on Economics and Computation, EC 2022 |
---|---|

Country/Territory | United States |

City | Boulder |

Period | 7/11/22 → 7/15/22 |

## All Science Journal Classification (ASJC) codes

- Computer Science (miscellaneous)
- Economics and Econometrics
- Computational Mathematics
- Statistics and Probability

## Keywords

- matching markets
- online matching
- stochastic matching