Abstract:

Hedonic Games and the Group Activity Selection Problem are two well-established models to describe the coalition formation of strategic agents. While most of the literature has been focusing on the existence and computation of stable outcomes, under the demanding assumption of complete knowledge of agents’ preferences, very little has been made on the elicitation of true preferences. With this paper, we provide an overview of strategyproof mechanisms for the aforementioned games with particular attention on mechanisms having a good approximation guarantee in terms of social welfare. Moreover, we outline future challenges in this area.

Abstract:

Hedonic Games (HGs) are a classical framework modeling coalition formation of strategic agents guided by their individual preferences. According to these preferences, it is desirable that a coalition structure (i.e. a partition of agents into coalitions) satisfies some form of stability. The most well-known and natural of such notions is arguably core-stability. Informally, a partition is core-stable if no subset of agents would like to deviate by regrouping in a so-called core-blocking coalition. Unfortunately, core-stable partitions seldom exist and even when they do, it is often computationally intractable to find one. To circumvent these problems, we propose the notion of ε-fractional core-stability, where at most an ε-fraction of all possible coalitions is allowed to core-block. It turns out that such a relaxation may guarantee both existence and polynomial-time computation. Specifically, we design efficient algorithms returning an ε-fractional core-stable partition, with ε exponentially decreasing in the number of agents, for two fundamental classes of HGs: Simple Fractional and Anonymous. From a probabilistic point of view, being the definition of ε-fractional core equivalent to requiring that uniformly sampled coalitions core-block with probability lower than ε, we further extend the definition to handle more complex sampling distributions. Along this line, when valuations have to be learned from samples in a PAC-learning fashion, we give positive and negative results on which distributions allow the efficient computation of outcomes that are ε-fractional core-stable with arbitrarily high confidence.

Abstract:

For the fundamental problem of fairly dividing a set of indivisible items among agents, envy-freeness up to any item (EFX) and maximin fairness (MMS) are arguably the most compelling fairness concepts proposed until now. Unfortunately, despite significant efforts over the past few years, whether EFX allocations always exist is still an enigmatic open problem, let alone their efficient computation. Furthermore, today we know that MMS allocations are not always guaranteed to exist. These facts weaken the usefulness of both EFX and MMS, albeit their appealing conceptual characteristics. We propose two alternative fairness concepts—called epistemic EFX (EEFX) and minimum EFX share fairness (MXS)—inspired by EFX and MMS. For both, we explore their relationships to well-studied fairness notions and, more importantly, prove that EEFX and MXS allocations always exist and can be computed efficiently for additive valuations. Our results justify that the new fairness concepts can be excellent alternatives to EFX and MMS.

Abstract:

Fair division of indivisible goods is a central challenge in artificial intelligence. For many prominent fairness criteria including envy-freeness (EF) or proportionality (PROP), no allocations satisfying these criteria might exist. Two popular remedies to this problem are randomization or relaxation of fairness concepts. A timely research direction is to combine the advantages of both, commonly referred to as Best of Both Worlds (BoBW). 

We consider fair division with entitlements, which allows to adjust notions of fairness to heterogeneous priorities among agents. This is an important generalization to standard fair division models and is not well-understood in terms of BoBW results. Our main result is a lottery for additive valuations and different entitlements that is ex-ante weighted envy-free (WEF), as well as ex-post weighted proportional up to one good (WPROP1) and weighted transfer envy-free up to one good (WEF(1, 1)). It can be computed in strongly polynomial time. We show that this result is tight – ex-ante WEF is incompatible with any stronger ex-post WEF relaxation. 

In addition, we extend BoBW results on group fairness to entitlements and explore generalizations of our results to instances with more expressive valuation functions.

Abstract:

We study PAC learnability and PAC stabilizability of Hedonic Games (HGs), i.e., efficiently inferring preferences or core-stable partitions from samples. We first expand the known learnability/stabilizability landscape for some of the most prominent HGs classes, providing results for Friends and Enemies Games, Bottom Responsive, and Anonymous HGs. Then, having a broader view in mind, we attempt to shed light on the structural properties leading to learnability/stabilizability, or lack thereof, for specific HGs classes. Along this path, we focus on the fully expressive Hedonic Coalition Nets representation of HGs. We identify two sets of conditions that lead to efficient learnability, and which encompass all of the known positive learnability results. On the side of stability, we reveal that, while the freedom of choosing an ad hoc adversarial distribution is the most obvious hurdle to achieving PAC stability, it is not the only one. First, we show a distribution independent necessary condition for PAC stability. Then, we focus on W-games, where players have individual preferences over other players and evaluate coalitions based on the least preferred member. We prove that these games are PAC stabilizable under the class of bounded distributions, which assign positive probability mass to all coalitions. Finally, we discuss why such a result is not easily extendable to other HGs classes even in this promising scenario. Namely, we establish a purely computational property necessary for achieving PAC stability.

Abstract:

We investigate strategyproof mechanisms in the Group Activity Selection Problem with the additively separable property. Namely, agents have distinct preferences for each activity and individual weights for the other agents. We evaluate our mechanisms in terms of their approximation ratio with respect to the maximum utilitarian social welfare.

We first show that, for arbitrary non-negative preferences, no deterministic mechanism can achieve a bounded approximation ratio. Thus, we provide a randomized  $k$-approximate mechanism, where $k$ is the number of activities, and a corresponding $2 - \frac{2}{k+1}$ lower bound. Furthermore, we propose a tight $(2 - \frac{1}{k})$-approximate randomized mechanism when activities are copyable.

We then turn our attention to instances where preferences can only be unitary, that is $0$ or $1$. In this case, we provide a $k$-approximate deterministic mechanism, which we show to be the best possible one within the class of strategyproof and anonymous mechanisms. We also provide a general lower bound of $\Omega\left( \sqrt{k}\right)$ when anonymity is no longer a constraint.  Finally, we focus on unitary preferences and weights, and prove that, while any mechanism returning the optimum is not strategyproof,  there exists a $2$-approximate deterministic mechanism.

Abstract:

We consider the problem of maximizing the Nash social welfare when allocating a set  of indivisible goods to a set  of agents. We study instances, in which all agents have 2-value additive valuations: The value of every agent i∈ N for every good j∈ G is vij∈{p,q}, for p,q∈ℕ, p≤q. Maybe surprisingly, we design an algorithm to compute an optimal allocation in polynomial time if p divides q, i.e., when p=1 and q∈ℕ after appropriate scaling. The problem is \classNP-hard whenever p and q are coprime and p≥3.

In terms of approximation, we present positive and negative results for general p and q. We show that our algorithm obtains an approximation ratio of at most 1.0345. Moreover, we prove that the problem is \classAPX-hard, with a lower bound of 1.000015 achieved at p/q=4/5.

Abstract:

In this paper we consider Distance Hedonic Games (DHGs), a class of non-transferable utility coalition formation games that properly generalizes previously existing models, like Social Distance Games (SDGs) and Fractional Hedonic Games (FHGs). In particular, while in SDGs each agent x contributes to the utility of another agent y in her coalition in an inversely proportional fashion with respect to their distance, and in FHGs only if they are neighbors, in DHGs we assume the existence of a scoring vector α, in which the i-th coefficient αi expresses the extent to which x contributes to the utility of y if they are at distance i. We assume the scoring vector to be the same for all agents, and focus on Nash stable outcomes in the arising games, i.e., on coalition structures in which no agent can unilaterally improve her gain by deviating. 

We consider two different natural scenarios for the scoring vector, with monotonically increasing and monotonically decreasing coefficients. In both cases we give NP-hardness and inapproximability results on the problems of finding a social optimum and a best Nash stable outcome. Moreover, we characterize the topologies of coalitions that provide high social welfare and consequently give suitable bounds on the Price of Anarchy and on the Price of Stability. 

Abstract:

In this paper we consider Distance Hedonic Games (DHGs), a class of non-transferable utility coalition formation games that properly generalizes previously existing models, like Social Distance Games (SDGs) and Fractional Hedonic Games (FHGs). In particular, while in SDGs each agent x contributes to the utility of another agent y in her coalition in an inversely proportional fashion with respect to their distance, and in FHGs only if they are neighbors, in DHGs we assume the existence of a scoring vector α, in which the i-th coefficient αi expresses the extent to which x contributes to the utility of y if they are at distance i. We assume the scoring vector to be the same for all agents, and focus on Nash stable outcomes in the arising games, i.e., on coalition structures in which no agent can unilaterally improve her gain by deviating. 

We consider two different natural scenarios for the scoring vector, with monotonically increasing and monotonically decreasing coefficients. In both cases we give NP-hardness and inapproximability results on the problems of finding a social optimum and a best Nash stable outcome. Moreover, we characterize the topologies of coalitions that provide high social welfare and consequently give suitable bounds on the Price of Anarchy and on the Price of Stability. 

Abstract:

We investigate strategyproof mechanisms for Friends and Enemies Games, a subclass of Hedonic Games in which every agent classifies any other one as a friend or as an enemy. In this setting, we consider the two classical scenarios proposed in the literature, called Friends Appreciation (FA) and Enemies Aversion (EA). Roughly speaking, in the former each agent gives priority to the number of friends in her coalition, while in the latter to the number of enemies.

We provide strategyproof mechanisms for both settings. More precisely, for FA we first present a deterministic n-approximation mechanism, and then show that a much better result can be accomplished by resorting to randomization. Namely, we provide a randomized mechanism whose expected approximation ratio is 4, and arbitrarily close to 4 with high probability. For EA, we give a simple  (1+ √2 )n -approximation mechanism, and show that its performance is asymptotically tight by proving that it is NP-hard to approximate the optimal solution within O( n1- ε )  for any fixed ε>0.

Finally, we show how to extend our results in the presence of neutrals, i.e., when agents can also be indifferent about other agents, and we discuss anonymity.

Abstract:

We investigate strategyproof mechanisms for Friends and Enemies Games, a subclass of Hedonic Games in which every agent classifies any other one as a friend or as an enemy. In this setting, we consider the two classical scenarios proposed in the literature, called Friends Appreciation (FA) and Enemies Aversion (EA). Roughly speaking, in the former each agent gives priority to the number of friends in her coalition, while in the latter to the number of enemies.

We focus on the objective of maximizing the sum of the utilities of the agents and provide strategyproof mechanisms for both settings. More precisely, for FA  we first present a deterministic n-approximation mechanism, n being the number of agents, and then show that a much better approximation can be achieved by resorting to randomization. Namely, we provide a randomized mechanism whose expected approximation ratio is 4, and arbitrarily close to 4 with high probability. For EA, we give a simple  (1+ √2 )n-approximation mechanism, and show that its performance is asymptotically tight by proving that it is NP-hard to approximate the optimal solution within O( n1- ε )  for any fixed ε>0. We also show that, if computational efficiency is not a concern, it is possible to achieve a  (1+ √2 )-approximation by means of a deterministic strategyproof mechanism with exponential runtime. Finally, we show how to extend our results in the presence of  neutrals, i.e., when agents can also be indifferent about other agents.

Abstract:

It is well-documented that social networks play a considerable role in information spreading. The dynamic processes governing the diffusion of information have been studied in many fields, including epidemiology, sociology, economics, and computer science. A widely studied problem in the area of viral marketing is the target set selection: in order to market a new product, hoping it will be adopted by a large fraction of individuals in the network, which set of individuals should we “target” (for instance, by offering them free samples of the product)? In this paper, we introduce a diffusion model in which some of the neighbors of a node have a negative influence on that node, namely, they induce the node to reject the feature that is supposed to be spread. We study the target set selection problem within this model, first proving a strong inapproximability result holding also when the diffusion process is required to reach all the nodes in a couple of rounds. Then, we consider a set of restrictions under which the problem is approximable to some extent.

Abstract:

A decade ago, Gerhard Woeginger posed an open problem that became well-known as “Gerhard’s Hiking Problem”: Consider a group of n people that want to go hiking; everyone expresses preferences over the size of their hiking group in the form of an interval between 1 and n. Is it possible to efficiently assign the n people to a set of hiking subgroups so that every person approves the size of their assigned subgroup? The problem is also known as efficiently deciding if an instance of an anonymous Hedonic Game with interval approval preferences admits a wonderful partition. We resolve the open problem in the affirmative by presenting an O(n^5) time algorithm for Gerhard’s Hiking Problem. Our solution is based on employing a dynamic programming approach for a specific rectangle stabbing problem from computational geometry. Moreover, we propose natural more demanding extensions of the problem, e.g., maximizing the number of satisfied people, and show that they are also efficiently solvable. Additionally, we precisely map the boundary of tractability for the wonderful partition problem by proving that finding such a partition becomes NP-hard if non-interval approval size sets of size two are allowed. This closes a gap in the complexity landscape, since hardness was only known for the case with non-interval approval size sets of size at most 3. Last but not least, we employ our solution to efficiently compute a partition that maximizes the egalitarian welfare for anonymous single-peaked Hedonic Games

Abstract:

We consider the problem of maximizing the Nash social welfare when allocating a set G of indivisible goods to a set N of agents. We study instances, in which all agents have 2-value additive valuations: The value of a good g ∈ G for an agent i ∈ N is either 1 or s, where s is an odd multiple of 1/2 larger than one. We show that the problem is solvable in polynomial time. In [ACH+22] it was shown that this problem is solvable in polynomial time if s is integral and is NP-hard whenever s = p/q, p ∈ N and q ∈ N are co-prime and p > q ≥ 3. For the latter situation, an approximation algorithm was also given. It obtains an approximation ratio of at most 1.0345. Moreover, the problem is APX-hard, with a lower bound of 1.000015 achieved at p/q = 5/4. The case q = 2 and odd p was left open. 

In the case of integral s, the problem is separable in the sense that the optimal allocation of the heavy goods (= value s for some agent) is independent of the number of light goods (= value 1 for all agents). This leads to an algorithm that first computes an optimal allocation of the heavy goods and then adds the light goods greedily. This separation no longer holds for s = 3/2; a simple example is given in the introduction. Thus an algorithm has to consider heavy and light goods together. This complicates matters considerably. Our algorithm is based on a collection of improvement rules that transfers any allocation into an optimal allocation and exploits a connection to matchings with parity constraints.