Speaker：Zhiyi Tan（Zhejiang University）

Time： 2019-04-22,10:30

Location：Conference Room 108 at Experiment Building at Haiyun Campus

Abstract: Sorting game is one of the frontier directions of sorting research and an important part of algorithmic game theory. In a kind of ranking game model first proposed by Koutsoupias and Papadimitriou, the workpiece can freely choose the processing machine, and each machine determines the processing method and order of the workpiece processed on the machine according to the given processing mechanism. The rules work together to form an ordering. Part cost is defined as the makepan or other quantity associated with the part in the sequence. The social cost of sorting is defined as a quantity related to the overall performance of sorting, such as makespan, total cost of artifact, etc. An ordering is called Nash equilibrium, if none of the workpieces can be reduced by changing the processing machine individually. Nash equilibrium ordering may not be the optimal ordering of social costs. This situation is called equilibrium inefficiency. Price of Anarchy and Price of Stability are two quantitative indicators to measure equilibrium inefficiency. In recent years, other equilibrium and expansion models have been proposed successively. The key problem of equilibrium analysis of ranking game is to prove the existence of equilibrium, reveal the process of realizing equilibrium and its computational complexity, and give the tight bound of the quantitative index of inefficiency. The key issue of mechanism design is the balanced performance analysis of existing mechanisms and the design of new and better mechanisms. The report will introduce the research progress in the mechanism design and equilibrium analysis of several parallel machine ranking game models, and give some open problems in this field.