具有任意优先级列表的无关联机器之间的协调机制

《ACM Transactions on Economics and Computation》：Coordination Mechanisms on Unrelated Machines with Arbitrary Priority Lists

　　```

摘要AI摘要

要查看此AI生成的摘要，您必须具有高级访问权限。

了解更多登录

摘要

摘要

在作业调度游戏中，每个作业都是一个自私的参与者，会选择一台机器以最小化自己的完成时间。为了减少这种分散决策导致的效率低下，人们采用了协调机制。本文通过研究协调机制在无关并行机器上的应用，为相关研究做出了贡献，在这些机器中，每台机器都可以使用自己的调度策略来确定分配作业的处理顺序。

由于在这种情况下并不保证存在纯纳什均衡（NE），我们根据实际应用的需求，识别了几类确保存在纳什均衡的实例。对于每一类实例，我们都设计了一个算法来计算纳什均衡，证明了最佳响应动态的收敛性，并分析了均衡在完工时间方面的效率低下问题。此外，我们还研究了两个基本问题：(1) 计算一个完工时间较短的纳什均衡调度；(2) 给定一系列处理时间，选择能够保证存在完工时间较短的纳什均衡的机器特定调度策略。对于这两个问题，我们都得出了计算难度上的结论。

AI摘要

AI生成的摘要（实验性）

此摘要是使用自动化工具生成的，并非由文章作者撰写或审核。它旨在帮助读者发现信息、评估文章的相关性，并帮助来自相关研究领域的读者理解文章内容。它是对作者提供的摘要的补充，作者提供的摘要仍然是文章的官方总结。完整文章是权威版本。点击此处了解更多。

点击这里对摘要的准确性、清晰度和实用性进行评论。您的反馈将有助于改进未来的生成版本。

要查看此AI生成的通俗语言摘要，您必须具有高级访问权限。

```