d4-conf-atal-2009-0016

A credible mirror exists in a large benefit-distribution setting: a public authority assigns standardized, indivisible items to millions of households, while only a modest number \(\tau\) of complete preference types occur. A type specifies a household’s utility for every bundle. Let \(R\) be the item classes, and let \(q_r\) be the per-household supply of class \(r\); at population scale \(n\), there are \(nq_r\) interchangeable copies. A household still receives an integral bundle \(B\subseteq R\). Only the *fraction* of a type receiving each bundle is continuous.

Write \(\mu_t\) for type \(t\)’s population share, and \(x_{tB}\) for the population share of type \(t\) receiving bundle \(B\). Feasible allocations satisfy
\[ x_{tB}\ge 0,\qquad \sum_{B\subseteq R}x_{tB}=\mu_t,\qquad \sum_{t}\sum_{B:r\in B}x_{tB}=q_r. \]
Thus no household gets a fractional item. The continuous variables describe how a large cohort is divided among whole-bundle assignments. A finite instance with matching rational shares and supplies gives grid-valued \(x\); the mirror allows any feasible proportions.

There is an important limit on what the paper itself anchors: it has no numbered theorem asserting a complexity classification such as NP-hardness or polynomial-time solvability. Its introduction discusses complexity in general, but that is not a named result I can use as an anchor. The anchors below are the authors’ own computational formulation theorems; their proofs are omitted for space.

My lead is Theorem 2 (OPTIMISATION). It states that for the paper’s listed cardinal preference forms—bundle, \(k\)-additive, logic-based, and weighted goals—and its four listed welfare functions—utilitarian, egalitarian, elitist, and Nash-product—the ASP encoding represents exactly the globally welfare-optimal allocations: every optimal allocation is represented by an optimal answer set, and every optimal answer set decodes to an optimal allocation. I rely on its bundle-form, utilitarian case.

The corresponding continuous problem, Utilitarian Resource Allocation\(_\infty\), takes \(R\), rational shares \(\mu_t\), per-capita supplies \(q_r\), and each type’s utility \(u_t(B)\) for bundles \(B\subseteq R\). It asks for a feasible \(x\) maximizing
\[ \sum_t\sum_{B\subseteq R}x_{tB}u_t(B). \]
A solution is an optimal mass assignment \(x\), with each mass element assigned an integral bundle. The objective is the finite utilitarian welfare divided by population size when \(x\) is a finite empirical allocation, so the scale change preserves the optimization question.

I expect this mirror to be Class A when bundle utilities are given explicitly: it is an LP with \(\tau 2^m\) variables and \(\tau+m\) allocation constraints, polynomial in the expanded utility-table length. That qualification matters: this is not a claim of polynomial time in \(m\) for succinct valuations. The further question is whether the paper’s succinct preference languages admit efficient pricing or separation, so the LP can be handled without expanding every bundle. Other natural follow-ups are bounds on rounding an optimal \(x\) to a prescribed finite population and the dependence of those bounds on \(\tau\) and \(m\).

A second, distinct mirror uses Theorem 8 (OPTIMISATION). The paper states that for its listed cardinal preference forms, its weak-constraint encoding returns exactly the allocations minimizing total pairwise envy: every minimum-envy allocation is represented by an optimal answer set, and every optimal answer set represents a minimum-envy allocation. Again, this is the authors’ formulation result, not a cited complexity theorem.

For Pairwise Envy Minimization\(_\infty\), take the same instance and feasible \(x\). Define \([z]_+=\max\{0,z\}\). Ask for a feasible \(x\) minimizing
\[ \mathcal E(x)= \sum_{t,B}\sum_{s,C} x_{tB}x_{sC}\,[u_t(C)-u_t(B)]_+. \]
A solution is a globally minimizing mass assignment. This is the expected envy of one independently sampled household toward another. For a finite allocation with mass fractions \(x\), the paper’s total envy is \(n^2\mathcal E(x)\); self-comparisons contribute zero, so normalization preserves the finite optimum and gives a natural population-scale objective.

My provisional forecast is Class C: the pairwise objective is quadratic in the assignment masses, so the continuous problem is no longer the LP from the utilitarian mirror. That is a reason to investigate continuum-specific hardness, not a proof of it. The key questions are whether the envy coefficients have hidden convexity or other exploitable structure, and whether hardness from finite allocations survives the ability to split types fractionally.

The scope here is deliberately limited to Theorem 2’s cardinal utilitarian optimization and Theorem 8’s cardinal minimum-envy optimization. I am not claiming a mirror for all 66 encodings, the ordinal criteria, Pareto optimality, or the other problems the paper mentions.

The weakest point is the regime itself: it needs many interchangeable copies of each resource class and agents who share a complete utility function over bundles. If item identities matter or preference support grows with the population, the proposed high-multiplicity model may not fit. The paper’s resources are discrete and nonsharable, and this mirror preserves that at the household level; grouping repeated items into classes and scaling their stocks is the co-modification that makes the population continuous. The authors could reasonably recognize this as their allocation problem in a high-multiplicity regime, but neither continuous theorem is already in the paper: the LP and quadratic optimization questions are new computational questions suggested by its named results.