Formalizing Admissibility Criteria in Coalition Formation among Goal-directed Agents
Luigi Sauro · 2005
This work studies how goal-directed agents can form profitable coalitions. A coalition is formed when some agents agree to cooperate for the achievement of a shared goal or to exchange with each other the achievement of their own goals. We define two criteria of admissibility that establish which coalitions can be formed under the assumption that agents are self-interested. The first admissibility criterion, the do-ut-des property, formalizes a notion of reciprocity that, informally, can be described as “I give something only if I obtain something else in exchange”. The second admissibility criterion, the composition property, requires that if two coalition formation processes do not effect each other, then they will managed separately. So, roughly, the composition property describes the preference of the agents to form small coalitions. This attitude can be justified by considering that a coalition formation process usually becomes more costly and it has less chance to succeed when the number of the agents involved in it increases. We compare the do-ut-des property, which is a qualitative criterion of admissibility, with the quantitative approach developed in Cooperative Game Theory. In particular, the do-ut-des property can be used as a qualitative methods to restrict the search space of a quantitative criterion of admissibility, we called the q-do-ut-des property, which is even more restrictive than the well-known notion of core. Finally, we define a modal logic to reason about which goals a group of agents can assure if they collaborate. With respect to similar modal logics, as Alternating Time Temporal Logic or Coalition Logic of Propositional Control, our logic enables to explicitly refer to the actions that the agents have to perform in order to achieve a certain state of affairs.