Multi-criteria Coalition Formation Games
When forming coalitions, agents have different utilities per coalition. Game-theoretic approaches typically assume that the scalar utility for each agent for each coalition is public information. However, we argue that this is not a realistic assumption,
- PDF / 339,385 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 51 Downloads / 198 Views
2
Department of Computer Science, University of Oxford, Oxford, UK [email protected] Artificial Intelligence Laboratory, Vrije Universiteit Brussel, Brussels, Belgium [email protected]
Abstract. When forming coalitions, agents have different utilities per coalition. Game-theoretic approaches typically assume that the scalar utility for each agent for each coalition is public information. However, we argue that this is not a realistic assumption, as agents may not want to divulge this information or are even incapable of expressing it. To mitigate this, we propose the multi-criteria coalition formation game model, in which there are different publicly available quality metrics (corresponding to different criteria) for which a value is publicly available for each coalition. The agents have private utility functions that determine their preferences with respect to these criteria, and thus also with respect to the different coalitions. Assuming that we can ask agents to compare two coalitions, we propose a heuristic (best response) algorithm for finding stable partitions in MC2FGs: local stability search (LSS). We show that while theoretically individually stable partitions need not exist in MC2FGs in general, empirically stable partitions can be found. Furthermore, we show that we can find individually stable partitions after asking only a small number of comparisons, which is highly important for applying this model in practice. Keywords: Multi-criteria · Hedonic games games · Preference elicitation · Local search
1
·
Coalition formation
Introduction
Coalitions are an essential part of life; typically we are not able to achieve our goals, or that of an organisation we are part of, by ourselves. Therefore, we need to cooperate in order to achieve these goals. For example, this paper has been written by a coalition of authors, who could not have written this paper individually, without the help of the other authors. Hedonic games, initiated by Banerjee et al. [4] and Bogomolnaia and Jackson [5], offer a versatile framework to model how coalitions are formed by multiple autonomous agents. An important consideration in this respect is coalitional/individual stability, i.e., no individuals wish to deviate from their current situation. In order to determine which coalition structures are stable, we need to know the preferences over different possible coalitions for each agent. The standard c Springer International Publishing AG 2017 J. Rothe (Ed.): ADT 2017, LNAI 10576, pp. 197–213, 2017. DOI: 10.1007/978-3-319-67504-6 14
198
A. Igarashi and D.M. Roijers
setting of hedonic games [6] assumes that we know, or can compute, the exact preferences of each agent over possible coalitions. However, this is not a realistic assumption; not only may agents not want to divulge this information for social or privacy reasons, but the agents might not even be able to specify their utilities a priori to begin with. For example, when working for a company, it may not be socially acceptable to order different possible teams y
Data Loading...
