  Time-inconsistency refers to a paradox in decision making where agents
exhibit inconsistent behaviors over time. Examples are procrastination where
agents tends to costly postpone easy tasks, and abandonments where agents start
a plan and quit in the middle. These behaviors are undesirable in the sense
that agents make clearly suboptimal decisions over optimal ones. To capture
such behaviors and more importantly, to quantify inefficiency caused by such
behaviors, [Kleinberg & Oren 2014] propose a graph model which is essentially
same as the standard planning model except for the cost structure. Using this
model, they initiate the study of several interesting problems: 1) cost ratio:
the worst ratio between the actual cost of the agent and the optimal cost, over
all graph instances; 2) motivating subgraph: how to motivate the agent to reach
the goal by deleting nodes and edges; 3) Intermediate rewards: how to motivate
agents to reach the goal by placing intermediate rewards. Kleinberg and Oren
give partial answers to these questions, but the main problems are still open.
In fact, they raise these problems explicitly as open problems in their paper.
In this paper, we give answers to all three open problems in [Kleinberg & Oren
2014]. First, we show a tight upper bound of cost ratio for graphs without
Akerlof's structure, thus 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. Therefore, it is computational inefficient to
motivate agents by placing intermediate rewards. The techniques we use to prove
these results are nontrivial and of independent interests.
