Equilibria for two parallel links: The strong price of anarchy versus the price of anarchy

Author Leah Epstein



PDF
Thumbnail PDF

File

DagSemProc.07261.9.pdf
  • Filesize: 118 kB
  • 8 pages

Document Identifiers

Author Details

Leah Epstein

Cite AsGet BibTex

Leah Epstein. Equilibria for two parallel links: The strong price of anarchy versus the price of anarchy. In Fair Division. Dagstuhl Seminar Proceedings, Volume 7261, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
https://doi.org/10.4230/DagSemProc.07261.9

Abstract

Following recent interest in the "strong price of anarchy" SPOA), we consider this measure, as well as the well known "price of anarchy" (POA) for the job scheduling problem on two uniformly related parallel machines (or links). The atomic players are the jobs, and the delay of a job is the completion time of the machine running it. The social goal is to minimize the maximum delay of any job. Thus the cost (or social cost) in this case is the makespan of the schedule. The selfish goal of each job is to minimize its delay, i.e., the delay of the machine that it chooses to run on. A pure Nash equilibrium is a schedule where no job can obtain a smaller delay by selfishly moving to a different configuration (machine), while other jobs remain in their original positions. A strong equilibrium is a schedule where no (non-empty) subset of jobs exists, where all jobs in this subset can benefit from changing their configuration. We say that all jobs in a subset benefit from moving to a different machine if all of them have a strictly smaller delay as a result of moving (while the other jobs remain in their positions, and may possibly have a larger delay as a result). The SPOA is the worst case ratio between the social cost of a (pure) strong equilibrium and the cost of an optimal assignment, that is, the minimum achievable social cost. The POA is a standard measure which takes into account not only strong equilibria but any (pure) equilibrium. These two measures consolidate and give the same results for some problems, whereas for other problems, the SPOA gives much more meaningful results than the POA. We study the behavior of the SPOA versus the behavior of the POA for this scheduling problem and give tight results for both these measures. We find the exact SPOA for any possible speed ratio s geq 1 of the machines, and compare it to the exact POA which we also find. We show that for a wide range of speeds ratios these two measures are very different (1.618<s<2.247), whereas for other values of $s$, these two measures give the exact same bound. We extend all our results for cases where a machine may have an initial load resulting from jobs that can only be assigned to this machine, and show tight bounds on the SPOA and the POA for three such variants as well.
Keywords
  • Nash equilibrium
  • strong equilibrium
  • uniformly related machyines

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail