2024/01/29 by Guru Guruganesh, Yoav Kolumbus, Guruganesh, Guru +11 · 2 citations
Computer Science · Decision Sciences · #Artificial Intelligence (cs.AI) #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Economics and business #Machine Learning (cs.LG) #Multi-Agent Systems and Negotiation #Theoretical Economics (econ.TH)
paper · pdf · doi:10.48550/arxiv.2401.16198
openalex publication_date 2024/01/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Many real-life contractual relations differ completely from the clean, static model at the heart of principal-agent theory. Typically, they involve repeated strategic interactions of the principal and agent, taking place under uncertainty and over time. While appealing in theory, players seldom use complex dynamic strategies in practice, often preferring to circumvent complexity and approach uncertainty through learning. We initiate the study of repeated contracts with a learning agent, focusing on agents who achieve no-regret outcomes. Optimizing against a no-regret agent is a known open problem in general games; we achieve an optimal solution to this problem for a canonical contract setting, in which the agent's choice among multiple actions leads to success/failure. The solution has a surprisingly simple structure: for some α> 0, initially offer the agent a linear contract with scalar α, then switch to offering a linear contract with scalar 0. This switch causes the agent to ``free-fall'' through their action space and during this time provides the principal with non-zero reward at zero cost. Despite apparent exploitation of the agent, this dynamic contract can leave both players better off compared to the best static contract. Our results generalize beyond success/failure, to arbitrary non-linear contracts which the principal rescales dynamically. Finally, we quantify the dependence of our results on knowledge of the time horizon, and are the first to address this consideration in the study of strategizing against learning agents.