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

DOI10.1137/21M1428297MaRDI QIDQ6101017zbMATH OpenFDO

Authors Marianne Akian, Stéphane Gaubert, 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

auction.best approximationequilibriainner radiusmean payoff gamesregressionTropical geometrytropical linear spaces

Mathematics Subject Classification ID

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

Abstract: We study a tropical linear regression problem consisting in finding the best approximation of a set of points by a tropical hyperplane. We establish a strong duality theorem, showing that the value of this problem coincides with the maximal radius of a Hilbert's ball included in a tropical polyhedron. We also show that this regression problem is polynomial-time equivalent to mean payoff games. We illustrate our results by solving an inverse problem from auction theory. In this setting, a tropical hyperplane represents the set of equilibrium prices. Tropical linear regression allows us to quantify the distance of a market to the set of equilibria, and infer secret preferences of a decision maker.

Recommendations

• Tropical linear-fractional programming and parametric mean payoff games
• Tropical pseudolinear and pseudoquadratic optimization as parametric mean-payoff games
• Tropical polyhedra are equivalent to mean payoff games
• Tropical Complementarity Problems and Nash Equilibria
• The empirical content of games with bounded regressors
• A note on the approximation of mean-payoff games
• Selection of equilibria in a linear quadratic mean-field game
• scientific article; zbMATH DE number 3883389
• Tropical polar cones, hypergraph transversals, and mean payoff games
• Linear-quadratic mean-field-type games: a direct method

Cites work

• \(l_\infty\)-approximation via subdominants.
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• A convergent hierarchy of non-linear eigenproblems to compute the joint spectral radius of nonnegative matrices
• A tropical isoperimetric inequality
• Affine Buildings and Tropical Convexity
• An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games
• Best approximation in max-plus semimodules
• Bribery and Favoritism by Auctioneers in Sealed-Bid Auctions
• Bribing in first-price auctions
• Complexity of tropical and MIN-plus linear prevarieties
• Convexity and log convexity for the spectral radius
• Convexity in tree spaces
• Discrete convexity and equilibria in economies with indivisible goods and money
• Duality and separation theorems in idempotent semimodules.
• Generators, extremals and bases of max cones
• scientific article; zbMATH DE number 4081342 (Why is no real title available?)
• scientific article; zbMATH DE number 627763 (Why is no real title available?)
• scientific article; zbMATH DE number 1012624 (Why is no real title available?)
• scientific article; zbMATH DE number 7023671 (Why is no real title available?)
• scientific article; zbMATH DE number 6437647 (Why is no real title available?)
• scientific article; zbMATH DE number 5019906 (Why is no real title available?)
• Invariant Half-Lines of Nonexpansive Piecewise-Linear Transformations
• L-infinity optimization to Bergman fans of matroids with an application to phylogenetics
• Linear independence over tropical semirings and beyond
• Max-algebra: The linear algebra of combinatorics?
• Max-linear systems. Theory and algorithms.
• Max-plus definite matrix closures and their eigenspaces
• Minimax algebra
• Non-archimedean amoebas and tropical varieties
• On the rate of convergence of Krasnosel'skiĭ-Mann iterations and their connection with sums of Bernoullis
• Positional strategies for mean payoff games
• Product-mix auctions and tropical geometry
• Repeated Games
• Sparsity in max-plus algebra and systems
• Stiefel tropical linear spaces
• Stochastic games
• Stochastic Games with Perfect Information and Time Average Payoff
• Subdominant matroid ultrametrics
• The complexity of mean payoff games on graphs
• The Minkowski theorem for max-plus convex sets
• The number of extreme points of tropical polyhedra
• The Perron-Frobenius theorem for homogeneous, monotone functions
• The tropical Grassmannian
• The Tropical Rank of a Tropical Matrix
• Topical and sub-topical functions, downward sets and abstract convexity
• Tropical convexity
• Tropical polyhedra are equivalent to mean payoff games
• Tropical principal component analysis and its application to phylogenetics
• Understanding preferences: ``demand types, and the existence of equilibrium with indivisibilities
• What Tropical Geometry Tells Us about the Complexity of Linear Programming

Cited in

(7)

• Tropical polyhedra are equivalent to mean payoff games
• Tropical polar cones, hypergraph transversals, and mean payoff games
• Plücker coordinates of the best-fit Stiefel tropical linear space to a mixture of Gaussian distributions
• Minimal representations of tropical rational functions
• Tropical convexity in location problems
• Tropical gradient descent
• Tropical geometric tools for machine learning: the TML package

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

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