Ambitropical convexity: The geometry of fixed point sets of Shapley operators - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

Ambitropical convexity: The geometry of fixed point sets of Shapley operators

(1) , (1) , (2)
1
2

Abstract

Shapley operators of undiscounted zero-sum two-player games are order-preserving maps that commute with the addition of a constant. We characterize the fixed point sets of Shapley operators, in finite dimension (i.e., for games with a finite state space). Some of these characterizations are of a lattice theoretical nature, whereas some other rely on metric or tropical geometry. More precisely, we show that fixed point sets of Shapley operators are special instances of hyperconvex spaces: they are sup-norm non-expansive retracts, and also lattices in the induced partial order. Moreover, they retain properties of convex sets, with a notion of convex hull defined only up to isomorphism. For deterministic games with finite action spaces, these fixed point sets are supports of polyhedral complexes, with a cell decomposition attached to stationary strategies of the players, in which each cell is an alcoved polyhedron of $A_n$ type. We finally provide an explicit local representation of the latter fixed point sets, as polyhedral fans canonically associated to lattices included in the Boolean hypercube.

Dates and versions

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

Identifiers

Cite

Marianne Akian, Stephane Gaubert, Sara Vannucci. Ambitropical convexity: The geometry of fixed point sets of Shapley operators. 2021. ⟨hal-03504873⟩
35 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More