Incentive Decision Processes

Sashank J. Reddi, Emma Brunskill
Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, PMLR R10:416-425, 2012.

Abstract

We consider Incentive Decision Processes, where a principal seeks to reduce its costs due to another agent’s behavior, by offering incentives to the agent for alternate behavior. We focus on the case where a principal interacts with a greedy agent whose preferences are hidden and static. Though IDPs can be directly modeled as partially observable Markov decision processes (POMDP), we show that it is possible to directly reduce or approximate the IDP as a polynomially-sized MDP: when this representation is approximate, we prove the resulting policy is boundedly-optimal for the original IDP. Our empirical simulations demonstrate the performance benefit of our algorithms over simpler approaches, and also demonstrate that our approximate representation results in a significantly faster algorithm whose performance is extremely close to the optimal policy for the original IDP.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR10-reddi12a, title = {Incentive Decision Processes}, author = {Reddi, Sashank J. and Brunskill, Emma}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {416--425}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/reddi12a/reddi12a.pdf}, url = {https://proceedings.mlr.press/r10/reddi12a.html}, abstract = {We consider Incentive Decision Processes, where a principal seeks to reduce its costs due to another agent’s behavior, by offering incentives to the agent for alternate behavior. We focus on the case where a principal interacts with a greedy agent whose preferences are hidden and static. Though IDPs can be directly modeled as partially observable Markov decision processes (POMDP), we show that it is possible to directly reduce or approximate the IDP as a polynomially-sized MDP: when this representation is approximate, we prove the resulting policy is boundedly-optimal for the original IDP. Our empirical simulations demonstrate the performance benefit of our algorithms over simpler approaches, and also demonstrate that our approximate representation results in a significantly faster algorithm whose performance is extremely close to the optimal policy for the original IDP.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Incentive Decision Processes %A Sashank J. Reddi %A Emma Brunskill %B Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2012 %E Nando de Freitas %E Kevin Murphy %F pmlr-vR10-reddi12a %I PMLR %P 416--425 %U https://proceedings.mlr.press/r10/reddi12a.html %V R10 %X We consider Incentive Decision Processes, where a principal seeks to reduce its costs due to another agent’s behavior, by offering incentives to the agent for alternate behavior. We focus on the case where a principal interacts with a greedy agent whose preferences are hidden and static. Though IDPs can be directly modeled as partially observable Markov decision processes (POMDP), we show that it is possible to directly reduce or approximate the IDP as a polynomially-sized MDP: when this representation is approximate, we prove the resulting policy is boundedly-optimal for the original IDP. Our empirical simulations demonstrate the performance benefit of our algorithms over simpler approaches, and also demonstrate that our approximate representation results in a significantly faster algorithm whose performance is extremely close to the optimal policy for the original IDP. %Z Reissued by PMLR on 04 October 2026.
APA
Reddi, S.J. & Brunskill, E.. (2012). Incentive Decision Processes. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R10:416-425 Available from https://proceedings.mlr.press/r10/reddi12a.html. Reissued by PMLR on 04 October 2026.

Related Material