排序博弈的机制设计与均衡分析
- A+
：Prof.Zhiyi Tan
：2019-04-22 10:30
：实验105
Speaker：Prof.Zhiyi Tan
Zhejiang University
Title: 排序博弈的机制设计与均衡分析
Time：22 April 2019,10:30
Location：实验楼105
Abstract: 排序博弈是排序研究的前沿方向之一，也是算法博弈论的重要组成部分。在Koutsoupias和Papadimitriou最早提出的一类排序博弈模型中，工件可自由选择加工机器，每台机器按给定的加工机制确定在该机器上加工的工件的加工方式和顺序，工件的选择和机器的规则共同作用形成一个排序。工件费用定义为工件在该排序中的完工时间或其它与之相关的量。排序的社会费用定义为一与排序整体性能相关的量，如makespan，工件总费用等。一排序称为Nash均衡，若没有一个工件可通过单独改变加工机器使其费用减小。Nash均衡排序未必社会费用最优的排序，该情形称为均衡的无效率性，Price of Anarchy和Price of Stability是衡量均衡无效率性的两个定量指标。近年来又相继提出了其他均衡和扩展模型。排序博弈均衡分析的关键问题是证明均衡的存在性，揭示实现均衡的过程及其计算复杂性，给出无效率性定量指标的紧界。机制设计的关键问题是对现有机制所形成的均衡的性能分析与新的、更好的机制的设计。报告将介绍在若干平行机排序博弈模型机制设计和均衡分析中的研究进展，并给出该领域的部分open问题。
Speaker Introduction：浙江大学数学科学学院 教授&博导
联系人： 刘龙城副教授
