We introduce a topological combinatorial game called the Region Smoothing Swap Game. The game is played on a game board derived from the connected shadow of a link diagram on a (possibly non-orientable) surface by smoothing at crossings. Moves in the game are performed on regions of the diagram and can switch the direc…
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.
168,695 papers · 148 categories
Trend · papers per month
48 results for “smooth games”
New method improves convergence for smooth games.
problem Improving convergence for smooth games.
method Stochastic Hamiltonian Gradient Methods (SHGD).
result SHGD converges linearly to the neighbourhood of a stationary point.
The Link Smoothing Gamemath.CO
We introduce a topological combinatorial game called the Link Smoothing Game. The game is played on the shadow of a link diagram and legal moves consist of smoothing precrossings. One player's goal is to keep the diagram connected while the other player's goal is to disconnect the shadow. We make significant progress t…
With the success of modern machine learning, it is becoming increasingly important to understand and control how learning algorithms interact. Unfortunately, negative results from game theory show there is little hope of understanding or controlling general n-player games. We therefore introduce smooth markets (SM-game…
We use matrix iteration theory to characterize acceleration in smooth games. We define the spectral shape of a family of games as the set containing all eigenvalues of the Jacobians of standard gradient dynamics in the family. Shapes restricted to the real line represent well-understood classes of problems, like minimi…
New algorithm solves non-convex, non-differentiable min-max games.
problem Limited theoretical understanding of non-smooth min-max games.
method Proximal gradient descent-ascent algorithm for convex-strongly convex games.
result Algorithm converges to ε-Nash equilibrium with polynomial gradient evaluations.
This paper analyzes saddle points and minimax points in non-convex smooth games.
problem Understanding local optimal points in non-convex smooth games.
method Comprehensive analysis of local minimax points, including their optimality conditions and stability.
result Local saddle points are uniformly local minimax points under mild continuity assumptions.
Negative momentum accelerates convergence in minimax games but at a suboptimal rate.
problem The convergence rate of negative momentum in minimax games is suboptimal.
method Extending variational inequality formulation, connecting momentum method with Chebyshev polynomials.
result Negative momentum accelerates convergence locally but at a suboptimal rate.
A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraintsmath.OC
Unified analysis of first-order methods for smooth games using IQCs.
problem Certify convergence rates of first-order methods for smooth and strongly-monotone games.
method Adapted integral quadratic constraints (IQCs) to study first-order methods and derive tight upper bounds of convergence rates.
result First global convergence rate for the negative momentum method with iteration complexity.
Improved FTPL algorithm reduces regret in predictable minimax games.
problem Online learning and minimax games with predictable loss sequences.
method Optimistic modification of FTPL with dual regularization view.
result Tighter regret bounds for predictable sequences, accuracy.
Paper analyzes adversarial attacks and defenses using game theory.
problem Unclear conditions for optimal attacks and defenses in adversarial learning.
method Game-theoretic framework with locally linear decision boundary model.
result Fast Gradient Method attack and Randomized Smoothing defense form a Nash Equilibrium.
Gradient methods converge exponentially in concave network games.
problem Finding Nash equilibria in concave network zero-sum games.
method Gradient Ascent and Optimistic Gradient Ascent analyses.
result Exponential convergence rates in various game settings.
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.
Data-driven modeling increasingly requires to find a Nash equilibrium in multi-player games, e.g. when training GANs. In this paper, we analyse a new extra-gradient method for Nash equilibrium finding, that performs gradient extrapolations and updates on a random subset of players at each iteration. This approach prova…
New convergence guarantees for SGDA and SCO under expected co-coercivity.
problem Solving smooth games with stochastic gradient descent-ascent and consensus optimization.
method Introducing expected co-coercivity and proving convergence guarantees for SGDA and SCO.
result Linear convergence of SGDA and SCO to a neighborhood of the solution with constant step-size, and convergence to the exact solution with stepsize-switching rules.
The paper explores game-theoretic alignment of LLMs with human preferences, finding limitations and conditions.
problem Aligning LLMs with human preferences using game theory.
method Systematic study of payoff choices in a two-player zero-sum game for desirable alignment properties.
result Impossibility of preference matching in game-theoretic LLM alignment under standard assumptions.
Gradient Descent Ascent converges to von-Neumann solution in hidden zero-sum games.
problem Understanding dynamics of zero-sum games with hidden structure.
method Gradient Descent Ascent applied to hidden zero-sum games with specific convex-concave structure.
result Gradient Descent Ascent converges to von-Neumann solution in strictly convex-concave hidden games.
We study a wide class of non-convex non-concave min-max games that generalizes over standard bilinear zero-sum games. In this class, players control the inputs of a smooth function whose output is being applied to a bilinear zero-sum game. This class of games is motivated by the indirect nature of the competition in Ge…
Last-iterate guarantees for learning in co-coercive games under noisy feedback.
problem Learning in co-coercive games with noisy feedback.
method Vanilla stochastic gradient descent with a new noise model.
result Last-iterate bound of order for co-coercive games.
Mean Field Games applied to finance and economics.
problem Modeling large populations in financial and economic systems.
method Mean Field Game theory applied to specific financial and economic scenarios.
result New applications in bitcoin mining, energy markets, and macro-economics.
Paper presents a GMFG framework for large stochastic games.
problem Learning Nash Equilibrium in large stochastic games.
method Value-based and policy-based reinforcement learning algorithms with smoothed policies.
result Proposed algorithms GMF-V and GMF-P are efficient and robust in GMFG setting.
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,…
Study best-response learning dynamics in zero-sum polymatrix games under full and minimal information settings.
problem Learning dynamics in zero-sum polymatrix games under different information settings.
method Two-timescale learning dynamics combining smoothed best-response updates and TD-learning for estimating local payoff functions.
result Polynomial-time finite-sample guarantees for convergence to an ε-Nash equilibrium in the minimal information case.
This paper studies game-type credit default swaps that allow the protection buyer and seller to raise or reduce their respective positions once prior to default. This leads to the study of an optimal stopping game subject to early default termination. Under a structural credit risk model based on spectrally negative Le…
Mean-field game of mean-variance portfolio management with peer-based relative risk aversionq-fin.MF
New MFG model for MV portfolio management with peer-based risk aversion.
problem Time-inconsistent mean-variance portfolio management with peer-based risk aversion.
method Mean-field game, smooth regularization, fixed-point arguments, convergence analysis.
result Existence of mean-field equilibrium in time-inconsistent MFG.
On the Lego-Teichmuller gamemath.GT
For a smooth oriented surface S, denote by M(S) the set of all ways to represent S as a result of gluing together standard spheres with holes (``the Lego game''). In this paper we give a full set of simple moves and relations which turn M(S) into a connected and simply-connected 2-complex. Results of this kind were fir…
New control methods improve dynamic measure transport paths.
problem Improving paths for dynamic measure transport.
method Connecting mean-field games to optimization problems for learning paths, advocating for smoothness of velocities.
result Our method recovers more efficient and smooth transport models compared to untilted paths.
This paper concerns the recursive utility maximization problem under partial information. We first transform our problem under partial information into the one under full information. When the generator of the recursive utility is concave, we adopt the variational formulation of the recursive utility which leads to a s…
Study on convergence of Langevin dynamics for zero-sum games in probability distributions.
problem Analyzing convergence of Langevin dynamics for zero-sum games in probability distributions.
method Proved exponential and biased convergence guarantees for mean-field and finite-particle min-max Langevin dynamics.
result Explicit iteration complexity for finite-particle algorithms to approximate equilibrium distributions.
GAME improves matrix completion by considering subgroup-specific latent structures.
problem Heterogeneous data with overlapping categories, smoothing away subgroup-specific variation.
method Group-Aware Matrix Estimation (GAME) with overlapping nuclear-norm penalties.
result GAME outperforms global low-rank estimators in structured missingness regimes.
We consider a discounted reward control problem in continuous time stochastic environment where the discount rate might be an unbounded function of the control process. We provide a set of general assumptions to ensure that there exists a smooth classical solution to the corresponding HJB equation. Moreover, some verif…
Robust SVM optimization in Banach spaces tackles classification uncertainty.
problem Binary classification in Banach spaces with uncertainty.
method Generalization of SVM results to Banach spaces, Representer Theorem, strong duality, Nash equilibrium formulation.
result Generalization of SVM results to Banach spaces, including Representer Theorem and strong duality.
Methods from convex optimization are widely used as building blocks for deep learning algorithms. However, the reasons for their empirical success are unclear, since modern convolutional networks (convnets), incorporating rectifier units and max-pooling, are neither smooth nor convex. Standard guarantees therefore do n…
Smooth calibration improves forecast reliability even with leaked information.
problem Improving forecast reliability with leaked information.
method Combining nearby forecasts to ensure smooth calibration, which can be guaranteed by deterministic procedures.
result Smooth calibration can be guaranteed by deterministic procedures even with leaked forecasts, and it yields uncoupled finite-memory dynamics in games.
Content Based Player and Game Interaction Model for Game Recommendation in the Cold Start settingcs.IR
Paper presents content-based models for game recommendation in cold start scenarios.
problem Cold start problem in game recommendation where new games and players have no historical data.
method Uses survey data to develop content-based interaction models that generalize to new games, players, and both.
result Content models outperform collaborative filtering in predicting new interactions.
In this work, we ask the following question: Can visual analogies, learned in an unsupervised way, be used in order to transfer knowledge between pairs of games and even play one game using an agent trained for another game? We attempt to answer this research question by creating visual analogies between a pair of game…
This paper considers a time-inconsistent stopping problem in which the inconsistency arises from non-constant time preference rates. We show that the smooth pasting principle, the main approach that has been used to construct explicit solutions for conventional time-consistent optimal stopping problems, may fail under …
Potential games, originally introduced in the early 1990's by Lloyd Shapley, the 2012 Nobel Laureate in Economics, and his colleague Dov Monderer, are a very important class of models in game theory. They have special properties such as the existence of Nash equilibria in pure strategies. This note introduces graphical…
Alt-GDA outperforms Sim-GDA in minimax games with near-optimal local convergence.
problem Minimax optimization convergence rate comparison
method Alternating Gradient Descent-Ascent (Alt-GDA) vs. Simultaneous Gradient Descent-Ascent (Sim-GDA)
result Alt-GDA achieves near-optimal local convergence rate for strongly convex-strongly concave problems, while Sim-GDA converges slower.
IGGP learns game rules from varying quality game play, finding no overall trend.
problem Learn game rules from varying quality game play.
method Used Sancho's intelligent game traces and ILP systems (Metagol, Aleph, ILASP) to induce game rules from traces of varying quality and volume.
result No overall trend in accuracy of learned game rules from varying quality and volume of training data.
We consider the problem of minimizing a smooth convex function by reducing the optimization to computing the Nash equilibrium of a particular zero-sum convex-concave game. Zero-sum games can be solved using online learning dynamics, where a classical technique involves simulating two no-regret algorithms that play agai…
Improved convergence rates for saddle-point optimization algorithms.
problem Understanding last-iterate convergence rates for saddle-point optimization algorithms in constrained settings.
method Expanding the understanding of last-iterate convergence for Optimistic Gradient Descent Ascent (OGDA) and Optimistic Multiplicative Weights Update (OMWU) in the constrained setting.
result Linear last-iterate convergence achieved with a universal constant learning rate for OMWU in bilinear games over the simplex.
We present a new general board game (GBG) playing and learning framework. GBG defines the common interfaces for board games, game states and their AI agents. It allows one to run competitions of different agents on different games. It standardizes those parts of board game playing and learning that otherwise would be t…
Just as war is sometimes fallaciously represented as a zero sum game -- when in fact war is a negative sum game - stock market trading, a positive sum game over time, is often erroneously represented as a zero sum game. This is called the "zero sum fallacy" -- the erroneous belief that one trader in a stock market exch…
The existence of stationary Markov perfect equilibria in stochastic games is shown under a general condition called "(decomposable) coarser transition kernels". This result covers various earlier existence results on correlated equilibria, noisy stochastic games, stochastic games with finite actions and state-independe…
The Linking-Unlinking Gamemath.GT
Combinatorial two-player games have recently been applied to knot theory. Examples of this include the Knotting-Unknotting Game and the Region Unknotting Game, both of which are played on knot shadows. These are turn-based games played by two players, where each player has a separate goal to achieve in order to win the…
Dynkin Games and Israeli Optionsq-fin.PR
We start briefly surveying research on optimal stopping games since their introduction by E.B.Dynkin more than 40 years ago. Recent renewed interest to dynkin's games is due, in particular, to the study of Israeli (game) options introduced in 2000. We discuss the work on these options and related derivative securities …
Educational game on crypto investment helps students grasp macroeconomics.
problem Weak connections between microeconomic decision-making and macroeconomic concepts in classroom games.
method Design and study of an educational game on cryptocurrency investment.
result Engages students in understanding macroeconomics through incentivized individual investment decisions.