ISSN:
1436-4646
Keywords:
Linear Programming
;
NP-Completeness
;
Polynomial Hierarchy
;
Computational Complexity
;
Stackleberg Strategies
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract The multi-level linear programs of Candler, Norton and Townsley are a simple class of sequenced-move games, in which players are restricted in their moves only by common linear constraints, and each seeks to optimize a fixed linear criterion function in his/her own continuous variables and those of other players. All data of the game and earlier moves are known to a player when he/she is to move. The one-player case is just linear programming. We show that questions concerning only the value of these games exhibit complexity which goes up all levels of the polynomial hierarchy and appears to increase with the number of players. For three players, the games allow reduction of theΣ 2 andΠ 2 levels of the hierarchy. These levels essentially include computations done with branch-and-bound, in which one is given an oracle which can instantaneously solve NP-complete problems (e.g., integer linear programs). More generally, games with (p + 1) players allow reductions ofΣ p andΠ p in the hierarchy. An easy corollary of these results is that value questions for two-player (bi-level) games of this type is NP-hard.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01586088
