English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the well-studied game-theoretic version of machine scheduling inwhich jobs correspond to self-interested users and machines correspond toresources. Here each user chooses a machine trying to minimize her own cost,and such selfish behavior typically results in some equilibrium which is notglobally optimal: An equilibrium is an allocation where no user can reduce herown cost by moving to another machine, which in general need not minimize themakespan, i.e., the maximum load over the machines.  We provide tight bounds on two well-studied notions in algorithmic gametheory, namely, the price of anarchy and the strong price of anarchy on machinescheduling setting which lies in between the related and the unrelated machinecase. Both notions study the social cost (makespan) of the worst equilibriumcompared to the optimum, with the strong price of anarchy restricting to astronger form of equilibria. Our results extend a prior study comparing theprice of anarchy to the strong price of anarchy for two related machines(Epstein, Acta Informatica 2010), thus providing further insights on therelation between these concepts. Our exact bounds give a qualitative andquantitative comparison between the two models. The bounds also show that thesetting is indeed easier than the two unrelated machines: In the latter, thestrong price of anarchy is $2$, while in ours it is strictly smaller.

Selfish Jobs with Favorite Machines: Price of Anarchy vs Strong Price of Anarchy