| paper | d4-conf-wine-2022-0018 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: NP-hard to obtain a \(1.092\)-approximation under the stated restrictions. · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 8
statement extracted from the paper’s text layer
Given a finite support \(K\) of complete approval types with rational masses \(\mu_\theta\), where \(\sum_{\theta\in K}\mu_\theta=1\), and \(T\) rounds with explicit menus \(\mathcal C_r\subseteq 2^K\), choose \(S_r\in\mathcal C_r\) to maximize \(\exp\!\left(\sum_{\theta\in K}\mu_\theta\log(1+\sum_{r=1}^T \mathbf 1[\theta\in S_r])\right)\). Is it NP-hard to approximate this optimum within a factor of \(1.092\), even when \(\mu_\theta=1/|K|\) for every type and every allowed option covers mass \(1/T\)?
A society is a distribution over complete approval types. Each round selects whole types through an allowed option; every member of a selected type receives one unit of coverage in that round. The objective is the population geometric mean of \(1+\) coverage, expressed as the mass-weighted mean of log coverage.
The mirror covers Theorem 8’s hardness for smoothed NSW and poses the type-weighted approximation analogue of Theorem 1. It leaves Theorem 12’s unsmoothed objective and the paper’s broader constraint families outside this question.
I would anchor the case on Theorem 8, with Theorem 1 as an algorithmic companion. The setting is a large population facing repeated public decisions or service-allocation rounds. Residents with the same approval and eligibility profile are one type; \(\mu_\theta\) is that type’s fraction of the population. This is close to the paper’s own public decision-making example, where an alternative covers the agents who approve it.
Define Continuous Type-Coverage NSW (CTC-NSW) as follows. An instance gives finite support \(K\) of \(\tau\) types, rational masses \(\mu_\theta\ge 0\) summing to \(1\), and \(T\) rounds. In each round \(r\), the allowed choices form a family \(\mathcal C_r\subseteq 2^K\); in the public-decision version, each choice is an alternative and its set contains the types it covers. A solution selects \(S_r\in\mathcal C_r\) for every round. Type \(\theta\)’s members each receive the integral coverage \(q_\theta=\sum_{r=1}^T \mathbf 1[\theta\in S_r]\), so the population Nash welfare is
\[ \operatorname{CNSW}(S_1,\ldots,S_T) =\exp\!\left(\sum_{\theta\in K}\mu_\theta\log(1+q_\theta)\right). \]
The \(+1\) and the per-person coverage rule are exactly those of the paper. The population enters through the type masses; the decisions remain selections from the feasible menus. For a large public or service population, many residents can share a profile, making the number of people \(N\) much larger than \(\tau\). If a capacity is part of a scenario, it can be expressed as a population fraction.
Lead mirror — CTC-NSW-APX. Theorem 8, proved in this paper using an approximation-preserving reduction from Feige’s maximum \(k\)-coverage result, states that it is NP-hard to approximate fair-coverage NSW within a factor of \(1.092\). Its reduction has \(n\) agents, \(T=k=n/s\) rounds, and the same explicit family of \(s\)-element sets available in each round. In the YES case, \(k\) sets cover all agents and the optimum NSW is at least \(2\). In the NO case, any \(k\) sets cover at most \((1-1/e)n\) agents, and the optimum NSW is at most \(1.83\). The resulting gap gives the stated \(1.092\) hardness.
The continuous question is: given a rational type distribution and explicit option menus, is it NP-hard to approximate CTC-NSW within \(1.092\), even when every option covers the same population mass and the number of rounds is \(T\)? A solution is the selected option for each round; its value is the weighted geometric mean above. For the reduction, give each source agent mass \(1/n\), and make each source set the approval set of an option. Every option then covers mass \(s/n=1/T\), and the continuous objective is exactly the discrete NSW objective. Repeated agents with an identical full approval profile can be merged into a type without changing that value. Replicating each profile many times makes \(N\) arbitrarily larger than the support while preserving the instance. I expect this question to have a Class B answer: the hardness comes from the incidence structure of the option menus, and the discrete instances embed directly.
Companion mirror — CTC-NSW-Approx. Theorem 1, also proved in the paper, says that with an FPTAS for nonnegative weight maximization over each \(\mathcal I_r\), the authors’ algorithm computes a \((18+1/(2nT))\)-approximation in polynomial time. The corresponding continuous question is whether CTC-NSW admits an \((18+o(1))\)-approximation in time polynomial in \(\tau,T,L\) and the oracle cost, assuming an FPTAS for \(\max_{S\in\mathcal C_r}\sum_{\theta\in S}w_\theta\). Here \(L\) is the bit length of the masses and weights, and the oracle receives weights on types. For explicit menus this maximization is exact by enumeration. I expect a Class A result: the local-search argument appears to carry over with each type’s logarithmic marginal weighted by \(\mu_\theta\), and its counting bound replaced by a bound on the mass of undercovered types. That extension would need its own bit-complexity proof; Theorem 1 as printed does not establish it.
The regime is plausible in recurring public decisions, load shedding, or service allocation: many households can have the same approval, demand, or eligibility profile, while the menu of alternatives and the number of profiles are much smaller than the headcount. The paper explicitly connects coverage to binary-additive public decision making. In the hardness construction, each option covers exactly \(1/T\) of the population, which also gives a natural per-capita scale.
The scope here is the paper’s smoothed NSW objective for fair coverage, especially its explicit-menu hardness result and the matching type-weighted approximation question. It does not claim to mirror every possible constraint family or the paper’s future extension to arbitrary additive values.
My weakest point is that the hardness construction’s support can grow with the source instance. Replicating agents makes the population much larger than the support, but it does not show hardness when the number of types is fixed. That leaves useful further questions: whether bounded \(\tau\) permits better algorithms; whether the hardness persists for nonuniform masses; and how the problem changes when a type’s members can be split across different coverage histories. The weakness limits which regimes these anchors settle. The mirror itself remains a direct population-distribution version of the authors’ coverage problem, with both a precise hardness boundary and a plausible continuous-optimization question.
The strongest objection is to the approximation companion, not to the hardness mirror. Theorem 1’s analysis uses the number of agents \(n\) both in its local-search stopping threshold and in its count of undercovered agents. Replacing counts with type masses needs a new argument and a bit-complexity analysis: tiny rational masses can be exponentially small in their encoding length. The proponent acknowledges this, so the paper does not itself establish an \((18+o(1))\)-approximation in time polynomial in \(\tau,T,L\). That companion should not be presented as a result that already carries over.
But this does not defeat the lead anchor. The type-weighted objective is a coherent population model for repeated public decisions: residents sharing an approval profile receive the same coverage in each round, and their mass weights their contribution to welfare. The hardness construction embeds exactly. Give each source agent mass \(1/n\) and make each source set an option; the objective and the \(1.092\) gap are unchanged. Duplicating every profile preserves the instance while making the underlying population arbitrarily large relative to its support. The resulting hardness is a valid Class B boundary, even if its combinatorial difficulty lies in the option menus.
The better version of the mirror therefore survives the obvious objections: it need not split types across public decisions, and it does not depend on the paper’s particular motivating story. Allowing fractions of a type to receive service could define another sensible mirror for settings such as load shedding, but it does not invalidate the public-decision version.
The negative case is weak where it matters. The approximation extension remains unproved, and the hardness mirror may reveal little beyond the discrete problem’s existing hardness. But those points do not show that the mirror is ill-posed or outside the programme’s scope. Since the instructions count a well-posed Class B mirror as worthwhile, I cannot honestly defeat Theorem 8’s anchor or support the claim that no worthwhile continuous mirror exists.
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.