Bounded Rationality of Restricted Turing Machines
Authors: Lijie Chen, Pingzhong Tang, Ruosong Wang
AAAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we explore this direction further, by studying a realistic model of bounded rationality, where agents are confined to use time-restricted or space-restricted Turing machines to implement their strategies. We first use computational complexity models to rigorously define time and space restrictions. We then study the important game theoretical question of how to compute and implement the best response of such a restricted Turing machine. For time-restricted case. We show that computing best response against a strategy whose running time is bounded by a polynomial in the number of rounds is NP-complete, more generally, computing best response against a strategy with oracle access to a P i -complete language whose running time is bounded by a polynomial in the number of rounds is P i+1-complete. ... We study the space-restricted case under two natural models and show that, computing its best response is PSPACE-complete. We also show that under one of these models, implementing a strategy s best response requires a super linear expansion in strategy size under a certain reasonable complexity conjecture. Those results suggest that, in contrast to time-restricted case, finding the best response in polynomial space is possible, but implementing them with linear expansion in size is impossible. The second question we study is that, if both players have bounded rationality and this is common knowledge, how does it affect on the play of the game? More specifically, how does it change the set of the Nash Equilibria? We show that, in infinitely repeated games, interesting new equilibria will emerge. The proof of this part is quite nontrivial and is of independent interest. |
| Researcher Affiliation | Academia | Lijie Chen, Pingzhong Tang, Ruosong Wang Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China. |
| Pseudocode | No | The paper does not contain any pseudocode or explicitly labeled algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement or link regarding the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not involve empirical training on datasets. It uses the Prisoner's Dilemma as a conceptual example, not as a dataset for training. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical validation experiments or dataset splits for validation. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not list any specific software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | The paper is theoretical and does not include details on experimental setup, such as hyperparameters or system-level training settings. |