Smooth Inequalities and Equilibrium Inefficiency in Scheduling Games

Details Smooth Inequalities and Equilibrium Inefficiency in Scheduling Games Smooth Inequalities and Equilibrium Inefficiency in Scheduling Games

2012-02-20

arxiv.org/abs/1202.4302v1

Computer Science

Computer Science and Game Theory

25 pages, 1 figure

Scientific paper

We study coordination mechanisms for Scheduling Games (with unrelated machines). In these games, each job represents a player, who needs to choose a machine for its execution, and intends to complete earliest possible. Our goal is to design scheduling policies that always admit a pure Nash equilibrium and guarantee a small price of anarchy for the l_k-norm social cost --- the objective balances overall quality of service and fairness. We consider policies with different amount of knowledge about jobs: non-clairvoyant, strongly-local and local. The analysis relies on the smooth argument together with adequate inequalities, called smooth inequalities. With this unified framework, we are able to prove the following results. First, we study the inefficiency in l_k-norm social costs of a strongly-local policy SPT and a non-clairvoyant policy EQUI. We show that the price of anarchy of policy SPT is O(k). We also prove a lower bound of Omega(k/log k) for all deterministic, non-preemptive, strongly-local and non-waiting policies (non-waiting policies produce schedules without idle times). These results ensure that SPT is close to optimal with respect to the class of l_k-norm social costs. Moreover, we prove that the non-clairvoyant policy EQUI has price of anarchy O(2^k). Second, we consider the makespan (l_infty-norm) social cost by making connection within the l_k-norm functions. We revisit some local policies and provide simpler, unified proofs from the framework's point of view. With the highlight of the approach, we derive a local policy Balance. This policy guarantees a price of anarchy of O(log m), which makes it the currently best known policy among the anonymous local policies that always admit a pure Nash equilibrium.

Affiliated with

Also associated with

No associations

Rating

Smooth Inequalities and Equilibrium Inefficiency in Scheduling Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Smooth Inequalities and Equilibrium Inefficiency in Scheduling Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Smooth Inequalities and Equilibrium Inefficiency in Scheduling Games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-564649