A Linear Programming Framework for Network Games

In this paper we present a linear programming game that is motivated by the assignment game of Shapley and Shubik. This new game is a very natural generalization of many of the network optimization games that have been well studied in the past. We first show that for this general class of games the core is nonempty. In fact any dual optimal solution of the underlying linear programming probem gives rise to a core allocation. We also show that for a particular subclass of games (which include the assignment, max flow and location games) the core exactly coincides with the set of optimal dual solutions. Additionally we study the relationship between this linear programming game and the production game of Owen.