Quantifying the search space for multi-agent system decision-making organizations

Abstract

When a group comes together to pursue a goal, how should the group interact? Both theory and practice show no single organization always performs best; the best organization depends on context. Therefore, a group should adapt how it interacts to fit the situation. In a multi-agent system (MAS), a decision-making framework (DMF) specifies the allocation of decision-making and action-execution responsibilities for a set of goals among agents within the MAS. Adaptive decision-making frameworks (ADMFs) is the ability to change the DMF, changing which agents are responsible for decision-making and action-execution for a set of goals. Interesting questions remain about the ability of an agent to find the 'best,' or 'near optimal' or 'sufficient' DMF among all the possible DMFs. This paper presents initial exploration of this investigation by asking, 'How does the state space of MAS decision-making organizations scale with growth in the number of agents, number of goals and complexity of the organization structure?' This paper presents tight computational bounds on the size of the search space for DMFs by applying combinatorial mathematics. The DMF representation is also shown to be a factor in the size of this search space.

Keywords:

• Multi-agent Systems
• Decision-making
• Agent Organizations
• Coordination
• Organization Search And Learning