Cost-sharing in Parking Games
In this paper, we study the total displacement statistic of parking functions from the perspective of cooperative game theory. We introduce parking games, which are coalitional cost-sharing games in characteristic function form derived from the total displacement statistic. We show that parking game...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2024-11-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | http://dmtcs.episciences.org/13113/pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850278300550692864 |
|---|---|
| author | Jennifer Elder Pamela E. Harris Jan Kretschmann J. Carlos Martínez Mori |
| author_facet | Jennifer Elder Pamela E. Harris Jan Kretschmann J. Carlos Martínez Mori |
| author_sort | Jennifer Elder |
| collection | DOAJ |
| description | In this paper, we study the total displacement statistic of parking functions from the perspective of cooperative game theory. We introduce parking games, which are coalitional cost-sharing games in characteristic function form derived from the total displacement statistic. We show that parking games are supermodular cost-sharing games, indicating that cooperation is difficult (i.e., their core is empty). Next, we study their Shapley value, which formalizes a notion of "fair" cost-sharing and amounts to charging each car for its expected marginal displacement under a random arrival order. Our main contribution is a polynomial-time algorithm to compute the Shapley value of parking games, in contrast with known hardness results on computing the Shapley value of arbitrary games. The algorithm leverages the permutation-invariance of total displacement, combinatorial enumeration, and dynamic programming. We conclude with open questions around an alternative solution concept for supermodular cost-sharing games and connections to other areas in combinatorics. |
| format | Article |
| id | doaj-art-a3dfb287411f4e948a35385c399f4255 |
| institution | OA Journals |
| issn | 1365-8050 |
| language | English |
| publishDate | 2024-11-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj-art-a3dfb287411f4e948a35385c399f42552025-08-20T01:49:33ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502024-11-01vol. 26:3Combinatorics10.46298/dmtcs.1311313113Cost-sharing in Parking GamesJennifer ElderPamela E. HarrisJan KretschmannJ. Carlos Martínez MoriIn this paper, we study the total displacement statistic of parking functions from the perspective of cooperative game theory. We introduce parking games, which are coalitional cost-sharing games in characteristic function form derived from the total displacement statistic. We show that parking games are supermodular cost-sharing games, indicating that cooperation is difficult (i.e., their core is empty). Next, we study their Shapley value, which formalizes a notion of "fair" cost-sharing and amounts to charging each car for its expected marginal displacement under a random arrival order. Our main contribution is a polynomial-time algorithm to compute the Shapley value of parking games, in contrast with known hardness results on computing the Shapley value of arbitrary games. The algorithm leverages the permutation-invariance of total displacement, combinatorial enumeration, and dynamic programming. We conclude with open questions around an alternative solution concept for supermodular cost-sharing games and connections to other areas in combinatorics.http://dmtcs.episciences.org/13113/pdfmathematics - combinatoricscomputer science - discrete mathematicscomputer science - computer science and game theory05a05, 91a12, 91a46 |
| spellingShingle | Jennifer Elder Pamela E. Harris Jan Kretschmann J. Carlos Martínez Mori Cost-sharing in Parking Games Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics computer science - discrete mathematics computer science - computer science and game theory 05a05, 91a12, 91a46 |
| title | Cost-sharing in Parking Games |
| title_full | Cost-sharing in Parking Games |
| title_fullStr | Cost-sharing in Parking Games |
| title_full_unstemmed | Cost-sharing in Parking Games |
| title_short | Cost-sharing in Parking Games |
| title_sort | cost sharing in parking games |
| topic | mathematics - combinatorics computer science - discrete mathematics computer science - computer science and game theory 05a05, 91a12, 91a46 |
| url | http://dmtcs.episciences.org/13113/pdf |
| work_keys_str_mv | AT jenniferelder costsharinginparkinggames AT pamelaeharris costsharinginparkinggames AT jankretschmann costsharinginparkinggames AT jcarlosmartinezmori costsharinginparkinggames |