Coordination mechanisms for selfish scheduling

In machine scheduling, a set of jobs must be scheduled on a set of machines so as to minimize some global objective function, such as the makespan, which we consider in this paper. In practice, jobs are often controlled by independent, selfishly acting agents, which each select a machine for processing that minimizes the (expected) completion time. This scenario can be formalized as a game in which the players are job owners, the strategies are machines, and a player’s disutility is the completion time of its jobs in the corresponding schedule. The equilibria of these games may result in larger-than-optimal overall makespan. The price of anarchy is the ratio of the worst-case equilibrium makespan to the optimal makespan. In this paper, we design and analyze scheduling policies, or coordination mechanisms, for machines which aim to minimize the price of anarchy of the corresponding game. We study coordination mechanisms for four classes of multiprocessor machine scheduling problems and derive upper and lower bounds on the price of anarchy of these mechanisms. For several of the proposed mechanisms, we also prove that the system converges to a pure-strategy Nash equilibrium in a linear number of rounds. Finally, we note that our results are applicable to several practical problems arising in communication networks.     

On the Performance of Approximate Equilibria in Congestion Games

We study the performance of approximate Nash equilibria for congestion games with polynomial latency functions. We consider how much the price of anarchy worsens and how much the price of stability improves as a function of the approximation factor ε. We give tight bounds for the price of anarchy of atomic and non-atomic congestion games and for the price of stability of non-atomic congestion games. For the price of stability of atomic congestion games we give non-tight bounds for linear latencies. Our results not only encompass and generalize the existing results of exact equilibria to ε-Nash equilibria, but they also provide a unified approach which reveals the common threads of the atomic and non-atomic price of anarchy results. By expanding the spectrum, we also cast the existing results in a new light.     

Stackelberg Strategies and Collusion in Network Games with Splittable Flow

We study the impact of collusion in network games with splittable flow and focus on the well established price of anarchy as a measure of this impact. We first investigate symmetric load balancing games and show that the price of anarchy is at most m, where m denotes the number of coalitions. For general networks, we present an instance showing that the price of anarchy is unbounded, even in the case of two coalitions. If latencies are restricted to polynomials with nonnegative coefficients and bounded degree, we prove upper bounds on the price of anarchy for general networks, which improve upon the current best ones except for affine latencies.     

Local and global price of anarchy of graphical games

This paper initiates a study of connections between local and global properties of graphical games. Specifically, we introduce a concept of local price of anarchy that quantifies how well subsets of agents respond to their environments. We then show several methods of bounding the global price of anarchy of a game in terms of the local price of anarchy. All our bounds are essentially tight.     

Contribution Games in Networks

We consider network contribution games, where each agent in a network has a budget of effort that he can contribute to different collaborative projects or relationships. Depending on the contribution of the involved agents a relationship will flourish or drown, and to measure the success we use a reward function for each relationship. Every agent is trying to maximize the reward from all relationships that it is involved in. We consider pairwise equilibria of this game, and characterize the existence, computational complexity, and quality of equilibrium based on the types of reward functions involved. When all reward functions are concave, we prove that the price of anarchy is at most?2. For convex functions the same only holds under some special but very natural conditions. Another special case extensively treated are minimum effort games, where the reward of a relationship depends only on the minimum effort of any of the participants. In these games, we can show existence of pairwise equilibrium and a price of anarchy of 2 for concave functions and special classes of games with convex functions. Finally, we show tight bounds for approximate equilibria and convergence of dynamics in these games.     

Efficient Coordination Mechanisms for Unrelated Machine Scheduling

We present three new coordination mechanisms for scheduling n selfish jobs on m unrelated machines. A coordination mechanism aims to mitigate the impact of selfishness of jobs on the efficiency of schedules by defining a local scheduling policy on each machine. The scheduling policies induce a game among the jobs and each job prefers to be scheduled on a machine so that its completion time is minimum given the assignments of the other jobs. We consider the maximum completion time among all jobs as the measure of the efficiency of schedules. The approximation ratio of a coordination mechanism quantifies the efficiency of pure Nash equilibria (price of anarchy) of the induced game. Our mechanisms are deterministic, local, and preemptive in the sense that the scheduling policy does not necessarily process the jobs in an uninterrupted way and may introduce some idle time. Our first coordination mechanism has approximation ratio Θ(logm) and always guarantees that the induced game has pure Nash equilibria to which the system converges in at most n rounds. This result improves a bound of O(log² m) due to Azar, Jain, and Mirrokni and, similarly to their mechanism, our mechanism uses a global ordering of the jobs according to their distinct IDs. Next we study the intriguing scenario where jobs are anonymous, i.e., they have no IDs. In this case, coordination mechanisms can only distinguish between jobs that have different load characteristics. Our second mechanism handles anonymous jobs and has approximation ratio $O(\frac{\log m}{\log\log m})$ although the game induced is not a potential game and, hence, the existence of pure Nash equilibria is not guaranteed by potential function arguments. However, it provides evidence that the known lower bounds for non-preemptive coordination mechanisms could be beaten using preemptive scheduling policies. Our third coordination mechanism also handles anonymous jobs and has a nice “cost-revealing” potential function. We use this potential function in order, not only to prove the existence of equilibria, but also to upper-bound the price of stability of the induced game by O(logm) and the price of anarchy by O(log² m). Our third coordination mechanism is the first that handles anonymous jobs and simultaneously guarantees that the induced game is a potential game and has bounded price of anarchy. In order to obtain the above bounds, our coordination mechanisms use m as a parameter. Slight variations of these mechanisms in which this information is not necessary achieve approximation ratios of O(m ^? ), for any constant ?>0.     

Coordination mechanisms

We introduce the notion of coordination mechanisms to improve the performance in systems with independent selfish and non-colluding agents. The quality of a coordination mechanism is measured by its price of anarchy—the worst-case performance of a Nash equilibrium over the (centrally controlled) social optimum. We give upper and lower bounds for the price of anarchy for selfish task allocation and congestion games.     

Nonpreemptive Coordination Mechanisms for Identical Machines

We focus on the problem of scheduling n weighted selfish tasks on m identical parallel machines and we study the performance of nonpreemptive coordination mechanisms. A nonpreemptive coordination mechanism consists of m local scheduling policies that decide the processing order of the tasks on each machine without delays or interruptions. We discuss the existence of Nash equilibria for this setting and show that it is not a guaranteed property of all nonpreemptive coordination mechanisms. Next, we focus on the wider class of randomized Nash equilibria and prove lower bounds on the price of anarchy. Our lower bounds are presented in comparison to the currently best known coordination mechanism (which uses delays) and lead to the conclusion that preemption or delays are required in order to improve on the currently best known solution.     

On Equilibria for ADM Minimization Games

In the ADM minimization problem the input is a set of arcs along a directed ring. The input arcs need to be partitioned into non-overlapping chains and cycles so as to minimize the total number of endpoints, where a k-arc cycle contributes k endpoints and a k-arc chain contains k+1 endpoints. We study ADM minimization problem both as non-cooperative and cooperative games. In these games each arc corresponds to a player, and the players share the cost of the ADM switches. We consider two cost allocation models, a model which was considered by Flammini et al., and a new cost allocation model, which is inspired by congestion games. We compare the price of anarchy and price of stability in the two cost allocation models, as well as the strong price of anarchy and the strong price of stability.     

On robust online scheduling algorithms

While standard parallel machine scheduling is concerned with good assignments of jobs to machines, we aim to understand how the quality of an assignment is affected if the jobs’ processing times are perturbed and therefore turn out to be longer (or shorter) than declared. We focus on online scheduling with perturbations occurring at any time, such as in railway systems when trains are late. For a variety of conditions on the severity of perturbations, we present bounds on the worst case ratio of two makespans. For the first makespan, we let the online algorithm assign jobs to machines, based on the non-perturbed processing times. We compute the makespan by replacing each job’s processing time with its perturbed version while still sticking to the computed assignment. The second is an optimal offline solution for the perturbed processing times. The deviation of this ratio from the competitive ratio of the online algorithm tells us about the “price of perturbations”. We analyze this setting for Graham’s algorithm, and among other bounds show a competitive ratio of 2 for perturbations decreasing the processing time of a job arbitrarily, and a competitive ratio of less than 2.5 for perturbations doubling the processing time of a job. We complement these results by providing lower bounds for any online algorithm in this setting. Finally, we propose a risk-aware online algorithm tailored for the possible bounded increase of the processing time of one job, and we show that this algorithm can be worse than Graham’s algorithm in some cases.     

On spectrum sharing games

Efficient spectrum-sharing mechanisms are crucial to alleviate the bandwidth limitation in wireless networks. In this paper, we consider the following question: can free spectrum be shared efficiently? We study this problem in the context of 802.11 or WiFi networks. Each access point (AP) in a WiFi network must be assigned a channel for it to service users. There are only finitely many possible channels that can be assigned. Moreover, neighboring access points must use different channels so as to avoid interference. Currently these channels are assigned by administrators who carefully consider channel conflicts and network loads. Channel conflicts among APs operated by different entities are currently resolved in an ad hoc manner (i.e., not in a coordinated way) or not resolved at all. We view the channel assignment problem as a game, where the players are the service providers and APs are acquired sequentially. We consider the price of anarchy of this game, which is the ratio between the total coverage of the APs in the worst Nash equilibrium of the game and what the total coverage of the APs would be if the channel assignment were done optimally by a central authority. We provide bounds on the price of anarchy depending on assumptions on the underlying network and the type of bargaining allowed between service providers. The key tool in the analysis is the identification of the Nash equilibria with the solutions to a maximal coloring problem in an appropriate graph. We relate the price of anarchy of these games to the approximation factor of local optimization algorithms for the maximum k-colorable subgraph problem. We also study the speed of convergence in these games.     

Approximation for scheduling on uniform nonsimultaneous parallel machines

We consider the problem of scheduling on uniform machines which may not start processing at the same time with the purpose of minimizing the maximum completion time. We propose using a variant of the MULTIFIT algorithm, LMULTIFIT, which generates schedules which end within 1.382 times the optimal maximum completion time for the general problem, and within \(\sqrt{6}/2\) times the optimal maximum completion time for problem instances with two machines. Both developments represent improvements over previous results. We prove that LMULTIFIT worst-case bounds for scheduling on simultaneous uniform machines are also LMULTIFIT worst-case approximation bounds for scheduling on nonsimultaneous uniform machines and show that worst-case approximation bounds of MULTIFIT variants for simultaneous uniform machines from previous literature also apply to LMULTIFIT. We also comment on how a PTAS for scheduling on a constant number of uniform machines with fixed jobs can be used to obtain a PTAS for scheduling on a constant number of uniform nonsimultaneous parallel machines.     

Learning with continuous experts using drifting games

We consider the problem of learning to predict as well as the best in a group of experts making continuous predictions. We assume the learning algorithm has prior knowledge of the maximum number of mistakes of the best expert. We propose a new master strategy that achieves the best known performance for on-line learning with continuous experts in the mistake bounded model. Our ideas are based on drifting games, a generalization of boosting and on-line learning algorithms. We prove new lower bounds based on the drifting games framework which, though not as tight as previous bounds, have simpler proofs and do not require an enormous number of experts. We also extend previous lower bounds to show that our upper bounds are exactly tight for sufficiently many experts. A surprising consequence of our work is that continuous experts are only as powerful as experts making binary or no prediction in each round.     

Non-clairvoyant Scheduling Games

In a scheduling game, each player owns a job and chooses a machine to execute it. While the social cost is the maximal load over all machines (makespan), the cost (disutility) of each player is the completion time of its own job. In the game, players may follow selfish strategies to optimize their cost and therefore their behaviors do not necessarily lead the game to an equilibrium. Even in the case there is an equilibrium, its makespan might be much larger than the social optimum, and this inefficiency is measured by the price of anarchy—the worst ratio between the makespan of an equilibrium and the optimum. Coordination mechanisms aim to reduce the price of anarchy by designing scheduling policies that specify how jobs assigned to a same machine are to be scheduled. Typically these policies define the schedule according to the processing times as announced by the jobs. One could wonder if there are policies that do not require this knowledge, and still provide a good price of anarchy. This would make the processing times be private information and avoid the problem of truthfulness. In this paper we study these so-called non-clairvoyant policies. In particular, we study the RANDOM policy that schedules the jobs in a random order without preemption, and the EQUI policy that schedules the jobs in parallel using time-multiplexing, assigning each job an equal fraction of CPU time.     

Topological Implications of Selfish Neighbor Selection in Unstructured Peer-to-Peer Networks

Current peer-to-peer (P2P) systems often suffer from a large fraction of freeriders not contributing any resources to the network. Various mechanisms have been designed to overcome this problem. However, the selfish behavior of peers has aspects which go beyond resource sharing. This paper studies the effects on the topology of a P2P network if peers selfishly select the peers to connect to. In our model, a peer exploits locality properties in order to minimize the latency (or response times) of its lookup operations. At the same time, the peer aims at not having to maintain links to too many other peers in the system. By giving tight bounds on the price of anarchy, we show that the resulting topologies can be much worse than if peers collaborated. Moreover, the network may never stabilize, even in the absence of churn. Finally, we establish the complexity of Nash equilibria in our game theoretic model of P2P networks. Specifically, we prove that it is NP-hard to decide whether our game has a Nash equilibrium and can stabilize.     

On the Convergence of Multicast Games in Directed Networks

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 network 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 selfish 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\sqrt{r})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 network 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 selfish 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)O(r\sqrt{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 W(r^k?{r})\Omega(r\sqrt[k]{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.     

Heuristic methods for the identical parallel machine flowtime problem with set-up times

We consider the scheduling of N jobs divided into G families for processing on M identical parallel machines. No set-up is necessary between jobs belonging to the same family. A set-up must be scheduled when switching from the processing of family i jobs to those of another family j, i≠j, the duration of this set-up being the sequence-independent set-up time s_j for family j. We propose heuristics for this problem and computationally evaluate the performance of the heuristics relative to lower bounds and solutions obtained using an exact algorithm.Scope and purposeWe study a machine-scheduling problem within which we have identical parallel machines, jobs arranged into families, and sequence-independent set-up times between jobs of different families on these machines. Our purpose is to develop simple, effective and efficient heuristics for this problem, and we seek to maximise the use of ideas and algorithms that have appeared previously in the literature for related problems. In our computational experiments, we seek to study the behaviour of these heuristics and uncover relevant properties of the scheduling problem. Within this experiment, we compare the observed performance of the heuristics relative to lower bounds and optimal solutions.     

Online scheduling on two uniform machines subject to eligibility constraints

We consider the online scheduling of a set of jobs on two uniform machines with the makespan as objective. The jobs are presented in a list. We consider two different eligibility constraint set assumptions, namely (i) arbitrary eligibility constraints and (ii) Grade of Service (GoS) eligibility constraints. In the first case, we prove that the High Speed Machine First (HSF) algorithm, which assigns jobs to the eligible machine that has the highest speed, is optimal. With regard to the second case, we point out an error in [M. Liu et al., Online scheduling on two uniform machines to minimize the makespan, Theoretical Computer Science 410 (21–23) (2009) 2099–2109]; we then provide tighter lower bounds and present algorithms with worst-case analysis for various ranges of machine speeds.     

Lower bounds for online makespan minimization on a small number of related machines

In online makespan minimization, the jobs characterized by their processing time arrive one-by-one and each has to be assigned to one of the m uniformly related machines. The goal is to minimize the length of the schedule. We prove new combinatorial lower bounds for m=4 and m=5, and computer-assisted lower bounds for m≤11.     

Selfish Load Balancing and Atomic Congestion Games

We revisit a classical load balancing problem in the modern context of decentralized systems and self-interested clients. In particular, there is a set of clients, each of whom must choose a server from a permissible set. Each client has a unit-length job and selfishly wants to minimize its own latency (job completion time). A server's latency is inversely proportional to its speed, but it grows linearly with (or, more generally, as the pth power of) the number of clients matched to it. This interaction is naturally modeled as an atomic congestion game, which we call selfish load balancing. We analyze the Nash equilibria of this game and prove nearly tight bounds on the price of anarchy (worst-case ratio between a Nash solution and the social optimum). In particular, for linear latency functions, we show that if the server speeds are relatively bounded and the number of clients is large compared with the number of servers, then every Nash assignment approaches social optimum. Without any assumptions on the number of clients, servers, and server speeds, the price of anarchy is at most 2.5. If all servers have the same speed, then the price of anarchy further improves to We also exhibit a lower bound of 2.01. Our proof techniques can also be adapted for the coordinated load balancing problem under L₂ norm, where it slightly improves the best previously known upper bound on the competitive ratio of a simple greedy scheme.