Accelerating set-based strategy sorting in multi-objective normal-form games

Shimon Regev

doi:10.1007/s00521-026-12416-1

2026-08-25

Shimon Regev *

Erella Eisenstadt-Matalon

Amiram Moshaiov

Achiya Elyasaf

DOI：10.1007/s00521-026-12416-1

原文链接

原文求助

摘要

En 中文

在考虑最坏情况时求解两人多目标标准形式博弈（MONFGs），每种策略自然由多个收益向量表示，每个向量对应与对手策略的一种可能交互。虽然将这些向量压缩为一个“代表性”向量（例如Nadir点）可能更简单，但这种标量化可能会掩盖重要的权衡，并在最坏性能至关重要的情境下可能错误识别解。为解决此问题，近期方法通过比较完整的收益向量集来精确捕捉对抗行为。然而，这种方法计算成本高昂。我们提出了一种新颖的两阶段加速方法，该方法保留了基于完整集的最坏情况比较的精确性，同时显著降低了运行时间。首先，一种计算成本较低的基于元组的支配性检查可识别明显被支配（因而非理性）的策略，并在不影响最终最坏情况非支配集的情况下将其剔除。其次，对剩余的策略池进行更复杂的基于集的支配性检查。我们从理论上证明，此两阶段流程与直接基于集的方法产生相同的最终解，但计算成本仅为后者的一小部分——尤其在大型策略空间中。我们通过两人竞争性旅行商问题（作为MONFG框架）在完全搜索场景（小规模问题）和协同进化设置（大规模问题）中验证了该方法的有效性。实证结果表明其与复杂度分析一致，并显示出显著加速，凸显了该方法在将基于集的最坏情况方法扩展至更复杂的多玩家决策领域的潜力。

Keyword:

Two-player multi-objective normal-form games (MONFGs)

Multi-objective games (MOGs)

Set-based worst-case dominance

Tuple-based dominance

Co-evolutionary algorithms

Rationalizability

Complexity analysis