In this paper, we consider the problem of fair division of indivisible goods, where the allocation of goods impacts society. Specifically, we introduce a second valuation function for each agent, which determines the social impact of allocating a good to the agent. Such impact is considered desirable for the society -- the higher, the better. Our goal is to understand how to allocate goods fairly from the agents' perspective while maintaining society as happy as possible. To this end, we measure the impact on society using the utilitarian social welfare, and provide both possibility and impossibility results. Our findings reveal that achieving good approximations, better than linear in the number of agents, is not possible while ensuring fairness to the agents. These impossibility results can be attributed to the fact that agents are completely unconscious of their social impact. Consequently, we explore scenarios where agents are socially aware, by introducing related fairness notions, and demonstrate that an appropriate definition of fairness is compatible with the social objective.

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.

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

We investigate strategyproof mechanisms in the Group Activity Selection Problem with the additively separable property. Namely, agents have distinct preferences for each activity and individual weights for the other agents. We evaluate our mechanisms in terms of their approximation ratio with respect to the maximum utilitarian social welfare. We first show that, for arbitrary non-negative preferences, no deterministic mechanism can achieve a bounded approximation ratio. Thus, we provide a randomized k-approximate mechanism, where k is the number of activities, and a corresponding 2-2/(k+1) lower bound. Furthermore, we propose a tight (2 - 1/k)-approximate randomized mechanism when activities are copyable. We then turn our attention to instances where preferences can only be unitary, that is 0 or 1. In this case, we provide a k-approximate deterministic mechanism, which we show to be the best possible one within the class of strategyproof and anonymous mechanisms. We also provide a general lower bound of Ω({\sqrt{k}) when anonymity is no longer a constraint. Finally, we focus on unitary preferences and weights, and prove that, while any mechanism returning the optimum is not strategyproof, there exists a 2-approximate deterministic mechanism.

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.

In polymatrix coordination games, each player x is a node of a graph and must select an action in her strategy set. Nodes are playing separate bimatrix games with their neighbors in the graph. Namely, the utility of x is given by the preference she has for her action plus, for each neighbor y, a payoff which strictly depends on the mutual actions played by x and y. We propose the new class of distance polymatrix coordination games, properly generalizing polymatrix coordination games, in which the overall utility of player x further depends on the payoffs arising by mutual actions of players v,z that are the endpoints of edges at any distance h

In this paper we consider Distance Hedonic Games (DHGs), a class of non-transferable utility coalition formation games that properly generalizes previously existing models, like Social Distance Games (SDGs) and unweighted Fractional Hedonic Games (FHGs). In particular, in DHGs we assume the existence of a scoring vector \(\alpha \), in which the i-th coefficient \(\alpha _i\) expresses the extent to which an agent x contributes to the utility of an agent y if they are at distance i. We focus on Nash stable outcomes in the arising games, i.e., on coalition structures in which no agent can unilaterally improve her gain by deviating.We consider two different natural scenarios for the scoring vector, with monotonically increasing and monotonically decreasing coefficients. In both cases we give NP-hardness and inapproximability results on the problems of finding a social optimum and a best Nash stable outcome. Moreover, we characterize the topologies of coalitions that provide high social welfare and consequently give suitable bounds on the Price of Anarchy and on the Price of Stability.

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.

Studies on public transportation in Europe suggest that European inhabitants use buses in ca. 56% of all public transport travels. One of the critical factors affecting such a percentage and more, in general, the demand for public transport services, with an increasing reluctance to use them, is their quality. End-users can perceive quality from various perspectives, including the availability of information, i.e., the access to details about the transit and the provided services. The approach proposed in this paper, using innovative methodologies resorting on data mining and machine learning techniques, aims to make available the unavailable data about public transport. In particular, by mining GPS traces, we manage to reconstruct the complete transit graph of public transport. The approach has been successfully validated on a real dataset collected from the local bus system of the city of L'Aquila (Italy). The experimental results demonstrate that the proposed approach and implemented framework are both effective and efficient, thus being ready for deployment.

We consider a class of coalition formation games that can be succinctly represented by means of hypergraphs and properly generalizes symmetric additively separable hedonic games. More precisely, an instance of hypegraph hedonic game consists of a weighted hypergraph, in which each agent is associated to a distinct node and her utility for being in a given coalition is equal to the sum of the weights of all the hyperedges included in the coalition. We study the performance of stable outcomes in such games, investigating the degradation of their social welfare under two different metrics, the k-Nash price of anarchy and k-core price of anarchy, where k is the maximum size of a deviating coalition. Such prices are defined as the worst-case ratio between the optimal social welfare and the social welfare obtained when the agents reach an outcome satisfying the respective stability criteria. We provide asymptotically tight upper and lower bounds on the values of these metrics for several classes of hypergraph hedonic games, parametrized according to the integer k, the hypergraph arity r and the number of agents n. Furthermore, we show that the problem of computing the exact value of such prices for a given instance is computationally hard, even in case of non-negative hyperedge weights.

We investigate strategyproof mechanisms for Friends and Enemies Games, a subclass of Hedonic Games in which every agent classifies any other one as a friend or as an enemy. In this setting, we consider the two classical scenarios proposed in the literature, called Friends Appreciation (FA) and Enemies Aversion (EA). Roughly speaking, in the former each agent gives priority to the number of friends in her coalition, while in the latter to the number of enemies.We provide strategyproof mechanisms for both settings. More precisely, for FA we first present a deterministic n-approximation mechanism, and then show that a much better result can be accomplished by resorting to randomization. Namely, we provide a randomized mechanism whose expected approximation ratio is 4, and arbitrarily close to 4 with high probability. For EA, we give a simple (1+√2)n-approximation mechanism, and show that its performance is asymptotically tight by proving that it is NP-hard to approximate the optimal solution within O(n1−ɛ) for any fixed ɛ > 0.Finally, we show how to extend our results in the presence of neutrals, i.e., when agents can also be indifferent about other agents, and we discuss anonymity.

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.

The sequential allocation protocol is a simple and popular mechanism to allocate indivisible goods, in which the agents take turns to pick the items according to a predefined sequence. While this protocol is not strategy-proof, it has been recently shown that finding a successful manipulation for an agent is an NP-hard problem [1]. Conversely, it is also known that finding an optimal manipulation can be solved in polynomial time in a few cases: if there are only two agents or if the manipulator has a binary or a lexicographic utility function. In this work, we take a parameterized approach to provide several new complexity results on this manipulation problem. More precisely, we give a complete picture of its parameterized complexity w.r.t. the following three parameters: the number n of agents, the number μ(a1) of times the manipulator a1 picks in the picking sequence, and the maximum range rgmax of an item. This third parameter is a correlation measure on the preference rankings of the agents. In particular, we provide XP algorithms for parameters n and μ(a1), and we show that the problem is fixed-parameter tractable w.r.t. rgmax and n + μ(a1). Interestingly enough, we show that w.r.t. the single parameters n and μ(a1) it is W[1]-hard.

We build upon previous models for differential pricing in social networks and fair price discrimination in markets, considering a setting in which multiple units of a single product must be sold to selected buyers so as to maximize the seller's revenue or the social welfare, while limiting the differences of the prices offered to social neighbors. We first consider the case of general social graph topologies, and provide optimal or nearly-optimal hardness and approximation results for the related optimization problems under various meaningful assumptions, including the inapproximability within any constant factor on the achievable revenue under the unique game conjecture. Then, we focus on topologies that are typical of social networks. Namely, we consider graphs where the node degrees follow a power-law distribution, and show that it is possible to obtain constant or good approximations for the seller's revenue maximization with high probability, thus improving upon the general case.

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.

We consider Social Distance Games (SDGs), that is cluster formation games in which the utility of each agent only depends on the composition of the cluster she belongs to, proportionally to her harmonic centrality, i.e., to the average inverse distance from the other agents in the cluster. Under a non-cooperative perspective, we adopt Nash stable outcomes, in which no agent can improve her utility by unilaterally changing her coalition, as the target solution concept. Although a Nash equilibrium for a SDG can always be computed in polynomial time, we obtain a negative result concerning the game convergence and we prove that computing a Nash equilibrium that maximizes the social welfare is NP-hard by a polynomial time reduction from the NP-complete Restricted Exact Cover by 3-Sets problem. We then focus on the performance of Nash equilibria and provide matching upper bound and lower bounds on the price of anarchy of Θ(n), where n is the number of nodes of the underlying graph. Moreover, we show that there exists a class of SDGs having a lower bound on the price of stability of 6/5 − ε, for any ε > 0. Finally, we characterize the price of stability 5 of SDGs for graphs with girth 4 and girth at least 5, the girth being the length of the shortest cycle in the graph.

Discriminatory pricing policies, even if at first glance can be perceived as unfair, are widespread. In fact, pricing differences for the same item among different national markets are common, or forms of discrimination based on the time of purchase, like in tickets' sales. In this work we propose a framework for capturing the setting of ``fair'' discriminatory pricing and study its application to multi-unit markets, in which many copies of the same item are on sale. Our model is able to incorporate the fundamental discrimination settings proposed in the literature, by expressing individual buyers constraints for assigning prices by means of a social relationship graph, modeling the information that each buyer can acquire about the prices assigned to the other buyers. After pointing out the positive effects of fair price discrimination, we investigate the computational complexity of maximizing the social welfare and the revenue in these markets, providing hardness and approximation results under various assumptions on the buyers valuations and on the social graph topology.

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 consider Social Distance Games (SDGs), that is cluster formation games in which agent utilities are proportional to their harmonic centralities in the respective coalitions, i.e., to the average inverse distance from the other agents. We adopt Nash stable outcomes, that is states in which no agent can improve her utility by unilaterally changing her coalition, as the target solution concept. Although SDGs always admit a Nash equilibrium, we prove that it is NP-hard to find a social welfare maximizing one and obtain a negative result concerning the game convergence. We then focus on the performance of Nash equilibria and provide matching upper bound and lower bounds on the price of anarchy of Θ(n), where n is the number of nodes of the underlying graph, and a lower bound on the price of stability of 6/5 - ε. Finally, we characterize the price of stability of SDGs for graphs with girth 4 and girth at least 5.

We investigate Pareto stability in Social Distance Games, that are coalition forming games in which agents utilities are proportional to their harmonic centralities in the respective coalitions, i.e., to the average inverse distance from the other agents. Pareto optimal solutions have been already considered in the literature as outcomes arising from the strategic interaction of the agents. In particular, they are stable under the deviation of the grand coalition, as they do not permit a simultaneous deviation by all the agents making all of them weakly better off and some strictly better off. We first show that, while computing a Pareto stable solution maximizing the social welfare is NP-hard in bounded degree graphs, a 2 min{Delta,sqrt n}-approximating one can be determined in polynomial time, where n is the number of agents and Delta the maximum node degree. We then determine asymptotically tight bounds on the Price of Pareto Optimality for several classes of social graphs arising from the following combinations: unbounded and bounded node degree, undirected and directed edges, unweighted and weighted edges.

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.

Price of Anarchy measures the welfare loss caused by selfish behavior: it is defined as the ratio of the social welfare in a socially optimal outcome and in a worst Nash equilibrium. A similar measure can be derived for other classes of stable outcomes. In this paper, we argue that Pareto optimality can be seen as a notion of stability, and introduce the concept of Price of Pareto Optimality: this is an analogue of the Price of Anarchy, where the maximum is computed over the class of Pareto optimal outcomes, i.e., outcomes that do not permit a deviation by the grand coalition that makes all players weakly better off and some players strictly better off. As a case study, we focus on hedonic games, and provide lower and upper bounds of the Price of Pareto Optimality in three classes of hedonic games: additively separable hedonic games, fractional hedonic games, and modified fractional hedonic games; for fractional hedonic games on trees our bounds are tight.

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.

In this article we consider multicriteria formulations of classical online problems in which an algorithm must simultaneously perform well with respect to two different cost measures. Every strategy for serving a sequence of requests is characterized by a pair of costs and therefore there can be many different minimal or optimal incomparable solutions. The adversary is assumed to choose from one of these minimal strategies and the performance of the algorithm is measured with respect to the costs the adversary pays servicing the sequence according to its determined choice of strategy. We consider a parametric family of functions which includes all the possible selections for such strategies. Then, starting from a simple general method that combines any multicriteria instance into a single-criterion one, we provide a universal multicriteria algorithm that can be applied to different online problems. In the multicriteria k -server formulation with two different edge weightings, for each function class, such a universal algorithm achieves competitive ratios that are only an O (log W ) multiplicative factor away from the corresponding determined lower bounds, where W is the maximum ratio between the two weights associated to each edge. We then extend our results to two specific functions, for which nearly optimal competitive algorithms are obtained by exploiting more knowledge of the selection properties. Finally, we show how to apply our framework to other multicriteria online problems sharing similar properties.

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

In this paper we extend the technique provided in [M. Flammini and S. Pérennès, Inform. and Comput., to appear] to allow the determination of lower bounds on the broadcasting and gossiping time required by the so-called restricted protocols. Informally, a protocol is {\small $({\cal I}, {\cal O})$}-restricted if at every processor each outgoing activation of an arc depends on at most ${\cal I}$ previous incoming activations and any incoming activation influences at most ${\cal O}$ successive outgoing activations. Examples of restricted protocols are systolic ones and those running on bounded degree networks. Thus, under the basic whispering model, we provide the first general lower bound on the gossiping time of d-bounded degree networks in the directed and half-duplex cases. Moreover, significantly improved broadcasting and gossiping lower bounds are obtained for well-known networks such as butterfly, de Bruijn, and Kautz graphs. All the results are also extended to other communication models such as the c-port and/or postal one.

Abstract We give complete characterizations for the classes of graphs with uniform cost links that admit optimum all shortest paths 1‐SLIRS (strict linear interval routing schemes) and 1‐LIRS (linear interval routing schemes). The characterization of all the interval routing schemes with uniform cost links that represent only a single shortest path is known to be NP‐complete. For any integer k > 0, we also show that the class of graphs with dynamic cost links that admit optimum all shortest paths k‐IRS (SIRS, LIRS, SLIRS) is equivalent to the class of graphs with dynamic cost links that admit an optimum single shortest path k‐IRS (SIRS, LIRS, SLIRS) and also equivalent to the class of graphs with dynamic cost links that admit single paths up to any constant stretch factor k‐IRS (SIRS, LIRS, SLIRS). © 2001 John Wiley & Sons, Inc.

In this paper we show that many general lower bounds on the broadcasting and gossiping time are optimal. In particular, let b(G) be the broadcasting time of a network G under the basic one-port model. The only lower bound on b(G) holding for every n vertices graph G is max$(\log_2 n, Diam(G))$, but the $\log_2 n$ factor cannot be achieved in bounded degree networks. In fact, let the parameter d be defined in undirected graphs as the maximum degree minus one and for directed graphs as the maximum out-degree. Then, in [ SIAM J. Discrete Math., 1 (1998), pp. 531--540; SIAM J. Discrete Math., 5 (1992), pp. 10--24] it has been proved that, for any graph G of parameter d, b(G) \geq \frac{\log_2 n}{\log_2 \xi}$, where $\xi$ is the largest real number such that $\xi^{d} -\xi^{d-1} - \xi^{d-2} -\cdots - \xi-1=0$. Since then many papers have proposed constructions of bounded degree networks having a small broadcast time [Proceedings of the 2nd International Euro-Par Conference (EUROPAR), Lecture Notes in Comput. Sci. 1123, Springer-Verlag, New York, 1996, pp. 313--324; IEEE Trans. Comput., 33 (1984), pp. 190--194], but so far the optimality of [SIAM J. Discrete Math., 1 (1998), pp. 531--540; {SIAM J. Discrete Math.}, 5 (1992), pp. 10--24] was still an open question. In this paper we prove that the above lower bound is tight, improving all the existing upper bounds by means of probabilistic methods. Namely, we show that for n arbitrarily large there exist families of n vertices graphs in which a uniformly drawn graph has broadcasting time as predicted by [SIAM J. Discrete Math., 1 (1998), pp. 531--540; SIAM J. Discrete Math., 5 (1992), pp. 10--24] with probability converging to 1. Moreover, we show that [SIAM J. Discrete Math., 1 (1998), pp. 531--540; SIAM J. Discrete Math., 5 (1992), pp. 10--24] is attained even in the case of gossiping and systolic gossiping in the full-duplex mode. Finally, new upper bounds on bounded-degree and systolic gossiping are also determined in the directed and half-duplex modes. While the systolic construction is tight and matches the lower bound of [Inform and Comput., to appear], we strongly conjecture that the bounded-degree result is optimal and that a corresponding matching lower bound is still to be proven.

In this paper, we provide low-congested interval routing schemes (IRS) for some common interconnection networks such as butterflies, wrapped butterflies, and cube-connected cycles. In particular, by exploiting their hypercubelike structure, we show that 1-IRS and 2-IRS are already sufficient to get schemes with a congestion which is at most c times the optimal one, for low constant values of c. All such schemes have also a small dilation proportional to the diameter. Moreover, a new lower bound on the congestion achievable by schemes for butterfly networks is provided, which improves upon the best previously known one [25]. © 2000 John Wiley & Sons, Inc.

k-Interval labeling schemes (k-ILS) are compact routing schemes on general networks which have been studied extensively and recently been implemented on the latest generation INMOS Transputer Router chips. In this paper, we introduce an extension of the k-ILS to the 〈k,s〉-DFILS (deadlock-free ILS), where k is the number of intervals and s is the number of buffers used at each node or edge to prevent deadlock. Whereas k-ILS only compactly represents shortest paths between pairs of nodes, this new extension aims to represent those particular ones that give rise also to deadlock-free routing controllers which use a low number of buffers per node or per edge. In particular, we consider deadlock-free routing controllers obtained using a standard deadlock prevention technique (acyclic orientation coverings) which can be applied both to packet and wormhole routing. While both time and space complexity results are given for general networks, tight results are shown for specific topologies, such as trees, rings, grids, complete graphs, and chordal rings. Moreover, trade-offs are derived between the number of intervals k and the number of buffers s in 〈k,s〉-DFILS for hypercubes, grids, tori, and Cartesian products of graphs. © 1999 John Wiley & Sons, Inc. Networks 34: 47–60, 1999

Several methods exist for routing messages in a network without using complete routing tables (compact routing). In k-interval routing schemes (k-IRS), links carry up to k intervals each. A message is routed over a certain link if its destination belongs to one of the intervals of the link. We present some results for the necessary value of k in order to achieve shortest-path routing. Even though low values of k suffice for very structured networks, we show that for 'general graphs' interval routing cannot significantly reduce the space requirements for shortest-path routing. In particular we show that for suitably large n, there are suitable values of p such that for randomly chosen graphs G ∈? n,P following holds, with high probability: if G admits an optimal k-IRS, then k = Ω(n 1 - 6/ln(np) - ln(np) / ln n ). The result is obtained by means of a novel matrix representation for the shortest paths in a network.

AU-optical networks promise data transmission rates several orders of magnitudes higher than current networks.The key to high transmission rates in these networks is to maintain the signal in optical form, thereby avoiding the prohibitive overhead of conversion to and from the electrical form, and to exploit the large bandwidth of optical fibers by sending man y signals at different frequencies along the same optical link.OpticaJ technology, however, is not as mature as electronic technology.Hence it is important to understand, how efficiently simple routing elements can be used for alloptical communication.In this paper, we consider two types of routing eIements.Both types can move messages at different wavelengths to different directions.If in the first type a message wants to use an outgoing link that is already occupied by another message using the same wavelength, the arriving message is eliminated (and therefore has to be rerouted).The second type can evaluate priorities of messages.If more than one message wants to use the same wavelength at the same time then the message with highest priority wins.We prove nearly matching upper and lower bounds for the runtime of a simple and efficient protocol for both types of routing elements, and apply our results to meshes, butterflies, and node-symmetric networks.

We show that 2-term DNF formulae are learnable in quadratic time using only a logarithmic number of positive examples if we assume that examples are drawn from a bounded distribution. We also show that k-term DNF formulae are learnable in polynomial time using positive and negative examples drawn from a bounded distribution.