Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria

DOI10.1137/21m1428297zbMath1519.14062arXiv2106.01930MaRDI QIDQ6101017

Stéphane Gaubert, Marianne Akian, Yang Qi, Omar Saadi

Publication date: 31 May 2023

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

best approximationregressionequilibriainner radiusmean payoff gamestropical linear spacesTropical geometryauction.

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26) Dynamic games (91A25) Applications of tropical geometry (14T90)

Related Items (1)

Plücker coordinates of the best-fit Stiefel tropical linear space to a mixture of Gaussian distributions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bribing in first-price auctions
• Stiefel tropical linear spaces
• The number of extreme points of tropical polyhedra
• Best approximation in max-plus semimodules
• A convergent hierarchy of non-linear eigenproblems to compute the joint spectral radius of nonnegative matrices
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• Max-plus definite matrix closures and their eigenspaces
• The Minkowski theorem for max-plus convex sets
• Generators, extremals and bases of max cones
• Convexity and log convexity for the spectral radius
• Positional strategies for mean payoff games
• Minimax algebra
• The complexity of mean payoff games on graphs
• Duality and separation theorems in idempotent semimodules.
• \(l_\infty\)-approximation via subdominants.
• Tropical principal component analysis and its application to phylogenetics
• A tropical isoperimetric inequality
• Subdominant matroid ultrametrics
• Max-algebra: The linear algebra of combinatorics?
• Tropical convexity
• On the rate of convergence of Krasnosel'skiĭ-Mann iterations and their connection with sums of Bernoullis
• Sparsity in max-plus algebra and systems
• Complexity of tropical and MIN-plus linear prevarieties
• TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES
• Repeated Games
• Linear independence over tropical semirings and beyond
• Bribery and Favoritism by Auctioneers in Sealed-Bid Auctions
• Non-archimedean amoebas and tropical varieties
• An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games
• Max-linear Systems: Theory and Algorithms
• The Tropical Rank of a Tropical Matrix
• Invariant Half-Lines of Nonexpansive Piecewise-Linear Transformations
• Topical and sub-topical functions, downward sets and abstract convexity
• The Perron-Frobenius theorem for homogeneous, monotone functions
• The tropical Grassmannian
• Product-Mix Auctions and Tropical Geometry
• What Tropical Geometry Tells Us about the Complexity of Linear Programming
• L-Infinity Optimization to Bergman Fans of Matroids with an Application to Phylogenetics
• Understanding Preferences: “Demand Types”, and the Existence of Equilibrium With Indivisibilities
• Convexity in Tree Spaces
• Affine Buildings and Tropical Convexity
• Stochastic Games with Perfect Information and Time Average Payoff
• Stochastic games
• Discrete convexity and equilibria in economies with indivisible goods and money

This page was built for publication: Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria