Approximating Continuous Multi-agent Contracts with Lyapunov Function Methods
摘要
We study a principal multi-agent contract design problem with continuous actions, where the principal delegates a task to a set of agents who take costly actions over a continuous interval. Prior work introduced by Dütting et al. (2023) has investigated a similar discrete version of the problem where the success probability function is submodular in the agents chosen by the principal. In this paper, we complement this work by examining the problem when the success probability function is DR-submodular in the agents over a continuous interval. Additionally, our model captures the setting of exerting efforts from chosen agents and extends the set-defined case studied in Dütting et al. (2023). As the agents will play a Nash game before the contract is provided by the principal, who aims to maximize her utility, we cast the principal-agent contract model as a bi-level maximization. We focus on the linear contracts design and provide a backward induction, which deduces the above bi-level problem to a fractional agent chosen single level optimization problem. We incorporate techniques from the literature on DR-submodular optimization and develop a Lyapunov function-based method that obtains a parameterized approximation for this problem. Our results contrast with the discrete submodular setting, where there exists a nearly 1/258-approximation from Dütting et al. (2023).