Sigal Oren

We present a novel graph-theoretic principal-agent model in which the agent is present biased (a bias that was well studied in behavioral economics). Our model captures situations in which a principal guides an agent in a complex multi-step project. We model the different steps and branches of the project as a directed acyclic graph with a source and a target, in which each edge has the cost for completing a corresponding task. If the agent reaches the target it receives some fixed reward R. We assume that the present-biased agent traverses the graph according to the framework of Kleinberg and Oren (EC’14) and as such will continue traversing the graph as long as his perceived cost is less than R. We further assume that each edge is assigned a value and if the agent reaches the target the principal’s payoff is the sum of values of the edges on the path that the agent traversed. Our goal in this work is to understand whether the principal can efficiently compute a subgraph that maximizes his payoff among all subgraphs in which the agent reaches the target. For this central question we provide both impossibility results and algorithms.