Computational Issues in Time-Inconsistent Planning
Authors: Pingzhong Tang, Yifeng Teng, Zihe Wang, Shenke Xiao, Yichong Xu
AAAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we give answers to all three open problems. First, we show a tight upper bound of cost ratio for graphs, and confirm the conjecture by Kleinberg and Oren that Akerlof s structure is indeed the worst case for cost ratio. Second, we prove that finding a motivating subgraph is NP-hard, showing that it is generally inefficient to motivate agents by deleting nodes and edges in the graph. Last but not least, we show that computing a strategy to place minimum amount of total reward is also NP-hard and we provide a 2napproximation algorithm. |
| Researcher Affiliation | Academia | Tsinghua University, University of Wisconsin-Madison, Shanghai University of Finance and Economics, Carnegie Mellon University |
| Pseudocode | Yes | Algorithm 1 The shortest good path algorithm for MINIMAL-TOTAL-REWARDβ |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code or links to a code repository for its methodology. |
| Open Datasets | No | This is a theoretical paper providing proofs and algorithms; it does not involve the use of datasets for training or evaluation. |
| Dataset Splits | No | This is a theoretical paper and does not involve empirical experiments with data splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any computational experiments; therefore, it does not specify any hardware used. |
| Software Dependencies | No | The paper is theoretical and does not describe any computational experiments or implementations; therefore, it does not list any specific software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper focusing on mathematical proofs and algorithm design, and as such, it does not describe experimental setups, hyperparameters, or training configurations. |