| paper | d4-conf-wine-2020-0026 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
Given a number-equivalent population scale \(N\), \(d\) good categories with \(Nq_g\) integral copies of category \(g\), a rational type distribution \(\mu\) over \(\tau\) complete valuation types, and monotone subadditive valuations \(v_t(b)\) on integral bundles \(b\), characterize the worst-case ratio between unrestricted maximum welfare and maximum EF1 welfare, and determine the complexity of computing a maximum-welfare EF1 allocation. In the mass model, variables \(x_{t,b}\ge 0\) satisfy \(\sum_b x_{t,b}=\mu_t\) and \(\sum_{t,b}x_{t,b}b_g=q_g\); EF1 must hold between every pair of positive-mass type-bundle configurations. Give the price and algorithmic bounds in \(N,d,\tau\), and input bit length \(L\), for scaled and unscaled valuations.
A society is a distribution \(\mu\) over complete valuation types. Each type’s mass is divided among integral bundle configurations \(b\), with \(x_{t,b}\) denoting the mass of type \(t\) receiving bundle \(b\). Total mass is \(\mu_t\) per type and total supply is \(q_g\) per category. Maximize \(W(x)=\sum_{t,b}x_{t,b}v_t(b)\) subject to support-wide EF1; compare this optimum with unrestricted maximum welfare.
It covers the EF1 price theorem and poses a continuous welfare-computation analogue of Lemma 4. It leaves the paper’s MMS result, Prop1 corollary, and supermodular appendix aside.
The strongest mirror I would defend is Continuous EF1 Welfare. The paper’s anchor is Theorem 1, proved in part here and in part using prior work: EF1 has price \(O(\sqrt n)\) for scaled subadditive valuations and \(O(n)\) for unscaled subadditive valuations; both bounds are tight even for additive valuations. The upper bounds are achieved by efficient algorithms. The scaled lower bound is due to Bei et al. (2019); the paper proves the upper bounds and the unscaled lower bound. As a constructive piece, Lemma 4 gives a polynomial-time algorithm for scaled subadditive valuations that returns an EF1 allocation with welfare at least \(\mathrm{OPT}/(12\sqrt n)-1/6\).
Here is a concrete continuous version. A large municipal programme distributes replicated categories of goods—say, standardized equipment or household kits—to a population with a small set \(T\) of complete valuation types. The type distribution is \(\mu\), with \(\sum_t\mu_t=1\); the number-equivalent population scale is \(N\). There are \(d\) good categories, with \(Nq_g\) copies of category \(g\), where the supplies are integral. Every person of type \(t\) has the same monotone subadditive valuation \(v_t(b)\) for an integral bundle \(b\in\mathbb Z_{\ge0}^d\). Thus each type has mass \(\mu_t\), and the supply per person is \(q_g\). For the scaled variant, normalize each type’s value for the full stock to \(1\).
The decision variable is \(x_{t,b}\ge0\): the mass of type \(t\) receiving bundle \(b\). It must satisfy \(\sum_b x_{t,b}=\mu_t\) and \(\sum_{t,b}x_{t,b}b_g=q_g\) for every category \(g\). Require EF1 across the support: whenever \(x_{t,b}>0\) and \(x_{s,d}>0\), then, if \(d\ne0\), some category \(g\) with \(d_g>0\) must satisfy \(v_t(b)\ge v_t(d-e_g)\). The welfare is \(W(x)=\sum_{t,b}x_{t,b}v_t(b)\). The problem is to compute a welfare-maximizing EF1 mass allocation and determine the price, \(W^*/W^*_{\mathrm{EF1}}\), as a function of \(N\), \(d\), support size \(\tau=|T|\), and input bit length \(L\). Bundles stay integral; only the mass assigned to each bundle is fractional.
I would expect the scaled price to remain \(O(\sqrt N)\), with the unscaled analogue \(O(N)\), and I would target a Class A algorithm polynomial in \(d,\tau,L\), using demand access for general subadditive types. There is a plausible configuration-LP route: for each type \(t\), let \(\ell_t\) be its least utility among bundles assigned positive mass. EF1 then requires every assigned bundle \(d\) to satisfy \(v_t(d-e_g)\le\ell_t\) for some removed good, for every type \(t\). Once the thresholds are fixed, admissible bundle configurations give a linear optimization problem over the masses \(x_{t,b}\). Searching thresholds and pricing new configurations are the substantive algorithmic questions. The paper’s finite-agent algorithms make this a natural target, but do not settle those steps.
The authors should recognize this as their problem: the society is the continuous object, agent types retain complete valuations, each unit of mass receives an integral bundle, and the output remains EF1. Replicated good categories and per-capita supplies are the co-modification needed to make the high-multiplicity regime meaningful. It is the same fairness-versus-welfare question, not continuity of the goods or of the outcome.
The soft spot is that Theorem 1’s proof uses a finite set of named agents and an optimal allocation that orders the individual goods into a line. That construction does not automatically become an algorithm on type masses, and the discrete lower bound may not survive fractionalizing assignments within types. So the price rate itself is an open part of the mirror: does it remain \(\Theta(\sqrt N)\), improve to a function of \(d\) or \(\tau\), or become bounded? The result covers the paper’s EF1 price theorem, not its MMS result or its broader valuation questions.
The strongest case against this anchor is that the proposed continuum problem has no single canonical scaling. If the number of goods stays fixed as the population grows, per-person supply vanishes. If supplies grow with the population, one-good EF1 slack may become negligible under scaled valuations, and the bundle domain grows with the chosen population scale. The paper’s \(\Theta(\sqrt n)\) result therefore does not identify what the continuous analogue’s parameter or fairness tradeoff should be.
There is also a mismatch between the result and the proposed task. Theorem 1 bounds a worst-case welfare ratio; Lemma 4 constructs one EF1 allocation with a welfare guarantee. Neither computes the welfare-maximizing EF1 allocation or determines the price for a given continuous instance. In the mass model, EF1 becomes a support-wide constraint between integral bundle configurations, with a disjunction over which good is removed. That is a new algorithmic problem, not a direct continuation of the paper’s algorithm.
These points weaken the proposed formulation, but they do not defeat the anchor. A municipality distributing replicated kits to a large population with a small set of complete valuation types is a credible high-multiplicity regime. Scaling kit supplies with population is a natural co-modification, and assigning fractional mass to configurations of integral bundles preserves individual EF1 comparisons. The resulting support-constraint problem may be hard, but mapping its complexity would itself fit the programme.
So I cannot honestly make the requested universal negative case here. The mirror needs a sharper statement of its scaling assumptions and computational target, but continuous EF1 welfare remains a worthwhile question.
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.