Conference Proceeding Article
Distributed constraint optimization problems (DCOPs) are well-suited for modeling multi-agent coordination problems where the primary interactions are between local subsets of agents. However, one limitation of DCOPs is the assumption that the constraint rewards are without uncertainty. Researchers have thus extended DCOPs to Stochastic DCOPs (SDCOPs), where rewards are sampled from known probability distribution reward functions, and introduced algorithms to find solutions with the largest expected reward. Unfortunately, such a solution might be very risky, that is, very likely to result in a poor reward. Thus, in this paper, we make three contributions: (1) we propose a stricter objective for SDCOPs, namely to find a solution with the most stochastically dominating probability distribution reward function; (2) we introduce an algorithm to find such solutions; and (3) we show that stochastically dominating solutions can indeed be less risky than expected reward maximizing solutions.
DCOP, DPOP, Stochastic Dominance, Uncertainty
Artificial Intelligence and Robotics | Computer Sciences | Operations Research, Systems Engineering and Industrial Engineering
Intelligent Systems and Decision Analytics
AAMAS '12: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems: 4-8 June 2012, Valencia, Spain
City or Country
NGUYEN DUC THIEN; YEOH, William; and LAU, Hoong Chuin.
Stochastic dominance in stochastic DCOPs for risk-sensitive applications. (2012). AAMAS '12: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems: 4-8 June 2012, Valencia, Spain. 1, 272-279. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/3370
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.