AI

Dynamic Coordination Mechanisms

Abstract

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 .