2021/06/03 by Marianne Akian, Stéphane Gaubert, Akian, Marianne +6
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Combinatorics (math.CO) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #cs.GT #math.CO #math.OC
paper · pdf · doi:10.48550/arxiv.2106.01930
openalex publication_date 2021/06/03 · arxiv created 2021/06/21 · arxiv updated 2021/06/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.