Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.09814 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910027533516800 |
|---|---|
| author | Martinez, Emile Garrido-Lucero, Felipe Grandi, Umberto |
| author_facet | Martinez, Emile Garrido-Lucero, Felipe Grandi, Umberto |
| contents | The assignment game models a housing market where buyers and sellers are matched, and transaction prices are set so that the resulting allocation is stable. Shapley and Shubik showed that every stable allocation is necessarily built on a maximum social welfare matching. In practice, however, stable allocations are rarely attainable, as matchings are often sub-optimal, particularly in online settings where eagents arrive sequentially to the market. In this paper, we introduce and compare two complementary measures of instability for allocations with sub-optimal matchings, establish their connections to the optimality ratio of the underlying matching, and use this framework to study the stability performances of randomized algorithms in online assignment games. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_09814 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Stability in Online Assignment Games Martinez, Emile Garrido-Lucero, Felipe Grandi, Umberto Computer Science and Game Theory The assignment game models a housing market where buyers and sellers are matched, and transaction prices are set so that the resulting allocation is stable. Shapley and Shubik showed that every stable allocation is necessarily built on a maximum social welfare matching. In practice, however, stable allocations are rarely attainable, as matchings are often sub-optimal, particularly in online settings where eagents arrive sequentially to the market. In this paper, we introduce and compare two complementary measures of instability for allocations with sub-optimal matchings, establish their connections to the optimality ratio of the underlying matching, and use this framework to study the stability performances of randomized algorithms in online assignment games. |
| title | Stability in Online Assignment Games |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2510.09814 |