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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We consider a scheduling game on parallel related machines, in which jobs tryto minimize their completion time by choosing a machine to be processed on.Each machine uses an individual priority list to decide on the order accordingto which the jobs on the machine are processed. We prove that it is NP-hard todecide if a pure Nash equilibrium exists and characterize four classes ofinstances in which a pure Nash equilibrium is guaranteed to exist. For each ofthese classes, we give an algorithm that computes a Nash equilibrium, we provethat best-response dynamics converge to a Nash equilibrium, and we bound theinefficiency of Nash equilibria with respect to the makespan of the scheduleand the sum of completion times. In addition, we show that although a pure Nashequilibrium is guaranteed to exist in instances with identical machines, it isNP-hard to approximate the best Nash equilibrium with respect to bothobjectives.

Scheduling Games with Machine-Dependent Priority Lists