Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Computational Issues in Time-Inconsistent Planning
Authors: Pingzhong Tang, Yifeng Teng, Zihe Wang, Shenke Xiao, Yichong Xu
AAAI 2017 | Venue PDF | 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. |