Cost Minimization for Equilibrium Transition
Authors: Haoqiang Huang, Zihe Wang, Zhide Wei, Jie Zhang
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main focus revolves around computing the minimum reward required to facilitate this equilibrium transition. Our findings reveal that determining whether the minimum reward is zero is NP-complete, and computing the minimum reward becomes APX-hard. Nonetheless, we bring some positive news, as this problem can be efficiently handled if either k or n is a fixed constant. Furthermore, we have devised an approximation algorithm with an additive error that runs in polynomial time. Lastly, we explore a specific case wherein the utility functions exhibit single-peaked characteristics, and we successfully demonstrate that the optimal reward can be computed in polynomial time. |
| Researcher Affiliation | Academia | 1Hong Kong University of Science and Technology 2Renmin University of China 3Peking University 4University of Bath |
| Pseudocode | Yes | Algorithm 1: Transformation Path Construction |
| Open Source Code | No | The paper is theoretical, presenting algorithms and complexity analysis, and does not describe a software system or methodology that would have associated open-source code for release. |
| Open Datasets | No | The paper is theoretical and does not involve the use of datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve dataset splits for validation or training. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not specify software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training configurations. |