A Simple Graph-Theoretic Model for Selfish Restricted Scheduling

In this work, we introduce and study a simple, graph-theoretic model for selfish

scheduling

among

m

non-cooperative

users

over a collection of

nmachines

; however, each user is restricted to assign its unsplittable

load

to one from a pair of machines that are allowed for the user. We model these bounded interactions using an

interaction graph,

whose vertices and edges are the machines and the users, respectively. We study the impact of our modeling assumptions on the properties of Nash equilibria in this new model. The main findings of our study are outlined as follows:

– We prove, as our main result, that the

parallel links

graph is the

best-case

interaction graph – the one that minimizes expected

makespan

of the

standard fully mixed Nash equilibrium

– among all

3-regular

interaction graphs. The proof employs a graph-theoretic lemma about

orientations

in 3-regular graphs, which may be of independent interest.

– We prove a lower bound on

Coordination Ratio

[16] – a measure of the cost incurred to the system due to the selfish behavior of the users. In particular, we prove that there is an interaction graph incurring Coordination Ratio

${\it \Omega} \left( \frac{\log n} {\log \log n} \right)$

. This bound is shown for pure Nash equilibria.

– We present counterexample interaction graphs to prove that a

fully mixed Nash equilibrium

may sometimes not exist at all. Moreover, we prove properties of the fully mixed Nash equilibrium for

complete bipartite

graphs and

hypercube

graphs.