# Efficient Algorithms for Planning with Participation Constraints

arXiv: https://arxiv.org/abs/2205.07767 · HTML: https://mlsanity.com/paper/2205.07767/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 26 references that are in the map.
- First posted on arXiv 16 May 2022.

## Builds on (most cited first, 5 of 5)

- [A Survey of Multi-Objective Sequential Decision-Making](https://mlsanity.com/paper/1402.0590/) (2014)
- [DESPOT: Online POMDP Planning with Regularization](https://mlsanity.com/paper/1609.03250/) (2016)
- [Automated Dynamic Mechanism Design](https://mlsanity.com/paper/2105.06008/) (2021)
- [Interactive POMDP Lite: Towards Practical Planning to Predict and Exploit Intentions for Interacting with Self-Interested Agents](https://mlsanity.com/paper/1304.5159/) (2013)
- [On the Complexity of Dynamic Mechanism Design](https://mlsanity.com/paper/1407.5373/) (2014)

## Built on by (most cited first, 6 of 6)

- [Principal-Agent Reward Shaping in MDPs](https://mlsanity.com/paper/2401.00298/) (2023)
- [Learning with Exposure Constraints in Recommendation Systems](https://mlsanity.com/paper/2302.01377/) (2023)
- [Incentivized Collaboration in Active Learning](https://mlsanity.com/paper/2311.00260/) (2023)
- [Algorithmic Content Selection and the Impact of User Disengagement](https://mlsanity.com/paper/2410.13108/) (2024)
- [Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation](https://mlsanity.com/paper/2412.16934/) (2024)
- [On Incentivized Exploration beyond Bayesianism and Full-Information](https://mlsanity.com/paper/2607.18300/) (2026)

## Abstract (arXiv)

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.