| paper | d4-conf-sagt-2015-0021 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→other discrete result → its continuous mirror
Answer: Worst-case nondeterministic bit communication is unbounded already for \(m=1\), \(\tau=2\), and constant \(L\). Under the additional normalization \(v_t(\mathbf 1)=1\), polynomial communication suffices for each fixed \(\varepsilon\in(0,1)\). · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Lemma 10
statement extracted from the paper’s text layer
Given \(m\) resources, \(\tau\) valuation types with public rational masses \(\mu_t>0\) summing to \(1\), per-capita supplies \(h_j\), and normalized, monotone, subadditive valuations \(v_t:[0,1]^m\to\mathbb{R}_{\ge 0}\) privately held by the type parties, determine the nondeterministic communication complexity of producing a feasible \((2-\varepsilon)\)-approximation to \(\mathrm{OPT}\). A feasible plan consists of a probability distribution \(\pi_t\) over bundles for each type, with welfare \(\sum_t\mu_t\int v_t(x)\,d\pi_t(x)\) and resource use \(\sum_t\mu_t\int x_j\,d\pi_t(x)\le h_j\) for every resource \(j\).
A communication problem with one private valuation input per type, population mass \(\mu_t\) per type, and an output allocation plan \(\pi_t\) that may split each type’s mass among bundles.
With communication kept faithful to Lemma 10, the number of private valuation inputs is \(\tau\); increasing cohort masses adds no communication parties, so the lemma alone does not show that high multiplicity creates a new hardness effect.
fatal: False
The mirror covers the welfare-approximation communication result in Lemma 10 and its role in Theorem 11. It leaves the paper’s equilibrium-efficiency bounds, budget results, and polyhedral-environment result aside.
The strongest anchor is Lemma 10, proved in this paper using a communication lower bound from Theorem 3 of Nisan [17]. It says that for every fixed \(\varepsilon>0\), any nondeterministic \((2-\varepsilon)\)-approximation for social welfare maximization with subadditive valuations requires exponentially many communication bits in the number \(m\) of resources. The proof transforms each hard combinatorial auction valuation \(v_i\) into a subadditive valuation on fractional bundles: for nonzero \(x_i\), \(v'_i(x_i)=v_i(A_{x_i})+1\), where \(A_{x_i}=\{j:x_{ij}>1/2\}\). This transfers a gap between optimum welfare \(n\) and \(1\) to a gap between \(2n\) and \(n+1\) in the resource allocation problem.
A continuous mirror is Continuous-Type Subadditive Welfare Approximation. Its input is \(m\) resources, a finite support \(T\) of \(\tau\) valuation types, positive rational masses \(\mu_t\) summing to one, a total population mass \(N\), and per-capita resource supplies \(h_j\). Each type \(t\) has a normalized, monotone, subadditive valuation \(v_t:[0,1]^m\to\mathbb R_{\ge0}\). A feasible solution gives each type cohort a finite allocation plan: type \(t\)’s mass \(N\mu_t\) is divided among bundles \(x\in[0,1]^m\), with total resource use at most \(Nh_j\) for resource \(j\). Its welfare is the mass-weighted sum of the cohort members’ valuations. The task is to output a plan whose welfare is at least \(\mathrm{OPT}/(2-\varepsilon)\). For the communication version anchored by Lemma 10, each type representative holds that type’s valuation, and the protocol must describe the allocation plan. Valuations can be given through the same value-oracle convention used for the communication lower bound.
This is a population continuization: agents with the same complete valuation form a cohort, and \(\mu_t\) is their population share. The allocation bundles remain divisible as in the paper; the continuous object is the population and the allocation plan for its mass. A natural regime is a resource platform serving millions of repeated workload profiles, with many fewer distinct valuation types. Replicating every cohort and scaling total resource supply with population gives the high-multiplicity setting. The type allocation plan can split a cohort among different bundles, so it still represents heterogeneous assignments to otherwise identical agents.
I expect this problem to be a Class B candidate: the reduction’s combinatorics concern the \(m\) resources and valuation structure, rather than a large number of distinct agents. The precise question for a prover is whether Lemma 10’s exponential communication lower bound survives when a type cohort may be split across bundles. A useful avenue on the other side is a configuration LP whose pricing step optimizes \(v_t(x)-\lambda\cdot x\) over bundles.
The weakest point is substantial: Lemma 10 is a communication lower bound for the welfare optimization underlying the paper’s mechanism results, not a centralized running-time lower bound. Its hard instances have fewer than \(m^{1/2-\eta}\) agents for a constant \(\eta>0\), and the continuous allocation plan adds the ability to split type mass. So I would not claim that its hardness already transfers. The mirror is still a sensible problem for the authors to recognize: it asks for the complexity of their same subadditive welfare objective in a high-multiplicity population regime. This case covers the welfare-optimization result in Lemma 10 and its use in Theorem 11; it does not continuize the paper’s other equilibrium-efficiency bounds.
The strongest objection is that Lemma 10’s lower bound is about communication between holders of private valuations. In the Nisan reduction, each of \(n\) players holds a distinct set \(I_i\), and the construction carries that private input into the subadditive valuation. The proposed mirror changes the input model: a centralized algorithm receives the type masses and valuation access. Lemma 10 then gives no running-time or oracle-query lower bound for that algorithm. The proponent’s “same value-oracle convention” also needs justification; the paper describes a communication reduction with private valuation data, not a centralized value-oracle algorithm.
Preserve the communication model by making each valuation type a party, and the hard input remains distributed across \(\tau\) distinct types. Duplicating each type many times adds population mass, but it adds no private information or communication parties. A mirror could ask about communication complexity with type parties and continuous masses, but its hardness would still come from the same \(\tau\) valuation inputs. That makes Lemma 10 weak support for a new complexity landscape driven by continuization.
This objection does not defeat the best version of the mirror. A centralized welfare problem over type cohorts is well-defined:
\[
\max_{\{\pi_t\}}\ \sum_t \mu_t\int v_t(x)\,d\pi_t(x)
\quad\text{subject to}\quad
\sum_t\mu_t\int x_j\,d\pi_t(x)\le h_j .
\]
Here \(\pi_t\) describes the bundles received by type \(t\)’s mass. Its configuration-LP pricing problem, \(\max_x\{v_t(x)-\lambda\cdot x\}\), is a genuine algorithmic question. Repeated workload profiles are also a plausible high-multiplicity regime. The paper’s fractional resource outcomes do not make the population continuous already.
So I would reject the claim that Lemma 10’s communication bound transfers directly to the proposed centralized mirror. I cannot honestly use that mismatch to establish the universal negative the task asks for: the continuous-type welfare problem remains sensible and potentially valuable, even if its connection to this paper’s only named computational result is loose. The negative case is weak at precisely that point.
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.