Efficient Querying for Cooperative Probabilistic Commitments
This work provides a more efficient way for cooperative agents in multiagent systems to find optimal commitments, which is important for improving coordination infrastructure.
This paper addresses the problem of efficiently finding optimal cooperative commitments in multiagent systems. The authors developed a greedy querying method with provable approximation bounds, empirically demonstrating it finds nearly optimal commitments in a fraction of the time compared to other methods.
Multiagent systems can use commitments as the core of a general coordination infrastructure, supporting both cooperative and non-cooperative interactions. Agents whose objectives are aligned, and where one agent can help another achieve greater reward by sacrificing some of its own reward, should choose a cooperative commitment to maximize their joint reward. We present a solution to the problem of how cooperative agents can efficiently find an (approximately) optimal commitment by querying about carefully-selected commitment choices. We prove structural properties of the agents' values as functions of the parameters of the commitment specification, and develop a greedy method for composing a query with provable approximation bounds, which we empirically show can find nearly optimal commitments in a fraction of the time methods that lack our insights require.