Dynamic Coordination Mechanisms

Handling the lack of coordination while designing efficient algorithms
in distributed systems has been a major topic of study
in the past decade. Coordination mechanisms have been proposed
as a tool to deal with the issue as well as lack of access
to global information in settings such as distributed systems.
In the context of resource allocation, a coordination mechanism
is a set of local policies that assigns a cost to each strategy
based on the available local information. For example,
in machine scheduling, this cost only depends on the processing
times of jobs assigned to the same machine. Although
a great tool to study distributed algorithms in the presence
of self-interested agents, coordination mechanisms have few
deficiencies as an analysis tool for distributed game theoretic
environments. For example, in many real-world settings, we
do not know the exact processing time of a job before it finishes.
Furthermore, in many settings, jobs arrive online, and
have different release times. Motivated by these requirements,
we propose dynamic coordination mechanisms, in which each
job selects a machine by looking at the set of jobs currently on
each machine and it can change its decision over time. In other
words, jobs can dynamically choose the (best machine dynamically.
We study scheduling and resource allocation problems
in this framework.
Here, we are given a set of M machines and a set N of
jobs or players. Each job j ∈ N has pj units of processing
requirement. The mechanism designer, however, is not aware
of the processing lengths of jobs. This is commonly referred
to as non-clairvoyant setting in the machine scheduling literature.
We consider two machine models: In the related machine
model, each machine has a speed νi, and a job can choose any
machine i ∈ M. In the restricted assignment model, every
machine has same speed; however, a job j can only go to a
subset of machines Mj .

• Algorithms and Theory