paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A pseudo-quasi-polynomial algorithm for mean-payoff parity games

mean-payoff parity 博弈的伪拟多项式算法
LICS Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science2018匹配度 2/10 · 该论文是 mean-payoff parity 博弈的纯理论算法研究，属于逻辑与自动机/形式化方法基础，但不涉及静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析等画像核心方向。引用 10 inbox
Laure Daviaud, Martin Jurdziński, Ranko Lazić
逻辑与自动机
crossref: 2026-09-12

AI 速览

一句话：为 mean-payoff parity 博弈提出一种伪拟多项式时间求解算法。

论文研究 mean-payoff parity game 的求解问题。该博弈是零和博弈：一名玩家既要满足定性的 parity 目标，又要最小化收益的长期平均值（mean payoff）；另一名玩家则试图破坏 parity 目标或最大化平均收益。作者提出一种 pseudo-quasi-polynomial 算法来求解该类博弈。摘要本身只给出博弈模型与算法类型，未展开具体技术细节、复杂度上界或实验评估；因此其核心贡献可概括为在 parity 条件与 mean-payoff 定量目标结合的博弈上给出的新算法及其理论算法贡献。

问题
如何在 mean-payoff parity game 中同时处理 parity 定性目标与 mean-payoff 定量目标，并设计高效求解算法。
方法
提出一种 pseudo-quasi-polynomial 算法，用于求解双方的零和 mean-payoff parity 博弈。
评估
摘要未给出实验评估；从论文标题看，评估形式为理论算法及其复杂度分析。
原文摘要（Abstract）

In a mean-payoff parity game, one of the two players aims both to achieve a qualitative parity objective and to minimize a quantitative long-term average of payoffs (aka. mean payoff). The game is zero-sum and hence the aim of the other player is to either foil the parity objective or to maximize the mean payoff.

链接与引用

DOI 原文 · PDF（开放获取） ·

BibTeX 
@inproceedings{paperbot4308,
  title = {A pseudo-quasi-polynomial algorithm for mean-payoff parity games},
  author = {Laure Daviaud and Martin Jurdziński and Ranko Lazić},
  booktitle = {LICS},
  year = {2018},
  doi = {10.1145/3209108.3209162}
}