An FPTAS for Computing Nash Equilibrium in Resource Graph Games
Authors: Hau Chan, Albert Xin Jiang
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we provide the first Fully Polytnomial Time Approximation Scheme (FPTAS) for computing an MSNE in any symmetric multilinear RGG where its constraint moralized resource graph has bounded treewidth. Our FPTAS can be generalized to compute optimal MSNE, and to games with a constant number of player types. As a consequence, our FPTAS provides new approximation results for security games, network congestion games, and bilinear games. Our algorithm makes use of a compact, primal-dual formulation of the MSNE condition. We then use a treedecomposition based dynamic programming approach to solve the resulting feasibility problem, passing partial assignments of primal and dual variables and partial sums of constraints across subgraphs. We omit all proofs in this version. A longer version of the paper with proofs and more discussion is available on the authors websites. |
| Researcher Affiliation | Academia | Hau Chan1 and Albert Xin Jiang2 1 University of Nebraska-Lincoln, Lincoln, NE 68588 2 Trinity University, San Antonio, TX 78212 |
| Pseudocode | No | The paper describes a |
| Open Source Code | No | The paper states: |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and properties of games; it does not utilize or refer to specific datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments that would require dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not list specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical, presenting an algorithm and its properties, and therefore does not describe a typical experimental setup with hyperparameters or system-level training settings. |