Mechanism Design For Randomized Decentralized On-line Machine Scheduling

Algorithmic mechanism design, an important area in Game Theory, Eco-nomic Theory, Optimization and Computer Science, has received extensive study in the past few years. Mechanism for the scheduling problem consists of two algorithms, the allocation algorithm and the payment algorithm. Recently, it has been well studied for some algorithms, which can meet some decentralized re-quirements in distribute computing and good computational properties such as good approximation performance ratio or asymptotically optimal performance ratio, in mechanism design setting. In this thesis, we study the design of ran-domized decentralization mechanism in a setting where a set of non-preemptive jobs select randomly a machine from a set of uniform machines to be processed on, and each machine can process at most one job at a time. We assume that each job is a selfish agent, and a job’s release time rj, its processing time pj and its weight wj is only known to the job itself, but not to the system or any other job. Each job arrives on-line over time and knows nothing except for the processing speeds of machines and a local sequencing rule that machines will commit. Instead of centrally assigning jobs to machines, jobs decide for machines themselves, and then report their private information to the selected machine which implements a local sequencing rule that takes an order in which jobs are processed on the machine. Jobs will receive compensation for their choosing a machine and "waiting" on it until completion. Since job j is inter-ested in being finished as early as possible, jobs may strategically report false values(rj,pj,wj) in order to be scheduled earlier. Our goal is to meet require-ments for randomly systems which ask for low communication complexity and local protocols that machines have to commit to rather than centralized coor-dination due to selfishly behaving jobs. We derive a randomized decentralized mechanism and introduce a new concept of myopic Bayes-Nash incentive com- patibility which weakens the classical Bayes-Nash incentive compatibility, but appropriate and natural for our setting. We show that our mechanism can induce jobs to report truthfully their private information referred to myopic Bayes-Nash implementability by using a graph theoretic interpretation of the incentive com-patibility constraints. Furthermore, we prove that the performance of this mech-anism is asymptotically optimal.