一句话：提出一种完全对称的目标改进算法，通过约束系统与误差最小化求解折扣支付博弈。
折扣支付博弈及其归约到的奇偶博弈、平均支付博弈在结构上具有对称性，但现有求解方法（如策略改进与值迭代）往往破坏这种对称性。本文从最优解应具备的性质出发，设计了一种完全对称的收敛方法：为每条边建立不等式约束系统，并通过对每个顶点选择一条出边来更新目标函数，这些出边可视为双方策略的松弛表示。目标是使所选不等式尽可能“紧”，不紧时以两边之差作为误差，并最小化误差总和。当且仅当达到协同最优策略时，所有被选不等式可同时取紧，误差和为零。算法在未找到协同最优策略时，交替地针对给定目标改进解、或针对给定解改进目标，逐步降低误差。该工作挑战了支付博弈求解非策略改进即值迭代的传统二分。
While discounted payoff games and classic games that reduce to them, like parity and mean-payoff games, are symmetric, their solutions are not. We have taken a fresh view on the properties that optimal solutions need to have, and devised a novel way to converge to them, which is entirely symmetric. We achieve this by building a constraint system that uses every edge to define an inequation, and update the objective function by taking a single outgoing edge for each vertex into account. These edges loosely represent strategies of both players, where the objective function intuitively asks to make the inequation to these edges sharp. In fact, where they are not sharp, there is an `error' represented by the difference between the two sides of the inequation, which is 0 where the inequation is sharp. Hence, the objective is to minimise the sum of these errors. For co-optimal strategies, and only for them, it can be achieved that all selected inequations are sharp or, equivalently, that the sum of these errors is zero. While no co-optimal strategies have been found, we step-wise improve the error by improving the solution for a given objective function or by improving the objective function for a given solution. This also challenges the gospel that methods for solving payoff games are either based on strategy improvement or on value iteration. arXiv admin note: substantial text overlap with arXiv:2310.01008
@article{paperbot4020,
title = {An Objective Improvement Approach to Solving Discounted Payoff Games},
author = {Daniele Dell'Erba and Arthur Dumas and Sven Schewe},
journal = {Logical Methods in Computer Science},
volume = {Volume 22, Issue 1},
year = {2026},
doi = {10.46298/lmcs-22(1:17)2026}
}