| paper | Fairness Concepts for Indivisible Items with Externalities |
| authors | — |
| venue | AAAI 2023 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | unclear |
Theorem 7.7 clearly supplies computational content, and Mass-GFS1 is a precise typed-population public-decision problem. However, the opponent correctly observes that replacing the paper’s per-agent 1/n entitlement by μ_t is not obtained by aggregating identical agents or taking a literal continuum limit. The paper’s public-decision motivation makes the extension plausible, but does not settle whether it remains the authors’ problem.
fails bit none — no continuous question survives
The proposed μ_t entitlement strengthens a type’s per-capita guarantee with its population mass, whereas every identical copy in the paper receives the same β_t/n guarantee and the atomless limit becomes vacuous.
fatal: False
It is undecided whether replacing per-agent 1/n by type-mass entitlement μ_t is a recognizable weighted extension of GFS1 or a new bloc-fairness axiom. An explicit author-recognizable weighted-GFS principle, or a faithful formulation retaining 1/n with a population-scale parameter, would settle it.
The proposed mirror covers only Theorem 7.7 and GFS1 in the public-decision setting; it leaves the EFX/EF1 results, nonexistence results, and fairness taxonomy untouched.
The strongest positive case is Theorem 7.7, which states that the authors’ Max-Min Round Robin algorithm computes a GFS1 allocation in polynomial time. This is proved by the authors here, with the detailed proof deferred to their full version (Aziz et al. 2022c), rather than being merely cited from prior work.
The natural mirror is not ordinary fair division with fractional items, but the paper’s own public-decision model. Imagine a city choosing one option for each of many discrete issues: school locations, zoning plans, infrastructure projects, or budget decisions. Millions of residents evaluate every issue-choice pair, but many residents have the same complete valuation vector. A type \(t\) is therefore the full vector \(v_t(a,q)\), giving that type’s value for every choice \(q\) of every issue \(a\). Its mass \(\mu_t\) is the fraction of residents of that type. The number of residents may be millions while \(\tau\), the number of distinct valuation types, is moderate.
The issues remain indivisible public decisions: exactly one choice is selected for each issue. Thus the population, and only the population, is continuized.
I would call the resulting problem Mass-GFS1 for Public Decisions.
An instance consists of:
For a policy \(\pi\in\prod_{a\in A}Q_a\), define
\[ u_t(\pi)=\sum_{a\in A}v_t(a,\pi(a)), \]
\[ \ell_t=\sum_{a\in A}\min_{q\in Q_a}v_t(a,q), \qquad \beta_t=\sum_{a\in A} \left(\max_{q\in Q_a}v_t(a,q)-\min_{q\in Q_a}v_t(a,q)\right). \]
The mass-weighted fair share of type \(t\) is
\[ \operatorname{MGFS}_t=\ell_t+\mu_t\beta_t. \]
A policy satisfies Mass-GFS1 if, for every positive-mass type \(t\), there exists an issue \(a\) such that replacing \(\pi(a)\) by \(t\)’s favourite choice gives that type at least its mass-weighted fair share:
\[ u_t(\pi)-v_t(a,\pi(a)) +\max_{q\in Q_a}v_t(a,q) \ge \operatorname{MGFS}_t. \]
The computational problem is: given the succinct typed society, output such a discrete policy, or report that none exists. This is a feasibility problem, just as Theorem 7.7 is; aggregate welfare \(\sum_t\mu_tu_t(\pi)\) could be used only as a tie-breaker.
This is recognisably the authors’ problem. Their GFS is explicitly introduced for public decision making, their \(\beta_i(a)\) is exactly the issue-level improvement quantity used above, and their GFS1 certificate is exactly a one-issue counterfactual. The only new ingredient is replacing equal individual entitlement \(1/n\) by population mass \(\mu_t\). That is the natural high-multiplicity interpretation: a large homogeneous constituency receives entitlement proportional to its mass. When every type is a singleton, \(\mu_t=1/n\), and the definition reduces exactly to the paper’s GFS1.
My expectation is Class A. Max-Min Round Robin already assigns each issue to a claimant and gives that claimant its best choice. Its proof relies on additivity and on the fact that one unclaimed issue can repair a type’s deficit. Those are precisely the features that survive type aggregation. The likely continuous result is a weighted, type-compressed version of the algorithm, or an equivalent small LP/assignment formulation, with running time polynomial in \(m\), \(\tau\), and the encoding length of the masses and values rather than in the expanded population size.
The main open questions are whether weighted Max-Min Round Robin always gives the stated guarantee for arbitrary rational masses, whether the weighted schedule can be implemented without expanding large denominators, and whether the resulting theorem yields an additive or rounding-preserving transfer back to finite elections.
The weakest point is important: the literal limit of the paper’s unweighted GFS1 as \(n\to\infty\) is degenerate, because \(1/n\) tends to zero. Mass-GFS1 is therefore a principled cohort-level continuation, not a theorem that follows automatically from taking an atomless limit. A hostile reader could say that the fairness unit has changed from an individual to a constituency. I think the mirror survives that objection because the paper itself motivates public decisions in terms of groups and shared interests, and because the weighted formulation is exactly what makes high multiplicity meaningful rather than trivial.
I would not try to mirror the paper’s fixed-two-agent and fixed-three-agent EFX/EF1 theorems as the main case: without a bloc interpretation, their population mass is largely decorative. Theorem 7.7 supplies the paper’s genuine many-agent, public-decision anchor and supports one precise, non-fractional continuous-population problem.
The proponent has chosen the paper’s strongest anchor. Theorem 7.7 is a named computational result, and the public-decision model can certainly contain large homogeneous constituencies. Thus the negative case cannot honestly rely on the absence of multiplicity or computational content.
The real problem is that \(\ell_t+\mu_t\beta_t\) is not the high-multiplicity version of GFS1. Suppose \(n_t\) identical agents have type \(t\), among \(n\) agents. In the paper, every copy imposes the same condition
\[ u_t(\pi)\ \text{(after one repair)}\ \ge \ell_t+\frac{1}{n}\beta_t. \]
The copies can therefore be compressed exactly into one constraint. Their multiplicity does not give the type a larger entitlement. Summing the original individual entitlements likewise produces a per-capita threshold of \(\ell_t+\beta_t/n\), not \(\ell_t+\mu_t\beta_t\).
The proposed formula instead turns population mass into collective political power: duplicating identical agents makes their fairness requirement stronger. That may be a defensible new bloc-fairness axiom, but it is not a continuation of the paper’s GFS1 notion. It changes the object from “every agent receives a proportional guarantee” to “a constituency receives a guarantee proportional to its size.” The paper supplies no principle selecting that reinterpretation over the alternatives: per-agent fairness, equal fairness among types, or aggregate group utility.
The literal atomless continuation is worse. Each individual has zero mass, so the \(1/n\) entitlement disappears. Since every policy already gives type \(t\) at least its worst-case value \(\ell_t\), GFS1 becomes vacuous: every policy satisfies the limiting condition. To obtain a nontrivial problem, one must introduce positive-mass cohorts and assign them collective entitlements. That is precisely the new normative axiom above, not a limit of the theorem.
The proponent can avoid a superficial objection by declaring valuation vectors to be canonical types, so identical residents cannot be artificially split. But that only makes the bloc interpretation well-defined; it does not make it faithful to Theorem 7.7. The resulting problem is a weighted public-decision problem inspired by GFS1, not the continuous mirror of the paper’s computational result.
This is not an airtight rejection: a researcher could reasonably decide that mass-weighted bloc fairness is the intended new model, especially for constituencies in public decision making. But that would be a worthwhile new fairness question only after importing a substantive group-entitlement principle. On the paper itself, the sole many-agent anchor has no nondegenerate, faithful population continuation.
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.