Search for: All records

In this paper, we study the total displacement statistic of parking functionsfrom the perspective of cooperative game theory. We introduce parking games,which are coalitional cost-sharing games in characteristic function formderived from the total displacement statistic. We show that parking games aresupermodular cost-sharing games, indicating that cooperation is difficult(i.e., their core is empty). Next, we study their Shapley value, whichformalizes a notion of fair cost-sharing and amounts to charging each car forits expected marginal displacement under a random arrival order. Our maincontribution is a polynomial-time algorithm to compute the Shapley value ofparking games, in contrast with known hardness results on computing the Shapleyvalue of arbitrary games. The algorithm leverages the permutation-invariance oftotal displacement, combinatorial enumeration, and dynamic programming. Weconclude with open questions around an alternative solution concept forsupermodular cost-sharing games and connections to other areas incombinatorics. 

Classical parking functions are defined as the parking preferences for $$n$$ cars driving (from west to east) down a one-way street containing parking spaces labeled from $$1$$ to $$n$$ (from west to east). Cars drive down the street toward their preferred spot and park there if the spot is available. Otherwise, the car continues driving down the street and takes the first available parking space, if such a space exists. If all cars can park using this parking rule, we call the $$n$$-tuple containing the cars' parking preferences a parking function.   In this paper, we introduce a generalization of the parking rule allowing cars whose preferred space is taken to first proceed up to $$k$$ spaces west of their preferred spot to park before proceeding east if all of those $$k$$ spaces are occupied. We call parking preferences which allow all cars to park under this new parking rule $$k$$-Naples parking functions of length $$n$$. This generalization gives a natural interpolation between classical parking functions, the case when $k=0$, and all $$n$$-tuples of positive integers $$1$$ to $$n$$, the case when $$k\geq n-1$$. Our main result provides a recursive formula for counting $$k$$-Naples parking functions of length $$n$$. We also give a characterization for the $k=1$ case by introducing a new function that maps $$1$$-Naples parking functions to classical parking functions, i.e. $$0$$-Naples parking functions. Lastly, we present a bijection between $$k$$-Naples parking functions of length $$n$$ whose entries are in weakly decreasing order and a family of signature Dyck paths.