## Abstract

In the stochastic matching problem, we are given a general (not necessarily bipartite) graph G(V, E), where each edge in E is realized with some constant probability p > 0 and the goal is to compute a bounded-degree (bounded by a function depending only on p) subgraph H of G such that the expected maximum matching size in H is close to the expected maximum matching size in G. The algorithms in this setting are considered non-Adaptive as they have to choose the subgraph H without knowing any information about the set of realized edges in G. Originally motivated by an application to kidney exchange, the stochastic matching problem and its variants have received significant attention in recent years. The state-of-The-Art non-Adaptive algorithms for stochastic matching achieve an approximation ratio of 12 -ϵ for any ϵ > 0, naturally raising the question that if 1/2 is the limit of what can be achieved with a non-Adaptive algorithm. In this work, we resolve this question by presenting the first algorithm for stochastic matching with an approximation guarantee that is strictly better than 1/2: The algorithm computes a subgraph H ofG with the maximum degree O (log (1/p)/ p) such that the ratio of expected size of a maximum matching in realizations of H and G is at least 1/2+δ0 for some absolute constant δ0 > 0. The degree bound on H achieved by our algorithm is essentially the best possible (up to an O(log (1/p)) factor) for any constant factor approximation algorithm, since an Ω( 1 p ) degree in H is necessary for a vertex to acquire at least one incident edge in a realization. Our result makes progress towards answering an open problem of Blum et al. (EC 2015) regarding the possibility of achieving a (1 - ϵ )-Approximation for the stochastic matching problem using non-Adaptive algorithms. From the technical point of view, a key ingredient of our algorithm is a structural result showing that a graph whose expected maximum matching size is opt always contains a b-matching of size (essentially) b opt, for b = 1 p .

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

Title of host publication | EC 2017 - Proceedings of the 2017 ACM Conference on Economics and Computation |

Publisher | Association for Computing Machinery, Inc |

Pages | 99-116 |

Number of pages | 18 |

ISBN (Electronic) | 9781450345279 |

DOIs | |

State | Published - Jun 20 2017 |

Externally published | Yes |

Event | 18th ACM Conference on Economics and Computation, EC 2017 - Cambridge, United States Duration: Jun 26 2017 → Jun 30 2017 |

### Publication series

Name | EC 2017 - Proceedings of the 2017 ACM Conference on Economics and Computation |
---|

### Conference

Conference | 18th ACM Conference on Economics and Computation, EC 2017 |
---|---|

Country/Territory | United States |

City | Cambridge |

Period | 6/26/17 → 6/30/17 |

## All Science Journal Classification (ASJC) codes

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

## Keywords

- Kidney exchange
- Stochastic matching