d4-conf-sagt-2015-0015

I would anchor the case on Theorem 9, proved in this paper. It says: given a market with indivisible goods, additive valuations, and a fixed price vector \(p\), it is coNP-hard to decide whether there is an allocation \(x\) such that \((x,p)\) is a competitive equilibrium from equal incomes. The authors note that Aziz had also studied this question, but they give their own proof by reduction from PARTITION.

A natural high-multiplicity setting is course assignment with two large cohorts of students who share the same valuation within each cohort. Course seats scale with enrollment, while each student’s bundle remains integral: a student either gets a seat in a course or does not. If the population has \(N\) students, take \(N/2\) of each type and \(N/2\) seats in each course category. Thus \(N\) grows while the number of distinct types stays at \(\tau=2\). The type records the student’s full valuation vector and equal budget. This is a population mirror: the allocation of seats to each individual stays discrete, while the allocation to a type is a mass distribution over bundles.

Here is the problem I would hand to a prover. Call it Fixed-Price CEEI Support for Continuous Additive Types. An instance has goods \(G=[m]\), types \(T\) with rational masses \(\mu_t\) summing to \(1\), additive values \(v_{tj}\), per-capita supplies \(q_j\), and a fixed nonnegative rational price vector \(p\). Every infinitesimal agent has budget \(1\) and must receive an integral bundle \(S\subseteq G\), with utility \(u_t(S)=\sum_{j\in S}v_{tj}\). The decision variable is \(y_{t,S}\), the mass of type \(t\) assigned bundle \(S\). The question is whether there is a \(y\) such that \(\sum_S y_{t,S}=\mu_t\); each assigned bundle spends exactly \(1\) and maximizes its type’s utility among bundles affordable at \(p\); and \(\sum_{t,S:j\in S}y_{t,S}\le q_j\), with equality whenever \(p_j>0\). The solution is the allocation measure \(y\); prices are inputs, just as in Theorem 9. All input numbers are binary rationals.

The paper’s PARTITION reduction carries over with only two types. Given positive integers \(s_1,\ldots,s_m\) summing to \(2V\), use ordinary goods \(1,\ldots,m\) and two special goods \(a,b\). Let both types have mass \(1/2\), and set every good’s per-capita supply to \(1/2\). Prices are \(p_j=s_j/(2V)\) for ordinary goods and \(p_a=p_b=1/2\). Type \(A\) values ordinary good \(j\) at \(s_j\), and values \(a,b\) at \(3V,V-1\); type \(B\) values each ordinary good at \(1\) and the special goods at \(0\).

The candidate allocation gives all type \(A\) mass bundle \(\{a,b\}\) and all type \(B\) mass bundle \([m]\). Each spends \(1\), and all supply clears. Type \(B\) can afford all ordinary goods, which is its unique utility-maximizing bundle. Type \(A\)’s assigned utility is \(4V-1\); the reduction’s case analysis shows it has a strictly better affordable bundle exactly when some subset of the \(s_j\) sums to \(V\). If such a subset exists, no other equilibrium allocation can avoid the problem: type \(B\)’s best response uses all ordinary supply, leaving type \(A\) with the special goods and the same profitable deviation. If no such subset exists, the displayed allocation is an equilibrium. So the continuous instance has an equilibrium exactly when the PARTITION instance has no solution. The mass allocation does not dissolve the reduction: type \(B\)’s strict demand pins down the allocation, and type \(A\)’s individual best-response test retains the subset-sum constraint.

I therefore expect this mirror to be Class B: coNP-hardness transfers, with the hard combinatorics in the goods and valuation agenda \(m\), not in the number of agents. In fact, the reduction has constant support size \(\tau=2\). Further questions include whether the continuous problem is coNP-complete under this encoding, and which restrictions on values or prices make it tractable.

The scope is deliberately narrow: it mirrors Theorem 9’s fixed-price allocation-support problem, not the paper’s general question of whether some prices and allocation form an equilibrium. The weak point is the supply co-modification. The paper starts with one copy of each good; this mirror scales each good category’s supply with the population and caps each person at one unit of that category. That is allowed by the continuization programme, and course seats make it a plausible regime, but a referee could still ask whether the multi-seat categories change the authors’ problem too much. The individual bundles remain integral, and the equal-income price-support question remains the same.