# truthful_mechanisms_for_steiner_tree_problems__4da76002.pdf

Truthful Mechanisms for Steiner Tree Problems

Jinshan Zhang1, Zhengyang Liu2*, Xiaotie Deng3, Jianwei Yin1

1 Zhejiang University 2 Beijing Institute of Technology 3 Peking University zhangjinshan@zju.edu.cn, zhengyang@bit.edu.cn, xiaotie@pku.edu.cn, zjuyjw@cs.zju.edu.cn

Consider an undirected graph G = (V, E) model for a communication network, where each edge is owned by a selfish agent, who reports the cost for offering the use of her edge. Note that each edge agent may misreport her own cost for the use of the edge for her own benefit. In such a noncooperative setting, we aim at designing an approximately truthful mechanism for establishing a Steiner tree, a minimum cost tree spanning over all the terminals. We present a truthful-in-expectation mechanism that achieves the approximation ratio ln 4 + ϵ 1.39, which matches the current best algorithmic ratio for STP.

1 Introduction

Given a graph G = (V, E) and a set of terminal vertices R V , each edge e E is associated by a cost c(e). The Steiner Tree Problem (STP) is to find a minimum cost tree over G that spans all the terminal vertices in R. One can also include extra intermediate vertices and edges to reduce the cost of the induced spanning tree. These extra vertices introduced to decrease the total cost of connection are known as Steiner points or Steiner vertices. The STP is one of the most important and fundamental problems widely studied in the fields of computer science and operations research, with wide practical applications such as the design of VLSI (Very Large Scale Integration), optical and wireless communication systems, as well as transportation and distribution networks (Hwang and Richards 1992). However, finding the optimal solution in the STP is known to be one of Karp s original 21 NP-complete problems (Karp 1972). That means we cannot hope to solve this problem exactly. For the approximate version, it is APXhard and can not be approximated within 96

95 unless P = NP (Bern and Plassmann 1989; Chleb ık and Chleb ıkov a 2008). During last decades, a sequence of improved approximation ratios for the problem (from 11

6 to 1 + ln 3

2 + ϵ 1.55) is obtained (Zelikovsky 1993; Karpinski and Zelikovsky 1997; Pr omel and Steger 2000; Robins and Zelikovsky 2005). Until recently, by leveraging the LP iterative rounding approach, a ln 4+ϵ 1.39-approximate algorithm

*Zhengyang Liu is the corresponding author. Copyright 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

is proposed in (Byrka et al. 2013) and later a deterministic more efficient algorithm with the same approximation ratio is given by (Goemans et al. 2012). Very recently, the same approximation ratio has been achieved by Traub and Zenklusen (2021), from a purely combinatorial point of view. For any large network, such as a network for the STP, there exists heterogeneous resources like vertices and edges, of which may be held by different owners. These owners intend to perform certain tasks to earn their rewards. We take the message broadcast as an example. From the perspective of network management, it seems that the rewards of the owners can be seen as the price of the service that forwards the messages. Therefore, economically speaking, each owner declares that its true price is desirable. It turns out that in several web applications or internet services, one needs to efficiently calculate the solution of the given optimization problem, where additional restrictions to active agents (through appropriate payments) can be proposed to cooperate within the algorithm. This combined output of the calculation and the payment is often referred to as a mechanism. A realistic applicable scenario based on the above motivation can be seen as a two-player game between the Internet Service Provider (ISP) and Content Provider (CP) (Saltzer, Reed, and Clark 1984; Armstrong 2006; Deng, Feng, and Papadimitriou 2016), where CP would like to build a connection among different sites to users (e.g., establishing a Steiner tree among terminal vertices) through the internet service provided by different ISPs (e.g., different edges belongs to different ISPs). Each ISP charges CP in order to maximize her own utility. From the above consideration and wide applications of the STP, we consider this problem in a strategic and noncooperative way. More precisely, each edge in the graph is held by a selfish agent who reports her private cost c(e) to the mechanism designer. The edge holder reports the cost of its edge to maximize his utility (i.e., valuation minus the payment, where the valuation is c(e)). It turns out that in many applications the mechanism designer should provide a mechanism that incentivizes each agent to report his true cost. Such a mechanism usually refers to a truthful mechanism. Previously, as far as we know, only a 2-approximate truthful mechanism (Wang, Li, and Wang 2004) for the STP with k terminal vertices was known and this ratio was im-

The Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI-23)

proved to (2 1

k) (Gual a and Proietti 2005) while preserving truthfulness. (Christodoulou and Sgouritsa 2019) considers the problem of designing network cost-sharing protocols with good equilibria under uncertainty, where only terminals are the agents who need to select a path to the same root and the objective of the mechanism designer is to construct a Steiner tree. In this paper, we propose a truthful (in expectation) mechanism for STPs on general graphs with arbitrary terminal vertices, of witch the ratio matches the current best algorithmic ratio ln 4 + ϵ 1.39. Precisely, a mechanism is truthful in expectation if no agent can obtain more expected utility by deviating from his truthful cost in the mechanism. We employ the decomposition technique due to (Lavi and Swamy 2011) for the design of truthful mechanisms to find a decomposition according to the optimal fractional solution of k Directed Component-based Relaxation (k-DCR), which is an LP relaxation of the STP. A detailed description of such a decomposition is shown in Section 3. This decomposition (which is a convex combination of a polynomial number of integral solutions) is based on the deterministic algorithm for k-DCR in (Traub and Zenklusen 2021) and achieves the same approximation ratio as that in deterministic algorithms. However, we cannot imply a truthful mechanism by directly employing the technique, since the solution of the k-DCR only considers on the components. We present a specified payment rule by transforming the payment on the component by that technique into the payment on the edge. We then show that our mechanism is truthful in expectation. Finally, by the well-known relation among k-DCR, STP and the maximal-in-range methodology, the approximation ratio ln 4 + ϵ of our mechanism is proved by choosing k = 2 1 ϵ for any given ϵ > 0. It is worth to mention that a direct application of the decomposition technique (Theorem 1) is the survivable Network Design (Orlowski et al. 2010; Lau et al. 2009).

Related work. Besides the current best algorithmic bounds for general graph proposed in (Byrka et al. 2013), there is other progress in the design of efficient algorithms for the STP. Chen and Hsieh (2020) present an efficient twophase heuristic strategy that achieves an approximation ratio of 1.4295 in the greedy regime. Chen and Hsieh (2022) study the STP with bounded edge-length d in which d is the ratio of the maximum edge cost to the minimum edge cost. This work analyzes the algorithm of Byrka et al. (2013) and shows that the approximation ratio of d ln 4 d+ln 4 1 + ϵ for general graphs and approximation ratio of 73d 60d+13 + ϵ for quasibipartite graphs. Siebert et al. (2020) present a set of integer programmings for the Steiner tree problem with the property that the best solution is obtained by solving all, and provide an optimal Steiner tree. Saikia and Karmakar (2021) present two deterministic distributed algorithms for the Steiner tree problem in the congest model, both of which improve the previous complexity of distributed algorithms for the STP. Based on the decomposition technique in Section 3 originated from (Lavi and Swamy 2011), the hypergraphic relaxation and the integrality gap for the Steiner tree problem are closely related to the mechanism design. In (2013),

Byrka et al. proved an integrality gap 1.55 for k directed component relaxation of the Steiner tree. Chakrabarty et al. (Chakrabarty, K onemann, and Pritchard 2010) describe a shorter proof of the same integrality gap bound, by applying some of their techniques to a randomized loss-contracting algorithm. The same authors (Chakrabarty, K onemann, and Pritchard 2013) prove new partition-based relaxation of hypergraphic linear programming relaxations for the Steiner tree problem is equivalent to many existing hypergraphic relaxation for the Steiner tree problem. In (Feldmann et al. 2016), Feldmann et al. give an efficient constructive proof that bi-directed component relaxation and hypergraphic linear programming relaxation are polyhedrally equivalent in instances that do not have an (edge-induced) claw on Steiner vertices. Goemans et al. (Goemans et al. 2012) first show that the component-based LP relaxation of the Steiner tree problem achieves an integrality of ln 4 and present a deterministic ln 4 + ϵ algorithm to find an integral solution with this gap. Very recently, Traub and Zenklusen (Traub and Zenklusen 2021) show the same integrality gap holds for k-DCR of the Steiner tree problem by deterministically finding an integral solution with such a gap through somehow greedy procedures. Our truthful mechanism with the ratio ln 4 + ϵ was based on this algorithm, with other fundamental insights. Another related work is the directed Steiner tree problem, where the given input graph is a directed one. Grandoni et al. (Grandoni, Laekhanukit, and Li 2019) present a tight O( log2 k

log log k) approximation algorithm for directed Steiner tree problem running in quasi-polynomial time e.g., in time npoly(log k). Li and Laekhanukit (2021) give the first known lower bound on the integrality gap of the standard flow LP relaxation for the directed Steiner tree problem that is polynomial in n, the number of vertices. Chitnis et al. (2021) systematically study several special cases of directed Steiner Network and determine their parameterized approximability for the parameter k, the demand pairs. By primaldual scheme, Friggstad and Mousavi (2021) give the first constant-factor approximation algorithm for quasi-bipartite instances of directed Steiner tree problem on graphs that exclude fixed minors. Before our work, the best known truthful approximation for the Steiner tree problem with the polynomial-time is shown by (Gual a and Proietti 2005) with the ratio 2 1

k, where k is the number of terminals. This paper improves this ratio to the current best algorithmic ratio by truthful in expectation mechanisms.

Orgnizations. The rest of this paper is orgnized as follows. We will show the necessary preliminaries in Section 2. In Section 3, we then describe the detailed decomposition technique for a related covering problem. Section 4 is devoted to the truthful mechanism for our problem. Finally, we conclude in Section 5.

2 Preliminaries

We are given an undirected graph G = (V, E), a nonnegative cost function c : E R 0 for each edge e E

and a set of terminals R V . The Steiner Tree Problem (STP) is to find a minimum cost tree on G spanning over the terminal set R where extra intermediate vertices and edges can be added to the graph in order to reduce the cost of the spanning tree. Note that any tree on G spanning on R is a feasible integral solution for STP. We call a vertex v V is a Steiner vertex if v V \ R. We also use I = (V, E, R, c) to denote an instance of the STP and I to denote the set of all the instances of the STP. Suppose each edge e E is held by a rational agent and then her valuation to edge e is c(e). A randomized mechanism M is a map M : I (X(I), P(I)), for any instance I I, where X(I) = (Xe(I))e E is a randomized solution for the STP (i.e., Xe(I) is the allocation probability of edge e) and P(I) = (Pe(I))e E R|E| + is the (expected) payment vector for each edge e E. We use c (e) to denote the bidding cost of edge e. We write Xe(I) as Xe(c ), for e E, where c = (c (e))e = (c (e), c ( e)), where c ( e) denotes the bidding cost vector of all the edges except edge e. Similarly, we have Pe(c ), e E. The (expected) utility ue(c (e), c ( e)) of agent e under the bidding vector c = (c (e), c ( e)) is

ue(c (e), c ( e)) = E[ c(Xe(c )) Pe(c )],

where c(Xe(c )) is the random cost of edge e under bidding vector c = (c (e), c ( e)), and the expectation is taken over all the random bits of the mechanism. Since in our setting it is a reverse auction or a procurement auction where sellers bid, we have Pe(I) 0, for all e E and I I, which means sellers will receive money from buyers. Definition 1. A mechanism M = (X, P) is truthful in expectation if for any I I, any edge e E,

ue(c(e), c ( e)) ue(c (e), c ( e)),

where c (e)e = (c (e), c ( e)) are their biddings and c(e) is the truthful cost of the edge e. For each subgraph C G, we use R(C) to denote the set of terminal vertices contained in the subgraph C. We consider two different LP relaxations of STP. One is called Bidirected Cut Relaxation (BCR) and the other is called hypergraphic linear programming relaxation (HYP) (or called directed component relaxation in another form of HYP). We first present the BCR formula. We replace each edge (u, v) E by two directed edges (u, v) and (v, u). For a given cut U V , we denote by δ+(U) = {(u, v) E | u U, v / U} the set of edges leaving U. We choose any terminal vertex r R as a root, then the objective of the BCR is

e E c(e)ze (BCR)

e δ+(U) ze 1 U V \ {r} : U R =

ze {0, 1} e E

The original relaxation of the BCR is to relax the constraint ze {0, 1}, e E above to ze 0, e E. In the following, when we refer to the relaxation form, we mean that the

Figure 1: An illustration of the in-arborescence

variables satisfy ze [0, + ). Note that the optimal integral solution of the BCR is also the optimal solution of the STP. We next introduce the formulas of HYPs. The form of the HYP we will show is the Directed Component-based Relaxation (DCR) (Chakrabarty, K onemann, and Pritchard 2010). A component C is simply a subgraph of G with the condition that it is a tree spanning over V (C), where all leaves of C are terminals, while all internal ones are not. We consider a directed version of full components. An in-arborescence is a directed rooted tree with each edge pointing to the root r (see Figure 1). The directed full-component is an in-arborescence to one of its terminals as the root, called its head. We denote by H(C) the head of directed full-component C. We call the set of all directed full-components D . By +(S), we denote all full-components C D for which the head lies outside S, while some other terminal of C lies inside. We also let x( +(S)) = P C +(S) x C. Similar with the BCR, we choose any r R as a root. The objective of the directed component relaxation is given by

C D c(C)x C (DCR)

s.t. x( +(U)) 1 U V \ {r} : U R = x C {0, 1} C D The central observation is that a collection of full components forms a Steiner tree if and only if its corresponding terminal sets form a hypergraph in which each pair of terminals are joined by a unique hyper-path, a so-called hyperspanning tree. Therefore, the union of every feasible integral solution of DCR is a feasible solution of Steiner Tree Problems due to the connected constraint that x( +(U)) 1, where U V \ {r} : U R = and the minimum objective requirement. We use Dk to denote the set of all the directed full components with at most k terminals. For each subset R R with |R | = r k, one can select a component C with R(C) = R as the component in Dk, where

C = arg min C

R(C ) = R , C is a full directed component .

Therefore, |Dk| = P r [k] |R| r . There is an one-to-one correspondence among the elements in Dk and the subset of R with size r k , such that for each R R with |R | = r k, there is one C Dk defined above, and vice versa. Hence, if k = 2 1 ϵ for any given ϵ, we have that |Dk| = poly(|R|). Furthermore, in this case, each component in Dk can be found in polynomial time (i.e., O(k|V |(|E| + |V | ln(|V |))) time) (Wang, Li, and Wang 2004). Then we have the restricted k-DCR

C Dk c(C)x C (k-DCR)

C +(U) x C 1 U V \ {r} : U R =

x C {0, 1} C Dk

Note that every feasible integral solution of k-DCR is also a feasible solution of Steiner tree problems. We call an integral solution of the BCR a feasible integral solution for the BCR, i.e., ze {0, 1}, e E. Recall that the optimal integral solution of the BCR is the optimal solution of the STP. Similarly, we can say integral solutions for the DCR or k-DCR. We use opt(BCR) and optf(BCR) to denote the value of optimal integral solution (which is the optimal value of STP) and optimal fractional solution for BCR. Similarly, we have the integral solution opt(DCR) and the fractional solution optf(DCR) for the DCR and we write opt(k-DCR) and optf(k-DCR) as optk(DCR) and optf,k(DCR), respectively. Definition 2. The approximation ratio of a mechanism M for Steiner tree problem concerning the optimal integral solution (resp. optimal fractional solution) is defined as

α(M) = max I I c(M(I))

resp. α(M) = max I I c(M(I))

where c(M(I)) is the cost output by the algorithm M on instance I and opt(I) is the optimal integral solution (resp. optimal fractional solution) on instance I. It is well known that Lemma 1 ((Borchers and Du 1997)). optk(DCR)

opt(BCR) ρk = 1 + 1 log k .

Hence, choose k = 2 1 ϵ , we know that the optimal integral solution of k-DCR is an (1+ϵ)-approximate optimal Steiner tree problem. In addition, we also have Lemma 2 ((Chakrabarty, K onemann, and Pritchard 2010)). optf,k(DCR) ρkoptf(BCR). We list some known results from literature including most recent work. Proposition 1 ((Traub and Zenklusen 2021)). There is a deterministic polynomial time algorithm for finding an integral solution of k-DCR with the approximation ratio ln 4 1.39 concerning optf,k(DCR). Definition 3. We call a Steiner tree instance Steiner clawfree if the graph G has no Steiner vertex with at least three Steiner neighbors.

We call a Steiner tree instance quasi-bipartite graphs if no Steiner vertices are adjacent (which form an independent set). Note that Steiner claw-free graph includes quasibipartite graph as a special case.

Proposition 2 ((Goemans et al. 2012; Feldmann et al. 2016)). There is a deterministic polynomial-time algorithm for finding an integral solution of BCR of Steiner clawfree STP with approximation ratio ln 4 1.39 concerning optf(BCR)

3 Truthful Mechanism for One Dimensional Covering Problem (OCP)

In (Lavi and Swamy 2011), the authors provide a general framework to transfer an α-approximate algorithm (with respect to the optimal fractional solution) for linear packing problem into a truthful in expectation mechanism. We recast their approach for one-dimensional covering problem, which provides a foundation for the design of the truthful in expectation mechanisms for the STP. Although compared to their method, we both use dual programming and the ellipsoid method to reduce the problems into linear programming with a polynomial-size of constraints, the design of detailed estimation including the objective value of the dual and the key point of the cutting ways of the hyperplane by the ellipsoid method are different. One-dimensional Covering Problem (OCP) is defined as follows:

i M cixi (OCP)

i Mj aixi bi j J, Mj M

xi {0, 1} i M

Here ci 0 and ai 0, i M, and M is the index set and |J| is the number of covering constraints. The procedure of decomposition of any optimal fractional solution x = (x i ), i M of the one-dimensional covering problem (OCP) is given as follows. Let { xℓ}ℓ L be the set of all the feasible integral solutions of the OCP, where L is the index set and |L| is the number of all the feasible integral solutions of the OCP. In the following part of this section, we suppose there exists a polynomial time algorithm A for OCP that achieves the approximation ratio α with respect to the optimal fractional solution of OCP. We write the Primal of the decomposition LP as follows.

ℓ L λℓ (Primal)

ℓ L λℓxℓ i = αx i i M

The Dual of the above decomposition LP is as follows.

i M αwix i + z (Dual)

i M wixℓ i + z 1 ℓ L

z 0, wi is arbitrary i M

Let P denote the set all the feasible fractional solutions of OCP. Let Z(P) denote the set of all the feasible integral solutions of OCP. Note that the parameters {ci}i M in OCP are non-negative. Let w+ = (w+ i )i M = (max{wi, 0})i M. We have the following lemma.

Lemma 3. For any vector w, we can find (in polynomial time) an integral solution xℓ Z(P) of OCP with the objective coefficient w such that X

i M wixℓ i α min x P

Proof. We can use A to find such an integral solution x with w+ = c as coefficients in objective function in OCP. Let xℓ i = x i , if wi 0 and xℓ i = 1, otherwise. Clearly, xℓ

is a feasible integral solution for OCP, i.e., xℓ P. Let x be the solution of min x P P i M wixi, i.e., P i M wix i = min x P P i M wixi and x P. By definition of x , P i M w+ i x i α P i M w+ i x i . By definition of xℓ, P i M w+ i xℓ i = P i M w+ i x i α P i M w+ i x i . Since xℓ i = 1 for all wi < 0, i M, we then have P i M wixℓ i α P i M wix i = α min x P P i M wixi.

Lemma 4. We can in polynomial time find a decomposition P ℓ L λℓxℓ i = αx i with P ℓ L λℓ= 1 and λℓ> 0, for all ℓ L.

Proof. First, note that if P i M αwix i + z < 1, by Lemma 3, we can find an integral solution xℓin polynomial time such that P i M wixℓ i + z α minx P P i M wixi + z P i M αwix i + z < 1. Hence, the optimal value of Dual is at least 1, by strong duality, the optimal value of Primal is at least 1. As P ℓ I λℓ 1, we know the optimal value of Dual and Primal are both 1. Secondly, we can add the constraint P i M αwix i + z 1 into the Dual. The ellipsoid algorithm (Gr otschel, Lov asz, and Schrijver 1993) can be used to solve the Dual as follows. We observe that the following separation oracle can be used to solve the Dual (or identify polynomial-size equivalent constraints of the Dual). These constraints will be the violated inequalities returned by the separation oracle during the execution of the ellipsoid method, that are used to cut the ellipsoid. If P i M αwix i +z < 1, by Lemma 3, we can find a violation constraint of the Dual as the cutting plane. Otherwise, we can use the half hyperplane P i M αwix i + z 1 as the cutting plane. Therefore, we can find an equivalent Dual with a set of constraints of size polynomial to solve the Dual, thus the Primal, which completes the proof.

As a direct consequence of Lemma 4, a truthful in expectation mechanism can be achieved by VCG payment as that in (Lavi and Swamy 2011).

Theorem 1. Suppose there is a polynomial-time algorithm for OCP that achieves the approximation ratio α with respect to the optimal fractional solution of OCP. Then, we can in polynomial time construct a truthful in expectation mechanism for OCP with the same approximation ratio α.

Proof. Let Lpoly be the index set of the polynomial-size decomposed solution in Lemma 4 i.e., P ℓ Lpoly λℓxℓ i = αx i , i M. Let opt i denote the optimal objective value of the OCP by removing agent i. Let Si = α(P j =i cjx j opt i). We will show that the mechanism with the following allocation rule and payment rule is truthful and (ex-post) individual rational and with the approximation ratio α:

1. The allocation rule: select the solution xℓwith probability λℓ, ℓ Lpoly; 2. The payment rule: for each random selection, charge agent i with the payment cixℓ i P

ℓ Lpoly λℓcixℓ i Si.

Now calculating the utility of agent i when he bids c i while his true cost is ci.

Ui(c i) = X

ℓ Lpoly λℓcixℓ i(c i)

ℓ Lpoly λℓ cixℓ i(c i) P ℓ Lpoly λℓcixℓ i(c i) Si(c i)

ℓ Lpoly λℓcixℓ i(c i)

P ℓ Lpoly λℓcixℓ i(c i) P ℓ Lpoly λℓcixℓ i(c i) Si(c i)

ℓ Lpoly λℓcixℓ i(c i) Si(c i) = αcix (c i) Si(c i)

= α( cix (c i) X

j =i cjx j(c i) + opt i)

j M cjx j(c i) + opt i) α( X

j M cjx j(ci) + opt i)

Therefore, the mechanism with the above allocation and payment rules is truthful in expectation. Thus, Theorem 1 follows.

4 Truthful Mechanisms for Steiner Tree Problems

The mechanism is based on the decomposition techniques in Section 3. A straightforward application of this technique gives a truthful in expectation mechanism for Steiner clawfree STP.

Theorem 2. There is a truthful in expectation mechanism with approximation ratio ln 4 1.39 for Steiner claw-free STP, which runs in polynomial time.

Proof. The proof is a direct consequence of Proposition 2 and Theorem 1 by noting that BCR is a special OCP.

It is interesting to observe that in Theorem 2, the allocation rule and payment rule are obtained by the BCR, but not based on the linear programming of the STP and hence the mechanism is truthful based on Theorem 1. As the allocation is a feasible solution to the STP, which induces a ln 4 1.39 approximation mechanism. It is worth to be aware that a direct application of Theorem 1 and Proposition 1 does not imply a truthful in expectation mechanism for STP in general graphs. Employing Proposition 1 and Theorem 1, a truthful in expectation mechanism is given for k-DCR with the ratio ln 4 by allowing each directed component to be held by a single agent. This is not a truthful mechanism for STP since in that problem each agent only controls a single edge. We will use Proposition 1 and Lemma 4 to design such a truthful mechanism with the ratio ln 4 + ϵ. Our approach consists of two steps. First, we will use the allocation rule given by Lemma 4. Second, using Maximal in Range (MIR), we will provide a sophisticated payment rule based on the above allocation rule. In intuition behind this payment rule comes from the payment rule of VCG payment rule over the directed components. Finally, this mechanism will be shown as the desired mechanism for the STP with the ratio ln 4 + ϵ by choosing k = 2 1 ϵ . Recall that when k = 2 1 ϵ , we have that |Dk| = poly(|R|). Note that k-DCR is an OCP. Hence, by Lemma 4, we can in polynomial time find a decomposition P ℓ L λℓxℓ C = αx C with P ℓ L λℓ= 1 and λℓ 0, for all ℓ L and C Dk, where {x C}C Dk is the optimal fractional solution of k-DCR, and L has the polynomial size of the input of STP. Recall that optf,k(DCR) denotes the optimal fractional value of k-DCR. For each edge e E, let DCR e (resp. k-DCR e) denotes the DCR form (resp. k-DCR) of STP by removing the edge e from the graph. Similarly, we have optf,k(DCR e). The mechanism M for k-DCR works as follows.

1. The allocation rule X: select the solution xℓwith the probability λℓ. 2. The payment rule P: for each edge e, the payment for e is

Pe = α optf,k(DCR) X

C:e C λℓc(e)xℓ C

α optf,k (DCR e) .

Theorem 3. The mechanism M is a truthful in expectation mechanism for Steiner tree problems in general graphs that achieves the approximation ratio ln 4+ϵ 1.39+ϵ, running in polynomial time for any given ϵ > 0.

Proof. We observe the following fact of the mechanism M. By the decomposition and the allocation rule X of M, the approximation ratio of M for k-DCR is ln 4 with respect to optf,k(DCR). By the fact that optf,k(DCR) ρk optf(BCR), where ρk = 1 + 1 log k]. M approximates

optf(BCR) with the ratio ln 4 + ϵ when k = 2 1 ϵ . This also shows that the running time of M is polynomial time for

any given ϵ > 0 provided k = 2 1 ϵ . Therefore, it is sufficient to show that M is a truthful in expectation mechanism. Observe that α optf,k (DCR e) α optf,k(DCR) since any feasible solution of k-DCR e is a feasible solution for k-DCR. Therefore, Pe 0, which shows that the payment is no negative money transfer. Given c( e), when consider the agent e, we write c = (c(e), c( e)) and c = (c (e), c( e)). By the allocation rule, the expected allocation Xe of edge e is Xe(c(e)) = P ℓ L P C:e C λℓxℓ C(c(e)). Observe that

α optf,k (DCR (c )) X

C:e C λℓc (e)xℓ C (c )

C:e C λℓc (e)xℓ C (c ) X

C:e C λℓc (e)xℓ C (c )

C:e C λℓc (e ) xℓ C (c ) .

Therefore, the expected utility ue of edge e is given by

ue (c ) = c(e)Xe (c ) Pe (c )

C:e C λℓxℓ C (c ) α optf,k (DCR (c ))

C:e C λℓc (e)xℓ C (c ) α optf,k (DCR e)

C:e C λℓxℓ C (c )

C:e C λℓc (e ) xℓ C (c ) α optf,k (DCR e)

= α optf,k (DCR e)

C:e C λℓc (e ) xℓ C (c ) + c(e) X

C:e C λℓxℓ C (c )

= α optf,k (DCR e) X

C:e C c (e ) X

ℓ L λℓxℓ C (c )

= α optf,k (DCR e) α X

C:e C c (e ) x C (c )

= α optf,k (DCR e) α X

C Dk(c ) c (C ) x C (c ) ,

where c(e) and c (e) denote the true cost and the bid of edge e respectively and x (c ) to denote the optimal fractional solution for k-DCR when e bids c (e) given the bids c( e) of all other edges, and Dk (c (e)) is the set of kdirected component when edge e bids c (e). Note that in the above calculation, we use C to denote the component containing R(C), which is one-to-one correspondence. The optimal solution {x C (c )}C Dk(c ) is a feasible solution for k-DCR and the fact that the true cost of a component containing R (C ) under the bid c = (c(e), c( e)) is no more than that under the bid c = (c (e), c( e)), i.e., for any R R, let C Dk (c ) containing R (with R (C ) = R

) and C Dk(c) containing R (with R(C) = R ), we have c (C ) c(C), where c (C ) = P e C c(e) using the true cost by recalling the formula (1). Note that C Dk (c ) has an one-to-one correspondence to C Dk(c) with R(C) = R (C ) = R R. Therefore, we have X

C Dk(c ) c (C ) x C (c ) X

C Dk(c) c(C)x C (c )

C Dk(c) c(C)x C(c),

where the first inequality comes from c (C ) c(C) and the second comes from that {x C (c )}C Dk(c ) is a feasible solution for k-DCR. Thus, ue (c (e)) ue(c(e)). This shows that the mechanism M is truthful in expectation.

Remark: Note that each feasible integral solution xℓcorresponds to a union set of directed components in Dk, which contains a tree spanning on all the terminals R used as the final solution of the STP. However, the payment rule we use is not based on this tree but the union set of directed components.

5 Conclusion We present a truthful-in-expectation mechanism for the STP on general graphs with the ratio ln 4 + ϵ 1.39, matching the current best algorithmic ratio for the STP. It is interesting to see to what extent the decomposition approach can be applied to other covering combinatorial problems for truthful approximate mechanisms. Besides, we are also interested to know whether there exists a deterministic truthful or universally truthful mechanism for the STP with the ratio 1.39.

Acknowledgments This work was supported by the National Key Research and Development Program of China (2022YFF0902005). Jianwei Yin was supported by the National Science Fund for Distinguished Young Scholars (No. 61825205). Jinshan Zhang was supported by the Key Research and Development Jianbing Program of Zhejiang Province (2023C01002), Hangzhou Major Project and Development Program (2022AIZD0140) and Yongjiang Talent Introduction Programm (2022A-236-G). Xiaotie Deng was supported by the National Natural Science Foundation of China (No. 62172012). Zhengyang Liu was supported by the National Natural Science Foundation of China (No. 62002017) and Beijing Institute of Technology Research Fund Program for Young Scholars.We are also grateful for the valuable comments from the anonymous reviewers.

References Armstrong, M. 2006. Competition in two-sided markets. The RAND journal of economics, 37(3): 668 691. Bern, M.; and Plassmann, P. 1989. The Steiner problem with edge lengths 1 and 2. Information Processing Letters, 32(4): 171 176. Borchers, A.; and Du, D.-Z. 1997. Thek-Steiner ratio in graphs. SIAM Journal on Computing, 26(3): 857 869.

Byrka, J.; Grandoni, F.; Rothvoß, T.; and Sanit a, L. 2013. Steiner tree approximation via iterative randomized rounding. Journal of the ACM (JACM), 60(1): 1 33. Chakrabarty, D.; K onemann, J.; and Pritchard, D. 2010. Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound. Operations Research Letters, 38(6): 567 570. Chakrabarty, D.; K onemann, J.; and Pritchard, D. 2013. Hypergraphic LP relaxations for Steiner trees. SIAM Journal on Discrete Mathematics, 27(1): 507 533. Chen, C.-Y.; and Hsieh, S.-Y. 2020. An efficient approximation algorithm for the Steiner tree problem. In Complexity and Approximation, 238 251. Springer. Chen, C.-Y.; and Hsieh, S.-Y. 2022. An improved algorithm for the Steiner tree problem with bounded edge-length. Journal of Computer and System Sciences, 123: 20 36. Chitnis, R.; Feldmann, A. E.; and Manurangsi, P. 2021. Parameterized approximation algorithms for bidirected Steiner network problems. ACM Transactions on Algorithms (TALG), 17(2): 1 68. Chleb ık, M.; and Chleb ıkov a, J. 2008. The Steiner tree problem on graphs: Inapproximability results. Theoretical Computer Science, 406(3): 207 214. Christodoulou, G.; and Sgouritsa, A. 2019. Designing networks with good equilibria under uncertainty. SIAM Journal on Computing, 48(4): 1364 1396. Deng, X.; Feng, Z.; and Papadimitriou, C. H. 2016. Powerlaw distributions in a two-sided market and net neutrality. In International Conference on Web and Internet Economics, 59 72. Springer. Feldmann, A. E.; K onemann, J.; Olver, N.; and Sanit a, L. 2016. On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree. Mathematical programming, 160(1): 379 406. Friggstad, Z.; and Mousavi, R. 2021. A Constant-Factor Approximation for Quasi-bipartite Directed Steiner Tree on Minor-Free Graphs. ar Xiv preprint ar Xiv:2111.02572. Goemans, M. X.; Olver, N.; Rothvoß, T.; and Zenklusen, R. 2012. Matroids and integrality gaps for hypergraphic Steiner tree relaxations. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, 1161 1176. Grandoni, F.; Laekhanukit, B.; and Li, S. 2019. O (log2 k/log log k)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 253 264. Gr otschel, M.; Lov asz, L.; and Schrijver, A. 1993. The ellipsoid method. In Geometric Algorithms and Combinatorial Optimization, 64 101. Springer. Gual a, L.; and Proietti, G. 2005. A truthful (2 2/k)- approximation mechanism for the Steiner tree problem with k terminals. In International Computing and Combinatorics Conference, 390 400. Springer. Hwang, F. K.; and Richards, D. S. 1992. Steiner tree problems. Networks, 22(1): 55 89.

Karp, R. M. 1972. Reducibility among combinatorial problems. In Complexity of computer computations, 85 103. Springer. Karpinski, M.; and Zelikovsky, A. 1997. New approximation algorithms for the Steiner tree problems. Journal of Combinatorial Optimization, 1(1): 47 65. Lau, L. C.; Naor, J.; Salavatipour, M. R.; and Singh, M. 2009. Survivable network design with degree or order constraints. SIAM Journal on Computing, 39(3): 1062 1087. Lavi, R.; and Swamy, C. 2011. Truthful and near-optimal mechanism design via linear programming. Journal of the ACM (JACM), 58(6): 1 24. Li, S.; and Laekhanukit, B. 2021. Polynomial Integrality Gap of Flow LP for Directed Steiner Tree. ar Xiv preprint ar Xiv:2110.13350. Orlowski, S.; Wess aly, R.; Pi oro, M.; and Tomaszewski, A. 2010. SNDlib 1.0 Survivable network design library. Networks: An International Journal, 55(3): 276 286. Pr omel, H. J.; and Steger, A. 2000. A new approximation algorithm for the Steiner tree problem with performance ratio 5/3. Journal of Algorithms, 36(1): 89 101. Robins, G.; and Zelikovsky, A. 2005. Tighter bounds for graph Steiner tree approximation. SIAM Journal on Discrete Mathematics, 19(1): 122 134. Saikia, P.; and Karmakar, S. 2021. Improved distributed approximation for Steiner tree in the CONGEST model. Journal of Parallel and Distributed Computing, 158: 196 212. Saltzer, J. H.; Reed, D. P.; and Clark, D. D. 1984. Endto-end arguments in system design. ACM Transactions on Computer Systems (TOCS), 2(4): 277 288. Siebert, M.; Ahmed, S.; and Nemhauser, G. 2020. A linear programming based approach to the Steiner tree problem with a fixed number of terminals. Networks, 75(2): 124 136. Traub, V.; and Zenklusen, R. 2021. Local search for weighted tree augmentation and Steiner tree. ar Xiv preprint ar Xiv:2107.07403. Wang, W.; Li, X.-Y.; and Wang, Y. 2004. Truthful multicast routing in selfish wireless networks. In Proceedings of the 10th annual international conference on Mobile computing and networking, 245 259. Zelikovsky, A. Z. 1993. An 11/6-approximation algorithm for the network Steiner problem. Algorithmica, 9(5): 463 470.