Optimal Reallocation under Additive and Ordinal Preferences

My lead mirror is a high-multiplicity version of the paper’s Pareto-optimality test.

Consider a large entitlement exchange with \(K\) agents and \(m\) kinds of indivisible one-use resources. There are only \(\tau\) recurring agent types, with \(K\gg\tau\). A type \(t\) includes both an additive utility vector \(u_t\) and an initial bundle \(e_t\); agents of the same type are indistinguishable in every respect relevant to reallocation. Assume, in the strongest version of the mirror, that all utilities use the same three values \(\alpha>\beta>\gamma\geq0\).

The continuous society is a distribution \(\mu\) over types. Resource supplies scale with the population: resource \(o\) has per-capita supply \(s_o=\sum_t\mu_t e_t(o)\). Each individual still receives an integral bundle \(B\in\{0,1\}^m\); only the population and aggregate resource counts are continuous. Thus a mass \(x_{t,B}\) means that this fraction of type \(t\) receives the integral bundle \(B\). It is not a fractional allocation of an object to an individual.

I would call the resulting problem \(\mathrm{3V\mbox{-}PO}_\infty\). Its instance consists of \(T,\mu,(u_t,e_t)_{t\in T}\), and the induced resource supplies. We ask whether there is a feasible mass reassignment \(x\) satisfying \(\sum_Bx_{t,B}=\mu_t\), \(\sum_{t,B}x_{t,B}B_o=s_o\) for every resource \(o\), and \(u_t(B)\geq u_t(e_t)\) whenever \(x_{t,B}>0\), with strict inequality for a positive total mass of agents. Equivalently, maximize \(z=\sum_{t,B:u_t(B)>u_t(e_t)}x_{t,B}\); the initial society is continuously Pareto optimal exactly when the optimum is \(0\).

This is a direct high-multiplicity analogue of the paper’s underlying problem. A finite \(K\)-agent market with \(K\mu_t\) clones of each type and \(Ks_o\) resource copies maps to the continuous instance, and conversely rational continuous data can be realized by a sufficiently large clone market. The Pareto condition remains individual: every member of every type must weakly improve, rather than merely receiving a better average utility.

The anchor is Theorem 3, proved in this paper. It states that testing Pareto optimality of a given assignment under additive utilities is strongly coNP-complete even when there are only three utility values. The reduction is from \((3,\mathrm{B}2)\)-SAT. For each variable it creates two agents, for each clause a clause agent, and two additional agents \(A\) and \(H\); it constructs an initial assignment \(q\) using variable, clause, and auxiliary goods. The only utility values are \(1\), \(t\), and \(\varepsilon=1/(6t)\). A satisfying truth assignment yields a Pareto improvement of \(q\), while any Pareto improvement of \(q\) induces a satisfying truth assignment. Hence \(q\) is not Pareto optimal exactly when the formula is satisfiable. The theorem therefore gives a genuine hardness anchor, not merely a formulation.

I expect \(\mathrm{3V\mbox{-}PO}_\infty\) to be in Class A, even though the discrete problem in Theorem 3 is strongly coNP-complete. For each type \(t\), let \(U_t\) be the family of bundles with \(u_t(B)\geq u_t(e_t)\). The continuous problem is a configuration LP whose variables are the masses \(x_{t,B}\). It has exponentially many bundle variables, but its pricing problem has a simple structure under three utility values.

Given resource shadow prices, pricing asks for the cheapest bundle meeting a utility threshold. Partition the resources for type \(t\) into the three utility classes. For every possible number of selected resources from each class, choose the cheapest resources in those classes. Enumerating the three counts gives a polynomial-time pricing algorithm; the strict-improvement columns are handled by the same calculation with a strict threshold. Standard column-generation or separation machinery should therefore solve the LP in polynomial time in \(m\), \(\tau\), and the encoding length.

This is exactly the kind of dissolution the programme is looking for: the discrete SAT hardness is encoded through the identities of individual agents and the integral assignment, whereas the continuous version replaces those identities by mass flow between finitely many complete types. The three-value restriction makes the resulting pricing problem especially promising. The expected classification is therefore Class A, with Theorem 3’s coNP-hardness disappearing in the population continuum.

The mirror covers Theorem 3 only. It does not claim that every result in the paper has a useful continuum analogue. It also generates natural follow-up questions: whether unrestricted additive values make pricing knapsack-hard and produce a Class C problem; whether the result changes when agents may receive multiple copies of a resource kind; and how exactly a continuous solution rounds to a \(K\)-agent allocation.

My weakest point is that the mirror must scale the resource supply and treat repeated copies of a good as one resource kind. A critic could say that the paper’s original objects are individually named and that the three-value pricing argument is a restriction rather than a theorem about the full additive model. I accept that limitation. But it is the honest high-multiplicity regime: the underlying question remains Pareto-improving reallocation of indivisible bundles under additive utilities and initial endowments, while only the population is replaced by mass. The fact that the original SAT gadget does not itself consist of repeated types is not a defect; the programme asks whether this problem has a sensible high-multiplicity regime, not whether every discrete reduction survives it unchanged.