A strategic learning algorithm for state-based games

DOI10.1016/J.AUTOMATICA.2019.108615MaRDI QIDQ2173896zbMATH OpenOpenAlexWikidataFDO

Authors Changxi Li, Yu Xing, Fenghua He, Daizhan Cheng

Publication date 17 April 2020

Published in Automatica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.05797

zbMATH Keywords

multi-agent systemsstrategic learningrecurrent state equilibriastate-based games

Mathematics Subject Classification ID

Applications of game theory (91A80) Stochastic learning and adaptive control (93E35) Rationality and learning in game theory (91A26) Multi-agent systems (93A16)

Abstract: Learning algorithm design for state-based games is investigated. A heuristic uncoupled learning algorithm, which is a two memory better reply with inertia dynamics, is proposed. Under certain reasonable conditions it is proved that for any initial state, if all agents in the state-based game follow the proposed learning algorithm, the action state pair converges almost surely to an action invariant set of recurrent state equilibria. The design relies on global and local searches with finite memory, inertia, and randomness. Finally, existence of time-efficient universal learning algorithm is studied. A class of state-based games is presented to show that there is no universal learning algorithm converging to a recurrent state equilibrium.

Recommendations

• State based potential games
• Absolutely expedient algorithms for learning Nash equilibria
• Learning efficient Nash equilibria in distributed systems
• Convergent learning algorithms for unknown reward games
• Efficient learning equilibrium

Cites work

• Achieving Pareto Optimality Through Distributed Learning
• Distributed optimization and games: a tutorial overview
• Dynamic fictitious play, dynamic gradient play, and distributed convergence to Nash equilibria
• Game-Theoretical Methods in Control of Engineering Systems: An Introduction to the Special Issue
• How long to equilibrium? The communication complexity of uncoupled equilibrium procedures
• Learning by trial and error
• Learning efficient Nash equilibria in distributed systems
• Selecting efficient correlated equilibria through distributed learning
• State based potential games
• Stochastic Games
• Stochastic uncoupled dynamics and Nash equilibrium
• Three problems in learning mixed-strategy Nash equilibria

Cited in

(11)

• Continuous limits of residual neural networks in case of large input data
• scientific article; zbMATH DE number 5670432 (Why is no real title available?)
• Orthogonal decomposition of incomplete-profile finite game space
• Stability analysis of networked evolutionary games with profile-dependent delays
• Rules for computing resistance of transitions of learning algorithms in games
• State based potential games
• On basis and pure Nash equilibrium of finite pure harmonic games
• A comprehensive survey on STP approach to finite games
• Stochastic convergence to recurrent state equilibrium for state-based games
• Minimum cost control of weighted networked evolutionary games with switched topologies and threshold
• Algebraic form and analysis of SIR epidemic dynamics over probabilistic dynamic networks

This page was built for publication: A strategic learning algorithm for state-based games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2173896)