Answer: \(A(m,r)=1\) when \(m=r\), and \(A(m,r)=+\infty\) when \(m>r\), for every admissible pair \(1\le r\le m\).
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThere is no mechanism that is truthful in expectation that achieves an approximation ratio better than (m −r)/2 + 1 for graphical matroids.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a graph \(G=(V,E)\) and a finite-support report measure over edge-cost roles, consider repeated network deployments whose aggregate hired vector must lie in \(\mathcal{B}(G)/m\), where \(\mathcal{B}(G)\) is the spanning-tree base polytope. What is the minimum worst-case approximation ratio achievable by a no-money mechanism that assigns each tagged agent an inclusion probability \(q_e(d;\nu)\), is truthful under binding reports, and satisfies aggregate feasibility?
Let \(G=(V,E)\) be a connected, loopless undirected multigraph with \(|V|\ge 2\), \(m=|E|\), and \(r=|V|-1\). Edge roles are public and cannot be misreported; costs and cost reports belong to \(\mathbb Q_{\ge 0}\), with no metric restriction.
A nonatomic society is a finite-support probability measure \(\nu\) on edge–cost types \((e,c)\), with \(\nu(\{e\}\times\mathbb Q_{\ge0})=1/m\) for every edge. It is given by its \(\tau\) positive-mass types and their binary rational masses; \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total binary input length; running times are measured in \(m,\tau,L,r\).
A no-money mechanism assigns a tagged agent of role \(e\) reporting \(d\) an inclusion probability \(q_e(d;\nu)\in[0,1]\), including for reports outside the support. A single agent's deviation leaves \(\nu\) unchanged. Binding reports give expected cost \(\max\{c,d\}q_e(d;\nu)\); truthfulness requires \(c q_e(c;\nu)\le\max\{c,d\}q_e(d;\nu)\) for every \(e,c,d,\nu\).
Write \(\mathcal B(G)\) for the spanning-tree base polytope. Aggregate feasibility requires \(x_e=\sum_{c:(e,c)\in\operatorname{supp}\nu}\nu(e,c)q_e(c;\nu)\) and \(x\in\mathcal B(G)/m\) for every report measure; deployments have no additional feasibility constraints.
At truthful reports, define \(\operatorname{SC}_M(\nu)=\sum_{(e,c)}c\nu(e,c)q_e(c;\nu)\) and \(\operatorname{OPT}(\nu)=\min\{\sum_{(e,c)}c y_{e,c}:0\le y_{e,c}\le\nu(e,c),\ (\sum_c y_{e,c})_{e\in E}\in\mathcal B(G)/m\}\).
Let \(A(m,r)\) be the infimum, over mechanisms satisfying these conditions on all such graphs and societies, of their worst-case approximation ratio. A ratio \(\alpha\) means \(\operatorname{SC}_M(\nu)\le\alpha\operatorname{OPT}(\nu)\) for every society, including those with zero optimum.
What is \(A(m,r)\), the optimal worst-case approximation ratio achievable by truthful no-money mechanisms in this nonatomic model?
For discrete edge agents, a polynomial-time truthful-in-expectation mechanism achieves \((m-r)/2+1\), and a graphical family rules out a better general guarantee ([Pountourakis–Schäfer](https://homepages.cwi.nl/~schaefer/ftp/pdf/SAGT14-Matroid-MD.pdf)).
No result settling exactly the nonatomic model above was located.
For every admissible pair \(1\le r\le m\), the answer is \(A(m,r)=1\) when \(m=r\), and \(A(m,r)=+\infty\) when \(m>r\).
The unbounded lower bound holds even with strictly positive rational costs and support size \(\tau=m+2\).
Tree case. Suppose \(m=r\). Connectivity implies that \(G\) is a tree, so its only spanning tree is \(E\). Aggregate feasibility therefore requires, for each edge \(e\),
\(\sum_c \nu(e,c)q_e(c;\nu)=1/m=\sum_c\nu(e,c)\).
Because every supported type has positive mass and every inclusion probability is at most \(1\), this forces \(q_e(c;\nu)=1\) at every supported type. The optimum likewise selects every supported type fully. Consequently, every feasible mechanism has social cost equal to the optimum.
The mechanism \(q_e(d;\nu)=1\) for all reports is truthful: its truthfulness inequality is \(c\le\max\{c,d\}\). Thus \(A(m,r)=1\).
A fixed graph for the unbounded lower bound. Now fix \(m>r\), and put \(k=m-r+1\), so \(k\ge2\).
Take vertices \(v_0,\ldots,v_r\), with \(k\) parallel edges between \(v_0\) and \(v_1\), and the \(r-1\) edges \(v_1v_2,\ldots,v_{r-1}v_r\). Denote the parallel-edge set by \(P\), and distinguish two of its edges, \(a\) and \(b\).
Every spanning tree contains all \(r-1\) path edges and exactly one edge of \(P\). These statements also hold for every vector in the spanning-tree base polytope, since that polytope is the convex hull of spanning-tree incidence vectors.
Choose an integer \(n\ge2\), and define \(\varepsilon=1/n\), \(H=n\), and \(\delta=1/(rn^2)=\varepsilon^2/r\). In particular, \(0<\delta<1<H\).
Define the society by the following conditional cost distributions within each role. Each listed conditional mass is multiplied by \(1/m\) to obtain its mass under \(\nu\).
| Edge role | Cost | Conditional mass |
|---|---:|---:|
| \(a\) | \(1\) | \(\varepsilon\) |
| \(a\) | \(H\) | \(1-\varepsilon\) |
| \(b\) | \(\delta\) | \(1-\varepsilon\) |
| \(b\) | \(H\) | \(\varepsilon\) |
| Each edge in \(P\setminus\{a,b\}\) | \(H\) | \(1\) |
| Each path edge | \(\delta\) | \(1\) |
All masses and costs are positive rationals. Every role has total mass \(1/m\), and the support size is \(\tau=m+2\).
The optimum. Work in units multiplied by \(m\). Each path edge must contribute inclusion mass \(1\), at cost \(\delta\), giving total cost \((r-1)\delta\).
The parallel roles must contribute total inclusion mass \(1\). Their available costs, in increasing order, are:
Since \(\delta<1<H\), the minimum cost is obtained by taking the first two groups fully. This is feasible: their role totals are \(1-\varepsilon\) on \(b\) and \(\varepsilon\) on \(a\), a convex combination of the two corresponding spanning trees. Therefore,
\(m\,\operatorname{OPT}(\nu)=\varepsilon+(r-\varepsilon)\delta>0\).
A lower bound for every truthful mechanism. Fix any truthful feasible mechanism, and suppress \(\nu\) in its notation. Write \(u=q_a(1)\), \(v=q_a(H)\), and \(z=q_b(\delta)\). Let
\(h=(1-\varepsilon)v+\varepsilon q_b(H)+\sum_{e\in P\setminus\{a,b\}}q_e(H)\)
be the total selected conditional mass of cost-\(H\) types.
Aggregate feasibility on \(P\) gives
\(\varepsilon u+(1-\varepsilon)z+h=1\).
Since \(z\le1\), it follows that \(h\ge\varepsilon(1-u)\).
Truthfulness for a cost-\(1\) agent of role \(a\) reporting \(H\), with the society unchanged, gives \(u\le Hv\). Hence
\(Hh\ge H(1-\varepsilon)v\ge(1-\varepsilon)u\).
Set \(s=m\,\operatorname{SC}_M(\nu)\). Dropping the nonnegative contributions of cost-\(\delta\) types yields \(s\ge\varepsilon u+Hh\). The preceding two bounds imply
\(s\ge u\)
and
\(s\ge\varepsilon u+H\varepsilon(1-u)=H\varepsilon-\varepsilon(H-1)u\).
Because \(H>1\) and \(u\le s\), the second inequality further gives
\(s\ge H\varepsilon-\varepsilon(H-1)s\).
Rearranging,
\(s\ge \dfrac{H\varepsilon}{1+\varepsilon(H-1)}=\dfrac{1}{2-\varepsilon}\).
This bound uses only necessary consequences of truthfulness and feasibility, so it applies to every mechanism in the question.
Divergence of the approximation ratio. Since \(\delta=\varepsilon^2/r\),
\(m\,\operatorname{OPT}(\nu)=\varepsilon+(r-\varepsilon)\delta\le\varepsilon+\varepsilon^2\).
Consequently,
\(\dfrac{\operatorname{SC}_M(\nu)}{\operatorname{OPT}(\nu)} \ge\dfrac{1}{\varepsilon(2-\varepsilon)(1+\varepsilon)} =\dfrac{n}{(2-1/n)(1+1/n)} >\dfrac n3\).
For any finite proposed ratio \(\alpha\), choose an integer \(n>3\alpha\). The resulting society violates that guarantee. The graph and support size remain fixed as \(n\) increases.
The mechanism class is nonempty: selecting a fixed spanning tree with report-independent probabilities is truthful and feasible. Nevertheless, every mechanism has unbounded worst-case ratio when \(m>r\). Thus \(A(m,r)=+\infty\).
The [Pountourakis–Schäfer discrete guarantee](https://homepages.cwi.nl/~schaefer/ftp/pdf/SAGT14-Matroid-MD.pdf) concerns one cost-bearing agent per edge. Here, heterogeneous costs within a role let the optimum select only cheap types, while truthfulness forces inclusion of expensive types in that same role. The construction proves that this distinction prevents every finite guarantee, even with strictly positive costs and positive optimum.
⟨structured verdict parsed — rendered above⟩
The claimed answer is proved: \(A(m,r)=1\) for \(m=r\), and \(A(m,r)=+\infty\) for \(m>r\). No major or minor mathematical issues were found.
The optimum has the same forced selection, so the costs coincide, including when the optimum is zero. The proposed mechanism assigns probability \(1\) at every report and satisfies \(c\le\max\{c,d\}\). Societies with positive costs also rule out any guarantee below \(1\). Hence the exact value follows.
Each path edge is a bridge. Every spanning tree therefore contains all path edges and exactly one parallel edge. These equalities persist under convex combinations, as claimed. The construction also covers \(r=1\), when there are no path edges.
There are exactly \(m+2\) supported edge–cost types. All costs and masses are positive rationals with finite binary encodings. Increasing their input lengths is allowed: the proposed approximation guarantee must hold for every society.
The parallel roles must supply total selected mass \(1\). Their available mass below cost \(H\) consists precisely of \(1-\varepsilon\) at cost \(\delta\) and \(\varepsilon\) at cost \(1\). Selecting both groups fully minimizes cost even under the relaxed constraint of total mass alone. The stated convex combination of spanning trees verifies feasibility under the actual base-polytope constraint.
Consequently, the exact expression
\(m\operatorname{OPT}(\nu)=\varepsilon+(r-\varepsilon)\delta>0\)
is correct.
\(\varepsilon u+(1-\varepsilon)z+h=1\).
Using \(z\le1\) gives \(h\ge\varepsilon(1-u)\), with the inequality direction correct.
All terms in \(h\) are nonnegative, so
\(Hh\ge H(1-\varepsilon)v\ge(1-\varepsilon)u\).
This argument uses only a necessary truthfulness inequality; no characterization of truthful mechanisms is assumed.
\(s\ge\varepsilon u+Hh\).
The two established bounds on \(h\) yield, respectively,
\(s\ge u\) and
\(s\ge H\varepsilon-\varepsilon(H-1)u\).
Since \(\varepsilon(H-1)>0\), substituting \(u\le s\) into the negative term has the stated direction. Rearrangement is valid because \(1+\varepsilon(H-1)>0\). Substituting \(H=n\) and \(\varepsilon=1/n\) gives exactly \(s\ge1/(2-\varepsilon)\).
\(m\operatorname{OPT}(\nu)\le\varepsilon+\varepsilon^2\)
follows directly from \(\delta=\varepsilon^2/r\). Division is valid because the optimum is strictly positive.
The resulting ratio bound is correct. For \(0<\varepsilon\le1/2\), its denominator factor satisfies
\((2-\varepsilon)(1+\varepsilon)=2+\varepsilon-\varepsilon^2<3\),
verifying the strict bound \(n/3\).
The graph is fixed for each pair \((m,r)\), and the same societies give the lower bound for every truthful feasible mechanism. Choosing arbitrarily large \(n\) therefore excludes every finite worst-case guarantee.
The cited discrete model assigns agents to individual matroid elements, consistent with the prover’s contextual distinction. Its theorem is not used in the nonatomic proof. [Pountourakis–Schäfer](https://homepages.cwi.nl/~schaefer/ftp/pdf/SAGT14-Matroid-MD.pdf)
No additional clarification, missing lemma, or mathematical repair is required. The result establishes an exact approximation limitation; it does not establish computational hardness.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.