text: We consider the well-studied game-theoretic version of machine scheduling in which jobs correspond to self-interested users and machines correspond to resources. Here each user chooses a machine trying to minimize her own cost, and such selfish behavior typically results in some equilibrium which is not globally optimal: An equilibrium is an allocation where no user can reduce her own cost by moving to another machine, which in general need not minimize the makespan, i.e., the maximum load over the machines. We provide tight bounds on two well-studied notions in algorithmic game theory, namely, the price of anarchy and the strong price of anarchy on machine scheduling setting which lies in between the related and the unrelated machine case. Both notions study the social cost (makespan) of the worst equilibrium compared to the optimum, with the strong price of anarchy restricting to a stronger form of equilibria. Our results extend a prior study comparing the price of anarchy to the strong price of anarchy for two related machines (Epstein, Acta Informatica 2010), thus providing further insights on the relation between these concepts. Our exact bounds give a qualitative and quantitative comparison between the two models. The bounds also show that the setting is indeed easier than the two unrelated machines: In the latter, the strong price of anarchy is @math , while in ours it is strictly smaller.
  @cite_14: A strong equilibrium is a pure Nash equilibrium which is resilient to deviations by coalitions. We define the strong price of anarchy (SPoA) to be the ratio of the worst strong equilibrium to the social optimum. Differently from the Price of Anarchy (defined as the ratio of the worst Nash Equilibrium to the social optimum), it quantifies the loss incurred from the lack of a central designer in settings that allow for coordination. We study the SPoA in two settings, namely job scheduling and network creation. In the job scheduling game we show that for unrelated machines the SPoA can be bounded as a function of the number of machines and the size of the coalition. For the network creation game we show that the SPoA is at most 2. In both cases we show that a strong equilibrium always exists, except for a well defined subset of network creation games.
  @cite_4: 
  @cite_8: The price of anarchy (POA) is a worst-case measure of the inefficiency of selfish behavior, defined as the ratio of the objective function value of a worst Nash equilibrium of a game and that of an optimal outcome. This measure implicitly assumes that players successfully reach some Nash equilibrium. This drawback motivates the search for inefficiency bounds that apply more generally to weaker notions of equilibria, such as mixed Nash and correlated equilibria; or to sequences of outcomes generated by natural experimentation strategies, such as successive best responses or simultaneous regret-minimization. We prove a general and fundamental connection between the price of anarchy and its seemingly stronger relatives in classes of games with a sum objective. First, we identify a "canonical sufficient condition" for an upper bound of the POA for pure Nash equilibria, which we call a smoothness argument. Second, we show that every bound derived via a smoothness argument extends automatically, with no quantitative degradation in the bound, to mixed Nash equilibria, correlated equilibria, and the average objective function value of regret-minimizing players (or "price of total anarchy"). Smoothness arguments also have automatic implications for the inefficiency of approximate and Bayesian-Nash equilibria and, under mild additional assumptions, for bicriteria bounds and for polynomial-length best-response sequences. We also identify classes of games --- most notably, congestion games with cost functions restricted to an arbitrary fixed set --- that are tight, in the sense that smoothness arguments are guaranteed to produce an optimal worst-case upper bound on the POA, even for the smallest set of interest (pure Nash equilibria). Byproducts of our proof of this result include the first tight bounds on the POA in congestion games with non-polynomial cost functions, and the first structural characterization of atomic congestion games that are universal worst-case examples for the POA.
  @cite_10: Strong Nash equilibria and Pareto-optimal Nash equilibria are natural and important strengthenings of the Nash equilibrium concept. We study these stronger notions of equilibrium in congestion games, focusing on the relationships between the price of anarchy for these equilibria and that for standard Nash equilibria (which is well understood). For symmetric congestion games with polynomial or exponential latency functions, we show that the price of anarchy for strong and Pareto-optimal equilibria is much smaller than the standard price of anarchy. On the other hand, for asymmetric congestion games with polynomial latencies the strong and Pareto prices of anarchy are essentially as large as the standard price of anarchy; while for asymmetric games with exponential latencies the Pareto and standard prices of anarchy are the same but the strong price of anarchy is substantially smaller. Finally, in the special case of linear latencies, we show that in asymmetric games the strong and Pareto prices of anarchy coincide exactly with the known value @math for standard Nash, but are strictly smaller for symmetric games.
  @cite_9: Increasing interest has recently been shown in analyzing the worst-case behavior of local search algorithms. In particular, the quality of local optima and the time needed to find the local optima by the simplest form of local search has been studied. This paper deals with worst-case performance of local search algorithms for makespan minimization on parallel machines. We analyze the quality of the local optima obtained by iterative improvement over the jump, swap, multi-exchange, and the newly defined push neighborhoods. Finally, for the jump neighborhood we provide bounds on the number of local search steps required to find a local optimum.
  @cite_1: 
  @cite_6: 
  @cite_0: 
  @cite_19: We consider a job scheduling game with two uniformly related parallel machines (or links). Jobs are atomic players, and the delay of a job is the completion time of the machine running it. The private goal of each job is to minimize its own delay and the social goal is to minimize the maximum delay of any job, that is, to minimize the makespan. We consider the well known price of anarchy as well as the strong price of anarchy, and show that for a wide range of speed ratios these two measures are very different whereas for other speed ratios these two measures give the exact same bound. We extend all our results for models of restricted assignment, where a machine may have an initial load resulting from jobs that can only be assigned to this machine, and show tight results for all variants.
  @cite_5: Givenn jobs andm identical processors anO(n) approximation algorithm is presented which tries to determine a nonpreemptive schedule with minimum finish time. Ifr is the number of jobs placed onto the processor with maximum finish time, then the worst case ratio of the new algorithm's finish time to the optimal solution is shown to be less thanrm (rm−m+1). Extensive empirical results show that the new algorithm is competitive with the LPT algorithm in terms of quality of solution and faster in terms of computing time.
  @cite_15: 
  @cite_16: 
  @cite_20: 
  @cite_12: 
  @cite_17: 
summary: The price of anarchy is for , and grows otherwise. Specifically, @math and @math @cite_16 , while @math @cite_14 . The case of a is of particular interest. For and machines, @math and @math @cite_15 , respectively. For machines, exact bounds as a function of the @math on both @math and @math are given in @cite_19 . The price of anarchy bounds are similar to related machines: @math and @math @cite_0 , where the analysis of @math is also in @cite_17 . The price of anarchy and the strong price of anarchy for pure equilibria are and bounded by a : @math @cite_12 , where the upper and lower bounds on @math can be deduced from @cite_5 and @cite_9 , respectively. Finally, @math @cite_6 @cite_16 @cite_4 . For further results on other problems and variants of these equilibrium concepts we refer the reader to e.g. @cite_8 @cite_20 @cite_1 @cite_10 and references therein.