For a congestion game, is a social cost minimization problem NP-hard?
A congestion game is described as follows:
Given a set $E$ of resorces.
$\cdot$ Each agent $i=1,...,k$ has an explicitly described strategy set $S_i \subseteq 2^E$.
$\cdot$ Each agent $i$ plays $s_i \in S_i$, and let ${\bf s}=(s_i)_{i \in [k]}$.
$\cdot$ The cost function $c_e:[k] \to {\mathbb R}$ is assigned to each resource $e \in E$.
$\cdot$ Each agent $i$ suffers the cost $C_i({\bf s})=\sum_{e\in s_i}c_e(n_e({\bf s}))$ where $n_e({\bf s})$ denotes the number of agents in outcome ${\bf s}$ that use a strategy that includes the resource $e$.
$\cdot$ The social cost $C({\bf s})=\sum_{i\in [k]}C_i({\bf s})$
If there is a paper that mentions the above, please tell me.
Any instance of 0-1 integer linear programming (which is NP-complete) can be reduced to a special case of social cost minimization in which there is only one agent, the variables $x_1, \ldots, x_{|E|}$ of the LP instance become 1 if the agent uses the corresponding resource and 0 otherwise, and the LP constraints determine the allowable strategy set $S_i$. I believe this establishes that social cost minimization is NP-hard.