Computational Issues in Time-Inconsistent Planning
Computational Issues in Time-Inconsistent Planning
复制标题
时间不一致规划中的计算问题
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Yichong Xu
中科院分区：
文献类型：
--
作者：
Pingzhong Tang;Yifeng Teng;Zihe Wang;Shenke Xiao;Yichong Xu
时间不一致是指决策过程中的一个悖论，即代理人随着时间的推移表现出不一致的行为。例如，代理人倾向于推迟简单任务的拖延，以及代理人开始计划并中途退出的放弃。为了捕捉这些行为并量化这些行为造成的低效率，Kleinberg和Oren（2014）提出了一个具有一定成本结构的图模型，并开始研究几个有趣的计算问题：1）成本比：在所有图实例中，代理的实际成本与最优成本之间的最差比率; 2）激励子图：如何通过删除节点和边来激励Agent达到目标; 3）中间奖励：如何通过放置中间奖励来激励Agent达到目标。Kleinberg和Oren给出了这些问题的部分答案，但主要问题是开放的。在本文中，我们给出了所有三个开放的问题的答案。首先，我们证明了图的成本比的一个紧上界，并证实了Kleinberg和Oren的猜想，即Akerlof结构确实是成本比的最坏情况。其次，我们证明了找到一个激励子图是NP-困难的，表明它通常是低效的激励代理删除节点和边的图。最后但并非最不重要的是，我们表明，计算的战略，把最低金额的总奖励也是NP-难的，我们提供了一个2n-近似算法。
Time-inconsistency refers to a paradox in decision making where agents exhibit inconsistent behaviors over time. Examples are procrastination where agents tend to postpone easy tasks, and abandonments where agents start a plan and quit in the middle. To capture such behaviors and to quantify inefficiency caused by such behaviors, Kleinberg and Oren (2014) propose a graph model with a certain cost structure and initiate the study of several interesting computation problems: 1) cost ratio: the worst ratio between the actual cost of the agent and the optimal cost, over all the graph instances; 2) motivating subgraph: how to motivate the agent to reach the goal by deleting nodes and edges; 3) Intermediate rewards: how to incentivize agents to reach the goal by placing intermediate rewards. Kleinberg and Oren give partial answers to these questions, but the main problems are open. 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 2n- approximation algorithm.