Akian, M., Gaubert, S., & Hochart, A. (2020). A Game Theory Approach To The Existence And Uniqueness Of Nonlinear PerronFrobenius Eigenvectors. Discret. Contin. Dyn. Syst., 40(1), 207–231.
Abstract: We establish a generalized PerronFrobenius theorem, based on a combinatorial criterion which entails the existence of an eigenvector for any nonlinear orderpreserving and positively homogeneous map f acting on the open orthant R>0(n). This criterion involves dominions, i.e., sets of states that can be made invariant by one player in a twoperson game that only depends on the behavior of f “at infinity”. In this way, we characterize the situation in which for all alpha, beta > 0, the “slice space” Salpha(beta) :={x is an element of R>0(n) vertical bar alpha x <= f(x) <= beta x} is bounded in Hilbert's projective metric, or, equivalently, for all uniform perturbations g of f, all the orbits of g are bounded in Hilbert's projective metric. This solves a problem raised by Gaubert and Gunawardena (Trans. AMS, 2004). We also show that the uniqueness of an eigenvector is characterized by a dominion condition, involving a different game depending now on the local behavior of f near an eigenvector. We show that the dominion conditions can be verified by directed hypergraph methods. We finally illustrate these results by considering specific classes of nonlinear maps, including Shapley operators, generalized means and nonnegative tensors.

Carbonnel, C., Romero, M., & Zivny, S. (2020). PointWidth and MaxCSPs. ACM Trans. Algorithms, 16(4), 28 pp.
Abstract: The complexity of (unboundedarity) MaxCSPs under structural restrictions is poorly understood. The two most general hypergraph properties known to ensure tractability of MaxCSPs, betaacyclicity and bounded (incidence) MIMwidth, are incomparable and lead to very different algorithms. We introduce the framework of point decompositions for hypergraphs and use it to derive a new sufficient condition for the tractability of (structurally restricted) MaxCSPs, which generalises both bounded MIMwidth and betaacyclicity. On the way, we give a new characterisation of bounded MIMwidth and discuss other hypergraph properties which are relevant to the complexity of MaxCSPs, such as betahypertreewidth.
