KR Conference 2012 Conference Paper
- Stefano Moretti
- Alexis Tsoukiàs
the objective to axiomatically characterize families of ordinal preferences over subsets (Barberà, Barrett, and Pattanaik 1984; Barberà, Bossert, and Pattanaik 2004; Bossert 1995; Bossert et al. 1994; Geist and Endriss 2011; Fishburn 1992; Kannai and Peleg 1984; Kreps 1979). In this context, an order w on the power set 2X is an extension of a primitive order < on X if and only if the relative ranking of any two singleton sets according to w is the same as the relative ranking of the corresponding alternatives according to <. The interpretation of the properties used to characterize extensions is deeply interconnected to the meaning that is attributed to sets. According to the survey of Barberà, Bossert, and Pattanaik (2004), the main contributions from the literature on ranking sets of objects may be grouped in three main classes of problems: 1) complete uncertainty, where a decision maker is asked to rank sets which are considered as formed by mutually exclusive objects (i. e., only one object from a set will materialize), and taking into account that he cannot influence the selection of an object from a set (Barberà, Barrett, and Pattanaik 1984; Kannai and Peleg 1984; Nitzan and Pattanaik 1984); 2) opportunity sets, where sets contain again mutually exclusive objects but, in this case, a decision maker compares sets taking into account that he can select a single element (and only one) from a set (Bossert et al. 1994; Kreps 1979; Puppe 1996); 3) sets as final outcomes, where each set contains objects that are assumed to materialize simultaneously, if that set is selected (Bossert 1995; Fishburn 1992; Roth 1985). This paper is devoted to the analysis of extensions for problems of the third class, where sets are formed by objects that are assumed to materialize at the same time. This situation can be observed in many different contexts like, for example, the college admission problem (Gale and Shapley 1962; Roth 1985), where different colleges need to rank sets of students based on their ranking of individual applicants. For these kind of problems, most of the axiomatic approaches from the literature focused on properties suggesting that the interaction among single objects should not play a relevant role in establishing the ranking among subsets (Bossert 1995; Roth 1985). For instance, the property of responsiveness, introduced by Roth (1985), says that a set S ⊆ X is preferred to a set T ⊆ X whenever S is obtained from T by replacing some object t ∈ T with an- We deal with the problem of how to extend a preference relation over a set X of “objects” to the set of all subsets of X. This problem has been carried out in the tradition of the literature on extending an order on a set to its power set with the objective to analyze the axiomatic structure of families of rankings over subsets. In particular, most of these approaches make use of axioms aimed to prevent any kind of interaction among the objects in X. In this paper, we apply coalitional games to study the problem of extending preferences over a finite set X to its power set 2X. A coalitional game can be seen as a numerical representation of a preference extension on 2X. We focus on a particular class of extensions on 2X such that the ranking induced by the Shapley value of each coalitional game representing an extension in this class, coincides with the original preference on X. Some properties of Shapley extensions are discussed, with the objective to justify and contextualize the application of Shapley extensions to the problem of ranking sets of possibly interacting objects.