Truthful Mechanisms for Steiner Tree Problems

Jinshan Zhang; Zhengyang Liu; Xiaotie Deng; Jianwei Yin

doi:10.1609/aaai.v37i5.25729

Truthful Mechanisms for Steiner Tree Problems

Jinshan Zhang, Zhengyang Liu^*, Xiaotie Deng, Jianwei Yin

^*Corresponding author for this work

School of Computer Science and Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Citation (Scopus)

Abstract

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 non-cooperative 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.

Original language	English
Title of host publication	AAAI-23 Technical Tracks 5
Editors	Brian Williams, Yiling Chen, Jennifer Neville
Publisher	AAAI press
Pages	5884-5891
Number of pages	8
ISBN (Electronic)	9781577358800
DOIs	https://doi.org/10.1609/aaai.v37i5.25729
Publication status	Published - 27 Jun 2023
Event	37th AAAI Conference on Artificial Intelligence, AAAI 2023 - Washington, United States Duration: 7 Feb 2023 → 14 Feb 2023

Publication series

Name	Proceedings of the 37th AAAI Conference on Artificial Intelligence, AAAI 2023
Volume	37

Conference

Conference	37th AAAI Conference on Artificial Intelligence, AAAI 2023
Country/Territory	United States
City	Washington
Period	7/02/23 → 14/02/23

Access to Document

10.1609/aaai.v37i5.25729

Cite this

@inproceedings{51de266ca7c44cc0a5b31f320756f4b6,

title = "Truthful Mechanisms for Steiner Tree Problems",

abstract = "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 non-cooperative 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.",

author = "Jinshan Zhang and Zhengyang Liu and Xiaotie Deng and Jianwei Yin",

note = "Publisher Copyright: Copyright {\textcopyright} 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.; 37th AAAI Conference on Artificial Intelligence, AAAI 2023 ; Conference date: 07-02-2023 Through 14-02-2023",

year = "2023",

month = jun,

day = "27",

doi = "10.1609/aaai.v37i5.25729",

language = "English",

series = "Proceedings of the 37th AAAI Conference on Artificial Intelligence, AAAI 2023",

publisher = "AAAI press",

pages = "5884--5891",

editor = "Brian Williams and Yiling Chen and Jennifer Neville",

booktitle = "AAAI-23 Technical Tracks 5",

}

Zhang, J, Liu, Z, Deng, X & Yin, J 2023, Truthful Mechanisms for Steiner Tree Problems. in B Williams, Y Chen & J Neville (eds), AAAI-23 Technical Tracks 5. Proceedings of the 37th AAAI Conference on Artificial Intelligence, AAAI 2023, vol. 37, AAAI press, pp. 5884-5891, 37th AAAI Conference on Artificial Intelligence, AAAI 2023, Washington, United States, 7/02/23. https://doi.org/10.1609/aaai.v37i5.25729

Truthful Mechanisms for Steiner Tree Problems. / Zhang, Jinshan; Liu, Zhengyang; Deng, Xiaotie et al.
AAAI-23 Technical Tracks 5. ed. / Brian Williams; Yiling Chen; Jennifer Neville. AAAI press, 2023. p. 5884-5891 (Proceedings of the 37th AAAI Conference on Artificial Intelligence, AAAI 2023; Vol. 37).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Truthful Mechanisms for Steiner Tree Problems

AU - Zhang, Jinshan

AU - Liu, Zhengyang

AU - Deng, Xiaotie

AU - Yin, Jianwei

PY - 2023/6/27

Y1 - 2023/6/27

N2 - 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 non-cooperative 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.

AB - 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 non-cooperative 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.

UR - http://www.scopus.com/inward/record.url?scp=85167874338&partnerID=8YFLogxK

U2 - 10.1609/aaai.v37i5.25729

DO - 10.1609/aaai.v37i5.25729

M3 - Conference contribution

AN - SCOPUS:85167874338

T3 - Proceedings of the 37th AAAI Conference on Artificial Intelligence, AAAI 2023

SP - 5884

EP - 5891

BT - AAAI-23 Technical Tracks 5

A2 - Williams, Brian

A2 - Chen, Yiling

A2 - Neville, Jennifer

PB - AAAI press

T2 - 37th AAAI Conference on Artificial Intelligence, AAAI 2023

Y2 - 7 February 2023 through 14 February 2023

ER -

Truthful Mechanisms for Steiner Tree Problems

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this