| paper | Best of Both Worlds: Agents with Entitlements |
| authors | — |
| venue | AAMAS 2023 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given rational binary-encoded agent types \(\Theta\) with masses \(\mu_\theta\), entitlements \(\lambda_\theta\) satisfying \(\sum_\theta \mu_\theta\lambda_\theta=1\), additive values \(v_\theta(h)\), tie orders, and homogeneous good classes \(h\in H\) with per-capita supplies \(\sigma_h\), construct a finite-support lottery over integral bundle-population allocations \(z_{\theta,B}\), where \(B\in\mathbb{Z}_{\ge 0}^{H}\), preserving type masses and good supplies, such that type-representative marginals satisfy ex-ante \(\mathrm{WSD\text{-}EF}\) and every positive-mass realization satisfies \(\mathrm{WPROP1}\) and \(\mathrm{WEF}(1,1)\) for every relevant pair of agents.
A high-multiplicity fair-division market with agent types carrying \(\bigl(v_\theta,\lambda_\theta,\text{tie order}\bigr)\), population masses \(\mu_\theta\), and repeated homogeneous goods with supplies \(\sigma_h\). Decision variables are bundle-mass configurations \(z_{\theta,B}\) and lottery weights over feasible integral bundle populations; the primary objective is constructive feasibility, with welfare maximization as an optional extension.
A polynomially bounded type-compressed HUG decomposition and pricing method are unproved; without them, the mirror may require clone expansion or exponentially many bundle configurations.
fatal: False
The mirror covers Theorem 2’s additive-entitlement lottery, including DSE, ex-ante \(\mathrm{WSD\text{-}EF}\), ex-ante \(\mathrm{WEF}\), ex-post \(\mathrm{WPROP1}\), and ex-post \(\mathrm{WEF}(1,1)\). It leaves Theorem 4, the general-valuation impossibility and extension results, and most auxiliary propositions outside the proposed mirror.
My strongest case is a narrow one: the paper’s Theorem 2, proved here, has a credible high-multiplicity population mirror. The theorem states that, for additive valuations and entitlements, one can compute in strongly polynomial time a lottery that is ex-ante WSD-EF and ex-post WPROP1 plus WEF\((1,1)\). I would call the mirror Entitled-BoBW\(_\infty\). I would not stretch the claim to the paper’s group-fairness result, Theorem 4, whose coalition structure creates a substantially harder compression issue.
The regime is a large allocation market with many interchangeable agents and many repeated indivisible goods. Think of a national programme distributing copies of a finite catalogue of equipment bundles to millions of schools, households, or departments. There are finitely many complete agent types \(\Theta\). A type \(\theta\) specifies an additive valuation \(v_\theta(h)\) for each good class \(h\), its entitlement parameter \(\lambda_\theta\), and its tie-breaking order. Agents of the same type are interchangeable in every respect used by the problem.
The instance is \((\Theta,\mu,\lambda,H,\sigma,v)\), where \(\mu_\theta\) is the population mass of type \(\theta\), \(\sum_\theta\mu_\theta=1\), and \(\sigma_h\) is the supply of good class \(h\) per unit population. The total per-capita supply is \(R=\sum_h\sigma_h\). Entitlements satisfy \(\sum_\theta\mu_\theta\lambda_\theta=1\). The interpretation is exact under cloning: for any denominator-clearing integer \(N\), create \(N\mu_\theta\) agents of type \(\theta\), \(N\sigma_h\) interchangeable copies of \(h\), and give each type-\(\theta\) agent weight \(w_{\theta,N}=\lambda_\theta/N\). Thus the continuous instance is not fractional goods allocation. It is the normalized description of a finite fair-division instance with repeated agents and repeated indivisible goods.
A deterministic population allocation assigns a mass \(z_{\theta,B}\) of type-\(\theta\) agents an integral bundle \(B\in\mathbb Z_+^H\). It must satisfy \(\sum_Bz_{\theta,B}=\mu_\theta\) and \(\sum_{\theta,B}z_{\theta,B}B_h=\sigma_h\) for every good class \(h\). A lottery is a finite-support distribution over such deterministic allocations. Its marginal \(X_{\theta h}\) is the expected number of copies of \(h\) received by a representative type-\(\theta\) agent.
The continuous problem is:
Find a finite-support lottery \(L\) over integral bundle allocations such that, for every pair of types \(\theta,\phi\), every value threshold \(a\), and every support allocation, the following hold.
First, ex-ante WSD-EF requires
\(\lambda_\phi\sum_{h:v_\theta(h)\ge a}X_{\theta h}\ge \lambda_\theta\sum_{h:v_\theta(h)\ge a}X_{\phi h}\).
Second, every positive-mass agent with bundle \(B\) must satisfy WPROP1: for some good class \(h\),
\(v_\theta(B+e_h)\ge \lambda_\theta\sum_{h'}\sigma_{h'}v_\theta(h')\).
Third, every pair of positive-mass bundle cells \(B\) and \(B'\), belonging respectively to types \(\theta\) and \(\phi\), must satisfy WEF\((1,1)\): either \(B'\) is empty or there is some \(h\) with \(B'_h>0\) such that
\(\lambda_\phi\bigl(v_\theta(B)+v_\theta(h)\bigr)\ge \lambda_\theta\bigl(v_\theta(B')-v_\theta(h)\bigr)\).
The objective is constructive feasibility: output such a lottery, rather than merely asserting that one exists. A natural optimization extension would maximize expected utilitarian welfare subject to these same constraints, but that is not needed for the mirror of Theorem 2.
The paper supplies a recognizable candidate algorithm. Run DifferentSpeedEating on the population masses: type \(\theta\) eats its most preferred available good at aggregate speed \(\mu_\theta\lambda_\theta\). When a good class is exhausted, all affected types move to their next available class. This produces a type-level fractional allocation \(X\). The paper’s Proposition 2 proves WSD-EF for this construction, and Proposition 3 derives ex-ante WEF. The remaining step is a population version of the paper’s HUG-decomposition: decompose \(X\) into finitely many integral bundle populations while preserving the column quotas and each type’s valuation-prefix quotas. The paper’s Theorem 1, cited from Budish et al., is the decomposition ingredient; Theorem 2 is the authors’ own proved result.
I expect this mirror to be Class A in the natural finite-catalogue regime, especially when the per-capita number of goods and the per-agent bundle size are bounded. DifferentSpeedEating has only finitely many type and good-exhaustion events, and the WSD-EF constraints are threshold inequalities over types and good classes. The interesting algorithmic question is whether the HUG decomposition can be performed directly on type and mass data, without expanding the denominator-cleared clone population. That is precisely the kind of configuration-LP or structured-decomposition problem that continuous optimization makes visible.
The authors should recognize this as their problem. For rational data, clearing denominators gives a literal finite instance of their fair-division model; conversely, any finite instance consisting of repeated valuation-and-entitlement types maps back to \(\mu\), \(\sigma\), and \(\lambda\). The paper’s “eating” process already reasons in aggregate speeds, and its lottery is already a convex combination of integral allocations. The mirror changes the population axis while retaining additive utilities, entitlements, indivisible bundles, and the exact ex-ante/ex-post fairness notions.
The main further questions are whether a type-compressed HUG decomposition always has polynomial support; whether its pricing problem is polynomial for arbitrary binary-encoded \(\sigma\); and what rounding guarantee relates a continuous solution to an \(N\)-agent clone instance. A natural boundary question is whether the construction survives more expressive valuations. The paper’s Theorem 5 suggests a sharp negative direction there, while Theorems 6 and 7 suggest restricted positive extensions.
My weakest point is the repeated-good assumption. If the paper is read as being about arbitrary named goods, replacing them by homogeneous good classes changes the regime. I think that is a legitimate high-multiplicity scenario, but it must be stated explicitly. The second vulnerability is the ex-post lottery: a marginal matrix alone is insufficient, because it does not preserve WPROP1 or WEF\((1,1)\) in every realization. If the required type-level integral decomposition turns out to require expanding an enormous clone population, the mirror remains a faithful high-multiplicity reformulation but not yet a polynomial continuous algorithm. That is a real open technical point, not something I would hide.
The strongest negative case is that the proponent has not yet supplied a continuous algorithmic theorem, only a plausible clone-normalized formulation.
The paper’s Theorem 2 is about a finite matrix with one row per named agent and one column per indivisible good. Its HUG decomposition imposes valuation-prefix constraints separately on every agent. Aggregating identical agents does not preserve those constraints automatically: an aggregate prefix quota can be satisfied by giving all high-valued goods to one submass and none to another. The latter agents may then violate WPROP1 or WEF\((1,1)\), although the type-level average looks correct.
There are only two obvious repairs. Keeping the clone rows preserves the theorem exactly, but the algorithm then runs in time polynomial in the expanded population \(N\), not in the binary description of \(\mu\) and \(\sigma\). Collapsing the rows requires a configuration formulation whose variables are bundle types \(B\). There may be exponentially many such bundles, and the ex-post conditions are disjunctive and support-dependent: for every pair of bundles one must certify the existence of a suitable good. The paper proves no type-compressed decomposition theorem or pricing oracle for this problem. Thus the claimed mirror is not yet a result; its central algorithmic step is precisely the unresolved part.
A second objection concerns what must be scaled. If the paper’s finite set of goods remains fixed while the population grows, total supply per capita vanishes. Almost every agent has the empty bundle, while the exceptional agents receiving goods have zero population mass. The ex-post guarantees then either disappear from the positive-mass model or become largely vacuous. To obtain a nondegenerate limit, the proponent scales the supply of goods as well and introduces homogeneous good classes. That is a sensible allocation-market model, but it is a substantive re-modelling of both sides of the instance, not merely a continuum population replacing named agents.
These objections do not defeat the stronger version of the mirror. Repeated schools receiving copies of a finite catalogue, for example, are a legitimate high-multiplicity regime. Denominator clearing gives a faithful finite clone instance, and the population version retains indivisible individual bundles rather than making goods divisible. Nor is this “already continuous” merely because the original paper uses fractional allocations and lotteries: that would be the wrong objection.
Consequently, the universal negative case is weak. Theorem 2 is a named computational result, the agents can genuinely be repeated, and the missing type-compressed decomposition is exactly the sort of new computational question ChoCo is meant to expose. The proper negative conclusion is only that the proponent has established a credible research direction, not a completed Class A mirror. I cannot honestly argue that no worthwhile continuous mirror exists.
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.