arXiv:2407.06676v2 cs.AI

지수 가중치 알고리즘이 수행하는 게임

Games played by Exponential Weights Algorithms

Maurizio d'Andrea (TSE-R), Fabien Gensbittel (TSE-R), J\'er\^ome Renault (TSE-R)

제출 2024-07-09

한국어 초록

본 논문은 일정한 학습률을 갖는 지수 가중치 알고리즘의 마지막 반복 수렴 특성을 연구한다. 각 플레이어가 초기 혼합 행동과 고정된 학습률로 특징지어지는 지수 가중치 알고리즘을 사용하는 이산 시간 반복 상호작용을 고려하며, 이에 따라 단계 $t$에서 플레이되는 혼합 행동 프로파일 $p^t$는 시간 동질적 마르코프 연쇄를 따른다. 첫째, 엄격한 내시 균형이 존재하는 경우 다음 단계에서 엄격한 내시 균형을 플레이할 확률이 거의 확실하게 0 또는 1로 수렴함을 보인다. 둘째, $p^t$의 극한이 존재할 경우 그 극한은 ``보수 균등화 내시 균형'' 집합에 속함을 보인다. 셋째, 플레이어의 보수가 대각선에서는 양수이고 그 외에는 0인 강한 조정 게임에서 $p^t$가 엄격한 내시 균형 중 하나로 거의 확실하게 수렴함을 보인다. 마지막으로 미해결 문제들을 제시하며 결론을 맺는다.

원문 초록

This paper studies the last-iterate convergence properties of the exponential weights algorithm with constant learning rates. We consider a repeated interaction in discrete time, where each player uses an exponential weights algorithm characterized by an initial mixed action and a fixed learning rate, so that the mixed action profile $p^t$ played at stage $t$ follows an homogeneous Markov chain. At first, we show that whenever a strict Nash equilibrium exists, the probability to play a strict Nash equilibrium at the next stage converges almost surely to 0 or 1. Secondly, we show that the limit of $p^t$, whenever it exists, belongs to the set of ``Nash Equilibria with Equalizing Payoffs''. Thirdly, we show that in strong coordination games, where the payoff of a player is positive on the diagonal and 0 elsewhere, $p^t$ converges almost surely to one of the strict Nash equilibria. We conclude with open questions.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2407.06676v2제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.