Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Publication

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

Mika Tapani Göös
2023
Journal Articles

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

Mika Tapani Göös
2023
Journal Articles

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

Concepts associés (8)

Computational complexity

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.

Complexité de la communication

La complexité de la communication ou complexité de communication est une notion étudiée en informatique théorique. Le dispositif abstrait classique est le suivant : Alice et Bob ont chacun un message, et ils veulent calculer un nouveau message à partir de leurs messages, en se transmettant un minimum d'information. Par exemple, Alice et Bob reçoivent un mot chacun, et ils doivent décider s'ils ont reçu le même mot ; ils peuvent bien sûr s'envoyer leur mot l'un à l'autre et comparer, mais la question est de minimiser le nombre de messages.

Théorie de la complexité (informatique théorique)

vignette|Quelques classes de complexité étudiées dans le domaine de la théorie de la complexité. Par exemple, P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée ...) requis par un algorithme pour résoudre un problème algorithmique.

Afficher plus

Publications associées (31)

Afficher plus

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

Graph Chatbot

Planetary-Scale Byzantine Fault Tolerance

Quantifying the Unknown: Data-Driven Approaches and Applications in Energy Systems

Scalable Quantum Algorithms for Noisy Quantum Computers