论文摘要
算法机制设计作为博弈论,经济理论,优化和计算机科学相交叉的一个重要的领域,在近些年得到了广泛的关注和研究.机器排序问题的机制设计包括对两种算法的研究：分配算法和支付算法.最近,对于可以满足在分布式计算环境中产生的分散式需求以及具有好的算法性能,比如好的近似性能比或渐近最优性能比的算法研究在机制设计领域得到了深入的开展.本文研究了一种随机的分散式机制设计问题,在这个机制里,每一个工作都随机的选择在一台机器上不中断的进行加工,并且每一台机器在同一时间内至多加工一个工作.假设工作都是具有自私行为的代理,每一个代理.j都具有私有信息：释放时间rj,加工时间pj和权重ωj.每一个工作都是被在线释放的,在到来之后,它们只知道机器的处理速度和机器将要执行的局部排序规则.不同于中央分配的计算环境,在分散式的环境中,每个工作自己选择加工其任务的机器,并向机器报告它的私有信息.每台机器都遵守一个局部排序规则,并按此规则对选择该机器的工作进行排序.每一个工作将因为选择一台机器并在这台机器上“等待”直到加工完成而得到补偿.每一个工作都希望尽早的完成加工,因此为了达到这个目标,工作j可能会错误的向已选择的机器报告它的私有信息（rj,pj,wj）为满足在分散式计算环境中,随机系统对较低的通信复杂性和机器要遵守分散式局部协议的需求,本文研究了一种随机分散式机制,并介绍了短视的贝叶斯-纳什激励相容性（myopic Bayes-Nash incentive compatibility）的概念.这个概念比经典的贝叶斯-纳什激励相容性（classical Bayes-Nash incentive compatibility）概念弱,但是适合本文所研究的问题.利用激励相容约束的图论解释方法,本文证明了在短视的贝叶斯-纳什激励相容（myopic Bayes-Nash incentive compatibility）的意义下,该机制可以鼓励工作真实的报告它们的私有信息.并且证明了所给的随机分散式机制的平均性能是渐近最优的.
论文目录
相关论文文献
标签：在线排序论文; 算法机制设计论文; 分散式论文; 图论解释论文; 短视的贝叶斯纳什论文; 激励相容性论文; 渐近最优论文;