d4-journals-mss-2021-0012

Strictly, this paper has no named computational-complexity result: no theorem or proposition places an encoded problem in P, proves it hard, or gives a parameterized complexity classification. Its named results establish equilibrium, uniqueness, and convergence. So the positive case has to be a computational question grounded in one of those results, not a claim that the paper already contains a ChoCo complexity result.

The strongest lead is Proposition 3.5, proved in this paper. It says that for an aggregative game \(F_{x,p}(\mu)=\beta_p(x,A(\mu))\), if Assumptions 3.1 and 3.3 hold, then there is a unique efficient state. That state is monomorphic within every population: \(\mu^{**}=(m_1\delta_{\alpha^{**}_1},\ldots,m_n\delta_{\alpha^{**}_n})\). The vector \((\alpha^{**}_1,\ldots,\alpha^{**}_n)\) is the unique maximizer of
\[ \bar G(\alpha_1,\ldots,\alpha_n) =\sum_{p\in P}m_p\beta_p\!\left(\alpha_p,\sum_{q\in P}m_q\alpha_q\right). \]
This is an analytic characterization, not a claimed running-time bound. It is nevertheless the paper’s clearest computational foothold: it reduces an optimization over population measures to an optimization over one action per type.

A concrete question built from it is Finite-Type Efficient-State Approximation. An instance gives \(\tau\) types with positive binary-rational masses \(m_p\) summing to one, action interval \([0,1]\), and explicitly encoded rational polynomials \(\beta_p(x,a)\). The instance is promised to satisfy the paper’s concavity assumptions. Given rational \(\epsilon>0\), return an action vector \(\hat\alpha\in[0,1]^\tau\) whose aggregate payoff is within \(\epsilon\) of the maximum:
\[ \bar G(\alpha^{**})-\bar G(\hat\alpha)\le\epsilon. \]
The corresponding society is \(\hat\mu_p=m_p\delta_{\hat\alpha_p}\). This asks for the paper’s efficient state itself, represented as type-level actions; it does not replace the game with a different outcome or objective.

The regime is natural in the paper’s own applications. For example, many farms drawing from a shared aquifer could choose extraction levels, with types determined by their technology, costs, and valuations. Each type has many agents with the same relevant payoff function; the population size \(N\) can be very large while the number of distinct types \(\tau\) is modest. Mass is the fraction of farms of each type, and the action is extraction per farm. In the tragedy-of-the-commons model, the planner’s state-dependent transfer is also explicit: an agent choosing \(x\) pays \(x(\mathrm{MP}(A)-\mathrm{AP}(A))\). Thus both the decision and the externality correction retain the paper’s economic meaning.

I would expect the approximation problem to be Class A under this explicit encoding: Proposition 3.5 supplies a concave finite-dimensional objective, making standard convex-optimization methods applicable, with running time measured in \(\tau\), encoding length, and \(\log(1/\epsilon)\). Exact representation of the optimizer is a separate question, since its coordinates need not be rational. This question could also lead to questions about exact-output complexity, computing transfers from estimated rather than known payoff functions, and finite-time convergence guarantees for the dynamics.

The authors would recognize this as computing their efficient state: the type masses, payoffs, action choices, and welfare objective are the ones in their model. The paper’s Theorem 4.4 gives further analytic support by proving convergence to that state under several evolutionary dynamics, subject to the stated conditions. It does not give finite-time complexity bounds, so I would not use it as a second computational anchor.

The weak point is substantial: the paper has already made the population continuous and already characterizes the optimizer. The proposed question adds a finite encoding and asks for a complexity analysis that the paper does not undertake. A reviewer could reasonably see it as a computational follow-up to an existing continuum model rather than a new continuization. It also gives no discrete hardness result whose difficulty might dissolve in the continuum. The positive case is therefore that this paper supplies an unusually clean, natural continuous substrate for a computational question—not that the paper itself establishes a new continuous mirror.