Monotone bargaining is Nash-solvable
Given two finite ordered sets A and B, let O=A×B denote the set of outcomes of the following game: Two players, Alice and Bob, have the sets of strategies X and Y that consist of all monotone non-decreasing mappings x:A→B and y:B→A, respectively. It is easily seen that each pair (x,y)∈X×Y produces at least one deal, that is, an outcome (a,b)∈O such that x(a)=b and y(b)=a. Denote by G(x,y)⊆O the set of all such deals related to (x,y). The obtained mapping G:X×Y→2O is a game correspondence. Choose an arbitrary deal g(x,y)∈G(x,y) to obtain a mapping g:X×Y→O, which is a game form. We show that each such game form is tight and, hence, Nash-solvable, that is, for any pair u=(uA,uB) of utility functions of Alice and Bob, the obtained monotone bargaining game (g,u) has at least one Nash equilibrium (x,y) in pure strategies. Moreover, |G(x,y)|=1 and, hence, (x,y) is a Nash equilibrium in game (g,u) for all g∈G. We also obtain an efficient algorithm that determines such an equilibrium in time quadratic in |O|, although the numbers of strategies are exponential in |O|. Our results show that, somewhat surprisingly, the players have no need to hide or randomize their bargaining strategies, even in the zero-sum case.