| paper | Nearly Equitable Allocations beyond Additivity and Monotonicity |
| authors | — |
| venue | AAAI 2024 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3
Given rational type masses \(\mu\) over finitely many WWL monotone valuation types, a finite catalogue \(G\) of indivisible item classes with rational per-capita supplies \(q\), and integral bundles \(S \subseteq G\), output a finite-support rational allocation \(y_{t,S}\) satisfying \(\sum_S y_{t,S} = \mu_t\), \(\sum_{t,S:g \in S} y_{t,S} = q_g\), and, for every occupied \((t,S),(u,R)\) and every \(g \in R\), \(v_u(R \setminus \{g\}) \le v_t(S)\).
A high-multiplicity configuration model: valuation types \(t\) carry mass \(\mu_t\); bundle configurations \(S\) receive mass \(y_{t,S}\); item classes have per-capita supplies \(q\); the objective is to find any support-level EQx allocation, with WWL structure enabling the proposed algorithmic study.
The support-level EQx predicate is discontinuous when bundle mass reaches zero, and the paper supplies no compression or separation theorem for the exponentially many bundle configurations, leaving the claimed Class A status unsubstantiated.
fatal: False
The mirror covers Theorems 3 and 5; it leaves the paper's nonexistence result, specialized existence results, and other computational guarantees untreated.
The strongest positive case is a high-multiplicity population version of the paper’s all-goods setting. My lead anchor is Theorem 3, proved in this paper: for monotone weakly well-layered valuations, Algorithm 1 computes an EQx allocation in polynomial time.
The natural regime is a large institution allocating repeated indivisible benefits: training slots, permits, desirable shifts, equipment packages, or other standardized entitlements. There are \(N\) agents but only \(\tau\ll N\) complete valuation types. A type includes the entire valuation function, eligibility, and all other parameters relevant to fairness. Thus agents of one type are genuinely interchangeable. The paper’s own connection to “few agent types” supports this regime.
To obtain a nondegenerate limit, the stock of items scales with the population too. Let \(G=\{g_1,\ldots,g_m\}\) be a finite catalogue of item classes, and let \(q_g\in\mathbb Q_{\ge0}\) be the number of physical copies of \(g\) per unit population. A finite realization with population \(N\) has \(N\mu_t\) agents of type \(t\) and \(Nq_g\) indivisible copies of \(g\). Each agent still receives an integral bundle \(S\subseteq G\); there is no fractional item and no lottery for an individual.
The continuous allocation variable is
\[ y_{t,S}\ge 0, \]
the mass of type-\(t\) agents receiving bundle \(S\). It must satisfy
\[ \sum_{S\subseteq G}y_{t,S}=\mu_t \]
for every type \(t\), and
\[ \sum_{t}\sum_{S\ni g}y_{t,S}=q_g \]
for every item class \(g\). A solution is a finite-support rational list of positive \(y_{t,S}\)'s satisfying these constraints and the EQx condition. The objective is the paper’s constructive one: find any fair allocation, with no welfare objective added.
For every pair of occupied cells \((t,S)\) and \((u,R)\), and every good \(g\in R\), require
\[ v_u(R\setminus\{g\})\le v_t(S). \]
This is exactly EQx: removing any good from any recipient’s bundle makes that recipient no richer than every other agent. The only continuous object is the distribution of agents over integral bundles.
I expect this problem, which I would call WWL-EQx\(_\infty\), to be in Class A. The key reason is structural rather than merely numerical. The proof of Theorem 3 shows that under weakly well-layered valuations the Fix phase of the Add-and-Fix algorithm never executes. Bundles grow greedily, and identical agents can be processed in mass rather than one named agent at a time. A continuous algorithm should be able to move mass between successive greedy bundle states, using a threshold or configuration formulation. The relevant pricing primitive is the same greedy marginal-value operation that drives the paper’s proof. Gross-substitutes, weighted matroid-rank, budget-additive, and related valuation classes make this a credible institutional model rather than an artificial tractable restriction.
My second anchor is Theorem 5, also a result of this paper rather than a cited theorem; its conference-version proof is omitted but the result is established in the full version. It gives a polynomial-time algorithm for a \((1-\varepsilon)\)-approximately EQx allocation under arbitrary monotone valuations.
The corresponding continuous problem, Approx-EQx\(_\infty(\varepsilon)\), has the same \(\mu\), item supplies, and type valuations as above, but does not assume WWL structure. Its required condition is, for every occupied \((t,S)\), every good \(g\in S\), and every other occupied \((u,R)\),
\[ (1-\varepsilon)v_t(S\setminus\{g\})\le v_u(R). \]
The objective is again to output any aggregate allocation \(y\) satisfying the supply constraints and this approximate fairness condition. I expect this version to remain in Class A, probably with an FPTAS-like dependence on \(1/\varepsilon\), because the multiplicative slack should make it possible to split type mass at value thresholds without resolving exact equalities. The continuous analogue of the paper’s approximate Add-and-Fix argument is a plausible starting point.
The mirror covers Theorems 3 and 5, not the whole paper. I would not use Theorem 7 as an anchor because it is specifically a two-agent result, and Theorems 9 and 10 are primarily existence results rather than efficient computational results. Theorem 6 is an important boundary case—subjective nonmonotone valuations can make EQx nonexistent and deciding existence is NP-hard—but its two-agent PARTITION reduction is a weaker population-continuity anchor. It may become a Class B boundary for a repeated-item version, but it is not needed for the positive case.
The main weakness is that the mirror must scale item stock along with population. If one keeps the paper’s finite item set fixed while sending the number of agents to a continuum, almost every agent receives nothing and EQx degenerates. So this is not simply “replace \(n\) by a measure”: it is a high-multiplicity fair-division regime with repeated item classes. That is a real modelling obligation, and the continuous algorithm is not automatic—the paper’s polynomial bound depends on named agents and numeric values, while the aggregate problem may have exponentially many bundle configurations.
Nevertheless, the mirror remains faithful: agents are still divided into bundles of indivisible items, valuations are still evaluated on those bundles, and the fairness predicate is unchanged. The further questions are exactly the useful ones for ChoCo: whether WWL structure gives a polynomial column-generation or threshold algorithm; whether general monotone exact EQx is continuum-specifically hard; and how an aggregate solution rounds to a finite \(N\)-agent allocation with controlled additive EQx error.
The strongest case against both anchors is that the proposed mirrors are not actually inherited from the paper’s theorems; they are new high-multiplicity configuration problems.
For Theorem 3, if the item set remains fixed while the population grows, the limit degenerates: only a vanishing fraction of agents can receive items, so almost everyone has the empty bundle and EQx loses its substantive content. The proponent avoids this by scaling item supplies with population. That is defensible, but it changes the model on both sides: it is no longer merely a continuous population version of the paper’s finite-item problem, but a new economy with per-capita resource supplies and bundle configurations.
The difficulty is not cosmetic. The proposed EQx condition is a support condition on \(y_{t,S}\). A bundle occupied by mass \(10^{-6}\) imposes exactly the same constraints as one occupied by mass \(0.4\), while mass zero removes all its constraints. Thus the predicate is discontinuous in the population distribution. A finite allocation containing one exceptional agent still has to satisfy EQx, but that agent disappears in the continuum limit. Interpreting EQx almost everywhere changes the fairness notion; requiring it on every occupied bundle preserves the discrete notion but makes support selection itself the central combinatorial problem.
Theorem 3’s proof gives no compression principle for that problem. Its running time is polynomial because it processes named agents one by one, repeatedly selecting a poorest agent and greedily adding individual items. In the proposed model, one must batch masses moving through potentially exponentially many bundle states. The greedy marginal operation for one current bundle is not a pricing oracle for the resulting configuration problem. WWL structure may eventually yield such an oracle, but that is a new theorem, not a consequence of Theorem 3.
Theorem 5 is an even weaker anchor. Its stated bound is linear in the explicit number \(n\) of agents. A continuous input would encode type masses and item supplies in binary; \(N\) may be exponentially larger than the input. Simulating \(N\) agents is therefore not a high-multiplicity algorithm. Moreover, “arbitrary monotone valuations” are supplied through value oracles over \(2^M\), not as compact valuation types. Once agents are aggregated, the algorithm must solve over exponentially many bundles without any separation or column-generation result supplied by the paper. Calling the result “FPTAS-like” at the mass level is speculation.
One can repair this by restricting to compact valuation classes and by defining support-level EQx over repeated item classes. But then Theorem 5’s arbitrary-monotone result is no longer the anchor; one has designed a new structured fair-division problem. That problem may be worthwhile, but the paper does not establish its computational relevance.
This negative case is not airtight. Repeated training slots or permits, finitely many complete valuation types, and item supplies scaling with population are genuinely plausible high-multiplicity scenarios. Rational aggregate allocations can also be expanded into finite replicated instances, so the mirror is mathematically coherent. The honest conclusion is therefore narrower: the proponent has not justified the claimed Class A mirrors from Theorems 3 and 5. A universal claim that no worthwhile mirror exists cannot be sustained; if the reader accepts the repeated-item regime, Theorem 3 remains a viable anchor.
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.