Efficient Algorithms for Planning with Participation Constraints
This work addresses a key challenge in multi-agent decision-making for scenarios like contract design, offering efficient computational solutions where only approximations existed before.
The paper tackles the problem of planning with participation constraints in Markov decision processes, where a principal must maximize utility while ensuring an agent's continued participation, by providing the first polynomial-time exact algorithm for finite-horizon settings and an efficient approximation algorithm for infinite-horizon cases.
We consider the problem of planning with participation constraints introduced in [Zhang et al., 2022]. In this problem, a principal chooses actions in a Markov decision process, resulting in separate utilities for the principal and the agent. However, the agent can and will choose to end the process whenever his expected onward utility becomes negative. The principal seeks to compute and commit to a policy that maximizes her expected utility, under the constraint that the agent should always want to continue participating. We provide the first polynomial-time exact algorithm for this problem for finite-horizon settings, where previously only an additive $\varepsilon$-approximation algorithm was known. Our approach can also be extended to the (discounted) infinite-horizon case, for which we give an algorithm that runs in time polynomial in the size of the input and $\log(1/\varepsilon)$, and returns a policy that is optimal up to an additive error of $\varepsilon$.