Hardness of Approximation Between P and NP

Aviad Rubinstein

Description

Nash equilibrium is the central solution concept in Game Theory.

Since Nash’s original paper in 1951, it has found countless applications in modeling strategic behavior of traders in markets, (human) drivers and (electronic) routers in congested networks, nations in nuclear disarmament negotiations, and more. A decade ago, the relevance of this solution concept was called into question by computer scientists, who proved (under appropriate complexity assumptions) that computing a Nash equilibrium is an intractable problem. And if centralized, specially designed algorithms cannot find Nash equilibria, why should we expect distributed, selfish agents to converge to one? The remaining hope was that at least approximate Nash equilibria can be efficiently computed.

Understanding whether there is an efficient algorithm for approximate Nash equilibrium has been the central open problem in this field for the past decade. In this book, we provide strong evidence that even finding an approximate Nash equilibrium is intractable. We prove several intractability theorems for different settings (two-player games and many-player games) and models (computational complexity, query complexity, and communication complexity). In particular, our main result is that under a plausible and natural complexity assumption ("Exponential Time Hypothesis for PPAD"), there is no polynomial-time algorithm for finding an approximate Nash equilibrium in two-player games.

The problem of approximate Nash equilibrium in a two-player game poses a unique technical challenge: it is a member of the class PPAD, which captures the complexity of several fundamental total problems, i.e., problems that always have a solution; and it also admits a quasipolynomial time algorithm. Either property alone is believed to place this problem far below NP-hard problems in the complexity hierarchy; having both simultaneously places it just above P, at what can be called the frontier of intractability. Indeed, the tools we develop in this book to advance on this frontier are useful for proving hardness of approximation of several other important problems whose complexity lies between P and NP: Brouwer’s fixed point, market equilibrium, CourseMatch (A-CEEI), densest k-subgraph, community detection, VC dimension and Littlestone dimension, and signaling in zero-sum games.

• Preface


• Part I: Overview
  • The Frontier of Intractability
  • Preliminaries


• Part II: Communication Complexity
  • Communication Complexity of Approximate Nash Equilibrium
  • Brouwer's Fixed Point


• Part III: PPAD
  • PPAD-Hardness of Approximation
  • The Generalized Circuit Problem
  • Many-Player Games
  • Bayesian Nash Equilibrium
  • Market Equilibrium
  • CourseMatch


• Part IV: Quasi-Polynomial Time
  • Birthday Repetition
  • Densest k-Subgraph
  • Community Detection
  • VC and Littlestone's Dimensions
  • Signaling


• Part V: Approximate Nash Equilibrium
  • 2-Player Approximate Nash Equilibrium


• References


• Index


• Author Biography

Sujets

• Sciences formelles
• Informatique théorique
• Algorithmes
• Computer Science
• Computers
• Informatique
• Game theory

Informations

• Publié par: Association for Computing Machinery and Morgan & Claypool Publishers
• Date de parution: 07 juin 2019
• Nombre de lectures: 0
• EAN13: 9781947487222
• Langue: English
• Poids de l'ouvrage: 3 Mo

Extrait

Hardness of Approximation Between P and NP
ACM Books
Editor in Chief
M. Tamer zsu, University of Waterloo
ACM Books is a series of high-quality books for the computer science community, published by ACM and many in collaboration with Morgan Claypool Publishers. ACM Books publications are widely distributed in both print and digital formats through booksellers and to libraries (and library consortia) and individual ACM members via the ACM Digital Library platform.
Hardness of Approximation Between P and NP
Aviad Rubinstein, Stanford University
2019
Conversational UX Design: A Practitioner s Guide to the Natural Conversation Framework
Robert J. Moore, IBM Research-Almaden
Raphael Arar, IBM Research-Almaden
2019
Heterogeneous Computing: Hardware and Software Perspectives
Mohamed Zahran, New York University
2019
Making Databases Work: The Pragmatic Wisdom of Michael Stonebraker
Editor: Michael L. Brodie
2018
The Handbook of Multimodal-Multisensor Interfaces, Volume 2: Signal Processing, Architectures, and Detection of Emotion and Cognition
Editors: Sharon Oviatt, Monash University
Bj rn Schuller, University of Augsburg and Imperial College London
Philip R. Cohen, Monash University
Daniel Sonntag, German Research Center for Artificial Intelligence (DFKI)
Gerasimos Potamianos, University of Thessaly
Antonio Kr ger, Saarland University and German Research Center for Artificial Intelligence (DFKI)
2018
Declarative Logic Programming: Theory, Systems, and Applications
Editors: Michael Kifer, Stony Brook University
Yanhong Annie Liu, Stony Brook University
2018
The Sparse Fourier Transform: Theory and Practice
Haitham Hassanieh, University of Illinois at Urbana-Champaign
2018
The Continuing Arms Race: Code-Reuse Attacks and Defenses
Editors: Per Larsen, Immunant, Inc .
Ahmad-Reza Sadeghi, Technische Universit t Darmstadt
2018
Frontiers of Multimedia Research
Editor: Shih-Fu Chang, Columbia University
2018
Shared-Memory Parallelism Can Be Simple, Fast, and Scalable
Julian Shun, University of California, Berkeley
2017
Computational Prediction of Protein Complexes from Protein Interaction Networks
Sriganesh Srihari, The University of Queensland Institute for Molecular Bioscience
Chern Han Yong, Duke-National University of Singapore Medical School
Limsoon Wong, National University of Singapore
2017
The Handbook of Multimodal-Multisensor Interfaces, Volume 1: Foundations, User Modeling, and Common Modality Combinations
Editors: Sharon Oviatt, Incaa Designs
Bj rn Schuller, University of Passau and Imperial College London
Philip R. Cohen, Voicebox Technologies
Daniel Sonntag, German Research Center for Artificial Intelligence (DFKI)
Gerasimos Potamianos, University of Thessaly
Antonio Kr ger, Saarland University and German Research Center for Artificial Intelligence (DFKI)
2017
Communities of Computing: Computer Science and Society in the ACM
Thomas J. Misa, Editor, University of Minnesota
2017
Text Data Management and Analysis: A Practical Introduction to Information Retrieval and Text Mining
ChengXiang Zhai, University of Illinois at Urbana-Champaign
Sean Massung, University of Illinois at Urbana-Champaign
2016
An Architecture for Fast and General Data Processing on Large Clusters
Matei Zaharia, Stanford University
2016
Reactive Internet Programming: State Chart XML in Action
Franck Barbier, University of Pau, France
2016
Verified Functional Programming in Agda
Aaron Stump, The University of Iowa
2016
The VR Book: Human-Centered Design for Virtual Reality
Jason Jerald, NextGen Interactions
2016
Ada s Legacy: Cultures of Computing from the Victorian to the Digital Age
Robin Hammerman, Stevens Institute of Technology
Andrew L. Russell, Stevens Institute of Technology
2016
Edmund Berkeley and the Social Responsibility of Computer Professionals
Bernadette Longo, New Jersey Institute of Technology
2015
Candidate Multilinear Maps
Sanjam Garg, University of California, Berkeley
2015
Smarter Than Their Machines: Oral Histories of Pioneers in Interactive Computing
John Cullinane, Northeastern University; Mossavar-Rahmani Center for Business and Government, John F. Kennedy School of Government, Harvard University
2015
A Framework for Scientific Discovery through Video Games
Seth Cooper, University of Washington
2014
Trust Extension as a Mechanism for Secure Code Execution on Commodity Computers
Bryan Jeffrey Parno, Microsoft Research
2014
Embracing Interference in Wireless Systems
Shyamnath Gollakota, University of Washington
2014
Hardness of Approximation Between P and NP
Aviad Rubinstein
Stanford University
ACM Books #24
Copyright 2019 by Association for Computing Machinery and Morgan Claypool Publishers
All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means-electronic, mechanical, photocopy, recording, or any other except for brief quotations in printed reviews-without the prior permission of the publisher.
Designations used by companies to distinguish their products are often claimed as trademarks or registered trademarks. In all instances in which the Association for Computing Machinery is aware of a claim, the product names appear in initial capital or all capital letters. Readers, however, should contact the appropriate companies for more complete information regarding trademarks and registration.
Hardness of Approximation Between P and NP
Aviad Rubinstein
books.acm.org
http://books.acm.org
ISBN: 978-1-94748-723-9 hardcover
ISBN: 978-1-94748-720-8 paperback
ISBN: 978-1-94748-722-2 ePub
ISBN: 978-1-94748-721-5 eBook
Series ISSN: 2374-6769 print 2374-6777 electronic
DOIs:
10.1145/3241304 Book
10.1145/3241304.3241305 Preface
10.1145/3241304.3241306 Chapter 1
10.1145/3241304.3241307 Chapter 2
10.1145/3241304.3241308 Chapter 3
10.1145/3241304.3241309 Chapter 4
10.1145/3241304.3241310 Chapter 5
10.1145/3241304.3241311 Chapter 6
10.1145/3241304.3241312 Chapter 7
10.1145/3241304.3241313 Chapter 8
10.1145/3241304.3241314 Chapter 9
10.1145/3241304.3241315 Chapter 10
10.1145/3241304.3241316 Chapter 11
10.1145/3241304.3241317 Chapter 12
10.1145/3241304.3241318 Chapter 13
10.1145/3241304.3241319 Chapter 14
10.1145/3241304.3241320 Chapter 15
10.1145/3241304.3241321 Chapter 16
10.1145/3241304.3241322 References / Index / Bios
A publication in the ACM Books series, #24
Editor in Chief: M. Tamer zsu, University of Waterloo
This book was typeset in Arnhem Pro 10/14 and Flama using Z Z T E X.
First Edition
10 9 8 7 6 5 4 3 2 1
Contents
Preface
Acknowledgments
PART I
OVERVIEW
Chapter 1
The Frontier of Intractability
1.1 PPAD: Finding a Needle You Know Is in the Haystack
1.2 Quasi-Polynomial Time and the Birthday Paradox
1.3 Approximate Nash Equilibrium
Chapter 2
Preliminaries
Notation
2.1 Nash Equilibrium and Relaxations
2.2 PPAD and E ND-OF-A- L INE
2.3 Exponential Time Hypotheses
2.4 PCP Theorems
2.5 Learning Theory
2.6 Information Theory
2.7 Useful Lemmata
PART II
COMMUNICATION COMPLEXITY
Chapter 3
Communication Complexity of Approximate Nash Equilibrium
Our Results
3.1 Uncoupled Dynamics
3.2 Techniques
3.3 Additional Related Literature
3.4 Proof Overview
3.5 Proofs
3.6 An Open Problem: Correlated Equilibria in 2-Player Games
Chapter 4
Brouwer s Fixed Point
4.1 B ROUWER with
4.2 Euclidean B ROUWER
PART III
PPAD
Chapter 5
PPAD-Hardness of Approximation
Chapter 6
The Generalized Circuit Problem
Our Results
6.1 Proof Overview
6.2 From Brouwer to -G CIRCUIT
6.3 G CIRCUIT with Fan-out 2
Chapter 7
Many-Player Games
Related Works: Tractable Special Cases
7.1 Graphical, Polymatrix Games
7.2 Succinct Games
Chapter 8
Bayesian Nash Equilibrium
Chapter 9
Market Equilibrium
9.1 Why Are Non-Monotone Markets Hard?
9.2 High-Level Structure of the Proof
9.3 Adaptations for Constant Factor Inapproximability
9.4 Non-Monotone Markets: Proof of Inapproximability
Chapter 10
CourseMatch
10.1 The Course Allocation Problem
10.2 A-CEEI Is PPAD-Hard
10.3 A-CEEI PPAD
PART IV
QUASI-POLYNOMIAL TIME
Chapter 11
Birthday Repetition
11.1 Warm-Up: Best -Nash
Chapter 12
Densest k -Subgraph
12.1 Construction (and Completeness)
12.2 Soundness
Chapter 13
Community Detection
13.1 Related Works
13.2 Overview of Proofs
13.3 Hardness of Counting Communities
13.4 Hardness of Detecting Communities
Chapter 14
VC and Littlestone s Dimensions
14.1 Discussion
14.2 Techniques
14.3 Related Work
14.4 Inapproximability of the VC Dimension
14.5 Inapproximability of Littlestone s Dimension
14.6 Quasi-polynomial Algorithm for Littlestone s Dimension
Chapter 15
Signaling
15.1 Techniques
15.2 Near-Optimal Signaling Is Hard
PART V
APPROXIMATE NASH EQUILIBRIUM
Chapter 16
2-Player Approximate Nash Equilibrium
Additional Related Work
16.1 Technical Overview
16.2 E ND-OF-A- L INE with Local Computation
16.3 Holographic Proof
16.4 Polymatrix WeakNash
16.5 From Polymatrix to Bimatrix
References
Index
Author Biography
Preface
This book is based on my Ph.D. thesis (by the same title), which I wrote at the University of California, Berkeley, with the wise guidance of Christos Papadimitriou.
In hindsight, it seems only natural that I ended up working on the complexity of Nash equilibrium, a problem that has been so closely associated with Christos for three decades. But the true story of how I came to work on equilibrium computation is completely different. During my first winter break at Berkeley, Abe Othman contacted me 1 and asked about the complexity of finding an Approximate Competitive Equilibrium from Equal Incomes (A-CEEI). At the time, Abe was preparing for the launch of Course Match, a system that implements a heuristic algorithm for A-CEEI to assign students to courses at the