Neighbor games and the leximax solution (Q1416784)

The authors introduce neighbor games, which are assignment (cooperative) games where the players are located on a line and matchings are only possible between neighbors. The core of such games is nonempty, and the problem arises of selecting a suitable element from it. The result of the paper is an operational characterization for neighbor games of the leximax solution (an imputation with minimum maximal element among core vectors) which is directly applied to finding an algorithm that identifies the leximax vector in a finite number of steps (polynomially bounded of order equal to the number of players to the cube).