Affiliations: Computer Science and Engineering, University of Michigan Ann Arbor, MI 48109, USA | [x] Delft University of Technology, PO Box 5031, 2600 GA Delft, The Netherlands | [y] Jet propulsion Laboratory, 4800 Oak Grove Dr., Pasadena, CA 91750, USA
Abstract: This work applies the CP-net preference representation to the problem of negotiating optimal joint outcomes, hoping to exploit the CP-net benefit of efficient preferential optimization in multiagent settings. A fundamental challenge in doing so is that acyclic CP-nets only capture an agent's preferences over outcomes qualitatively, as a partial order, making comparisons between agents' strengths of preferences over outcomes problematic. This article presents a plausible (though not the only) strategy to assess outcomes based on their relative positions in the agents' partial orders. Given the ability to compare strength of preference over outcomes, a brute-force search in the space of outcomes can provably yield an optimal (maximin) joint outcome. More importantly, it is shown that the optimal joint outcome can, in principle, be found more efficiently by using a multiagent variation of the CP-net preferential optimization algorithm, provided that the right decisions are made about which agent assigns each variable. Finally, heuristics are developed that find an approximately optimal variable assignment strategy. Empirical evaluation indicates that, relative to the outcome graph search, the new heuristic algorithm based on direct variable assignment achieves exponential speedup, while costing only a small constant factor in solution quality.
Keywords: Multiagent reasoning, preferences, social choice, Search strategies, heuristic methods
