| paper | d4-conf-aaai-2024-1289 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3.4 (Upper Bound for Multiplicative Envy)
Given a finite set of complete valuation types \(\Theta\) with masses \(\mu\), an online item stream with values \(v_\theta(s)\in\{0\}\cup[\varepsilon,1]\), and per-capita supply scaled with population size, consider the fluid limit of the paper's greedy rule. Track a measure over individual bundle states, including each type's value for each agent's bundle, and route arriving item flow to states maximizing the paper's priority \(v_\theta(s)/u\). When every type has unbounded monopolistic utility, what is the supremal asymptotic multiplicative envy \(\operatorname*{ess\,sup}_{x,y} w_{\theta(x)}(y)/w_{\theta(x)}(x)\) over positive-mass states and admissible streams? Is it \(1+2\log(1/\varepsilon)\)?
A continuum of agents distributed over complete valuation-trajectory types \(\Theta\), with type masses \(\mu\). Items remain indivisible at the finite-population scale, while supply scales per capita and induces a flow of agents through individual bundle states in the limit. Each state records its own utility and the value each type assigns to its bundle; the flow follows the greedy priority rule. Measure worst-pair envy by the essential supremum over represented states.
A single agent of vanishing population mass could witness the finite model's maximum envy and disappear from the limiting measure; the proponent notes that a limit argument is needed but does not establish one. This leaves transfer of the precise bound and matching lower-bound stream uncertain.
fatal: False
The mirror concerns integral greedy's adversarial multiplicative-envy upper bound in Theorem 3.4 and asks whether the matching construction in Theorem 3.5 survives; it leaves the Nash-welfare bounds, seeded variant, and PACE results aside.
The strongest honest positive case is narrow: the paper has a pair of numbered results about worst-case online performance, but no numbered result classifying a problem as NP-hard, in P, or similar. The introduction mentions offline Nash-welfare APX-hardness only in unnumbered background prose. So this can be a mirror of the paper’s competitive analysis if that counts for ChoCo; it is not a standard computational-complexity anchor.
The best anchors are Theorem 3.4, proved in the paper, and Theorem 3.5, also proved there. Under Assumption 3.1—each agent’s total value grows without bound with the horizon, and each item value is either zero or in \([\varepsilon,1]\)—Theorem 3.4 bounds the first-order integral greedy algorithm’s multiplicative envy for every pair of agents by \(1+2\log(1/\varepsilon)+O(1/T)\), even with unequal weights. Theorem 3.5 proves the matching asymptotic lower bound: for every pair, the worst-case envy of greedy is at least \(1+2\log(1/\varepsilon)\). The paper’s two-agent construction establishes the lower bound. Together, these results say the asymptotic bound is tight. [Theorem 3.4 and Theorem 3.5 in the AAAI-24 paper](https://ojs.aaai.org/index.php/AAAI/article/download/28858/29632)
A plausible mirror is Continuous Cohort Envy for Online Greedy Allocation. Take a large population divided into two equal-mass cohorts, \(A\) and \(B\), with equal per-person budgets. A type is a cohort’s complete valuation trajectory: all members of \(A\) share values \(v_A(s)\), and all members of \(B\) share \(v_B(s)\), where each value is either zero or lies in \([\varepsilon,1]\). Think of a high-volume allocation service with many users in a few stable preference cohorts. To keep per-person utility meaningful as the population grows, scale the number of arriving unit items with population size.
The limit can preserve the paper’s integral assignments. Let \(\nu_\theta(s)\) describe the mass of type-\(\theta\) agents at each accumulated utility state. At each instant, the allocation flow assigns the arriving item to a mass of individual agents; each finite-population item still goes whole to one person. The continuous greedy rule selects recipients maximizing \(v_\theta(s)/u\), where \(u\) is that recipient’s accumulated utility. A state records enough of an individual’s bundle value to evaluate how a type-\(A\) agent values a type-\(B\) agent’s bundle. Define population envy as the worst such cross-type utility ratio, retaining the paper’s comparison of one agent’s value for another agent’s bundle with their own utility.
For Theorem 3.4, the prover’s question is whether this model’s worst-case asymptotic envy is at most \(1+2\log(1/\varepsilon)\). For Theorem 3.5, it is whether there is an admissible pair of cohort value streams attaining that lower bound. The combined problem is to determine the exact worst-case envy and give both a bound and a matching stream family. I would expect the same value, \(1+2\log(1/\varepsilon)\): the paper’s proof already reduces envy to a one-dimensional bound that approaches an integral as accumulated utility grows, and its lower-bound construction is built from just two agents. In ChoCo’s trichotomy this looks Class A-like, through continuous optimization and analysis—not a claim that the original problem is in P.
The regime is credible for this narrow question: the number of people can be very large while the mirror uses only two valuation types. The authors would likely recognize the subject—online allocation, greedy decisions, and multiplicative envy remain intact—but would need to accept population-level worst-pair envy and per-capita scaling as the right limit formulation.
The soft spot is substantial: in the paper, greedy acts on named agents’ individual utility states, while the continuous model must represent a distribution of states within each cohort. The mirror therefore needs a careful limit argument; replacing a cohort by one representative with its average utility would not preserve the greedy decisions. And even if the mirror works, these theorems concern competitive performance, not the complexity landscape that is ChoCo’s central target.
The strongest case against these anchors is that they are performance analyses of a particular online rule, not results about the computational complexity of an allocation problem. The relevant theorems bound greedy’s envy; the allocation decision itself is just a per-item maximization of \(B_i v_i^t/U_i^{t-1}\). A continuous version could pose an interesting question about the behavior of a fluid online process, but that would be an analytic limit question. The paper offers no numbered complexity result for that mirror to carry into ChoCo’s computational programme.
There is also a mismatch in what grows. The envy theorems take \(T\), the number of arriving items, to infinity with the agent set fixed. The lower-bound construction is explicitly a two-agent construction. Replacing those agents with large cohorts changes the greedy process: each indivisible item still goes to one person, and recipients within a cohort acquire different utility histories. A representative agent or cohort average cannot reproduce the paper’s decision rule. A more careful mirror can track a distribution of within-cohort states, as the proponent suggests, but that produces a new fluid online model rather than a direct continuous-population reading of the theorem.
That state distribution still faces a problem with the quantity being bounded: maximum individual envy. The paper takes a maximum over named agents. A continuous population measure can describe the states occupied by positive mass, but it may lose an exceptional agent whose mass vanishes as the population grows. Replacing the maximum with an essential supremum can discard that witness; retaining a supremum over vanishing-mass states requires information the limiting measure need not contain. The upper-bound theorem therefore does not transfer just by replacing cohort counts with masses.
The lower-bound theorem has the same difficulty in sharper form. Its witness is a pair of agents receiving the constructed streams. If each becomes a positive-mass cohort, items are allocated among cohort members according to their individual accumulated utilities, so the two-agent trajectory no longer follows. If a single representative receives each item, the population has not been continuized. One could study the limiting worst envy over finite cohort refinements, but that requires specifying a joint population-and-horizon limit and showing that the maximum survives it.
So neither theorem, as stated, supplies a strong ChoCo complexity anchor, and their exact worst-pair envy objective is fragile under population aggregation. That is the best case against them. It does not establish the user’s universal claim: a state-distribution model with a suitably chosen cohort-level envy measure could be a worthwhile online-allocation study. But that would be a new performance-analysis question, not a computational mirror of Theorems 3.4 and 3.5 in the programme’s stated sense.
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.