Motivating Time-Inconsistent Agents: A Computational Approach
In this paper we investigate the computational complexity of motivating time-inconsistent agents to complete long term projects. We resort to an elegant graph-theoretic model, introduced by Kleinberg and Oren, which consists of a task graph G with n vertices, including a source s and target t, and an agent that incrementally constructs a path from s to t in order to collect rewards. The twist is that the agent is present-biased and discounts future costs and rewards by a factor β∈[0,1]. Our design objective is to ensure that the agent reaches t i.e.\ completes the project, for as little reward as possible. Such graphs are called motivating. We consider two strategies. First, we place a single reward r at t and try to guide the agent by removing edges from G. We prove that deciding the existence of such motivating subgraphs is NP-complete if r is fixed. More importantly, we generalize our reduction to a hardness of approximation result for computing the minimum r that admits a motivating subgraph. In particular, we show that no polynomial-time approximation to within a ratio of n/4 or less is possible, unless P=NP. Furthermore, we develop a (1+n)-approximation algorithm and thus settle the approximability of computing motivating subgraphs. Secondly, we study motivating reward configurations, where non-negative rewards r(v) may be placed on arbitrary vertices v of G. The agent only receives the rewards of visited vertices. Again we give an NP-completeness result for deciding the existence of a motivating reward configuration within a fixed budget b. This result even holds if b=0, which in turn implies that no efficient approximation of a minimum b within a ration grater or equal to 1 is possible, unless P=NP.
