  The computational study of equilibria involving constraints on players'
strategies has been largely neglected. However, in real-world applications,
players are usually subject to constraints ruling out the feasibility of some
of their strategies, such as, e.g., safety requirements and budget caps.
Computational studies on constrained versions of the Nash equilibrium have lead
to some results under very stringent assumptions, while finding constrained
versions of the correlated equilibrium (CE) is still unexplored. In this paper,
we introduce and computationally characterize constrained Phi-equilibria -- a
more general notion than constrained CEs -- in normal-form games. We show that
computing such equilibria is in general computationally intractable, and also
that the set of the equilibria may not be convex, providing a sharp divide with
unconstrained CEs. Nevertheless, we provide a polynomial-time algorithm for
computing a constrained (approximate) Phi-equilibrium maximizing a given linear
function, when either the number of constraints or that of players' actions is
fixed. Moreover, in the special case in which a player's constraints do not
depend on other players' strategies, we show that an exact, function-maximizing
equilibrium can be computed in polynomial time, while one (approximate)
equilibrium can be found with an efficient decentralized no-regret learning
algorithm.
