Improving the Price of Anarchy via Predictions in Parallel-Link Networks
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912474651951104 |
|---|---|
| author | Christodoulou, George Christoforidis, Vasilis Sgouritsa, Alkmini Vlachos, Ioannis |
| author_facet | Christodoulou, George Christoforidis, Vasilis Sgouritsa, Alkmini Vlachos, Ioannis |
| contents | We study non-atomic congestion games on parallel-link networks with affine cost functions. We investigate the power of machine-learned predictions in the design of coordination mechanisms aimed at minimizing the impact of selfishness. Our main results demonstrate that enhancing coordination mechanisms with a simple advice on the input rate can optimize the social cost whenever the advice is accurate (consistency), while only incurring minimal losses even when the predictions are arbitrarily inaccurate (bounded robustness). Moreover, we provide a full characterization of the consistent mechanisms that holds for all monotone cost functions, and show that our suggested mechanism is optimal with respect to the robustness. We further explore the notion of smoothness within this context: we extend our mechanism to achieve error-tolerance, i.e. we provide an approximation guarantee that degrades smoothly as a function of the prediction error, up to a predetermined threshold, while achieving a bounded robustness. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_07915 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improving the Price of Anarchy via Predictions in Parallel-Link Networks Christodoulou, George Christoforidis, Vasilis Sgouritsa, Alkmini Vlachos, Ioannis Computer Science and Game Theory We study non-atomic congestion games on parallel-link networks with affine cost functions. We investigate the power of machine-learned predictions in the design of coordination mechanisms aimed at minimizing the impact of selfishness. Our main results demonstrate that enhancing coordination mechanisms with a simple advice on the input rate can optimize the social cost whenever the advice is accurate (consistency), while only incurring minimal losses even when the predictions are arbitrarily inaccurate (bounded robustness). Moreover, we provide a full characterization of the consistent mechanisms that holds for all monotone cost functions, and show that our suggested mechanism is optimal with respect to the robustness. We further explore the notion of smoothness within this context: we extend our mechanism to achieve error-tolerance, i.e. we provide an approximation guarantee that degrades smoothly as a function of the prediction error, up to a predetermined threshold, while achieving a bounded robustness. |
| title | Improving the Price of Anarchy via Predictions in Parallel-Link Networks |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2507.07915 |