On the Value of Penalties in Time-Inconsistent Planning
On the Value of Penalties in Time-Inconsistent Planning
复制标题
论时间不一致计划中惩罚的价值
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Dennis Kraft
中科院分区：
文献类型：
--
作者：
S. Albers;Dennis Kraft
由于固有的当前偏见，人们往往会随着时间的推移而表现得不一致。由于这可能会影响业绩，因此需要相应地调整社会和经济环境。减少时间不一致行为影响的常用工具是惩罚和禁止。这些工具被称为承诺手段。在最近的工作中，Kleinberg和Oren [6，7]将基于禁止的承诺设备的设计与一个组合问题联系起来，在这个组合问题中，从具有n个节点的任务图G中删除边。然而，这个问题是NP-难的，在小于1/3的比率内近似[2]。为了解决这个问题，我们提出了一个基于惩罚的承诺装置，不删除边缘，但提高了他们的成本。我们的做法有两方面的好处。在概念方面，我们表明惩罚比禁止有效1/β倍，其中β（0，1]参数化当前偏差。在计算方面，我们提出了一个2-近似算法分配的罚款显着提高逼近。为了补充这一结果，我们证明了最佳的惩罚是NP-难近似的比率为1.08192。
People tend to behave inconsistently over time due to an inherent present bias. As this may impair performance, social and economic settings need to be adapted accordingly. Common tools to reduce the impact of time-inconsistent behavior are penalties and prohibition. Such tools are called commitment devices. In recent work Kleinberg and Oren [6, 7] connect the design of prohibition-based commitment devices to a combinatorial problem in which edges are removed from a task graph G with n nodes. However, this problem is NP-hard to approximate within a ratio less than √n/3 [2]. To address this issue, we propose a penalty-based commitment device that does not delete edges but raises their cost. The benefits of our approach are twofold. On the conceptual side, we show that penalties are up to 1/β times more efficient than prohibition, where β ϵ (0,1] parameterizes the present bias. On the computational side, we significantly improve approximability by presenting a 2-approximation algorithm for allocating the penalties. To complement this result, we prove that optimal penalties are NP-hard to approximate within a ratio of 1.08192.