Tropical polyhedra are equivalent to mean payoff games

Details Tropical polyhedra are equivalent to mean payoff games Tropical polyhedra are equivalent to mean payoff games

2009-12-12

arxiv.org/abs/0912.2462v3

Mathematics

Combinatorics

28 pages, 5 figures; v2: updated references, added background materials and illustrations; v3: minor improvements, references

Scientific paper

10.1142/S0218196711006674

We show that several decision problems originating from max-plus or tropical convexity are equivalent to zero-sum two player game problems. In particular, we set up an equivalence between the external representation of tropical convex sets and zero-sum stochastic games, in which tropical polyhedra correspond to deterministic games with finite action spaces. Then, we show that the winning initial positions can be determined from the associated tropical polyhedron. We obtain as a corollary a game theoretical proof of the fact that the tropical rank of a matrix, defined as the maximal size of a submatrix for which the optimal assignment problem has a unique solution, coincides with the maximal number of rows (or columns) of the matrix which are linearly independent in the tropical sense. Our proofs rely on techniques from non-linear Perron-Frobenius theory.

Affiliated with

Also associated with

No associations

Rating

Tropical polyhedra are equivalent to mean payoff games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Tropical polyhedra are equivalent to mean payoff games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tropical polyhedra are equivalent to mean payoff games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-556467