d4-conf-sagt-2014-0011

My lead, and sole anchor, is Theorem 5, proved in this paper. It says that for graphical matroids, no mechanism that is truthful in expectation can achieve an approximation ratio better than \((m-r)/2+1\), where \(m\) is the number of elements and \(r\) is the matroid rank. This is an approximation lower bound for truthful mechanisms, not an NP-hardness theorem.

A concrete mirror is Repeated-Network Continuum Hiring. Fix a connected graph \(G=(V,E)\) with \(m\) edges and rank \(r\). Imagine \(N\) identical network deployments, each needing a spanning tree. For each edge role \(e\), there are \(N\) interchangeable contractors, all with the same actual unit cost \(a_e\). Thus there are \(mN\) people but only \(m\) types, \(t_e=(e,a_e)\). Normalizing population mass by \(mN\), each type has mass \(\mu_{t_e}=1/m\). This preserves every edge-cost vector from the paper’s graph instances while making each edge role a large cohort.

The decision variable \(x_e\) is the fraction of the whole population hired from edge role \(e\). Feasibility is
\[ x\in \frac{1}{m}\mathcal B(G), \qquad \mathcal B(G)=\operatorname{conv}\{\mathbf 1_T:T\text{ is a spanning tree of }G\}. \]
This is the aggregate limit of hiring a spanning tree in each copy. The truthful optimum is
\[ \operatorname{OPT}_\infty(G,a) =\min_{x\in \frac{1}{m}\mathcal B(G)}\sum_{e\in E}a_ex_e =\frac{1}{m}\min_{T\text{ spanning tree}}\sum_{e\in T}a_e. \]

The problem to hand a prover is: given \(G\) and a finite-support report measure over its edge roles, find the minimum worst-case approximation ratio of a no-money mechanism that selects feasible hired mass and is truthful in expectation under binding reports. More precisely, the mechanism must provide an inclusion probability \(q_e(d;\nu)\) for a tagged agent of role \(e\) reporting cost \(d\), given the measure \(\nu\) of the other agents’ reports. Its aggregate hired vector must lie in \(\mathcal B(G)/m\), and for every actual cost \(a\) and alternative report \(d\) it must satisfy
\[ a\,q_e(a;\nu)\le \max\{a,d\}\,q_e(d;\nu). \]
The objective is to minimize the worst-case truthful social cost divided by \(\operatorname{OPT}_\infty(G,a)\). A solution is a mechanism rule with a proved feasibility, truthfulness, and ratio guarantee.

For this regime I expect Class A, with ratio \(1\). Here is the reason. For each role, take a weighted median of the reports from the other members of that role, compute a minimum spanning tree using those medians, and hire all the mass in roles on that tree. In the atomless limit, one person’s report does not change the report measure, so their inclusion probability is independent of their own report. If selected, truthful reporting minimizes their binding cost; if not selected, they incur no hiring cost. At a truthful population, each role’s report measure is concentrated at \(a_e\), so the mechanism chooses a minimum-cost spanning tree. The hired mass is \(\mathbf 1_T/m\), and the mechanism attains the optimum. Medians and a minimum spanning tree are computable in polynomial time. The same idea has a finite repeated-deployment version using leave-one-out reports: each deployment still receives a spanning tree, and a person’s own report does not affect the tree for their deployment.

The authors should recognize this as a mirror of their problem: the agents are still hired to perform network tasks, the objective is still minimum total cost, reports remain binding, and the outcome remains a matroid base. The continuous object is the population mass in each edge-cost type. The fractional base polytope describes the aggregate of repeated bases; it is part of the mirror forced by the population scaling.

The weak point is substantial: this is a specific high-multiplicity regime, with one shared cost per edge role. If a role contains several cost types, selecting the right fractions of people within it becomes a real incentive problem, and the median mechanism gives no general ratio guarantee. Theorem 5 also does not itself imply a lower bound for repeated copies. That is why this mirror is a useful test of whether the theorem’s obstruction survives continuization, rather than a claim that the paper’s full lower bound disappears.

This case covers Theorem 5 only. It leaves open how the best ratio depends on support size when roles have heterogeneous costs, whether useful guarantees hold for finite \(N\), and whether the lower bound returns when coalitional misreports or more general cost profiles are included.