The Price of Strategic Information: Degree-Based Bounds on Inefficiency in Distributed Learning Games
Proceedings of the ACM on Measurement and Analysis of Computing Systems · 29.05.2026 · 10 (2) · 1-28
DOI: 10.1145/3805651 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Measurement and Analysis of Computing Systems, online erschienen am 29.05.2026. Verfasst von Tuan Ngoc Do und 5 weiteren Autor:innen. Die Arbeit nennt 21 Literaturangaben.
Abstract (Originalsprache)
Distributed learning over communication networks relies on agents strategically sharing information with their neighbors. To model the need for mutual consent in information trade-off, we introduce the Strategic Information Game with reciprocal transfers, where effective information flow requires bilateral commitment from both endpoints. Within this framework, our main contribution is a tight degree-based characterization of inefficiency: the Price of Strategic Information is bounded by one plus the maximum degree, and this bound is achieved with equality for regular graphs in the negligible-cost regime. Notably, this result reveals that the maximum degree, rather than spectral properties such as the algebraic connectivity, governs strategic inefficiency under local utilities. Beyond this characterization, we establish existence of pure Nash equilibria via concave game theory, provide polynomial-time algorithms for constructing bound-optimal topologies and computing coarse correlated equilibria, and prove an impossibility result showing that the all-zero equilibrium cannot be eliminated under transfer-free reciprocal protocols.
Zitieren
APA
Do, T. N., Nguyen, H. D., Nguyen, K. Q., Dao, H. Q., Nguyen, A. D., & Nguyen, L. C. (2026). The Price of Strategic Information: Degree-Based Bounds on Inefficiency in Distributed Learning Games. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 10(2), 1-28. https://doi.org/10.1145/3805651
Vancouver
Do TN, Nguyen HD, Nguyen KQ, Dao HQ, Nguyen AD, Nguyen LC. The Price of Strategic Information: Degree-Based Bounds on Inefficiency in Distributed Learning Games. Proceedings of the ACM on Measurement and Analysis of Computing Systems. 2026;10(2):1-28. doi:10.1145/3805651
BibTeX
@article{Do2026,
author = {Do, Tuan Ngoc and Nguyen, Hai Duc and Nguyen, Khanh Quoc and Dao, Hiep Quang and Nguyen, Anh Duc-Duy and Nguyen, Luong Cong},
title = {The Price of Strategic Information: Degree-Based Bounds on Inefficiency in Distributed Learning Games},
journal = {Proceedings of the ACM on Measurement and Analysis of Computing Systems},
year = {2026},
volume = {10},
number = {2},
pages = {1--28},
doi = {10.1145/3805651}
}
EUVIMED