| paper | d4-conf-atal-2013-0046 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: polynomial-time solvable · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 7
statement extracted from the paper’s text layer
Given a finite good catalogue \(G\), type masses \(\mu_t\) summing to \(1\), an XOR utility \(u_t\), a current bundle \(A_t^0\), a required subset \(P_t\) for each type \(t\), and per-capita supplies \(b_g\), decide whether there are assignments \(y_{t,B}\ge 0\) to integral bundles \(B\subseteq G\) such that \(\sum_{B\supseteq P_t}y_{t,B}=\mu_t\) and \(\sum_{t,B:\,g\in B}y_{t,B}\le b_g\), with \(\mathcal L_y(q)\ge\mathcal L_x(q)\) for every \(q\in[0,1]\) and strict inequality for some \(q\). Here \(\mathcal L_y(q)\) is the total utility of the poorest \(q\)-fraction under \(y\), and \(\mathcal L_x\) is the corresponding curve for the current bundles.
A finite-support population of XOR-valuation types, each carrying mass \(\mu_t\), with decision variables assigning that mass among integral household bundles. Bundle use is bounded by per-capita supplies, and the decision criterion is Lorenz dominance over the current allocation.
The polynomial pricing sketch still needs to show that a reduced-cost minimizer can be represented by the required bundle together with a listed XOR bid, including when the required bundle already triggers a higher-weight bid; this challenges the Class A prediction, not the mirror’s formulation.
fatal: False
The mirror covers Proposition 7’s XOR Lorenz-improvement result. It leaves the Pigou-Dalton results, other preference languages, and the Gini and Robin Hood optimization formulations outside its scope.
I think the strongest honest mirror is a continuum Lorenz Improvement problem for XOR valuations. Consider a large public programme distributing indivisible household goods from a standard catalogue: for example, routers, heating devices, or accessibility equipment. There may be millions of households but only a moderate number \(\tau\) of recurring valuation and allocation profiles. A type \(t\) records the household’s complete XOR utility function, its current bundle, and any bundle commitments imposed by a partial allocation. Its mass \(\mu_t\) is the fraction of households of that type. Each catalogue good remains indivisible for each household; its stock is replicated with the population, at a fixed per-capita supply \(b_g\).
Here is the proposed decision problem. An instance gives the finite good set \(G\); rational type masses \(\mu_t\) summing to \(1\); each type’s utility \(u_t\), current bundle \(A_t^0\), and required subset \(P_t\); and per-capita supplies \(b_g\). A candidate allocation is a mass assignment \(y_{t,B}\ge 0\): the mass of type \(t\) receiving the whole bundle \(B\subseteq G\). It must satisfy
\[
\sum_{B\supseteq P_t} y_{t,B}=\mu_t
\quad\text{and}\quad
\sum_{t,B:\,g\in B} y_{t,B}\le b_g .
\]
Let \(\mathcal L_y(q)\) be the total utility of the poorest \(q\)-fraction of the population under this assignment, defined by integrating the utility quantile function; let \(\mathcal L_x\) be the corresponding curve for the current bundles \(A_t^0\). The question is whether there is a feasible \(y\) such that \(\mathcal L_y(q)\ge\mathcal L_x(q)\) for every \(q\in[0,1]\), with strict inequality for at least one \(q\). The answer is yes or no, and a yes-instance has a feasible mass assignment \(y\) as witness. Mass can split among bundles, but every household represented by each mass receives an integral bundle.
The anchor is Proposition 7, proved in this paper: *“Lorenz Improvement is NP-complete for the XOR-language.”* In full, the paper’s problem takes a scenario \(\langle N,G,U\rangle\), an allocation \(A\), and a partial allocation \(P\), and asks whether there exists an allocation \(A'\) extending \(P\) such that \(L(A)<L(A')\)—that is, every cumulative utility of the poorest \(k\) agents weakly increases and at least one strictly increases. The paper proves NP-membership directly and proves NP-hardness by reduction from threshold utilitarian-welfare optimization for XOR, cited as NP-hard in [19, Theorem 12.1]. So Proposition 7 is the paper’s result; the welfare-hardness fact it uses is cited prior work.
My expected outcome for the continuous problem is Class A: tractable, in time polynomial in the number of goods, types, listed XOR bids, and input bit length. The reason is specific to this mirror, not a claim that indivisible allocation is generally easy. Write
\[
D_y(z)=\sum_{t,B}y_{t,B}\bigl(z-u_t(B)\bigr)_+ .
\]
The continuum Lorenz condition is equivalent to \(D_y(z)\le D_x(z)\) for every \(z\). These are linear constraints in \(y\); only finitely many \(z\)-values need checking, namely the utility values in the baseline and the listed XOR bids. Strict improvement can be captured by requiring positive total slack across those constraints. This gives an LP with a variable for each type-bundle pair, potentially exponentially many in \(|G|\).
That LP points to the same algorithmic bottleneck emphasized by the programme: pricing. For a type and a fixed XOR utility level \(w\), any bundle attaining \(w>0\) contains a listed bid set of weight \(w\). Under nonnegative resource prices, adding goods beyond a minimal such bundle cannot improve its reduced cost. A pricing oracle can therefore check the listed bids (together with the type’s required subset and its outside option), rather than search all \(2^{|G|}\) bundles. This is the proof route I would ask a prover to establish, including the bit-complexity details. It makes the continuous problem a concrete candidate for an exponential-column LP with tractable pricing.
The mirror covers Proposition 7’s XOR Lorenz-improvement result, not the paper’s other complexity claims or its Gini and Robin Hood optimization formulations. A finite election-like allocation with \(N\) households and \(n_t\) members of each type maps to masses \(\mu_t=n_t/N\); goods counts map to per-capita supplies. Conversely, rational mass assignments can be realized by taking a sufficiently large population whose size clears their denominators. The natural next questions are how much rounding error arises at a prescribed finite population size, how the complexity changes for other preference languages, and whether the proposed XOR pricing argument yields an exact polynomial-time algorithm.
The soft spot is that this mirror changes the resource regime: the paper studies a finite set of goods among named agents, while this model replicates standardized goods with population size and permits mass to divide among bundle choices. That can remove the discrete assignment choices responsible for the paper’s hardness. I think the mirror is still recognizable as the authors’ problem because it keeps the same XOR utilities, integral household bundles, partial-allocation commitments, and Lorenz criterion; it changes the population and resource scale in the way a high-multiplicity version requires. The case depends on that regime being a plausible one for the application, not on claiming that Proposition 7’s hardness transfers.
I can’t honestly defeat the anchor. Proposition 7 is a named complexity result about precisely the kind of allocation question the programme targets: whether an allocation admits a Lorenz improvement. That makes “no computational result to mirror” unavailable here.
The best objection is that the proposed mirror scales the supply of goods with the population. If the goods are unique objects from a fixed stock, that changes the economic problem substantially. But the stronger version survives: take a repeated allocation setting with a standard catalogue of goods, recurring household types, and per-capita stock. Each household still receives an indivisible bundle; only the population and inventory scale. The programme explicitly allows that co-modification, and it is a plausible regime for public provision or standardized equipment.
Nor does the Lorenz criterion lose its meaning in that regime. It compares the lower-tail utility of fractions of the population, so the aggregate curve remains informative when individual agents have measure zero. Recording preferences, current bundles, and commitments in each type preserves the relevant information; varying assignments within a type does not require tracking identities.
The proposed pricing argument may need a careful proof, especially around which bundles can be discarded and how strict improvement is represented. That is a technical challenge to the proposed algorithm, not a reason the continuous question is ill-posed. The paper’s XOR utilities give a finite list of relevant utility levels, and bundles can often be reduced to required items plus a listed bid that attains their utility. I don’t see a fundamental obstacle that survives the replicated-goods setting.
So the negative case is weak: the fixed-stock interpretation is a real limitation for some applications, but it does not defeat a better, recognizable high-multiplicity mirror of Proposition 7. I would report that this anchor survives the case against.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.