Fair Distribution of Coalition-Value Calculations across Multiple Agents

30^th November 2017, 14:00
Terry Payne

Abstract

Within characteristic function games, agents have the option of exploiting the potential synergy that can emerge from collaborating with their peers, by joining one of many different coalitions in order to achieve their individual or joint goals. However, in order to determine which to join, they need to determine the coalition-value for each of the candidate coalitions (which characterises the payoff they receive, and whether the coalition will be stable).

This can be computationally demanding as the number of coalitions increases exponentially with the number of agents available, and various approaches mediate this problem by distributing the computational load across the agent community.

In this talk, I'll present a novel method for distributing coalition value calculations across several agents, with the following characteristics:
(i) no inter-agent communication is required;
(ii) the coalition value calculations are (approximately) equally partitioned across each of the agents;
(iii) each value is calculated once and only once for each coalition, thus redundant calculations are eliminated;
(iv) there are an equal number of operations for agents with equally sized allocations; and
(v) an agent is only allocated those coalitions in which it is a potential member.

The use of “(n,s)-sequences” to facilitate this, as well as the algorithm used to generate these sequences will be sketched, before showing how our “(n,s)-sequences” are effectively an encoding of black-white combinatorial necklaces (i.e. with n beads where k are black).