前言

排序博弈是从优化的角度分析研究排序问题中存在的博弈现象，也是从博弈的观点研究排序问题。不同于经典排序所考虑的单决策者问题，排序博弈研究的是排序问题中工件或者机器属于不同决策者的博弈问题，从而所研究的内容更加贴合实际生产活动所出现的多决策者问题。例如，在某银行服务大厅内，多个客户在柜台前站成一排等待服务，每个客户有一个任务，已知每个客户的任务的服务时间，并且每个客户的费用函数是客户服务完毕时间的不减函数。多个决策者通过合作，即联合行动共同决定工件的加工顺序，能够产生节省费用。如何产生最大的节省费用，以及如何在参与合作的人中分配这些节省的费用，是这个多决策者问题需要解决的。这样的多决策者问题可以建模为一个可转移效用的排序博弈问题。

本书主要介绍各种典型的排序博弈问题模型及其理论方法。全书共分为7章：第1章简要介绍排序问题的描述和表示，以及算法和计算复杂性，包括对工件加工数据和特征、机器加工环境、加工性能指标函数的描述。第2章简要介绍了本书涉及的博弈理论中的成熟模型及其基本概念和基本理论，包括具有转移效用的联盟博弈、纳什讨价还价问题、公平定价问题和算法博弈论中的若干概念。第3章介绍联盟排序博弈，在该模型中工件属于不同的参与人，并且工件已经有一个初始的排序。参与人可以通过合作重新安排工件的加工顺序，从而产生节省费用，该模型中要解决的问题是如何在参与合作的人中分配这些节省的费用。第4章介绍两台机器的讨价还价问题，在该模型中机器属于不同的参与人。参与人通过协商确定工件的一个划分，使得相应的合作收益分配方案能够使所有参与人认可和接受。该章主要介绍两台机器的讨价还价问题的纳什讨价还价解。第5章介绍两代理排序的公平定价问题，在该模型中工件属于两个不同的参与人。基于不同的公平解概念，研究公平解存在的条件，并分析其结构性质和性能。第6章和第7章分别介绍时间表长（Makespan）和并行加工（Parallel Processing）机制下的均衡分析，此类模型研究的主要问题是纳什均衡和强均衡的存在性，并对其进行性能分析。在此类模型中工件属于不同的参与人（局中人），参与人的策略空间就是机器集，当确定了机器加工机制和费用准则后，每个参与人在任意局势下的费用就能够被计算出来。每个参与人只是希望能减少自己的工件加工费用而不会去顾及总体目标。

本书的写作得到了唐国春先生的大力帮助和鼓励，并得到了“排序与调度丛书”编辑委员会各位老师的鼎力支持；同时也收到了排序与调度同仁和各位审稿专家的宝贵建议；清华大学出版社的编辑在本书的成稿过程中多次给予指导和建议；在本书撰写期间，作者的研究生在资料和文献整理方面给予了大力协助。在此，作者一并对上述各位表示衷心的感谢！

本书的出版得到了国家出版基金的资助。本书所涉及的部分研究成果也得到了作者主持的国家自然科学基金项目（项目号：12261039）的支持。

由于作者水平有限，本书难免存在疏漏甚至不妥之处，许多内容也有待深入研究和完善，敬请读者批评指正。

作者

2024年1月