Author(s): Jonathan P. Pearce, Rajiv T. Maheswaran, and Milind Tambe
Title: Graph-Based Bounds on k-optimal Joint-action Sets for Multiple Agents
Abstract: In multi-agent systems where sets of joint actions (JAs) are generated, tools are needed to evaluate these sets and efficiently allocate resources for the many JAs. To address evaluation, we introduce k-optimality as a metric that captures desirable properties of diversity and relative quality. Our main contribution is a method to utilize local interaction structure to obtain bounds on cardinalities of k-optimal JA sets. Bounds help choose the appropriate level of k-optimality for settings with fixed resources and help determine appropriate resource allocation for settings where a fixed level of k-optimality is desired. In addition, our bounds for 1-optimal JA sets also apply to the number of pure-strategy Nash equilibria in a graphical game of noncooperative agents.
Download: PDF
Thursday, 19-May-2005 20:50:57 CEST