Tropical linear regression and mean payoff games: or, how to measure the distance to equilibria - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

Tropical linear regression and mean payoff games: or, how to measure the distance to equilibria

(1) , (1) , (1) , (1)
1
Marianne Akian
  • Function : Author
  • PersonId : 830429
Stéphane Gaubert
Omar Saadi
  • Function : Author
  • PersonId : 1036751
Yang Qi
  • Function : Author
  • PersonId : 1086866

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.

Dates and versions

hal-03504875 , version 1 (29-12-2021)

Identifiers

Cite

Marianne Akian, Stéphane Gaubert, Omar Saadi, Yang Qi. Tropical linear regression and mean payoff games: or, how to measure the distance to equilibria. 2021. ⟨hal-03504875⟩
37 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More