We introduce a new notion of deterministic stable solution for non-cooperative games, termed subsidized equilibrium. It assumes that an amount of money can be used as a pool of subsidies to stabilize a strategy profile that otherwise would not be accepted by (some of) the players. Roughly speaking, for a given amount of money, a strategy profile is a subsidized equilibrium if the total payoff loss incurred by players not playing best-responses does not exceed that amount, i.e., there is enough money to refund all players experiencing a regret. With respect to many other solution concepts in the literature, the notion of subsidized equilibrium has important advantages. Specifically, for a sufficiently high value of money, a subsidized equilibrium always exists and can even be computed in polynomial time; also, existence of an efficient subsidized equilibrium can be guaranteed. Thus, determining for which amounts of money existence, polynomial time computability and efficiency can or cannot be achieved becomes an intriguing question. We provide initial results towards this direction for some widely studied classes of games.

The core is a well-known and fundamental notion of stability in games intended to model coalition formation such as hedonic games: an outcome is core stable if there exists no blocking coalition , i.e., no set of agents that may profit by forming a coalition together. The fact that the cardinality of a blocking coalition, i.e., the number of deviating agents that have to coordinate themselves, can be arbitrarily high, and the fact that agents may benefit only by a tiny amount from their deviation, while they could incur in a higher cost for deviating, suggest that the core is not able to suitably model practical scenarios in large and highly distributed multi-agent systems. For this reason, we consider relaxed core stable outcomes where the notion of permissible deviations is modified along two orthogonal directions: the former takes into account the size q of the deviating coalition, and the latter the amount of utility gain, in terms of a multiplicative factor k , for each member of the deviating coalition. These changes result in two different notions of stability, namely, the q-size core and k-improvement core . We consider fractional hedonic games, that is a well-known subclass of hedonic games for which core stable outcomes are not guaranteed to exist and it is computationally hard to decide non-emptiness of the core; we investigate these relaxed concepts of stability with respect to their existence, computability and performance in terms of price of anarchy and price of stability, by providing in many cases tight or almost tight bounds. Interestingly, the considered relaxed notions of core also possess the appealing property of recovering, in some notable cases, the convergence, the existence and the possibility of computing stable solutions in polynomial time.

This article deals with hedonic skill games, a non-transferable utility counterpart of coalitional skill games which model collaboration among entities through the abstract notions of tasks and the skills required to complete them. In the weighted tasks setting, we show that deciding whether an instance of the game admits a Nash stable outcome is NP-complete. We then characterize the instances admitting a Nash stable outcome. This characterization relies on the fact that every agent holds (resp., every task requires) either a single skill or more than one skill. For these instances, the complexity of computing a Nash stable outcome is determined, together with the possibility that natural dynamics converge to a Nash stable outcome from any initial configuration. Our study is completed with a thorough analysis of the price of anarchy of instances always admitting a Nash stable outcome.

We study digraph k-coloring games where strategic agents are vertices of a digraph and arcs represent agents' mutual unidirectional conflicts/idiosyncrasies. Each agent can select, as strategy, one of k different colors, and her payoff in a given state (a k-coloring) is given by the number of outgoing neighbors with a color different from her one. Such games model lots of strategic real-world scenarios and are related to several fundamental classes of anti-coordination games. Unfortunately, the problem of understanding whether an instance of the game admits a pure Nash equilibrium (NE), i.e., a state where no agent can improve her payoff by changing strategy, is NP-complete. Thus, in this paper, we focus on algorithms to compute an approximate NE: informally, a coloring is an approximate γ-NE, for some γ ≥ 1, if no agent can improve her payoff, by changing strategy, by a multiplicative factor of γ. Our contribution is manifold and of both theoretical and experimental nature. First, we characterize the hardness of finding pure and approximate equilibria in both general and special classes of digraphs. Second, we design and analyze three approximation algorithms with different theoretical guarantees on the approximation ratio, under different conditions; (i) algorithm APPROX-1 which computes, for any k ≥ 3, a Δo-NE for any n vertex graph having a maximum outdegree of Δo, in polynomial time; (ii) algorithm LLL-SPE, a randomized algorithm that, for any constant k ≥ 2, determines a γ-NE for some constant γ but only in digraphs whose minimum outdegree is sufficiently large, in polynomial time in expectation; (iii) algorithm APPROX-3 which, for any ε, computes a (1+ε)-NE by using O(log(n)/ε) colors, for any n-vertex digraph. Note that, the latter shows that a (1+ε)-NE exists and can be computed in polynomial time for k = O(log(n)). Finally, to assess how proposed algorithms behave in the typical case, we complete our study with an extensive experimental evaluation showing that, while newly introduced algorithms achieve bounded worst case behavior, they generally perform poorly in practice. Motivated by such unsatisfactory performance, we shift our attention to the best-response paradigm, successfully applied to other classes of games, and design and experimentally evaluate it a heuristic based on such paradigm. Our experiments provide strong evidences of such approach outperforming, in terms of approximation and computational time, all other methods and hence identify it as the most suited candidate for practical usage. More remarkably, it is also able to compute exact, pure NE in the great majority of cases. This suggests that, while these games are known to not always possess a pure NE, such an equilibrium often exists and can be efficiently computed, even by a distributed uncoordinated interaction of the agents.

In hedonic games, a set of n agents, having preferences over all possible coalition structures, needs to agree on a stable outcome. In this work, we initiate the study of hedonic games with fixed-size coalitions, where the set of possible coalition structures is restricted as follows: there are k coalitions, each coalition has a fixed size, and the sum of the sizes of all coalitions equals n. We focus on the basic model of additively separable hedonic games with symmetric preferences, where an agent's preference is captured by a utility function which sums up a contribution due to any other agent in the same coalition. In this setting, an outcome is stable if no pair of agents can exchange coalitions and improve their utilities. Conditioned on the definition of improvement, three stability notions arise: swap stability under transferable utilities, which requires to improve the sum of the utilities of both agents, swap stability, which requires to improve the utility of one agent without decreasing the utility of the other one, and strict swap stability, requiring to improve the utilities of both agents simultaneously. We analyse the fundamental questions of existence, complexity and efficiency of stable outcomes, and that of complexity of a social optimum.

We investigate the problem of preselecting a subset of buyers (also called agents) participating in a market so as to optimize the performance of stable outcomes. We consider four scenarios arising from the combination of two stability notions, namely market envy-freeness and agent envy-freeness, with the two state-of-the-art objective functions of social welfare and seller’s revenue. When insisting on market envy-freeness, we prove that the problem cannot be approximated within n 1−ε (with n being the number of buyers) for any ε > 0, under both objective functions; we also provide approximation algorithms with an approximation ratio tight up to subpolynomial multiplicative factors for social welfare and the seller’s revenue. The negative result, in particular, holds even for markets with single-minded buyers. We also prove that maximizing the seller’s revenue is NP-hard even for a single buyer, thus closing a previous open question. Under agent envy-freeness and for both objective functions, instead, we design a polynomial time algorithm transforming any stable outcome for a market involving any subset of buyers into a stable outcome for the whole market without worsening its performance. This result creates an interesting middle-ground situation where, if on the one hand buyer preselection cannot improve the performance of agent envy-free outcomes, on the other one it can be used as a tool for simplifying the combinatorial structure of the buyers’ valuation functions in a given market. Finally, we consider the restricted case of multi-unit markets, where all items are of the same type and are assigned the same price. For these markets, we show that preselection may improve the performance of stable outcomes in all of the four considered scenarios, and design corresponding approximation algorithms.

The core is a well-known and fundamental notion of stability in games intended to model coalition formation such as hedonic games. The fact that the number of deviating agents (that have to coordinate themselves) can be arbitrarily high, and the fact that agents may benefit only by a tiny amount from their deviation (while they could incur in a cost for deviating), suggest that the core is not able to suitably model many practical scenarios in large and highly distributed multi-agent systems. For this reason, we consider relaxed core stable outcomes where the notion of permissible deviations is modified along two orthogonal directions: the former takes into account the size of the deviating coalition, and the latter the amount of utility gain for each member of the deviating coalition. These changes result in two different notions of stability, namely, the q-size core and k-improvement core. We investigate these concepts of stability in fractional hedonic games, that is a well-known subclass of hedonic games for which core stable outcomes are not guaranteed to exist and it is computationally hard to decide nonemptiness of the core. Interestingly, the considered relaxed notions of core also possess the appealing property of recovering, in some notable cases, the convergence, the existence and the possibility of computing stable solutions in polynomial time.

Abstract Motivated by many practical applications, in this paper we study budget feasible mechanisms with the goal of procuring an independent set of a matroid. More specifically, we are given a matroid $${\mathcal {M}}=(E,{\mathcal {I}})$$ M = ( E , I ) . Each element of the ground set E is controlled by a selfish agent and the cost of the element is private information of the agent itself. A budget limited buyer has additive valuations over the elements of E. The goal is to design an incentive compatible budget feasible mechanism which procures an independent set of the matroid of largest possible value. We also consider the more general case of the pair $${\mathcal {M}}=(E,{\mathcal {I}})$$ M = ( E , I ) satisfying only the hereditary property. This includes matroids as well as matroid intersection. We show that, given a polynomial time deterministic algorithm that returns an $$\alpha $$ α -approximation to the problem of finding a maximum-value independent set in $${\mathcal {M}}$$ M , there exists an individually rational, truthful and budget feasible mechanism which is $$(3\alpha +1)$$ ( 3 α + 1 ) -approximated and runs in polynomial time, thus yielding also a 4-approximation for the special case of matroids.

Additively separable hedonic games and fractional hedonic games have received considerable attention in the literature. They are coalition formation games among selfish agents based on their mutual preferences. Most of the work in the literature characterizes the existence and structure of stable outcomes (i.e., partitions into coalitions) assuming that preferences are given. However, there is little discussion of this assumption. In fact, agents receive different utilities if they belong to different coalitions, and thus it is natural for them to declare their preferences strategically in order to maximize their benefit. In this paper we consider strategyproof mechanisms for additively separable hedonic games and fractional hedonic games, that is, partitioning methods without payments such that utility maximizing agents have no incentive to lie about their true preferences. We focus on social welfare maximization and provide several lower and upper bounds on the performance achievable by strategyproof mechanisms for general and specific additive functions. In most of the cases we provide tight or asymptotically tight results. All our mechanisms are simple and can be run in polynomial time. Moreover, all the lower bounds are unconditional, that is, they do not rely on any computational complexity assumptions.

We consider the online version of the coalition structure generation problem, in which agents, corresponding to the vertices of a graph, appear in an online fashion and have to be partitioned into coalitions by an authority (i.e., an online algorithm). When an agent appears, the algorithm has to decide whether to put the agent into an existing coalition or to create a new one containing, at this moment, only her. The decision is irrevocable. The objective is partitioning agents into coalitions so as to maximize the resulting social welfare that is the sum of all coalition values. We consider two cases for the value of a coalition: (1) the sum of the weights of its edges, and (2) the sum of the weights of its edges divided by its size. Coalition structures appear in a variety of application in AI, multi-agent systems, networks, as well as in social networks, data analysis, computational biology, game theory, and scheduling. For each of the coalition value functions we consider the bounded and unbounded cases depending on whether or not the size of a coalition can exceed a given value α. Furthermore, we consider the case of a limited number of coalitions and various weight functions for the edges, i.e., unrestricted, positive and constant weights. We show tight or nearly tight bounds for the competitive ratio in each case.

In coalition formation games self-organized coalitions are created as a result of the strategic interactions of independent agents. In this paper we assume that for each couple of agents ( i , j ), weight \(w_{i,j}=w_{j,i}\) reflects how much agents i and j benefit from belonging to the same coalition. We consider the (symmetric) modified fractional hedonic game , that is a coalition formation game in which agents’ utilities are such that the total benefit of agent i belonging to a coalition (given by the sum of \(w_{i,j}\) over all other agents j belonging to the same coalition) is averaged over all the other members of that coalition, i.e., excluding herself. Modified fractional hedonic games constitute a class of succinctly representable hedonic games. We are interested in the scenario in which agents, individually or jointly, choose to form a new coalition or to join an existing one, until a stable outcome is reached. To this aim, we consider common stability notions leading to strong Nash stable outcomes, Nash stable outcomes or core stable outcomes: we study their existence, complexity and performance, both in the case of general weights and in the case of 0–1 weights. In particular, we completely characterize the existence of the considered stable outcomes and show many tight or asymptotically tight results on the performance of these natural stable outcomes for modified fractional hedonic games, also highlighting the differences with respect to the model of fractional hedonic games, in which the total benefit of an agent in a coalition is averaged over all members of that coalition, i.e., including herself.

The generalized group activity selection problem (GGASP) consists in assigning agents to activities according to their preferences, which depend on both the activity and the set of its participants. We consider additively separable GGASPs, where every agent has a separate valuation for each activity as well as for any other agent, and her overall utility is given by the sum of the valuations she has for the selected activity and its participants. Depending on the nature of the agents' valuations, nine different variants of the problem arise. We completely characterize the complexity of computing a social optimum and provide approximation algorithms for the NP-hard cases. We also focus on Nash stable outcomes, for which we give some complexity results and a full picture of the related performance by providing tights bounds on both the price of anarchy and the price of stability.

We study the existence of allocations of indivisible goods that are envy-free up to one good (EF1), under the additional constraint that each bundle needs to be connected in an underlying item graph G. When the items are arranged in a path, we show that EF1 allocations are guaranteed to exist for arbitrary monotonic utility functions over bundles, provided that either there are at most four agents, or there are any number of agents but they all have identical utility functions. Our existence proofs are based on classical arguments from the divisible cake-cutting setting, and involve discrete analogues of cut-and-choose, of Stromquist's moving-knife protocol, and of the Su-Simmons argument based on Sperner's lemma. Sperner's lemma can also be used to show that on a path, an EF2 allocation exists for any number of agents. Except for the results using Sperner's lemma, all of our procedures can be implemented by efficient algorithms. Our positive results for paths imply the existence of connected EF1 or EF2 allocations whenever G is traceable, i.e., contains a Hamiltonian path. For the case of two agents, we completely characterize the class of graphs G that guarantee the existence of EF1 allocations as the class of graphs whose biconnected components are arranged in a path. This class is strictly larger than the class of traceable graphs; one can check in linear time whether a graph belongs to this class, and if so return an EF1 allocation.

In this paper we consider a generalization of the well-known budgeted maximum coverage problem. We are given a ground set of elements and a set of bins. The goal is to find a subset of elements along with an associated set of bins, such that the overall cost is at most a given budget, and the profit is maximized. Each bin has its own cost and the cost of each element depends on its associated bin. The profit is measured by a monotone submodular function over the elements. We first present an algorithm that guarantees an approximation factor of $\frac{1}{2}\left(1-\frac{1}{e^α}\right)$, where $α\leq 1$ is the approximation factor of an algorithm for a sub-problem. We give two polynomial-time algorithms to solve this sub-problem. The first one gives us $α=1- ε$ if the costs satisfies a specific condition, which is fulfilled in several relevant cases, including the unitary costs case and the problem of maximizing a monotone submodular function under a knapsack constraint. The second one guarantees $α=1-\frac{1}{e}-ε$ for the general case. The gap between our approximation guarantees and the known inapproximability bounds is $\frac{1}{2}$. We extend our algorithm to a bi-criterion approximation algorithm in which we are allowed to spend an extra budget up to a factor $β\geq 1$ to guarantee a $\frac{1}{2}\left(1-\frac{1}{e^{αβ}}\right)$-approximation. If we set $β=\frac{1}α\ln \left(\frac{1}{2ε}\right)$, the algorithm achieves an approximation factor of $\frac{1}{2}-ε$, for any arbitrarily small $ε>0$.

We consider fractional hedonic games, a subclass of coalition formation games that can be succinctly modeled by means of a graph in which nodes represent agents and edge weights the degree of preference of the corresponding endpoints. The happiness or utility of an agent for being in a coalition is the average value she ascribes to its members. We adopt Nash stable outcomes as the target solution concept; that is we focus on states in which no agent can improve her utility by unilaterally changing her own group. We provide existence, efficiency and complexity results for games played on both general and specific graph topologies. As to the efficiency results, we mainly study the quality of the best Nash stable outcome and refer to the ratio between the social welfare of an optimal coalition structure and the one of such an equilibrium as to the price of stability. In this respect, we remark that a best Nash stable outcome has a natural meaning of stability, since it is the optimal solution among the ones which can be accepted by selfish agents. We provide upper and lower bounds on the price of stability for different topologies, both in case of weighted and unweighted edges. Beside the results for general graphs, we give refined bounds for various specific cases, such as triangle-free, bipartite graphs and tree graphs. For these families, we also show how to efficiently compute Nash stable outcomes with provable good social welfare.

We revisit fundamental problems in undirected and directed graphs, such as the problems of computing spanning trees, shortest paths, steiner trees, and spanning arborescences of minimum cost. We assume that there are d different cost functions associated with the edges of the input graph and seek for solutions to the resulting multidimensional graph problems so that the p-norm of the different costs of the solution is minimized. We present combinatorial algorithms that achieve very good approximations for this objective. The main advantage of our algorithms is their simplicity: they are as simple as classical combinatorial graph algorithms of Dijkstra and Kruskal, or the greedy algorithm for matroids.

We consider the problem of computing approximate Nash equilibria in monotone congestion games with polynomially decreasing cost functions. This class of games generalizes the one of network congestion games, while polynomially decreasing cost functions also include the fundamental Shapley cost sharing value. We design an algorithm that, given a parameter $$\gamma >1$$ and a subroutine able to compute $$\rho $$ -approximate best-responses, outputs a $$\gamma (1/p+\rho )$$ -approximate Nash equilibrium, where p is the number of players. The computational complexity of the algorithm heavily depends on the choice of $$\gamma $$ . In particular, when $$\gamma \in O(1)$$ , the complexity is quasi-polynomial, while when $$\gamma \in \varOmega (p^\epsilon )$$ , for a fixed constant $$\epsilon >0$$ , it becomes polynomial. Our algorithm provides the first non-trivial approximability results for this class of games and achieves an almost tight performance for network games in directed graphs. On the negative side, we also show that the problem of computing a Nash equilibrium in Shapley network cost sharing games is PLS-complete even in undirected graphs, where previous hardness results where known only in the directed case.

Placement of regenerators in optical networks has attracted the attention of recent research works in optical networks. In this problem, we are given a network with an underlying topology of a graphGand with a set of requests that correspond to paths inG. There is a need to put a regenerator every certain distance, because of a decrease in the power of the signal. In this paper, we investigate the problem of minimizing the number of locations to place the regenerators. We present analytical results regarding the complexity of this problem, in four cases, depending on whether or not there is a bound on the number of regenerators at each node, and depending on whether or not the routing is given or only the requests are given (and part of the solution is also to determine the actual routing). These results include polynomial time algorithms, NP-completeness results, approximation algorithms, and inapproximability results.

We consider a scheduling problem in which a bounded number of jobs can be processed simultaneously by a single machine. The input is a set of n jobs J = {J1,..., Jn}. Each job, Jj, is associated with an interval [sj, cj] along which it should be processed. Also given is the parallelism parameter g ges 1, which is the maximal number of jobs that can be processed simultaneously by a single machine. Each machine operates along a contiguous time interval, called its busy interval, which contains all the intervals corresponding to the jobs it processes. The goal is to assign the jobs to machines such that the total busy time of the machines is minimized. The problem is known to be NP-hard already for g = 2. We present a 4-approximation algorithm for general instances, and approximation algorithms with improved ratios for instances with bounded lengths, for instances where any two intervals intersect, and for instances where no interval is properly contained in another. Our study has important application in optimizing the switching costs of optical networks.

Placement of regenerators in optical networks has attracted the attention of recent research works in optical networks. In this problem we are given a network, with an underlying topology of a graph G, and with a set of requests that correspond to paths in G. There is a need to put a regenerator every certain distance, because of a decrease in the power of the signal. In this work we investigate the problem of minimizing the number of locations to place the regenerators. We present analytical results regarding the complexity of this problem, in four cases, depending on whether or not there is a bound on the number of regenerators at each node, and depending on whether or not the routing is given or only the requests are given (and part of the solution is also to determine the actual routing). These results include polynomial time algorithms, NP-complete results, approximation algorithms, and inapproximability results.