| paper | d4-conf-atal-2020-0232 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
Answer: Yes: a polynomial-time \(\frac12\)-approximation exists, with one rational team template and a binary encoded multiplicity. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 3.3
statement extracted from the paper’s text layer
Given capacity types \(r\) with weights \(w_r\), rational proportions \(\mu_r\), population scale \(N\), and repeatable tasks \(j\) with thresholds \(q_j\) and rewards \(v_j\), partition the atomless mass \(N\mu_r\) into disjoint measurable teams, each assigned a task and having total capacity at least its threshold. Can an algorithm return teams with reward at least \(\frac12\mathrm{OPT}_\infty\) in time polynomial in the input bit length?
Types are capacity levels \(w_r\) with mass \(N\mu_r\). Choose integer task counts \(z_j\ge 0\) and allocated masses \(a_{rj}\ge 0\), subject to \(\sum_j a_{rj}\le N\mu_r\) and \(\sum_r w_r a_{rj}=q_jz_j\); maximize \(\sum_j v_jz_j\). Atomlessness permits each allocated task mass to be partitioned into teams.
The mirror covers Theorem 3.3's half-approximation for coalition-structure welfare. It leaves the cost-of-stability result, bargaining model, and human-play experiments aside.
The strongest case is for a high-multiplicity mirror of the paper’s coalition-structure problem in a repeatable workforce setting. In the paper, a task earns its reward when a coalition’s total weight reaches its threshold, and different coalitions may complete the same task type. A large pool of workers with a few standardized capacity levels is a plausible regime for that model: type is a worker’s capacity \(w_r\), mass is the headcount in that capacity tier, and \(N\mu_r\) is the mass of type \(r\) in a population of size \(N\). For example, a freelance platform might assign millions of workers in a small number of standardized availability tiers to recurring contract types. Workers in a tier have the same relevant capacity and task access; there are few types compared with the population. The platform seeks high total revenue from the teams it forms.
My lead anchor is Theorem 3.3, proved in this paper. It says that for any TTG, an efficient algorithm computes a coalition structure whose social welfare is at least \(\frac12\mathrm{OPT}(G)\). It concerns approximate welfare maximization over partitions of the players into coalitions, with each coalition’s value determined by the best threshold task it can complete. The paper also reports that exact discrete OptCS is NP-complete, citing [17]; that is useful context, but the numbered result I rely on is Theorem 3.3.
The continuous question I would hand to a prover is Atomless TTG Half-OptCS. An instance has a finite set of capacity types \(r\), each with weight \(w_r\in\mathbb{Z}_{>0}\); rational proportions \(\mu_r\) summing to \(1\); a population scale \(N\); and repeatable tasks \(j\) with thresholds \(q_j\in\mathbb{Z}_{>0}\) and rewards \(v_j\in\mathbb{Z}_{>0}\), ordered as in the paper. Each type is an atomless population of mass \(N\mu_r\). A feasible answer forms disjoint measurable teams; a team assigned task \(j\) must have total capacity at least \(q_j\), and earns \(v_j\). The question is to return teams of total reward at least half the maximum possible reward.
There is a compact way to state and reconstruct a solution. Give an integer \(z_j\ge 0\) for the number of teams doing task \(j\), and nonnegative rational \(a_{rj}\) for the mass of type \(r\) allocated to those teams, with \(\sum_j a_{rj}\le N\mu_r\) and \(\sum_r w_r a_{rj}=q_jz_j\). Because each type population is atomless, its mass can be cut to fill \(z_j\) teams of exactly the required capacity; no individual has to be split between teams. The answer’s value is \(\sum_jv_jz_j\), and it must be at least \(\frac12\mathrm{OPT}_\infty\). Unused mass can be partitioned into teams that complete no task.
I expect this approximation question to be Class A, tractable. Let \(W=N\sum_r\mu_rw_r\) be total capacity. In the atomless model, task teams can be filled from that pooled capacity, so the task counts satisfy \(\sum_jq_jz_j\le W\). This gives a compressed task-count problem; a density-based choice of task type and repeated teams gives a half-approximation in time polynomial in the task list and input bit length, with counts represented in binary. That is a reason to expect a continuous result, not a claim that Theorem 3.3’s explicit-player algorithm already runs in time polynomial in \(\tau\) and \(L\). The theorem’s stated efficiency is for the discrete input; the compressed continuous analysis would need its own proof.
This mirror covers Theorem 3.3’s approximate coalition-structure welfare result. It does not try to continuize the paper’s cost-of-stability bound or its bargaining and human-play experiments. Further questions include whether exact Atomless TTG OptCS remains hard, whether the cited discrete hardness survives in any form, and how well a compressed continuous solution can be rounded back to a large finite electorate.
The weak point is that atomlessness removes the finite-player packing obstacle: type mass can be cut to meet thresholds exactly. That makes the continuous problem easier and means the theorem’s particular contiguity argument does not transfer directly. Still, the mirror retains the paper’s central decision—how to form threshold-feasible teams to maximize total task reward—and uses population mass to represent large cohorts of interchangeable workers. Whether the authors would accept that as their continuous analogue, rather than as a simplified workforce-planning variant, is the key point for the opposing case to test.
The strongest case against this anchor is that atomlessness strips away the feature Theorem 3.3 has to handle. With mass \(N\mu_r\) of each capacity type, all capacity can be pooled and divided continuously. The type distribution then matters only through total capacity \(W=N\sum_r\mu_rw_r\). An allocation is just integer task counts \(z_j\) satisfying \(\sum_j q_jz_j\le W\).
That makes the theorem’s half approximation immediate. Choose \(j^*\) maximizing \(v_j/q_j\), and form \(\lfloor W/q_{j^*}\rfloor\) teams for that task. Since any feasible allocation earns at most \(W\max_j(v_j/q_j)\), this achieves at least half the optimum. The exact version is the familiar integer task-count problem of maximizing \(\sum_jv_jz_j\) subject to \(\sum_jq_jz_j\le W\). The mirror therefore loses the paper’s player-packing structure; its type support and the paper’s contiguity argument disappear.
A richer model could make capacities task-dependent or impose eligibility constraints, but those would add structure absent from this TTG and would need a separate case that the authors recognize as their problem. Preserving indivisible headcounts inside each task team would retain more of the original packing difficulty, but would also give up the atomless simplification that makes this proposed mirror work.
This is a real argument about the mirror’s research value, but it does not defeat the anchor. A large workforce with a few capacity tiers and repeatable contracts is plausible, and it matches the paper’s weights, thresholds, and rewards. I cannot honestly support the universal claim that no worthwhile continuous mirror exists here; the negative case is weak.
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.