Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

Mika Tapani Göös
2023
Article

Résumé

We prove an N2-o(1) lower bound on the randomized communication complexity of finding an epsilon-approximate Nash equilibrium (for constant epsilon > 0) in a two-player N x N game.

Source officielle

https://infoscience.epfl.ch/record/309903?ln=fr

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

Byzantine consensus is Θ(n^2): the Dolev-Reischuk bound is tight even in partial synchrony!

Communication Complexity of Collision

Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization

Byzantine consensus is Θ(n^2): the Dolev-Reischuk bound is tight even in partial synchrony!

Communication Complexity of Collision

Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization