On Games With Coupled Constraints

We study a general cost minimization game in which each player minimizes the cost of its resource consumption while achieving a target utility level. The player strategies are coupled through both their cost functions and their utility functions. Equilibrium exists only for certain target utility levels, and is characterized by the equilibrium of a dual game in which each player maximizes its utility while keeping the cost of its resource consumption below a cost threshold. We show that the dual game possesses equilibrium under very mild conditions, in particular with no a priori assumption on the compactness of player strategy sets. We also obtain an inner estimate of the set of equilibrium utility levels in the case of decoupled cost functions by a minimax approach. We then relax the hard constraint on achieving a target utility level, and introduce an unconstrained weighted cost minimization game which always possesses equilibrium. Under mild conditions, we recover the original equilibrium as the penalty on not achieving the target utility levels increases. Finally, we discuss the possibility of learning to play an equilibrium strategy via the best response dynamics.