d4-journals-jair-2023-0006

The strongest mirror is the paper’s Theorem 3, proved in this paper. It says that in a negative mixed-manna instance, if agents have SPLC utilities for goods and linear utilities for bads, then with a constant number of bads one can compute all competitive equilibria in polynomial time. Here “all” means that for each equilibrium utility profile, the algorithm returns an equilibrium with that same profile. The result allows arbitrarily many agents and goods.

I would turn that into a type-based competitive-equilibrium problem with bounded chores. The population is a distribution \(\mu\) over \(\tau\) types, where \(\mu_t\) is the fraction of the population of type \(t\), and \(\sum_t\mu_t=1\). A type fully specifies its SPLC utility functions for every good, its linear disutility for every chore, and its per-person budget. There are \(m\) item categories, including a fixed number \(d\) of chores, with \(d\) constant. Give each category a rational supply \(q_j\) per unit of population mass. The masses, supplies, budgets, and utility data are binary rationals.

A type receives a per-person bundle \(x_t\), and the market has prices \(p_j\). A type’s bundle must maximize its utility subject to its budget at those prices; the market must clear, so \(\sum_t\mu_t x_{tj}=q_j\) for every item \(j\); and budgets must be fully spent, as in the paper’s equilibrium definition. Restrict to negative instances, with negative budgets \(e_t<0\), linear disutility for chores, and SPLC utility for goods. A solution is a supporting price vector and type-level bundles, with one equilibrium returned for each distinct vector of type utilities.

This is a population model, not a claim that divisible outcomes make the paper continuous already. The items are divisible in the paper; the new continuous object is the distribution of people. A plausible regime is a large workforce or municipality with many participants but relatively few complete preference-and-budget types. People in each type share the same preferences and entitlement, while the number of distinct types \(\tau\) is much smaller than the population. The chores could be recurring work categories and the goods could be divisible benefits or resources. Negative budgets can represent participants who are net recipients of compensation for taking on chores.

Per-capita supplies are part of this mirror. In a finite population of \(n\) people, the corresponding market has \(nq_j\) units of item \(j\); dividing the clearing equations by \(n\) gives the type-mass constraints above. This scaling makes the market a plausible growing-population regime. It also keeps the paper’s problem recognizable: it remains competitive-equilibrium computation with mixed manna, the same utility restrictions, and the same chore-count parameter.

I expect this problem to be tractable for fixed \(d\). Theorem 3’s algorithm enumerates price and utility-per-buck configurations whose number is polynomial when the number of bads is constant, then checks equilibrium feasibility. In the type model, comparisons are between types, so the natural count is \(\tau\), not the number of people. Masses enter the market-clearing feasibility constraints as rational coefficients. That suggests a running time polynomial in \(\tau\), \(m\), the number of utility segments, and the input bit length, for fixed \(d\). Aggregating identical agents is exact here: their preferences and budgets agree by definition, and their allocations can be averaged while preserving equilibrium utilities.

The paper’s other named results could support narrower mirrors, but I would not add them as anchors: Theorem 3 is the clearest match to a large population with few recurring chore categories. Nor would I use the PPAD-hardness entries in Table 1 as anchors; they are cited prior results, not numbered results proved here.

The mirror covers Theorem 3’s negative-instance result, not the paper’s full set of equilibrium results. It raises natural next questions: does the same type-level tractability extend to SPLC chore utilities, which the paper identifies as open? Can the dependence on \(d\) be made fixed-parameter tractable, or does hardness emerge when the number of chores grows?

My weakest point is the supply scaling. If the intended regime holds total supplies fixed while the population grows, per-person supplies shrink, and that may not represent the market the authors had in mind. I think the growing-workforce interpretation is still credible, and the programme explicitly allows per-capita supplies to scale with population. Since the paper’s agents are discrete individuals, the type-mass algorithm would also need to be established; Theorem 3 motivates that question but does not itself prove its continuous version.