20 citations · 43 across the 31 of their papers we have counts for
14 papers · 1 filter
On the Power of Perturbation under Sampling in Solving Extensive-Form Games
Wataru Masaka, Mitsuki Sakamoto, Kenshi Abe +3
We investigate how perturbation does and does not improve the Follow-the-Regularized-Leader (FTRL) algorithm in solving imperfect-information extensive-form games under sampling, w…
Approximate State Abstraction for Markov Games
Hiroki Ishibashi, Kenshi Abe, Atsushi Iwasaki
This paper introduces state abstraction for two-player zero-sum Markov games (TZMGs), where the payoffs for the two players are determined by the state representing the environment…
Time-Varyingness in Auction Breaks Revenue Equivalence
Yuma Fujimoto, Kaito Ariu, Kenshi Abe
Auction is applied for trade with various mechanisms. A simple but practical question is which mechanism, typically first-price or second-price auctions, is preferred from the pers…
Last Iterate Convergence in Monotone Mean Field Games
Noboru Isobe, Kenshi Abe, Kaito Ariu
In the Lasry--Lions framework, Mean-Field Games (MFGs) model interactions among an infinite number of agents. However, existing algorithms either require strict monotonicity or onl…
Boosting Perturbed Gradient Ascent for Last-Iterate Convergence in Games
Kenshi Abe, Mitsuki Sakamoto, Kaito Ariu +1
This paper presents a payoff perturbation technique, introducing a strong convexity to players' payoff functions in games. This technique is specifically designed for first-order m…
Synchronization in Learning in Periodic Zero-Sum Games Triggers Divergence from Nash Equilibrium
Yuma Fujimoto, Kaito Ariu, Kenshi Abe
Learning in zero-sum games studies a situation where multiple agents competitively learn their strategy. In such multi-agent learning, we often see that the strategies cycle around…
Global Behavior of Learning Dynamics in Zero-Sum Games with Memory Asymmetry
Yuma Fujimoto, Kaito Ariu, Kenshi Abe
This study examines the global behavior of dynamics in learning in games between two players, X and Y. We consider the simplest situation for memory asymmetry between two players:…
Nash Equilibrium and Learning Dynamics in Three-Player Matching -Action Games
Yuma Fujimoto, Kaito Ariu, Kenshi Abe
Learning in games discusses the processes where multiple players learn their optimal strategies through the repetition of game plays. The dynamics of learning between two players i…
Adaptively Perturbed Mirror Descent for Learning in Games
Kenshi Abe, Kaito Ariu, Mitsuki Sakamoto +1
This paper proposes a payoff perturbation technique for the Mirror Descent (MD) algorithm in games where the gradient of the payoff functions is monotone in the strategy profile sp…
Memory Asymmetry Creates Heteroclinic Orbits to Nash Equilibrium in Learning in Zero-Sum Games
Yuma Fujimoto, Kaito Ariu, Kenshi Abe
Learning in games considers how multiple agents maximize their own rewards through repeated games. Memory, an ability that an agent changes his/her action depending on the history…
Learning in Multi-Memory Games Triggers Complex Dynamics Diverging from Nash Equilibrium
Yuma Fujimoto, Kaito Ariu, Kenshi Abe
Repeated games consider a situation where multiple agents are motivated by their independent rewards throughout learning. In general, the dynamics of their learning become complex.…
Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Games
Kenshi Abe, Kaito Ariu, Mitsuki Sakamoto +2
This paper proposes Mutation-Driven Multiplicative Weights Update (M2WU) for learning an equilibrium in two-player zero-sum normal-form games and proves that it exhibits the last-i…
Mutation-Driven Follow the Regularized Leader for Last-Iterate Convergence in Zero-Sum Games
Kenshi Abe, Mitsuki Sakamoto, Atsushi Iwasaki
In this study, we consider a variant of the Follow the Regularized Leader (FTRL) dynamics in two-player zero-sum games. FTRL is guaranteed to converge to a Nash equilibrium when ti…
Anytime Capacity Expansion in Medical Residency Match by Monte Carlo Tree Search
Kenshi Abe, Junpei Komiyama, Atsushi Iwasaki
This paper considers the capacity expansion problem in two-sided matchings, where the policymaker is allowed to allocate some extra seats as well as the standard seats. In medical…