On Games with Coupled Constraints

We study the problem of cost minimization in competitive resource allocation problems, motivated by our previous work on power minimization in MIMO interference systems. Our setup leads to a general cost minimization game in which each player wishes to minimize the cost of its resource consumption while achieving a target utility level. In general, the player strategies are coupled through both their cost functions and their utility functions. Equilibrium exists only for a certain set of target utility levels which in general is a proper set of all achievable utility levels. To characterize the set of equilibrium utility levels, we introduce the dual of a cost minimization game called a utility maximization game in which each player wishes to maximize its utility while keeping the cost of its resource consumption below a cost threshold. We associate the set of equilibrium utility levels with the set of equilibrium of the dual game corresponding to all cost thresholds, and show that the dual game always possesses an equilibrium. 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 a weighted cost minimization game which always possesses an equilibrium. We recover the original equilibria through the equilibria of the weighted cost minimization game as the penalty on not achieving the target utility levels increases.