×

Principal-agent problems with present-biased agents. (English) Zbl 1431.91216

Fotakis, Dimitris (ed.) et al., Algorithmic game theory. 12th International symposium, SAGT 2019, Athens, Greece, September 30 – October 3, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11801, 237-251 (2019).
Summary: 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 J. Kleinberg and S. Oren [“Time-inconsistent planning: a computational problem in behavioral economics”, In: Proceedings of the 15th ACM conference on economics and computation, EC 2014. New York, NY: Association for Computing Machinery (ACM). 547–564 (2014; doi:10.1145/2600057.2602890)] 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.
For the entire collection see [Zbl 1422.91031].

MSC:

91B43 Principal-agent models
05C90 Applications of graph theory
68W05 Nonnumerical algorithms
PDFBibTeX XMLCite
Full Text: DOI Link