Inconsistent Planning: When in Doubt, Toss a Coin!
Authors: Yuriy Dementiev, Fedor Fomin, Artur Ignatiev9724-9731
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We introduce the randomized version of the cost of irrationality and initiate its study from the computational perspective. To support our point of view on the cost of irrationality, we start from the combinatorial result (Theorem 1), showing that there are time-inconsistent planning models with exponentially (in n) many feasible paths of different costs. It yields that in the deterministic model of Kleinberg and Oren (Definition 1) there could be exponentially many different costs of irrationality. To study the cost of irrationality Xβ, we define the following computational problem. ESTIMATING THE COST OF IRRATIONALITY (ECI) Input: A time-inconsistent planning model M = (G, w, s, t, p, β), and W 0. Task: Compute Pr(Xβ W). We show in Theorem 2 that ECI is #P-hard. Thus computationally, ECI is not easier than counting Hamiltonian cycles, counting perfect matching, satidying assignments, and all other #P-complete problems. |
| Researcher Affiliation | Academia | Yuriy Dementiev1, Fedor Fomin2, Artur Ignatiev1 1 Saint-Petersburg State University, Russia 2 Department of Informatics, University of Bergen, Norway |
| Pseudocode | Yes | Algorithm 1: Dynamic programming for ECI Input: M = (G, w, s, t, p, β), W 0 Output: Pr(Cβ W d(s, t) ) |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code or links to code repositories for the described methodology. |
| Open Datasets | No | This is a theoretical paper and does not involve empirical experiments with datasets for training or evaluation. |
| Dataset Splits | No | This is a theoretical paper and does not involve empirical experiments with dataset splits for validation. |
| Hardware Specification | No | This is a theoretical paper and does not mention any specific hardware used for running experiments. |
| Software Dependencies | No | The paper provides theoretical algorithms and proofs but does not list any specific software dependencies or version numbers for implementation. |
| Experiment Setup | No | This is a theoretical paper and does not describe an experimental setup with hyperparameters or system-level training settings. |