@conference {1509414,
	title = {Solution Sets for DCOPs and Graphical Games },
	booktitle = {Fifth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS)},
	year = {2006},
	abstract = {A distributed constraint optimization problem (DCOP) is a formalism that captures the rewards and costs of local interactions within
a team of agents, each of whom is choosing an individual action.
When rapidly selecting a single joint action for a team, we typically
solve DCOPs (often using locally optimal algorithms) to generate
a single solution. However, in scenarios where a set of joint actions
(i.e. a set of assignments to a DCOP) is to be generated, metrics are
needed to help appropriately select this set and efficiently allocate
resources for the joint actions in the set. To address this need, we
introduce k-optimality, a metric that captures the desirable properties of diversity and relative quality of a set of locally-optimal
solutions using a parameter that can be tuned based on the level of
these properties required. To achieve effective resource allocation
for this set, we introduce several upper bounds on the cardinalities of k-optimal joint action sets. These bounds are computable in
constant time if we ignore the graph structure, but tighter, graphbased bounds are feasible with higher computation cost. 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 a 1-optimal joint action set for a DCOP also
apply to the number of pure-strategy Nash equilibria in a graphical
game of noncooperative agents.},
	author = {Jonathan P. Pearce and Rajiv T. Maheswaran and Tambe, Milind}
}
