Truthful Mechanisms for Steiner Tree Problems

Jinshan Zhang, Zhengyang Liu, Xiaotie Deng, Jianwei Yin

AAAI 2023 pp. 5884-5891

doi:10.1609/AAAI.V37I5.25729 /aaai/2023/zhang2023aaai-truthful/

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.

PDF AAAI Semantic Scholar

Cite

Text

Zhang et al. "Truthful Mechanisms for Steiner Tree Problems." AAAI Conference on Artificial Intelligence, 2023. doi:10.1609/AAAI.V37I5.25729

Markdown

[Zhang et al. "Truthful Mechanisms for Steiner Tree Problems." AAAI Conference on Artificial Intelligence, 2023.](https://mlanthology.org/aaai/2023/zhang2023aaai-truthful/) doi:10.1609/AAAI.V37I5.25729

BibTeX

@inproceedings{zhang2023aaai-truthful,
  title     = {{Truthful Mechanisms for Steiner Tree Problems}},
  author    = {Zhang, Jinshan and Liu, Zhengyang and Deng, Xiaotie and Yin, Jianwei},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2023},
  pages     = {5884-5891},
  doi       = {10.1609/AAAI.V37I5.25729},
  url       = {https://mlanthology.org/aaai/2023/zhang2023aaai-truthful/}
}