Answer: \(\alpha_{\mathrm{path}}(N,\tau)=N\) for every \(N\geq2\) and \(\tau\geq1\); it grows linearly with \(N\) for every fixed \(\tau\).
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateNo truthful mechanism for the min-max path problem can be better than n-approximate.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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\)?
A public network template consists of a finite undirected graph \(G=(V,E)\), distinct connected terminals \(s,t\), and a partition \(E=\bigsqcup_{i=1}^{N}E_i\) into nonempty supplier holdings, with \(N\geq2\).
Each supplier has a public role \(r_i\); each role has a finite set of edge slots \(S_r\), and the template specifies a bijection \(\phi_i:E_i\to S_{r_i}\). A complete role-cost type is \((r,c)\), where \(c\in\mathbb{Q}_{\geq0}^{S_r}\); supplier identities are not part of types.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational. Require \(\sum_a\mu_a=1\) and \(N\mu_a\in\mathbb{Z}_{>0}\); \(\tau\) is the support size, not the number of possible types. These multiplicities must match the template's role counts.
The distribution specifies a multiset of supplier types; guarantees range over every assignment of this multiset to compatible supplier slots. Suppliers individually submit labeled cost-vector reports; the distribution is an empirical profile description, not a public prior or a restriction on possible reports.
For a simple integral \(s\)-to-\(t\) path \(P\), supplier \(i\)'s cost is \(C_i(P,c_i)=\sum_{e\in P\cap E_i}c_i(\phi_i(e))\), and \(\operatorname{OPT}(c)=\min_P\max_i C_i(P,c_i)\). Costs are not multiplied by masses.
A deterministic mechanism chooses such a path and finite real payments \(p_i\), with utilities \(p_i-C_i\). Require dominant-strategy truthfulness on all nonnegative rational cost-vector profiles, including unilateral deviations that increase support size; ownership and roles cannot be misreported. Tie-breaking is part of the mechanism.
Define \(\alpha_{\mathrm{path}}(N,\tau)\) as the infimum, over these truthful mechanisms, of uniform approximation factors over all templates and compatible profiles having support size at most \(\tau\): \(\max_i C_i(A(c),c_i)\leq\alpha\operatorname{OPT}(c)\), including when \(\operatorname{OPT}(c)=0\).
There is no running-time restriction. State any running times in \(m=|V|+|E|\), support size \(\tau\), total binary input length \(L\), and \(N\).
What is the optimal worst-case approximation ratio \(\alpha_{\mathrm{path}}(N,\tau)\) achievable by deterministic dominant-strategy truthful mechanisms? For each fixed \(\tau\), is it bounded independently of \(N\), or must it grow without bound?
For unrestricted discrete societies, the optimal deterministic truthful approximation factor is \(N\), without a running-time restriction; VCG attains it. [Verified source](https://doi.org/10.1016/j.geb.2018.05.003)
No result settling the guarantee for bounded support of complete role-cost types was located in the literature search.
For every \(N\geq2\) and every positive integer \(\tau\),
\[
\boxed{\alpha_{\mathrm{path}}(N,\tau)=N.}
\]
Thus, for each fixed \(\tau\), the optimal factor grows linearly with \(N\). The lower bound already holds for societies with one complete role-cost type.
The unrestricted lower bound is established by [Leucci, Mamageishvili, and Penna](https://arxiv.org/abs/1712.06709). Below is a self-contained proof that preserves the support requirement.
The construction uses exactly the stated notion of type equality: suppliers have the same public role and the same complete vector in its slots. Their public slot bijections may place those slots differently in the graph.
For a labeled report profile \(c\), choose a simple path \(A(c)\) minimizing
\[
T(P,c)=\sum_{i=1}^{N}C_i(P,c_i),
\]
using a fixed deterministic tie-breaking rule.
Use Groves payments
\[
p_i(c)=H_i(c_{-i})-\sum_{j\ne i}C_j(A(c),c_j),
\]
where, for example,
\[
H_i(c_{-i})=\sum_{j\ne i}\sum_{e\in E_j}c_j(\phi_j(e)).
\]
These payments are finite rationals.
Fix supplier \(i\)'s true vector \(c_i\) and the other reports \(c_{-i}\). If a report by \(i\) produces path \(P\), her utility is
\[
H_i(c_{-i})-\left(C_i(P,c_i)+\sum_{j\ne i}C_j(P,c_j)\right).
\]
Reporting \(c_i\) makes the mechanism minimize the parenthesized expression over all feasible paths. Hence truthful reporting maximizes utility, proving dominant-strategy truthfulness on the entire report domain.
If \(P^\star\) minimizes the maximum supplier cost, nonnegativity gives
\[
\max_i C_i(A(c),c_i)
\leq T(A(c),c)
\leq T(P^\star,c)
\leq N\operatorname{OPT}(c).
\]
This also covers \(\operatorname{OPT}(c)=0\): then the chosen path has total cost zero, so every supplier's cost is zero.
The mechanism runs in \(\operatorname{poly}(m,N,\tau,L)\) bit operations: it needs one shortest-path computation with exact rational weights, deterministic tie-breaking, and rational summations.
Therefore \(\alpha_{\mathrm{path}}(N,\tau)\leq N\).
Call an edge *active* if it belongs to some simple terminal path. Other edges never contribute to any supplier's path cost.
Lemma. Fix the other suppliers' reports. Suppose the mechanism chooses \(P\) when supplier \(i\) reports \(x_i\). Change her report to \(y_i\) so that:
Then the new chosen path \(Q\) satisfies
\[
Q\cap E_i=P\cap E_i.
\]
Proof. Apply truthfulness once with true type \(x_i\) and once with true type \(y_i\). Adding the two incentive inequalities cancels payments and gives
\[
C_i(P,x_i)+C_i(Q,y_i)
\leq C_i(Q,x_i)+C_i(P,y_i).
\]
Write \(d(e)=y_i(\phi_i(e))-x_i(\phi_i(e))\). The inequality becomes
\[
\sum_{e\in Q\cap E_i}d(e)
\leq \sum_{e\in P\cap E_i}d(e).
\]
Consequently,
\[
\sum_{e\in(Q\setminus P)\cap E_i}d(e)
-
\sum_{e\in(P\setminus Q)\cap E_i}d(e)
\leq0.
\]
Every term in the first sum is strictly positive, and every term in the second sum is strictly negative. If either edge difference were nonempty, the left side would be strictly positive. Both differences must therefore be empty. Edges that are not active occur in neither path and do not affect this argument. \(\square\)
Fix an arbitrary deterministic truthful mechanism and an integer \(\ell\geq2\).
Create vertices \(u_0,\ldots,u_\ell\), with \(s=u_0\) and \(t=u_\ell\). For each block \(k\in\{1,\ldots,\ell\}\), join \(u_{k-1}\) to \(u_k\) by \(N\) internally vertex-disjoint branches, indexed by \(a\in\{1,\ldots,N\}\).
Each branch has \(N\) edges,
\[
e_{k,a,1},\ldots,e_{k,a,N},
\]
in that order, with \(e_{k,a,i}\) owned by supplier \(i\).
Every simple terminal path chooses exactly one branch in each block. Indeed, the block endpoints separate consecutive blocks, and each branch's internal vertices have degree two.
For every supplier \(i\), the set \(P\cap E_i\) identifies the branch chosen in every block. Thus, on this graph,
\[
P\cap E_i=Q\cap E_i\quad\Longrightarrow\quad P=Q.
\]
Give every supplier the same role \(r\), with slot set
\[
S_r=\{1,\ldots,N\}\times\{1,\ldots,\ell\}\times\{1,\ldots,N\}.
\]
For supplier \(i\), map the active edge \(e_{k,a,i}\) to slot \((i,k,a)\).
For every remaining slot \((j,k,a)\), where \(j\ne i\), create a distinct edge owned by \(i\), joining \(s\) to a new private leaf, and map that edge to \((j,k,a)\).
A leaf edge belongs to no simple terminal path. This padding makes each map \(\phi_i:E_i\to S_r\) a bijection. Every supplier owns \(N^2\ell\) edges, and all have the same role.
The slot names are common public coordinates; they do not add supplier identity to a type. In particular, assigning the same vector \(q\in\mathbb{Q}_{\geq0}^{S_r}\) to everyone gives exactly one complete type \((r,q)\).
The template is connected, has nonempty holdings, and has \(m=O(N^3\ell)\). It is fixed before observing the mechanism's output.
Set \(\varepsilon=1/\ell^2\). Initially, supplier \(i\)'s vector \(x_i\) is
\[
x_i(j,k,a)=
\begin{cases}
1,&j=i\text{ and }a=i,\\
\varepsilon,&j=i\text{ and }a\ne i,\\
0,&j\ne i.
\end{cases}
\]
Thus each branch has one active edge of cost \(1\), owned by its branch index, and all its other active edges have cost \(\varepsilon\).
Let the mechanism choose \(P^0\), with branch \(a_k\) in block \(k\). Define
\[
b_i=\bigl|\{k:a_k=i\}\bigr|.
\]
Since \(\sum_i b_i=\ell\), some supplier \(h\) has
\[
b:=b_h\geq\ell/N.
\]
For notation, let
\[
w_i(a)=
\begin{cases}
1,&a=i,\\
\varepsilon,&a\ne i.
\end{cases}
\]
Now define one common vector \(q\) on all slots:
\[
q(i,k,a)=
\begin{cases}
w_i(a)-\varepsilon/2,&a=a_k\text{ and }i=h,\\
0,&a=a_k\text{ and }i\ne h,\\
w_i(a)+\varepsilon,&a\ne a_k.
\end{cases}
\]
All its entries are nonnegative rationals.
Replace suppliers' reports \(x_i\) by \(q\), one supplier at a time.
For the supplier currently being changed:
The lemma therefore preserves her selected active edges. Those edges identify the entire path, so the chosen path remains \(P^0\). Induction over the suppliers proves
\[
A(q,\ldots,q)=P^0.
\]
This step uses truthfulness at intermediate profiles, whose support can exceed one. That is permitted—and required—by the task's global truthfulness condition.
At the final profile, every supplier has exactly the same complete type \((r,q)\). Its society description has mass \(1\), satisfies \(N\mu=N\), and matches the role count.
At the final profile, every supplier other than \(h\) has zero cost on \(P^0\). Supplier \(h\)'s cost is
\[
C_h(P^0,q)
=b(1-\varepsilon/2)+(\ell-b)\varepsilon/2
\geq b(1-\varepsilon/2).
\]
We next exhibit a cheaper path for the maximum-cost objective.
Let
\[
B=\{k:a_k=h\},
\]
so \(|B|=b\). Construct \(Q\) as follows:
Outside \(B\), retaining the original branch costs supplier \(h\) exactly \(\varepsilon/2\) per block and costs every other supplier zero.
Within \(B\):
Hence every supplier's cost on \(Q\) is at most
\[
\left\lceil\frac bN\right\rceil(1+\varepsilon)+2\varepsilon\ell.
\]
Therefore,
\[
\operatorname{OPT}(q,\ldots,q)
\leq
\left\lceil\frac bN\right\rceil(1+\varepsilon)+2\varepsilon\ell.
\]
Substituting \(\varepsilon=1/\ell^2\), using \(b\leq\ell\), and recalling \(N,\ell\geq2\), gives
\[
\operatorname{OPT}(q,\ldots,q)
\leq
\frac bN+1+\frac{b}{N\ell^2}+\frac1{\ell^2}+\frac2\ell
\leq\frac bN+3.
\]
The optimum is positive: every feasible path uses an active edge of supplier \(h\) in every block, and all her active-edge costs are positive. Division is thus valid, and
\[
\frac{\max_i C_i(A(q,\ldots,q),q)}
{\operatorname{OPT}(q,\ldots,q)}
\geq
\frac{b(1-1/(2\ell^2))}{b/N+3}
=
\frac{N(1-1/(2\ell^2))}{1+3N/b}
\geq
\frac{N(1-1/(2\ell^2))}{1+3N^2/\ell}.
\]
For fixed \(N\), the last expression tends to \(N\) as \(\ell\) tends to infinity. Thus, for every \(\alpha<N\), a sufficiently large finite template and a support-one profile violate an \(\alpha\)-approximation guarantee.
Because the mechanism was arbitrary, this proves
\[
\alpha_{\mathrm{path}}(N,1)\geq N.
\]
Support-one profiles are included whenever \(\tau\geq1\), so the same lower bound holds for every such \(\tau\). Together with the truthful upper bound, this establishes the claimed equality.
⟨structured verdict parsed — rendered above⟩
The proof resolves the assigned question: \(\alpha_{\mathrm{path}}(N,\tau)=N\) for every \(N\geq2\) and every positive integer \(\tau\). The support-one lower bound is valid under the task’s definition of complete role-cost types. I found no major or minor mathematical gaps.
The feasible set of simple terminal paths is finite and nonempty. Thus the total-cost minimizer exists, and fixed deterministic tie-breaking defines an allocation.
The stated payments give supplier \(i\) utility
\(H_i(c_{-i})-C_i(P,c_i)-\sum_{j\ne i}C_j(P,c_j)\)
when her report induces path \(P\). Holding other reports fixed, truthful reporting minimizes precisely the cost expression subtracted from \(H_i(c_{-i})\). This proves dominant-strategy truthfulness against every allowed unilateral report, without any support restriction.
All payments are finite rationals. Nonnegativity justifies each inequality in the approximation chain, including
\(T(P^\star,c)\leq N\operatorname{OPT}(c)\).
When the optimum is zero, the selected total cost must also be zero, so every supplier’s selected cost is zero.
The polynomial implementation claim is consistent with exact rational shortest-path computation and deterministic tie-breaking. Rational sums and comparisons have polynomial bit complexity in the stated input parameters.
The two incentive inequalities are applied with the same other-supplier reports and with the two possible true vectors \(x_i\) and \(y_i\). Payments therefore cancel as claimed.
The resulting inequality has the correct direction:
\(\sum_{e\in Q\cap E_i}d(e)\leq\sum_{e\in P\cap E_i}d(e)\).
Every edge in \((Q\setminus P)\cap E_i\) is active and has positive \(d(e)\). Every edge in \((P\setminus Q)\cap E_i\) has negative \(d(e)\), which is subtracted. Consequently, any nonempty difference would make the left side of the rearranged inequality strictly positive.
The conclusion \(Q\cap E_i=P\cap E_i\) follows. No assumption about payments beyond truthfulness and finiteness is needed.
The successive block endpoints separate the terminal path into blocks. Within each block, the branches have disjoint interiors and internal vertices of degree two. A simple terminal path therefore traverses exactly one complete branch in each block.
Every branch contains one edge belonging to every supplier. For any supplier, her selected edges identify the branch in each block. Hence preservation of one supplier’s selected edge set preserves the entire terminal path in this construction.
Private leaf edges cannot belong to a simple terminal path: entering their leaf would require returning through the same edge and repeating a vertex.
The slot set has \(N^2\ell\) elements. Each supplier has \(N\ell\) active edges and \((N-1)N\ell\) padding edges, so the specified map is indeed a bijection.
The role is common to every supplier. The coordinate \(i\) in a slot label is a common public coordinate, and different suppliers’ bijections may assign different coordinates to their active edges. This does not make supplier identity part of a type.
Accordingly, assigning the complete vector \(q\) to every supplier produces exactly one type \((r,q)\), including equality on all padding coordinates. Its mass is \(1\), its multiplicity is \(N\), and its role count matches the template.
The construction also satisfies the remaining template requirements: finite undirected graph, distinct connected terminals, nonempty disjoint supplier holdings, and \(m=O(N^3\ell)\).
The initial costs have the stated values: branch \(a\) has cost \(1\) for supplier \(a\), and cost \(\varepsilon\) for every other supplier.
Since \(\sum_i b_i=\ell\), the choice of \(h\) with \(b_h\geq\ell/N\) is justified.
Every entry of \(q\) is a nonnegative rational. In particular, selected active edges of \(h\) cost either \(1-\varepsilon/2\) or \(\varepsilon/2\), both positive because \(\ell\geq2\). Selected active edges of other suppliers become zero, and every unselected active edge increases by \(\varepsilon\).
At each replacement, the supplier being changed still reports her original vector \(x_i\). Previous replacements affect only other suppliers.
Provided the current path is \(P^0\), all her selected active edges strictly decrease and all her unselected active edges strictly increase. The lemma preserves her selected edge set, which identifies the whole path. The induction proving \(A(q,\ldots,q)=P^0\) is therefore valid.
Intermediate profiles need not have support one. Their use is expressly permitted by the task’s requirement of truthfulness on the entire report domain. No bounded-support approximation guarantee is invoked at those profiles.
On \(P^0\), every supplier other than \(h\) has zero cost. Supplier \(h\)’s stated cost
\(b(1-\varepsilon/2)+(\ell-b)\varepsilon/2\)
correctly counts the two possible selected-edge costs.
The comparison path exists because branch choices are independent across blocks. Distributing the \(b\) choices among \(N\) indices with each used at most \(\lceil b/N\rceil\) is feasible.
The costs listed for each branch choice are correct. Each supplier incurs at most \(\lceil b/N\rceil\) contributions bounded by \(1+\varepsilon\); the remaining contributions, including those outside \(B\), are covered by \(2\varepsilon\ell\). Thus the stated upper bound on the optimum is valid.
Substitution of \(\varepsilon=1/\ell^2\) and the ceiling bound gives the displayed estimate. The additive terms are bounded by \(3\) throughout \(N,\ell\geq2\), so \(\operatorname{OPT}\leq b/N+3\) is correct.
Supplier \(h\) has positive cost on every active edge she owns, and every feasible path uses one such edge in every block. The optimum is therefore positive, validating division.
The final ratio inequality uses \(b\geq\ell/N\) in the correct direction. For each fixed \(N\), its right-hand side tends to \(N\). Hence every factor strictly below \(N\) fails on a sufficiently large finite support-one instance. The argument does not require an instance attaining ratio exactly \(N\).
The mechanism is arbitrary, the template is fixed before its initial output is observed, and the resulting profile is an allowed worst-case profile. Choosing that profile after inspecting the deterministic allocation is legitimate for a uniform lower bound.
Support-one profiles belong to every class with support at most \(\tau\geq1\). The lower bound therefore combines with the upper bound to establish the claimed equality for all requested parameters.
The cited paper’s abstract supports the background unrestricted approximation claim; the bounded-support conclusion is established by the supplied argument itself. [Leucci, Mamageishvili, and Penna](https://arxiv.org/abs/1712.06709)
No repair or additional clarification is required. The complexity-status classification below is “other” because the established result concerns the optimal truthful approximation guarantee; it does not classify the complexity of exact optimization.
⟨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.