Contract Design Under Approximate Best Responses

Francesco Bacchiocchi, Jiarui Gan, Matteo Castiglioni, Alberto Marchesi, Nicola Gatti
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:2203-2220, 2025.

Abstract

Principal-agent problems model scenarios where a principal aims at incentivizing an agent to take costly, unobservable actions through the provision of payments. Such interactions are ubiquitous in several real-world applications, ranging from blockchain to the delegation of machine learning tasks. In this paper, we initiate the study of hidden-action principal-agent problems under approximate best responses, in which the agent may select any action that is not too much suboptimal given the principal’s payment scheme (a.k.a. contract). Our main result is a polynomial-time algorithm to compute an optimal contract under approximate best responses. This is perhaps surprising, as computing an optimal commitment under approximate best responses is known to be computationally intractable in Stackelberg games. We also investigate the learnability of contracts under approximate best responses, by providing a no-regret learning algorithm for a natural application scenario where the principal does not know anything about the environment.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-bacchiocchi25a, title = {Contract Design Under Approximate Best Responses}, author = {Bacchiocchi, Francesco and Gan, Jiarui and Castiglioni, Matteo and Marchesi, Alberto and Gatti, Nicola}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {2203--2220}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/bacchiocchi25a/bacchiocchi25a.pdf}, url = {https://proceedings.mlr.press/v267/bacchiocchi25a.html}, abstract = {Principal-agent problems model scenarios where a principal aims at incentivizing an agent to take costly, unobservable actions through the provision of payments. Such interactions are ubiquitous in several real-world applications, ranging from blockchain to the delegation of machine learning tasks. In this paper, we initiate the study of hidden-action principal-agent problems under approximate best responses, in which the agent may select any action that is not too much suboptimal given the principal’s payment scheme (a.k.a. contract). Our main result is a polynomial-time algorithm to compute an optimal contract under approximate best responses. This is perhaps surprising, as computing an optimal commitment under approximate best responses is known to be computationally intractable in Stackelberg games. We also investigate the learnability of contracts under approximate best responses, by providing a no-regret learning algorithm for a natural application scenario where the principal does not know anything about the environment.} }
Endnote
%0 Conference Paper %T Contract Design Under Approximate Best Responses %A Francesco Bacchiocchi %A Jiarui Gan %A Matteo Castiglioni %A Alberto Marchesi %A Nicola Gatti %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-bacchiocchi25a %I PMLR %P 2203--2220 %U https://proceedings.mlr.press/v267/bacchiocchi25a.html %V 267 %X Principal-agent problems model scenarios where a principal aims at incentivizing an agent to take costly, unobservable actions through the provision of payments. Such interactions are ubiquitous in several real-world applications, ranging from blockchain to the delegation of machine learning tasks. In this paper, we initiate the study of hidden-action principal-agent problems under approximate best responses, in which the agent may select any action that is not too much suboptimal given the principal’s payment scheme (a.k.a. contract). Our main result is a polynomial-time algorithm to compute an optimal contract under approximate best responses. This is perhaps surprising, as computing an optimal commitment under approximate best responses is known to be computationally intractable in Stackelberg games. We also investigate the learnability of contracts under approximate best responses, by providing a no-regret learning algorithm for a natural application scenario where the principal does not know anything about the environment.
APA
Bacchiocchi, F., Gan, J., Castiglioni, M., Marchesi, A. & Gatti, N.. (2025). Contract Design Under Approximate Best Responses. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:2203-2220 Available from https://proceedings.mlr.press/v267/bacchiocchi25a.html.

Related Material