EQUILIBRIUM POINTS IN NONZERO-SUM n-PERSON
Submodular Games · 1979
A submodular game is a finite noncooperative game in which the set of feasible joint decisions is a sublattice and the cost function of each player has properties of submodularity and antitone differences. Examples of submodular games include 1) a game version of a system with complementary products; 2) an extension of the minimum cut problem to a situation where players choose from different sets of nodes and perceive different capacities, with special cases being a game with players choosing whether or not to participate in available economic activities and a game version of the selection problem; 3) the pricing problem of competitors producing substitute products; 4) a game version of the facility location problem; and 5) a game with players determining their optimal usage of available products. A fixed point approach establishes the existence of a pure equilibrium point for certain submodular games. Two algorithms which correspond to fictitious play in dynamic games generate sequences of feasible joint decisions converging monotonically to a pure equilibrium point. Bounds show these algorithms to be very efficient when the set of feasible decisions is finite. An optimal decision for each player is an isotone function of the decisions of other players. Introduction. Consider a noncooperative n-person game with the players indicated by 1,..., n. The decision of player is an mi-vector xi. The joint decision is x =(Xl,',x,). The set of feasible joint decisions is a subset S of E where m i=1 mi. The feasible decisions for a given player may depend upon the decisions chosen by the other players. (By assigning a very large or infinite cost to each m-vector not in S one could embed such a game into a game in which any m-vector is considered feasible, but that approach is not convenient here because it is not easy to transform subsequent assumptions about the players' cost functions into equivalent properties for such extended costs.) Let x xi (Xl, xi-1, Xi+l, Xn) be the vector of decisions of all players except player i. Let (x; yi) (xl, , xi-1, yi, Xi+l, , xn) be the vector of joint decisions for all n players where yi is the decision of player and x xi is the vector of decisions of the other n 1 players. The set of feasible decisions for player given x xi is Si(X) {yi'(X; Yi) E S}. The vectors x xi and (x; yi) and the set Si(x do not depend on xi. Define Ti {x xi Si(x) is nonempty} and Si x-x,', Si(x). As a result of a joint decision x E S, player incurs the cost fi(x) where fi(x) is a real-valued function on S for 1,..., n. A feasible joint decision x 6 S is an equilibrium point if fi(x)<-fi(x; yi) for all yi6 Si(x) and i= 1, ,n.