동시 확률 게임에서 B\"uchi 목표의 전략 복잡성

우리는 가산 그래프에서 2인 동시 확률 B\"uchi 게임을 연구합니다. 두 플레이어인 Max와 Min은 각각 목표 상태 집합을 무한히 자주 방문할 확률을 최대화하고 최소화하려고 합니다. 우리는 항상 단지 단계 카운터와 1 비트의 공용 메모리만 사용하는 -최적 Max 전략이 존재함을 보여줍니다. 이 상한은 모든 가산 그래프에 대해 성립하지만, 유한 그래프의 특별한 경우에서도 새로운 결과입니다. 이 상한은 단계 카운터만 사용하는 Max 전략이나 유한 메모리만 사용하는 것이 유한 게임 그래프에서도 충분하지 않다는 점에서 타이트합니다. 이 상한은 약간 더 강한 새로운 결과의 결과입니다: 결합된 B\"uchi 및 비기록 목표에 대한 -최적 Max 전략은 단지 1 비트의 공용 메모리만 필요하지만 메모리 없이는 안 됩니다. 우리의 증명 기법은 또한 비기록 목표에 대한 -최적 Max 전략이 메모리 없이 가능하다는 밀접하게 관련된 결과를 산출합니다(이는 무한 그래프에서만 의미가 있습니다).