EUVIMEDEUVIMED entdecken
Crossref

The Price of Strategic Information: Degree-Based Bounds on Inefficiency in Distributed Learning Games

Tuan Ngoc Do, Hai Duc Nguyen, Khanh Quoc Nguyen, Hiep Quang Dao, Anh Duc-Duy Nguyen, Luong Cong Nguyen

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →