We revisit the setting of fair allocation of indivisible items among agents with heterogeneous, non-monotone valuations. We explore the existence and efficient computation of allocations that approximately satisfy either envy-freeness or equity constraints. Approximate envy-freeness ensures that each agent values her bundle at least as much as those given to the others, after some (or any) item removal, while approximate equity guarantees roughly equal valuations among agents, under similar adjustments. As a key technical contribution of this work, by leveraging fixed-point theorems (such as Sperner's Lemma and its variants), we establish the existence of envy-free-up-to-one-good-and-one-chore (EF1_g^c) and equitable-up-to-one-good-and-one-chore (EQ1_g^c) allocations, for non-monotone valuations that are always either non-negative or non-positive. These notions represent slight relaxations of the well-studied envy-free-up-to-one-item (EF1) and equitable-up-to-one-item (EQ1) guarantees, respectively. Our existential results hold even when items are arranged in a path and bundles must form connected sub-paths. The case of non-positive valuations, in particular, has been solved by proving a novel multi-coloring variant of Sperner's Lemma that constitutes a combinatorial result of independent interest. In addition, we also design a polynomial-time dynamic programming algorithm that computes an EQ1_g^c allocation. For monotone non-increasing valuations and path-connected bundles, all the above results can be extended to EF1 and EQ1 guarantees as well. Finally, we provide existential and computational results for certain stronger up-to-any-item equity notions under objective valuations, where items are partitioned into goods and chores.

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.

In this work, we consider the problem of improving the efficiency of utility-sharing games, by resorting to a limited amount of subsidies. Utility-sharing games model scenarios in which strategic and self-interested players interact with each other by selecting resources. Each resource produces a utility that depends on the number of players selecting it, as a non-negative, non-decreasing and concave function, and each of these players receives an equal share of this utility. As the players’ selfish behavior may lead to pure Nash equilibria whose total utility is sub-optimal, previous work has resorted to subsidies, incentivizing the use of some resources, to contrast this phenomenon. We focus on the case in which the budget used to provide subsidies is bounded. We consider a class of mechanisms, called α -subsidy mechanisms, that allocate the budget in such a way that each player’s payoff is re-scaled up to a factor α ≥ 1. We design a specific sub-class of α -subsidy mechanisms, that can be implemented efficiently and distributedly by each resource, and evaluate their efficiency by providing upper bounds on their price of anarchy. These bounds are parametrized by both α and the underlying utility functions and are shown to be best-possible for α -subsidy mechanisms. Finally, we apply our results to the particular case of monomial utility functions of degree p ∈ (0, 1), and derive bounds on the price of anarchy that are parametrized by p and α .

Respiratory diseases are among the leading causes of morbidity worldwide, making timely and accurate diagnosis essential. However, interpreting chest X-rays is challenging due to the variability of pathological manifestations and the subjectivity of human analysis. In this study, we propose a multimodal approach that integrates automated image analysis with textual clinical data, leveraging a Visual Question Answering (VQA)based architecture and a text generation model for diagnostic report production. The use of Grad-CAM enhances the interpretability of the system by highlighting the most relevant image regions for diagnosis. The model was trained on a balanced dataset obtained by merging three sources-Lung X-ray Data, NIH Chest X-rays, and Chest X-Ray Images-ensuring fair classification across Normal and Pneumonia categories. The pipeline includes visual feature extraction using a Vision Transformer (ViT), automatic pathology classification, and diagnostic report generation with an advanced language model. Results indicate a significant improvement in diagnostic accuracy compared to traditional methods, supported by key performance metrics such as accuracy 95.3%, sensitivity, specificity, and F1-score. Furthermore, integrating the system into an interactive web app facilitates clinical adoption, enhancing diagnostic efficiency and supporting personalized management of pulmonary diseases.

We study the performance of mildly greedy players in k-coloring games, a relevant subclass of anti-coordination games. A mildly greedy player is a selfish agent who is willing to deviate from a certain strategy profile only if her payoff improves by a factor of more than ε, for some given ε ≥ 0. In presence of mildly greedy players, stability is captured by the concept of (1+ε)-approximate Nash equilibrium. In this paper, we first show that, for any k-coloring game, the (1+ε)-approximate price of anarchy, i.e., the price of anarchy of (1+ε)-approximate pure Nash equilibria, is at least (k-1)/((k-1)ε +k), and that this bound is tight for any ε ≥ 0. Then, we evaluate the approximation ratio of the solutions achieved after a (1 + ε)-approximate one-round walk starting from any initial strategy profile, where a (1 + ε)-approximate one-round walk is a sequence of (1 + ε)-approximate best-responses, one for each player. We provide a lower bound of min{(k-2)/k, (k-1)/((k-1)ε+k)} on this ratio, for any ε ≥ 0 and k ≥ 5; for the cases of k = 3 and k = 4, we give finer bounds depending on ε. Our work generalizes the results known for cut games, the special case of k-coloring games restricted to k = 2.

We study a hedonic game for which feasible coalitions are prescribed by a graph representing the agents’ social relations. A group of agents can form a feasible coalition if and only if their corresponding vertices can be spanned with a star. This requirement guarantees that agents are connected, close to each other, and one central agent can coordinate the actions of the group. In our game, everyone strives to join the largest feasible coalition. We study the existence and computational complexity of both Nash stable and core stable partitions. Then, we provide tight or asymptotically tight bounds on their efficiency, measured in terms of the price of anarchy and the price of stability, under two natural social functions, namely, the number of agents who are not in a singleton coalition, and the number of coalitions. We also derive refined bounds for games in which the social graph is claw-free. Finally, we investigate the complexity of computing socially optimal partitions, as well as extreme Nash stable ones.

We address the problem of improving the worst-case efficiency of pure Nash equilibria (aka, the price of anarchy) in affine congestion games, through a novel use of signalling. We assume that, for each player in the game, a most preferred strategy is publicly signalled. This can be done either distributedly by the players themselves, or be the outcome of some centralized algorithm. We apply this signalling scheme to two well-studied scenarios: games with partially altruistic players and games with resource taxation. We show a significant improvement in the price of anarchy of these games, whenever the aggregate signalled strategy profile is a good approximation of the game social optimum.

In most major cities and urban areas, residents form homogeneous neighborhoods along ethnic or socioeconomic lines. This phenomenon is widely known as residential segregation and has been studied extensively. Fifty years ago, Schelling proposed a landmark model that explains residential segregation in an elegant agent-based way. A recent stream of papers analyzed Schelling's model using game-theoretic approaches. However, all these works considered models with a given number of discrete types modeling different ethnic groups. We focus on segregation caused by non-categorical attributes, such as household income or position in a political left-right spectrum. For this, we consider agent types that can be represented as real numbers. This opens up a great variety of reasonable models and, as a proof of concept, we focus on several natural candidates. In particular, we consider agents that evaluate their location by the average type-difference or the maximum type-difference to their neighbors, or by having a certain tolerance range for type-values of neighboring agents.We study the existence and computation of equilibria and provide bounds on the Price of Anarchy and Stability. Also, we present simulation results that compare our models and shed light on the obtained equilibria for our variants.

We reconsider atomic and non-atomic affine congestion games under the assumption that players are partitioned into p priority classes and resources schedule their users according to a priority-based policy, breaking ties uniformly at random. We derive tight bounds on both the price of anarchy and the price of stability as a function of p, revealing an interesting separation between the general case of p≥2 and the priority-free scenario of p=1. In fact, while in absence of priorities the worst-case prices of anarchy and stability of non-atomic games are lower than their counterparts in atomic ones, the two classes share the same bounds when p≥2. Moreover, while the worst-case price of stability is lower than the worst-case price of anarchy in atomic games with no priorities, their values become equal when p≥2. Said differently, the presence of priorities simultaneously irons out any combinatorial difference between atomic and non-atomic requests and among different pure Nash equilibria to produce a unique representative worst-case situation. Notably, our results keep holding even under singleton strategies. Besides being of independent interest, priority-based scheduling shares tight connections with online load balancing and finds a natural application within the theory of coordination mechanisms and cost-sharing policies for congestion games. Under this perspective, a number of possible research directions also arise.

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.

Residential segregation in metropolitan areas is a phenomenon that can be observed all over the world. Recently, this was investigated via game-theoretic models. There, selfish agents of two types are equipped with a monotone utility function that ensures higher utility if an agent has more same-type neighbors. The agents strategically choose their location on a given graph that serves as residential area to maximize their utility. However, sociological polls suggest that real-world agents are actually favoring mixed-type neighborhoods, and hence should be modeled via non-monotone utility functions. To address this, we study Swap Schelling Games with single-peaked utility functions. Our main finding is that tolerance, i.e., agents favoring fifty-fifty neighborhoods or being in the minority, is necessary for equilibrium existence on almost regular or bipartite graphs. Regarding the quality of equilibria, we derive (almost) tight bounds on the Price of Anarchy and the Price of Stability. In particular, we show that the latter is constant on bipartite and almost regular graphs.

Modeling how agents form their opinions is of paramount importance for designing marketing and electoral campaigns. In this work, we present a new framework for opinion formation which generalizes the well-known Friedkin-Johnsen model by incorporating three important features: (i) social group membership, that limits the amount of influence that people not belonging to the same group may lead on a given agent; (ii) both attraction among friends, and repulsion among enemies; (iii) different strengths of influence lead from different people on a given agent, even if the social relationships among them are the same. We show that, despite its generality, our model always admits a pure Nash equilibrium which, under opportune mild conditions, is even unique. Next, we analyze the performances of these equilibria with respect to a social objective function defined as a convex combination, parametrized by a value λ∈[0,1], of the costs yielded by the untruthfulness of the declared opinions and the total cost of social pressure. We prove bounds on both the price of anarchy and the price of stability which show that, for not-too-extreme values of λ, performance at equilibrium are very close to optimal ones. For instance, in several interesting scenarios, the prices of anarchy and stability are both equal to max{2λ,1-λ}/min{2λ,1-λ} which never exceeds 2 for λ∈[1/5,1/2].

Abstract Residential segregation is a wide-spread phenomenon that can be observed in almost every major city. In these urban areas residents with different racial or socioeconomic background tend to form homogeneous clusters. Schelling’s famous agent-based model for residential segregation explains how such clusters can form even if all agents are tolerant, i.e., if they agree to live in mixed neighborhoods. For segregation to occur, all it needs is a slight bias towards agents preferring similar neighbors. Very recently, Schelling’s model has been investigated from a game-theoretic point of view with selfish agents that strategically select their residential location. In these games, agents can improve on their current location by performing a location swap with another agent who is willing to swap. We significantly deepen these investigations by studying the influence of the underlying topology modeling the residential area on the existence of equilibria, the Price of Anarchy and on the dynamic properties of the resulting strategic multi-agent system. Moreover, as a new conceptual contribution, we also consider the influence of locality, i.e., if the location swaps are restricted to swaps of neighboring agents. We give improved almost tight bounds on the Price of Anarchy for arbitrary underlying graphs and we present (almost) tight bounds for regular graphs, paths and cycles. Moreover, we give almost tight bounds for grids, which are commonly used in empirical studies. For grids we also show that locality has a severe impact on the game dynamics.

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.

We propose and analyse a game describing the interactions between readers and publishers, with the aim of understanding to what extent the strategic behaviour of the latter may influence the quality of content publishing in the World Wide Web. For games with identical publishers, we provide a wide characterization of the cases in which pure Nash equilibria are guaranteed to exist, which mainly depends on the number of publishers and, subordinately, on some of the parameters we use to model their writing abilities. Then, for any game possessing pure Nash equilibria, we show that the price of anarchy is at most 2, even in presence of heterogeneous publishers. Finally, we provide better and tight bounds for some special cases of games with identical publishers.

Residential segregation is a wide-spread phenomenon that can be observed in almost every major city. In these urban areas residents with different racial or socioeconomic background tend to form homogeneous clusters. Schelling’s famous agent-based model for residential segregation explains how such clusters can form even if all agents are tolerant, i.e., if they agree to live in mixed neighborhoods. For segregation to occur, all it needs is a slight bias towards agents preferring similar neighbors. Very recently, Schelling’s model has been investigated from a game-theoretic point of view with selfish agents that strategically select their residential location. In these games, agents can improve on their current location by performing a location swap with another agent who is willing to swap. We significantly deepen these investigations by studying the influence of the underlying topology modeling the residential area on the existence of equilibria, the Price of Anarchy and on the dynamic properties of the resulting strategic multi-agent system. Moreover, as a new conceptual contribution, we also consider the influence of locality, i.e., if the location swaps are restricted to swaps of neighboring agents. We give improved almost tight bounds on the Price of Anarchy for arbitrary underlying graphs and we present (almost) tight bounds for regular graphs, paths and cycles. Moreover, we give almost tight bounds for grids, which are commonly used in empirical studies. For grids we also show that locality has a severe impact on the game dynamics.

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.

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.

To what extent does the structure of the players' strategy space influence the efficiency of decentralized solutions in congestion games? In this work, we investigate whether better performance are possible when restricting to load balancing games in which players can only choose among single resources. We consider three different solutions concepts, namely, approximate pure Nash equilibria, approximate one-round walks generated by selfish players aiming at minimizing their personal cost and approximate one-round walks generated by cooperative players aiming at minimizing the marginal increase in the sum of the players' personal costs. The last two concepts can be interpreted as solutions of greedy online algorithms for the related resource selection problem. We show that, under fairly general latency functions on the resources, better bounds cannot be achieved if players are either weighted or asymmetric. On the positive side, we prove that, under mild assumptions on the latency functions, improvements on the performance of approximate pure Nash equilibria are possible for load balancing games with weighted and symmetric players in the case of identical resources. We also design lower bounds on the performance of one-round walks in load balancing games with unweighted players and identical resources.

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 study the complexity of decision problems about symmetric Nash equilibria for symmetric multi-player games. These decision problems concern the existence of a symmetric Nash equilibrium with certain natural properties. We show that a handful of such decision problems are Existential-R-complete; that is, they are exactly as hard as deciding the Existential Theory of the Reals.

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 efficiency of taxation in congestion games with polynomial latency functions along the line of research initiated by [Caragiannis et al., ACM Transactions on Algorithms, 2010] who focused on both pure and mixed Nash equilibria in games with affine latencies only. By exploiting the primal-dual method [Bilo, Proceedings of the 10th Workshop on Approximation and Online Algorithms, 2012], we obtain interesting upper bounds with respect to a variety of different solution concepts ranging from approximate pure Nash equilibria up to approximate coarse correlated equilibria, and including also approximate one-round walks starting from the empty state. Our findings show a high beneficial effect of taxation which increases more than linearly with the degree of the latency functions. In some cases, a tight relationship with some well-studied polynomials in Combinatorics and Number Theory, such as the Touchard and the Geometric polynomials, arises. In these cases we can also show matching lower bounds, albeit under mild assumptions; interestingly, our upper bounds are derived by exploiting the combinatorial definition of these polynomials, while our lower bounds are constructed by relying on their analytical characterization.

[Schaefer and Stefankovic, Theory of Computing Systems, 2015] provided an explicit formulation of EXISTS-R as the class capturing the complexity of deciding the Existential Theory of the Reals, and established that deciding, given a 3-player game, whether or not it has a Nash equilibrium with no probability exceeding a given rational is EXISTS-R-complete. Four more decision problems about Nash equilibria for 3-player games were very recently shown EXISTS-R-complete via a chain of individual, problem-specific reductions in [Garg et al., Proceedings of ICALP 2015]; determining more such EXISTS-R-complete problems was posed there as an open problem. In this work, we deliver an extensive catalog of EXISTS-R-complete decision problems about Nash equilibria in 3-player games, thus resolving completely the open problem from [Garg et al., Proceedings of ICALP 2015]. Towards this end, we present a single and very simple, unifying reduction from the EXISTS-R-complete decision problem from [Schaefer and Stefankovic, Theory of Computing Systems, 2015] to (almost) all the decision problems about Nash equilibria that were before shown NP-complete for 2-player games in [Bilo and Mavronicolas, Proceedings of SAGT 2012; Conitzer and Sandholm, Games and Economic Behavior, 2008; Gilboa and Zemel, Games and Economic Behavior, 1989]. Encompassed in the catalog are the four decision problems shown EXISTS-R-complete in [Garg et al., Proceedings of ICALP 2015].

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 investigate the efficiency of some Stackelberg strategies in congestion games with affine latency functions. A Stackelberg strategy is an algorithm that chooses a subset of players and assigns them a prescribed strategy with the purpose of mitigating the detrimental effect that the selfish behavior of the remaining uncoordinated players may cause to the overall performance of the system. The efficiency of a Stackelberg strategy is measured in terms of the price of anarchy of the pure Nash equilibria they induce. Three Stackelberg strategies, namely Largest Latency First , Cover and Scale , were already considered in the literature and non-tight upper and lower bounds on their price of anarchy were given. We reconsider these strategies and provide the exact bound on the price of anarchy of both Largest Latency First and Cover and a better upper bound on the price of anarchy of Scale .

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 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.

In the non cooperative version of the classical minimum bin packing problem, an item is charged a cost according to the percentage of the used bin space it requires. We study the game induced by the selfish behavior of the items which are interested in being packed in one of the bins so as to minimize their cost. We prove that such a game always converges to a pure Nash equilibrium starting from any initial packing of the items, estimate the number of steps needed to reach one such equilibrium, prove the hardness of computing good equilibria and give an upper and a lower bound for the price of anarchy of the game. Then, we consider a multidimensional extension of the problem in which each item can require to be packed in more than just one bin. Unfortunately, we show that in such a case the induced game may not admit a pure Nash equilibrium even under particular restrictions. The study of these games finds applications in the analysis of the bandwidth cost sharing problem in non cooperative networks

Summary form only given. The continuous growth of the routing tables sizes in backbone routers is one of the most compelling scaling problems affecting the Internet. Beside the deriving waste of memory, the main problem posed by this phenomena is a general increase of the tables lookup time during the routing of the IP datagrams. Thus, a considerable research effort has been devoted in the design of algorithms for fast lookups and for compressing existing tables. However, the envisaged close enhancement of the current version of the IP protocol to IPv6 and the introduction of the so called network address translators (NATs) urgently require the solution of the IP routing tables minimization problem in a new and more effective way, that is by performing addresses reassignments. In such a setting, we first give an algorithm with an asymptotically optimal running time that assigns addresses so as to minimize the size of a single routing table. We then show that minimizing the sum of the sizes of n routing tables is an intractable problem, i.e. NP-hard, and present a 3h-approximation algorithm, where h is the length of the IP addresses.

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.

In this paper we consider the problem of sharing the costs of multicast transmissions in ad hoc wireless networks. Assuming that the receiving users are selfish, we provide strategy- proof mechanisms that are either optimally budget balanced or efficient for the case in which the distance-power gradient α =1 or the stations belong to a ne-dimensional Euclidean space.Then, by extending to multicasting previous results on wireless broadcasting,we show the existence of efficiently computable 2(3 d.1)-approximate budget balance mechanisms in any d -dimensional space for every α ≥ d.