6 accepted papers
We study fundamental connections between coalition formation games and clustering, illustrating the cross-disciplinary relevance of these concepts. We focus on graphical hedonic games where agents' preferences are compactly represented by a friendship graph and an enemy graph. In the context of…
We survey the notion of control in various areas of computational social choice (COMSOC) such as voting, fair allocation, cooperative game theory, matching under preferences, and group identification. In all these scenarios, control can be exerted, for instance, by adding or deleting agents with the
Both Schulze and ranked pairs are voting rules that satisfy many natural, desirable axioms. Many standard types of electoral control (with a chair seeking to change the outcome of an election by interfering with the election structure) have already been studied. However, for control by replacing can…
Fair allocation of indivisible goods is a central topic in many AI applications. Unfortunately, the corresponding problems are known to be NP-hard for many fairness concepts, so unless P = NP, exact polynomial-time algorithms cannot exist for them. In practical applications, however, it would be hig…
Nguyen et al. [2016] introduced altruistic hedonic games in which agents’ utilities depend not only on their own preferences but also on those of their friends in the same coalition. We propose to extend their model to coalition formation games in general, considering also the friends in other coali…
In fair division of indivisible goods, finding an allocation that satisfies fairness and efficiency simultaneously is highly desired but computationally hard. We solve this problem approximately in polynomial time by modeling it as a bi-criteria optimization problem that can be solved efficiently…