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.

Coalition formation over graphs is a well studied class of games whose players are vertices and feasible coalitions must be connected subgraphs. In this setting, the existence and computation of equilibria, under various notions of stability, has attracted a lot of attention. However, the natural process by which players, starting from any feasible state, strive to reach an equilibrium after a series of unilateral improving deviations, has been less studied. We investigate the convergence of dynamics towards individually stable outcomes under the following perspective: what are the most general classes of preferences and graph topologies guaranteeing convergence? To this aim, on the one hand, we cover a hierarchy of preferences, ranging from the most general to a subcase of additively separable preferences, including individually rational and monotone cases. On the other hand, given that convergence may fail in graphs admitting a cycle even in our most restrictive preference class, we analyze acyclic graph topologies such as trees, paths, and stars.

Many allocation and matching problems (e.g., student-school assignments, job allocation, organ donation) involve coupling agents based on mutual preferences. A central requirement in matching problems is that of stability, that is classically defined as follows: a matching is stable if no blocking pair exists, where a blocking pair is a pair of agents preferring each other over their assigned partners. We assume that matchings are constrained by a given undirected acceptability graph: two agents may be matched only if they are connected by an edge. While stable matchings are guaranteed for specific graph topologies, such as bipartite graphs, stability is not always achievable in more general scenarios. In this paper, we introduce a relaxed notion of stability, yielding to the study of approximately stable matching. Specifically, we define a matching as approximately stable if there exists no k-blocking pair, i.e., no pair of agents who could both improve their assigned partners by at least k positions in their respective preference rankings, by forming a new match together. This refinement captures the idea that small agent gains may not justify a deviation. We provide some theoretical results about the existence and computability of approximately stable matchings, revealing their strengths as well as their inherent limitations. We believe that the introduced notion of approximate stability, along with our foundational findings, constitute a solid basis for future research on matching problems.

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.

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.

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.

Motivated by possible applications in fault-tolerant routing, we introduce the notion of uniform mixed equilibria in network congestion games with adversarial link failures, where players need to route traffic from a source to a destination node. Given an integer rho >= 1, a rho-uniform mixed strategy is a mixed strategy in which a player plays exactly rho edge disjoint paths with uniform probabilities, so that a rho-uniform mixed equilibrium is a tuple of rho-uniform mixed strategies, one for each player, in which no player can lower her cost by deviating to another rho-uniform mixed strategy. For games with weighted players and affine latency functions, we show existence of rho-uniform mixed equilibria and provide a tight characterization of their price of anarchy. For games with unweighted players, instead, we extend the existential guarantee to any class of latency functions and, restricted to games with affine latencies, we derive a tight characterization of both the prices of anarchy and stability.

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 investigate the issues of existence and efficiency of lookahead equilibria in congestion games. Lookahead equilibria, whose study has been initiated by Mirrokniet al.(2012), correspond to the natural extension of pure Nash equilibria in which the players, when making use of global information in order to predict subsequent reactions of the other ones, have computationally limited capabilities.

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.

We consider broadcast network design games in undirected networks in which every player is a node wishing to receive communication from a distinguished source node s and the cost of each communication link is equally shared among the downstream receivers according to the Shapley value. We prove that the Price of Stability of such games is constant, thus closing a long-standing open problem raised in [2]. Our result is obtained by means of homogenization, a new technique that, in any intermediate state locally diverging from a given optimal solution T*, is able to restore local similarity by exploiting cost differences between nearby players in T*.

We present a new approximation algorithm for the Minimum Energy Broadcast Routing (MEBR) problem in ad hoc wireless networks that achieves an exponentially better approximation factor compared to the well-known Minimum Spanning Tree (MST) heuristic. Namely, for any instance where a minimum spanning tree of the set of stations is guaranteed to cost at most ρ ≥ 2 times the cost of an optimal solution for MEBR, we prove that our algorithm achieves an approximation ratio bounded by 2lnρ-2 ln 2 + 2. This result is particularly relevant for its consequences on Euclidean instances where we significantly improve previous results. In this respect, our experimental analysis confirms the better performance of the algorithm also in practice.

We investigate the speed of convergence of best response dynamics to approximately optimal solutions in congestion games with linear delay functions. In Ackermann et al. [2008] it has been shown that the convergence time of such dynamics to Nash equilibrium may be exponential in the number of playersn. Motivated by such a negative result, we focus on the study of the states (not necessarily being equilibria) reached after a limited number of players' selfish moves, and we show that Θ(nlog logn) best responses are necessary and sufficient to achieve states that approximate the optimal solution by a constant factor, under the assumption that everyO(n) steps each player performs a constant (and nonnull) number of best responses. We show that such result is tight also for the simplest case of singleton congestion games.

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.

We introduce a new general framework for the analysis of non cooperative games with limited social knowledge. Such an incomplete knowledge is modeled by means of a social graph G in which nodes represent players and there is an edge from i to j if i knows j, with the assumption that the payoff of each player is affected only by the strategies of the adjacent ones. In particular, we consider congestion games with linear latency functions in which each player is aware only of a subset of all the other ones. We first give a complete characterization of the games possessing pure Nash equilibria, and then investigate the impact of the limited knowledge of the players on the performance of the game, in terms of price of anarchy and price of stability.

We investigate the convergence of the price of anarchy after a limited number of moves in the classical multicast communication game when the underlying communication networks is directed. Namely, a subset of nodes of the network are interested in receiving the transmission from a given source node and can share the cost of the used links according to fixed cost sharing methods. At each step, a single receiver is allowed to modify its communication strategy, that is to select a communication path from the source, and assuming a sel?sh or rational behavior, it will make a best response move, that is it will select a solution yielding the minimum possible payment or shared cost. We determine lower and upper bounds on the price of anarchy,that is the highest possible ratio among the overall cost of the links used by the receivers and the minimum possible cost realizing the required communications, after a limited number of moves under the fundamental Shapley cost sharing method. In particular, assuming that the initial set of connecting paths can be arbitrary, we show an O(r√r) upper bound on the price of anarchy after 2 rounds, during each of which all the receivers move exactly once, and a matching lower bound, that we also extend to Ω(rk√r)for any number k =≥ 2 rounds, where r is the number of receivers. Similarly, exactly matching upper and lower bounds equal to r are determined for any number of rounds when starting from the empty state in which no path has been selected. Analogous results are obtained also with respect to other three natural cost sharing methods considered in the literature, that is the egalitarian, path-proportional and egalitarian-path proportional ones. Most results are also extended to the undirected case in which the communication links are bidirectional.

Summary form only given. We consider the bicriteria version of the classical Graham's scheduling problem in which two cost measures must be simultaneously minimized. We present a parametric family of online algorithms /spl Fscr//sub m/= {A/sub k/|1/spl les/k/spl les/m} such that, for each fixed integer k, A/sub k/ is (2m-k/m-k+1,m+k-1/k)-competitive. Then we prove that, for m=2 and m=3, the tradeoffs-on the competitive ratios realized by the algorithms in /spl Fscr//sub m/ correspond to the Pareto curve, that is they are all and only the optimal ones, while for m > 3 they give an r-approximation of the Pareto curve with r=5/4 for m=4, r=6/5 for m=5, r=1.186 for m=6 and so forth, with r always less than 1.295. Unfortunately, for m > 3, obtaining Pareto curves is not trivial, as they would yield optimal algorithms for the single criterion case in correspondence of the extremal tradeoffs. However, the situation seems more promising for the intermediate cases. In fact, we prove that for 5 processors the tradeoff(7/3,7/3) of A/sub 3//spl epsi/ /spl Fscr//sub 5/is optimal. Finally, we extend our results to the general d-dimensional case with corresponding applications to the vector scheduling problem.