Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2604.00129 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910091080368128 |
|---|---|
| author | Babaioff, Moshe Rubinstein, Aviad Tan, Xizhi Wang, Kangning |
| author_facet | Babaioff, Moshe Rubinstein, Aviad Tan, Xizhi Wang, Kangning |
| contents | A central challenge in mechanism design is to develop truthful trade mechanisms that maximize the expected gains-from-trade (GFT) in two-sided markets with strategic agents. As achieving the full GFT is generally impossible, much of the literature has focused on constant-factor approximations. Existing results, however, are limited to the highly structured settings of bilateral trade and double auctions, in which every buyer can trade with every seller.
We consider the significantly more general setting of two-sided matching markets with arbitrary downward-closed constraints on the family of allowed matchings. For this setting, we present a simple randomized truthful mechanism that guarantees a constant-factor approximation to the optimal expected GFT. This result also resolves an open problem posed by Cai, Goldner, Ma, and Zhao (2021). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_00129 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Approximating Gains-from-Trade in Matching Markets Babaioff, Moshe Rubinstein, Aviad Tan, Xizhi Wang, Kangning Computer Science and Game Theory A central challenge in mechanism design is to develop truthful trade mechanisms that maximize the expected gains-from-trade (GFT) in two-sided markets with strategic agents. As achieving the full GFT is generally impossible, much of the literature has focused on constant-factor approximations. Existing results, however, are limited to the highly structured settings of bilateral trade and double auctions, in which every buyer can trade with every seller. We consider the significantly more general setting of two-sided matching markets with arbitrary downward-closed constraints on the family of allowed matchings. For this setting, we present a simple randomized truthful mechanism that guarantees a constant-factor approximation to the optimal expected GFT. This result also resolves an open problem posed by Cai, Goldner, Ma, and Zhao (2021). |
| title | Approximating Gains-from-Trade in Matching Markets |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2604.00129 |