| paper | Algorithmically Fair Maximization of Multiple Submodular Objective Functions |
| authors | — |
| venue | AAMAS 2025 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4.10
statement extracted from the paper’s text layer
Given agent types \(a\in[\tau]\) with rational masses \(\mu_a\), resource types \(q\in Q\) with rational supplies \(\sigma_q\), per-type monotone submodular objectives \(f_a\), \(p_a\)-system constraints \(\mathcal I_a\), a canonical deterministic Round-Robin schedule with greedy tie-breaking, and an \((\gamma,\beta)\)-robustness certificate, compute the induced mass \(x_{a,B}\) of agents receiving each feasible integral whole-copy bundle \(B\), satisfying \(\sum_B x_{a,B}=\mu_a\) and \(\sum_{a,B}B_qx_{a,B}\le\sigma_q\), and decide whether \(g_a(x):=\inf\{f_a(B):x_{a,B}>0\}\ge\rho_a\) for each requested type.
A typed high-multiplicity Round-Robin allocation model with agent masses \(\mu_a\), repeated integral resource copies of supplies \(\sigma_q\), configuration-flow variables \(x_{a,B}\), greedy sequential transitions, and worst positive-mass bundle value as the objective.
The robustness premise forces resource supply to scale with \(n\), and type masses alone do not determine within-type histories or Round-Robin positions; the mirror must therefore add repeated-resource supplies and a canonical schedule.
fatal: False
The mirror covers the monotone robust-instance guarantee of Theorem 4.10 and Corollary 4.11; it leaves the focal-agent hardness of Theorem 5.1, non-monotone results, EF1 corollaries, and randomized guarantees untreated.
The strongest positive case is a large-market, high-multiplicity version of the paper’s Round-Robin allocation problem. The natural scenario is not “fractional submodular sets,” but many exchangeable campaigners competing for many repeated resource opportunities: advertising firms selecting audience slots, hospitals selecting patient cohorts, or firms selecting interchangeable network nodes. A type records the complete objective-and-constraint profile of an agent. If there are \(N\) agents but only \(\tau\ll N\) such profiles, their population is described by rational masses \(\mu_a\).
My lead anchor is Theorem 4.10, proved in this paper. It states that if an instance is \((\gamma n+i-1,\beta)\)-robust for agent \(i\), then greedy Round-Robin produces a solution satisfying
\[ f_i(S_i)\ge \frac{\mathrm{OPT}_i}{\beta(p_i+1+1/\gamma)}. \]
This is unusually well suited to continuization because the theorem’s own motivation is explicitly “large-market”: an agent should have many disjoint, nearly optimal alternatives, so that other agents’ choices do not destroy its value. The resulting population regime is precisely one with many repeated agent types and resources whose supply scales with population.
Call the continuous problem Robust Typed Round-Robin Maximization\(_\infty\). An instance consists of:
A bundle remains an integral bundle: if \(B\) is assigned to an agent, it contains whole resource copies, never fractions of an item. The continuous variable is the mass \(x_{a,B}\) of type-\(a\) agents receiving bundle \(B\). It must satisfy
\[ \sum_B x_{a,B}=\mu_a \]
and, for every resource type \(q\),
\[ \sum_{a,B} B_qx_{a,B}\le \sigma_q. \]
The Round-Robin restriction is represented by transition flows: at each turn, at most one item copy is added to each agent’s current bundle, and a greedy type may choose only a feasible available item of maximum marginal value. The output is the complete bundle-mass distribution \(x\), together with each type’s worst positive-mass value
\[ g_a(x)=\inf\{f_a(B):x_{a,B}>0\}. \]
Thus the computational question is: compute the aggregate greedy Round-Robin allocation and its typewise guarantees; equivalently, decide whether \(g_a(x)\ge \rho_a\) for specified thresholds.
This is a genuine high-multiplicity mirror. Clearing denominators in \(\mu\), \(\sigma\), and \(x\) produces a finite population of repeated agent clones and repeated resource copies. Conversely, normalized finite clone populations give rational mass instances. The large-market robustness condition becomes a packing of \(\gamma N\) disjoint near-optimal bundles among \(N\) agents. The expected classification is Class A for protocol execution when the resource catalogue and typewise marginal queries are explicit: greedy choices and aggregate transition flows should be computable without iterating over \(N\). Exact computation of \(\mathrm{OPT}_a\), or recognition of robustness from oracle access alone, is a separate optimization problem and may remain hard.
This mirror covers Theorem 4.10 and, as its population-wide consequence, Corollary 4.11, also proved here. It does not claim to cover every theorem in the paper: in particular, the non-monotone results and the EF1 corollaries require additional bundle-state machinery.
A second, genuinely complexity-oriented anchor is Theorem 5.1, also proved here. It says that, even when every other agent has an additive objective and follows the greedy policy, no polynomial-time algorithm can achieve a \((1+\varepsilon)\)-improvement over the focal agent’s greedy policy for any fixed \(\varepsilon\in(0,0.3)\), unless \(P=NP\).
The corresponding problem is Typed Focal Best Response under Round-Robin\(_\infty\). There is a finite typed population of opponent agents with rational masses; all opponent types have additive objectives and use greedy Round-Robin. A distinguished focal type has a submodular objective \(f_\star\) and may choose an arbitrary legal policy. Given the resource supplies, type masses, protocol order, tie-breaking, and \(\varepsilon\), the task is to output a legal focal policy and induced mass-flow allocation whose value is at least \((1+\varepsilon)\) times the focal greedy baseline whenever such an improvement exists.
This should be Class B if the resource catalogue retains the paper’s item-selection combinatorics: the finite problem embeds by taking rational clone masses and a one-clone focal cohort, while the hardness lives in the item structure rather than in population multiplicity. The open question is whether the hardness remains when the focal agent itself is replaced by a positive-mass synchronized cohort. That is a worthwhile continuum-specific question rather than a defect in the mirror.
The weakest point is the continuum Round-Robin semantics. A literal atomless population has no canonical first agent, and arbitrary fractional bundle flows could erase the paper’s indivisibility. The proposed model therefore has to specify a canonical type order, tie-breaking, scaled resource supplies, and integral bundle configurations. This makes it an extension rather than a purely formal replacement of \(n\) by a real number. Still, it is an extension the authors should recognize: it preserves their agents, submodular objectives, \(p\)-system constraints, disjoint resources, greedy protocol, robustness notion, and computational question, while making the paper’s own “large-scale robust instance” intuition mathematically explicit.
The strongest negative case is that neither proposed anchor yields a genuine population-continuized computational problem of the kind ChoCo is looking for. A new fluid fair-division model could certainly be invented, but that is weaker than finding a worthwhile continuous mirror of this paper.
Theorem 4.10 and Corollary 4.11 are not complexity results. They analyse an already polynomial-time greedy protocol and prove approximation guarantees under a robustness assumption. A continuous version that asks for the aggregate execution of that protocol would therefore be a new implementation model, not a continuization of a computational problem stated by the paper.
More seriously, the large-market interpretation is incompatible with keeping only the population continuous. Theorem 4.10 assumes \(\Theta(n)\) pairwise disjoint near-optimal integral bundles. For any nontrivial instance, each such bundle consumes at least one item, so the ground set must also satisfy \(m=\Omega(n)\). If \(M\) is fixed, the robustness premise disappears in the limit except in degenerate cases. If \(M\) scales with \(n\), then the resource catalogue—not merely the population—has been continuized or given high multiplicity.
The proponent’s repair does not resolve this fork. If resource copies remain distinguishable, the masses \(\mu_a\) do not compress the hard part: the submodular functions are still functions of named items, greedy choices depend on item identities, and the aggregate transition system can have exponentially many bundle states. The proposed variables \(x_{a,B}\) are therefore not an evident finite LP; they are a configuration formulation whose pricing and state representation inherit the original combinatorial difficulty. If copies are instead identified by resource type, then \(f_i:2^M\to\mathbb R\) has been replaced by a function on resource counts or continuous quantities. That may be a legitimate new DR-submodular or fluid-allocation problem, but it is not the paper’s problem with a continuous population.
Round-Robin also has no canonical limit determined by type masses. Two populations with the same masses can be ordered in blocks, cyclically, or by a random permutation, and contested items can then be allocated differently. In Theorem 4.10, the focal agent’s position \(i\) is part of the benchmark through \(\mathrm{OPT}_i^{-}\); in a positive-mass type, different clones occupy different positions and have different histories. Encoding those positions as types destroys finite multiplicity; suppressing them changes the sequential problem. The proposed type order is an additional scheduling model, not information contained in the continuous society.
Theorem 5.1 is the genuine computational anchor, but it has the opposite defect. Its hard object is a single distinguished agent \(j\), with an individual adaptive policy, competing against fixed opponents. A one-clone focal cohort has mass \(1/N\), which vanishes in the high-multiplicity limit. Clearing denominators merely re-encodes the finite instance; it does not produce a meaningful continuous population problem.
Giving the focal type positive mass changes the question fundamentally. If all focal clones are synchronized, they cannot reproduce the original policy, because the original agent chooses one item at a time while observing a changing \(Q\). If they use the same adaptive policy independently, their histories diverge and there is no longer one focal solution \(S_j\). If they are centrally coordinated through a mass-flow decision, the model has replaced individual best response by collective control and generally permits fractional coordination. One must then choose a new objective—average value, worst-clone value, a quantile, or something else—and each choice changes the theorem’s predicate “improve whenever possible.” Making identity or position part of the type restores the original semantics only by producing \(O(N)\) types.
Thus the proponent’s two escape routes fail in opposite ways: the first turns a finite approximation guarantee into an underspecified fluid fair-division model; the second preserves the computational theorem only by making the relevant agent measure zero. There may be an interesting new paper on fluid Round-Robin allocation with typed submodular valuations, but the supplied paper does not provide a worthwhile continuous mirror in the ChoCo sense. The negative case is not a mathematical impossibility claim—one can always formulate a related model—but neither named anchor currently survives as a population-only, finite-type computational 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.