Although recent work in AI has made great progress in solving large, zero-sum, extensive-form games, the underlying assumption in most past work is that the parameters of the game itself are known to the agents. This paper deals with the relatively under-explored but equally important "inverse" setting, where the param…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
169,051 papers · 148 categories
Trend · papers per month
48 results for “extensive games”
A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergencecs.GT
Policy gradient method proves convergence in imperfect-information games.
problem Policy gradient methods in imperfect-information games (EFGs).
method Policy gradient approach with best-iterate convergence.
result Policy gradient leads to provable best-iterate convergence in self-play EFGs.
Paper studies how to combine regret minimizers for solving complex games.
problem Solving large-scale extensive-form games with constraints.
method Derives a calculus for constructing regret minimizers for composite convex sets.
result Local regret minimizers for simpler sets can be combined into an aggregate for composite sets.
Paper models game theory for defending against data poisoning attacks.
problem Defending against data poisoning attacks using game theory.
method Modeling attacker-defender game, proving non-existence of pure Nash Equilibrium, proposing mixed strategy approach, and developing an algorithm to approximate Nash Equilibrium.
result Demonstrated effectiveness of mixed strategy defense in experiments.
Lazy-CFR: fast and near optimal regret minimization for extensive games with imperfect informationcs.LG
Lazy-CFR improves CFR's efficiency and performance in imperfect information games.
problem Efficiency and performance in imperfect information games with imperfect information.
method Lazy update technique to avoid full traversal of game tree, resulting in a more efficient CFR variant.
result Lazy-CFR achieves better convergence and significantly outperforms vanilla CFR in experiments.
Agents Play Mix-gamephysics.soc-ph
In mix-game which is an extension of minority game, there are two groups of agents; group1 plays the majority game, but the group2 plays the minority game. This paper studies the change of the average winnings of agents and volatilities vs. the change of mixture of agents in mix-game model. It finds that the correlatio…
Paper solves learning imperfect-information games with fewer episodes.
problem Learning imperfect-information extensive-form games from bandit feedback.
method Balanced Online Mirror Descent and Balanced Counterfactual Regret Minimization algorithms.
result Achieves near-optimal sample complexity for finding approximate Nash equilibria.
Paper addresses inefficiency in converting EFGs to NFGs for learning.
problem Inefficiency in converting Extensive-Form Games to Normal-Form Games.
method Uses -Hedge algorithm and Online Mirror Descent (OMD) for polynomial-time learning of EFGs.
result Achieves EFCE-regret, matching information-theoretic lower bound.
DREAM learns optimal strategies in imperfect games without needing a simulator.
problem Learning optimal strategies in imperfect-information games with multiple agents.
method DREAM is a deep reinforcement learning algorithm that converges to Nash Equilibria and coarse correlated equilibria.
result DREAM achieves state-of-the-art performance in benchmark games and is competitive with simulator-based algorithms.
Study shows Elo models fail to accurately measure transitive strength in competitive games.
problem Elo models fail to correctly identify the transitive component in real-world competitive games.
method Investigated the challenge of identifying the transitive component in games, proposed an extension of the Elo score.
result Disc ranking system assigns two scores: skill and consistency.
This chapter reviews recent advances in multi-agent reinforcement learning.
problem Theoretical foundations for multi-agent reinforcement learning are lacking.
method Selective overview of MARL algorithms with theoretical analysis.
result Identification of new research directions in MARL theory.
Entropy regularization improves MFG learning efficiency and stability.
problem Improving Mean Field Game learning efficiency and stability.
method Entropy regularization applied to MFG with learning.
result Entropy regularization yields time-dependent policies and stabilizes convergence.
Real payoffs and virtual trading in agent based market modelscond-mat.stat-mech
The \$-Game was recently introduced as an extension of the Minority Game. In this paper we compare this model with the well know Minority Game and the Majority Game models. Due to the inter-temporal nature of the market payoff, we introduce a two step transaction with single and mixed group of interacting traders. When…
Paper studies constrained control games with a novel approximation method.
problem Games with constrained control directions.
method Approximation procedure based on -stability estimates and almost sure convergence.
result Existence of game's value and optimal strategy for the stopper.
Game theory enhances preference learning, improving feature selection and interpretability.
problem Improving feature selection and interpretability in preference learning.
method Formulates preference learning as a two-player zero-sum game, proposing an algorithm to incrementally add features.
result Demonstrates the convergence of the algorithm and shows its effectiveness in feature selection and interpretability.
We study minority games in efficient regime. By incorporating the utility function and aggregating agents with similar strategies we develop an effective mesoscale notion of state of the game. Using this approach, the game can be represented as a Markov process with substantially reduced number of states with explicitl…
Develops a new method for solving generalized eigenvalue problems efficiently.
problem Efficiently solving generalized eigenvalue problems for large datasets.
method Inspired by the Generalized Hebbian Algorithm, develops a game-theory inspired approach to solving GEPs.
result Demonstrates state-of-the-art performance for optimizing Deep CCA.
Expands MFGs to handle real-world asymmetric multi-agent games efficiently.
problem Applying mean-field games to real-world, heterogeneous multi-agent systems.
method Develops a method to symmetrize and extend finite-player games to infinite-player MFGs, proving approximation bounds and convergence guarantees.
result TD learning converges to approximate Nash equilibria in finite-sample settings, enabling symmetrized learning without explicit MFG models.
A quantum financial approach to finite games of strategy is addressed, with an extension of Nash's theorem to the quantum financial setting, allowing for an entanglement of games of strategy with two-period financial allocation problems that are expressed in terms of: the consumption plans' optimization problem in pure…
Unified framework for estimating reward functions in competitive games.
problem Estimating unknown reward functions in competitive games.
method Unified framework with entropy regularization for reward function recovery.
result Strong theoretical guarantees and practical effectiveness demonstrated.
This paper studies the correlations of the average winnings of agents and the volatilities of systems based on mix-game model which is an extension of minority game (MG). In mix-game, there are two groups of agents; group1 plays the majority game, but the group2 plays the minority game. The results show that the correl…
The last financial and economic crisis demonstrated the dysfunctional long-term effects of aggressive behaviour in financial markets. Yet, evolutionary game theory predicts that under the condition of strategic dependence a certain degree of aggressive behaviour remains within a given population of agents. However, as …
Increasing iterate averaging improves convergence rates for saddle-point problems.
problem Solving saddle-point problems efficiently.
method Increasing iterate averaging schemes applied to various first-order methods.
result Increasing iterate averaging preserves the convergence rate with no additional assumptions or overhead.
Deep fictitious play converges to Nash equilibrium in stochastic differential games.
problem Finding Nash equilibrium in large stochastic differential games.
method Decouples the game into sub-optimization problems and solves each player's optimal strategy with deep BSDE method.
result Deep fictitious play converges to the true Nash equilibrium.
The paper introduces and studies hedging for game (Israeli) style extension of swing options considered as multiple exercise derivatives. Assuming that the underlying security can be traded without restrictions we derive a formula for valuation of multiple exercise options via classical hedging arguments. Introducing t…
Algorithm learns from changing zero-sum games with no regret.
problem Learning in time-varying zero-sum games.
method Developed a single parameter-free algorithm with three performance measures.
result Algorithm recovers best known results for fixed games and adapts to non-stationarity.
Deep learning enhances solving complex mean field games in finance.
problem Solving large-scale mean field games with financial applications.
method Combining mean field games theory with deep learning techniques.
result Improved solutions for large-scale financial games.
We introduce a simple extension of the minority game in which the market rewards contrarian (resp. trend-following) strategies when it is far from (resp. close to) efficiency. The model displays a smooth crossover from a regime where contrarians dominate to one where trend-followers dominate. In the intermediate phase,…
First sample-efficient algorithm for learning EFCE in bandit feedback settings.
problem Learning EFCE in bandit feedback settings for IIEFGs.
method Proposed -EFCE and uncoupled no-regret algorithm with wide-range regret minimization.
result First sample-efficient algorithm for learning EFCE from bandit feedback.
We study the problem of super-replication for game options under proportional transaction costs. We consider a multidimensional continuous time model, in which the discounted stock price process satisfies the conditional full support property. We show that the super-replication price is the cheapest cost of a trivial s…
Hybrid SAC improves RL for video games with discrete, continuous actions.
problem Improving RL performance in video games with practical constraints.
method Extension of Soft Actor-Critic (SAC) for handling discrete, continuous, and parameterized actions.
result Hybrid SAC successfully solves a high-speed driving task and is competitive on parameterized actions benchmarks.
The paper extends macroscopic market making to stochastic games, revealing properties and solving equations.
problem Price competition among market makers in a stochastic game setting.
method Extension of macroscopic market making framework to stochastic games, introducing multidimensional characteristic equations.
result New well-posedness results for forward-backward stochastic differential equations.
In this paper we review our earlier work on quantum computing and the Nash Equilibrium, in particular, tracing the history of the discovery of new Nash Equilibria and then reviewing the ways in which quantum computing may be expected to generate new classes of Nash equilibria. We then extend this work through a substan…
We study the problem of learning classifiers robust to universal adversarial perturbations. While prior work approaches this problem via robust optimization, adversarial training, or input transformation, we instead phrase it as a two-player zero-sum game. In this new formulation, both players simultaneously play the s…
Paper proposes incentive mechanism to encourage participation in federated learning.
problem Users are reluctant to participate in federated learning due to privacy concerns.
method Formulated as a two-stage Stackelberg game, designed an incentive mechanism to select and compensate users.
result Demonstrated effectiveness of the proposed incentive mechanism through simulations.
New method finds all Nash equilibria via vector optimization.
problem Finding all Nash equilibria in games.
method Formulate vector optimization problem to find Pareto optimal solutions.
result Characterize set of all Nash equilibria as Pareto optimal solutions.
RLCFR improves CFR's generalization in imperfect information games.
problem Improving CFR's performance in large-scale, imperfect information games.
method RLCFR integrates CFR with deep reinforcement learning to update strategies dynamically.
result RLCFR significantly enhances CFR's generalization ability in various games.
Balance, Imbalance, and Rebalance: Understanding Robust Overfitting from a Minimax Game Perspectivecs.LG
Paper explains adversarial training's robust overfitting through a minimax game perspective.
problem Adversarial training suffers from robust overfitting after learning rate decay.
method Viewing adversarial training as a dynamic minimax game, analyzing how LR decay breaks balance and leads to overfitting.
result ReBalanced Adversarial Training (ReBAT) alleviates robust overfitting without sacrificing robustness.
Paper solves discounted stochastic games with near-optimal time and sample complexity.
problem Solving discounted stochastic two-player games with optimal complexity.
method Generalizes Q-learning to two-player strategy computation, overcoming limitations of existing methods.
result Near-optimal -strategy computation with polylogarithmic factors in and .
Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibriumcs.LG
Algorithm finds Nash equilibria in complex games with function approximation.
problem Learning Nash equilibria in two-player zero-sum Markov Games with nonlinear function approximation.
method Online learning algorithm using upper and lower confidence bounds derived from optimism in the face of uncertainty.
result Achieves regret with polynomial complexity, under mild assumptions.
Game-theoretic model captures investor interactions for stock price forecasting.
problem Complex market dynamics driving stock price movements.
method Game-theoretic modeling of heterogeneous investor interactions in a dynamic graph structure.
result Our method outperforms state-of-the-art stock price forecasting methods.
This paper relaxes the common prior assumption in the public and private information game of Morris and Shin (2000, 2004). For the generalized game, where the agent's prior expectations are heterogenous, it derives a sharp condition for the emergence of unique/multiple equilibria. This condition indicates that unique e…
This paper studies robust payoff allocation in submodular games, especially against replication.
problem Payoff allocation in submodular games, especially robustness against replication.
method Systematically studied replication manipulation in submodular games, introduced replication robustness metric, and validated with empirical ML data market.
result Conditions characterizing robustness of semivalues in submodular games.
Deep learning theory for Nash equilibrium in stochastic games.
problem Computing Nash equilibrium in non-zero-sum stochastic differential games.
method Fictitious play applied to deep neural networks for solving -player optimization problems.
result Deep learning algorithm converges to open-loop Nash equilibrium under appropriate assumptions.
This paper tackles global Nash equilibrium in non-convex multi-player games.
problem Challenges in finding global Nash equilibrium due to non-convexity.
method Conjugate transformation and variational inequality formulation to prove existence and design algorithms.
result Designs an ODE-based algorithm with exponential convergence rate and proves its effectiveness in practical scenarios.
Paper solves non-convex min-max games using gradient descent-ascent.
problem Solving saddle point games in non-convex settings.
method Iterative gradient descent-ascent algorithms for both players.
result First order stationary points found efficiently.
Fractal neural networks play SimCity and Conway's Game of Life on varying scales.
problem Generalizing agents' performance to larger gameboards than during training.
method Reinforcement learning in a custom environment, using fractal neural networks.
result Agents can generalize to larger gameboards, solving a minigame unsolvable with local strategies.
Study of pursuit-evasion game on sphere and its relation to planar Apollonius circle.
problem Analyzing pursuit-evasion game on a sphere and its properties.
method Extending classical planar pursuit-evasion game to spherical geometry, studying equilibrium intercept points and their relation to Apollonius domain.
result Condition for intercept point to belong to Apollonius domain on sphere, analogous to planar game.