| paper | d4-journals-geb-2018-0031 |
| 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: \(\alpha_{\mathrm{path}}(N,\tau)=N\) for every \(N\geq2\) and \(\tau\geq1\); it grows linearly with \(N\) for every fixed \(\tau\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
For a scalable family of undirected network templates with \(N\) suppliers and at most \(\tau\) complete role-cost types, given by a distribution \(\mu\) with \(N\mu_t\) integral, determine the best worst-case approximation ratio \(\alpha_{\mathrm{path}}(N,\tau)\) achievable by dominant-strategy truthful mechanisms that return an integral \(s\)-to-\(t\) path and minimize the maximum supplier cost. In particular, for fixed \(\tau\), can this ratio be bounded independently of \(N\)?
Use a scalable undirected graph family in which each type specifies both the supplier's network role and its edge-cost vector, and type \(t\) has mass \(\mu_t\). At finite scale \(N\), the mechanism receives the suppliers' reports, returns an integral path, and must remain truthful when one supplier's report changes the type distribution by \(1/N\); its objective is the maximum individual cost on the path. Study the best worst-case approximation ratio as a function of \(N\) and \(\tau\).
The proposed template family is not instantiated, so it remains to show that suppliers with the same stated role-cost type are interchangeable while path feasibility is preserved; in general networks, this role information can force the support to grow with \(N\).
fatal: False
The mirror covers the truthful approximation barriers in Theorems 1 and 2 for scalable, repeated-role network families. It leaves the non-truthful PTAS in Theorem 11 and the paper's other background results aside; neither theorem establishes a bound for fixed \(\tau\).
The strongest case is a narrow one: Theorem 1, the min-max path result, is the lead; Theorem 2, for directed MST, is a second anchor. Both are proved in this paper. Theorem 1 says that for a graph whose edges are partitioned among \(n\) agents, no truthful mechanism can guarantee an approximation ratio better than \(n\) for choosing an \(s\)-to-\(t\) path that minimizes the maximum agent cost. Theorem 2 says the same for choosing a rooted directed spanning tree that minimizes the maximum agent cost. The bounds do not assume a limit on running time. In both cases the paper also gives the matching \(n\)-approximation through VCG, so the claimed barrier is tight.
A plausible regime is a large network procurement market with many interchangeable suppliers in a small number of standardized roles and cost classes. A supplier’s type is its full role in the graph—its owned edge bundle, expressed in the local coordinates of that role—and its costs on those edges. Two suppliers count as the same type only when they are interchangeable under the network template and have the same costs. For example, a repeated network structure could have \(N\) suppliers but only \(\tau\) distinct role-cost types, with \(N\) much larger than \(\tau\).
I would formulate the lead mirror as High-Multiplicity Truthful Min-Max Path. An instance gives an undirected graph template with terminals \(s,t\), a population scale \(N\), and a distribution \(\mu\) over \(\tau\) role-cost types, with \(N\mu_t\) an integer for every type \(t\). The scale expands the template into a graph with \(N\) suppliers, each owning its prescribed edge bundle. A supplier of type \(t\) has costs \(c_t(e)\) on those edges. A mechanism receives the suppliers’ reported costs, returns an integral \(s\)-to-\(t\) path \(P\), and pays each supplier. It must be dominant-strategy truthful for each supplier, including when one supplier’s report changes the reported distribution by \(1/N\). Its approximation ratio on a true profile is
\[
\frac{\max_i\sum_{e\in P\cap E_i}c_i(e)}
{\min_Q\max_i\sum_{e\in Q\cap E_i}c_i(e)}.
\]
The question to hand a prover is: for profiles supported on at most \(\tau\) types, what is the best worst-case approximation ratio \(\alpha_{\mathrm{path}}(N,\tau)\) achievable by a truthful mechanism? In particular, for fixed \(\tau\), can the ratio be bounded independently of \(N\), or must it still grow with the population? A positive solution is a truthful mechanism family and its guarantee; a negative solution is a lower bound ruling out such a family. When \(\tau\) grows to \(N\), the paper’s Theorem 1 supplies the \(N\)-scale boundary. My conjecture for the fixed-\(\tau\) regime is that an \(N\)-independent, type-dependent guarantee may be possible. That is a conjecture about the new regime, not a consequence of Theorem 1.
The corresponding High-Multiplicity Truthful Min-Max Directed MST question uses a directed graph template with root \(s\), the same population and type data, and mechanisms returning an integral rooted arborescence. Its objective is the same maximum supplier cost, with the denominator minimized over rooted arborescences. The prover is asked to determine \(\alpha_{\mathrm{arborescence}}(N,\tau)\), especially whether it can be bounded independently of \(N\) for fixed \(\tau\). Theorem 2 gives the unrestricted-support \(N\)-scale anchor; I would tentatively expect a type-dependent bound in the fixed-support regime here too, though the directed tree constraints make that the less secure conjecture.
These mirrors keep the paper’s central question intact: suppliers have private costs, the mechanism must preserve truthfulness, and the chosen network object minimizes the maximum individual cost. The population is represented by rational proportions, while the path or tree remains integral. Keeping each supplier’s \(1/N\) influence in the finite-scale mechanism is deliberate: a literally atomless agent may have no effect on the outcome, making individual truthfulness vacuous. The continuous object is the distribution \(\mu\) and the asymptotic dependence on \(N\) and \(\tau\), with truthful mechanisms defined at every finite scale.
The boundary is clear. If support is unrestricted, the discrete lower bounds carry over whenever the repeated-network template can realize the paper’s construction; that is the hardness-transfer side. The open mirror is the high-multiplicity case where \(N\gg\tau\): can the guarantee depend on the number of distinct types instead of the number of suppliers? The paper does not answer that question.
The weakest point is that the proofs’ successive, agent-specific cost changes need not preserve small support. They establish the \(N\)-scale lower bound on general profiles, not on profiles with \(\tau\ll N\). So these theorems motivate the mirror and pin down its unrestricted boundary, but they do not establish the fixed-\(\tau\) result. I would leave Theorem 11’s PTAS for non-truthful min-max path out of the anchor set: it is useful context, but it does not itself resolve this continuous population question.
I would oppose both mirrors on the same structural ground: each theorem is about a maximum over individual edge owners, under a truthfulness condition defined by one owner changing their report. A distribution over cost types does not, by itself, preserve either the owners’ network roles or those individual deviations.
For Theorem 1, an owner’s full type must include the bundle of edges they control and its cost vector across the blocks. The proposed “role-cost type” works only when owners in that class are interchangeable in the expanded graph. In a general network, edge location affects which paths are feasible, so equal costs do not make owners the same type. Theorem 2 is even more dependent on location: an arc owner’s role includes how their arcs connect the rooted tree. Omitting that structure loses information needed to specify feasible paths or arborescences; including it can make the number of types grow with the number of owners.
The proofs also do not establish the proposed fixed-\(\tau\), large-\(N\) boundary. They hold the number of agents \(n\) fixed while increasing the number of blocks \(\ell\) to approach the \(n\)-approximation bound. Their cost changes are owner-specific. In a growing-population version, the type must encode the owner’s whole cost pattern, which can make support grow with \(N\). This does not show that the fixed-support question has a dull answer; it shows that the paper’s results do not supply the claimed boundary for that regime.
There is a more basic limit problem. On a fixed graph, a path or tree selects finitely many edges. With \(N\) owners, the selected owners can therefore have vanishing mass. A continuum model using essential supremum can lose them from the objective, even though one selected owner can determine the finite instance’s maximum cost. A model using supremum over the support keeps their effect, but then a deviation that changes mass by \(1/N\) can remain consequential as its mass tends to zero. The objective and the unilateral truthfulness constraint do not pass cleanly to the same aggregate limit.
The strongest version of the proponent’s mirror keeps \(N\) finite, asks for \(\alpha(N,\tau)\), and represents repeated, interchangeable suppliers in a scalable network template. That is a coherent high-multiplicity mechanism-design question. It retains atomic deviations and the individual approximation objective. It also retains finite-agent strategic constraints: a supplier changes the reported distribution by \(1/N\), and the mechanism must still act on the specific supplier and their network role. It is therefore not yet a continuous-society computational question of the kind this programme is meant to study. A continuum mechanism could be defined, but it would need to specify how it assigns integral network bundles to mass and how individual incentive constraints survive when a single report has zero mass. Changing to cohort reports or aggregate truthfulness would change the mechanism problem.
Theorems 1 and 2 are genuine named approximation results, so the “no result to mirror” objection does not apply literally. Their bounds concern the cost of dominant-strategy truthfulness and hold regardless of running time. They do not identify a complexity or pricing problem for continuous optimization to resolve. Dropping truthfulness would leave a different optimization question; keeping it leaves the individual-incentive obstacle above.
The negative case is not airtight. An exchangeable, co-scaled supplier model could be plausible, and studying \(\alpha(N,\tau)\) there may be worthwhile. My objection is that this is a separate restricted mechanism-design programme unless it supplies a well-defined continuous model that preserves both path or tree feasibility and individual truthfulness. The supplied mirror has not made that bridge yet.
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.