| paper | d4-conf-ijcai-2022-0127 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given rational masses \(\mu_t\) of advertiser types \(t=(w,v,b)\), slot-class supplies \(q_k\), group-specific click-through rates \(\alpha_{wk}\), quality factors \(\gamma_w\), and \(\beta\leq 1\), compute group allocations \(x_{wk}\) with \(x_{hk}+x_{\ell k}=q_k\). For each group \(w\), define \(V_w(z)\) as the maximum of \(\sum_{t\in T_w,k}\gamma_w\alpha_{wk}b_t y_{tk}\), subject to \(\sum_{t\in T_w}y_{tk}=z_k\), \(\sum_k y_{tk}\leq\mu_t\), and \(y_{tk}\geq0\). Require \(V_h(x_h)\geq\beta V_h(x_\ell)\) and \(V_\ell(x_\ell)\geq\beta V_\ell(x_h)\).
A society with finite support over advertiser types and rational type masses, alongside per-capita supplies of indivisible ad opportunities in finitely many slot classes. The decision variables are group-to-class masses \(x_{wk}\) and type-to-class flows \(y_{tk}\); the task is feasibility, with no additional objective.
The allocation \(x_{hk}=x_{\ell k}=q_k/2\) satisfies group \(\beta\)-envy-freeness for every \(\beta\leq 1\), so the continuous feasibility problem ignores the masses and is immediately solvable.
fatal: False
The mirror covers Theorem 2's group \(\beta\)-EFX allocation guarantee in the atomless, scaled-supply limit, where it becomes group \(\beta\)-envy-freeness. It does not cover Theorem 1's \(\beta\)-EF1 guarantee, the payment and welfare bounds in Theorems 3–6, or the equilibrium results in Theorems 7–8.
The strongest honest case is narrow: the paper’s group fair-division layer, not its whole mechanism or learning analysis. My lead is Continuous Group \(\beta\)-EF Slot Allocation.
The closest named algorithmic anchor is Theorem 2, proved in this paper. It says that the allocation computed by the group envy-cycle-elimination algorithm (GECE) is group \(\beta\)-EFX: for each ordered pair of groups \(w,w'\), and each slot \(j\) assigned to \(w'\), group \(w\)’s value for its own slots is at least \(\beta\) times its value for \(w'\)’s slots after removing \(j\). The value is calculated from the groups’ bids. The paper adapts the envy-cycle idea of Lipton et al.; the group guarantee is proved here. The paper does not state a named P-versus-NP or other complexity-class theorem, so I would not present Theorem 2 as one. It is a correctness result for an explicit fair-allocation algorithm, which is the closest named computational anchor available.
For a plausible high-multiplicity regime, take a large batch of similar advertising opportunities on a platform with many advertisers. A post-bid advertiser type is \(t=(w,v,b)\): its group, valuation, and realized bid, together with the other attributes the allocation problem uses. Let \(\mu_t\) be the fraction of advertisers of type \(t\), with support size \(\tau\ll N\) for a market of \(N\) advertisers. Both group identity and bid matter to this problem, so they belong in the type. Assume each group has enough advertiser mass to fill any bundle of slots, as in the paper’s assumption that each group has at least \(m\) advertisers.
The supply scales with the market: class \(k\) has \(q_k\) advertising opportunities per advertiser, with group-specific click-through rate \(\alpha_{wk}\) and quality factor \(\gamma_w\). Write \(\rho=\sum_k q_k\) and require each group’s mass to be at least \(\rho\). Each opportunity still goes to one advertiser. The continuous quantities describe aggregate masses: in a finite market, a group’s allocation of class \(k\) is roughly \(N x_{wk}\) whole opportunities. This co-scaling of supply is part of the mirror because the paper’s auction allocates a growing number of slots; it is not a move to divisible ads for individual advertisers.
Given a bundle \(z=(z_k)\) of opportunity mass, define group \(w\)’s bid value by the finite-support transport problem
\[
V_w(z)=\max_{y\ge 0}\sum_{t\in T_w}\sum_k \gamma_w\alpha_{wk}b_t y_{tk},
\quad
\sum_{t\in T_w}y_{tk}=z_k,\quad
\sum_k y_{tk}\le\mu_t.
\]
Here \(y_{tk}\) is the mass of type \(t\) assigned to class \(k\). It captures the group’s best bid-based use of that bundle, in the same spirit as the paper’s per-group ranking of advertisers.
The continuous problem is: given the rational type masses, slot-class supplies, click-through rates, quality factors, and \(\beta\), find bundles \(x_h,x_\ell\) with \(x_{hk}+x_{\ell k}=q_k\) for every class \(k\), such that \(V_h(x_h)\ge\beta V_h(x_\ell)\) and \(V_\ell(x_\ell)\ge\beta V_\ell(x_h)\). A solution is the group allocation \(x\), together with type-to-slot mass flows realizing the groups’ own assignments; the displayed LPs specify the values used for the envy checks. This is Continuous Group \(\beta\)-EF Slot Allocation.
It is the natural atomless limit of Theorem 2’s group \(\beta\)-EFX condition. When individual slot mass shrinks with market size, removing one slot changes a group’s value by a vanishing amount, assuming bids and click-through rates stay bounded. Thus finite-market EFX approaches group \(\beta\)-envy-freeness in the limit. This does change the guarantee: the continuous question is EF, rather than literally EFX on a list of indivisible slots.
I expect a Class A route, though this paper does not establish it. Each group’s value on a bundle is a finite-support transport LP value, suggesting a convex market-equilibrium or separation approach with complexity in \(\tau\), the number of slot classes, and the input bit length \(L\). The prover’s question is whether a fair allocation can be computed with such a bound and certified exactly. A useful next question is how to round the mass allocation back to a finite market while retaining \(\beta\)-EFX, or an additive error that vanishes with the largest slot’s share of supply.
This mirrors only the GECE fairness result. It does not claim to continuize the paper’s payment rules, welfare bounds, or no-regret equilibrium results. The soft spot is that the finite theorem partitions indivisible slots between two groups, while this mirror scales the slot supply and takes an atomless limit, turning EFX into EF. A referee could reasonably view that as a new fair-allocation market rather than a direct high-multiplicity version of GECE. The case survives if the setting is a large batch of standardized advertising opportunities: the advertisers are the population being aggregated, individual assignments remain integral, and the fractional quantities arise only in type-level averages.
The only plausible anchor is Theorem 2: GECE’s output is group \(\beta\)-EFX. But the theorem establishes a fairness guarantee, not a complexity bound or a complexity classification. Its continuous mirror runs into a more basic problem: either the population masses stop mattering, or the fairness condition becomes trivial.
Keep the paper’s number \(m\) of indivisible slots fixed while the advertiser population grows. For a finite type support with positive masses \(\mu_t\), a type has about \(N\mu_t\) advertisers in a population of size \(N\). Eventually, every positive-mass type has enough copies to fill all \(m\) slots. The group valuations used by GECE then depend on which types are present and their bids, not on their masses. If types instead form a continuous bid distribution, the finitely many winning advertisers are zero-mass extremes; their identities or extreme order statistics are not captured by an aggregate mass allocation. Either way, there is no meaningful mass-transfer problem corresponding to GECE.
The proponent’s stronger repair is to scale slot supply with population size. That preserves nonzero type-to-slot flows, but in the limit each slot class is divisible. Under the proposed value functions, giving each group the same half of every class satisfies group \(\beta\)-envy-freeness for every \(\beta\leq 1\): each group values its own bundle exactly as it values the identical bundle assigned to the other group. The atom-removal clause that made EFX interesting has vanished. So the stated continuous feasibility question has an immediate solution, independent of the masses or the proposed transport LPs.
One could add a welfare objective and ask for the welfare-maximizing fair allocation. That is the strongest repair, and the paper’s welfare theorems make it a recognizable follow-on. But it adds an objective that Theorem 2 does not optimize; with explicit finite type support and slot classes, the resulting assignment values have direct LP formulations. That looks like a routine finite optimization problem, not a new complexity landscape opened by continuization.
The weak point in this negative case is that an author might still consider that welfare-optimization follow-on worthwhile, particularly alongside the paper’s other theorems. I would not rule it out. But it does not rescue the proposed mirror of GECE: with fixed supply, masses disappear; with scaled supply, the stated fairness question is already solved by equal bundles.
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.