Monotone bargaining is Nash-solvable
share
Given two finite ordered sets A = {a_1, ..., a_m} and B = {b_1, ..., b_n}, introduce the set of m n outcomes of the game O = {(a, b) | a ∈ A, b ∈ B} = {(a_i, b_j) | i ∈ I = {1, ..., m}, j ∈ J = {1, ..., n}. 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 = G_m,n: X × Y → 2^O is a game correspondence. Choose an arbitrary deal g(x,y) ∈ G(x,y) to obtained a mapping g : X × Y → O, which is a game form. We will show that each such game form is tight and, hence, Nash-solvable, that is, for any pair u = (u_A, u_B) of utility functions u_A : O → R of Alice and u_B: O → R of Bob, the obtained monotone bargaining game (g, u) has at least one Nash equilibrium in pure strategies. Moreover, the same equilibrium can be chosen for all selections g(x,y) ∈ G(x,y). We also obtain an efficient algorithm that determines such an equilibrium in time linear in m n, although the numbers of strategies |X| = m+n-1m and |Y| = m+n-1n are exponential in m n. Our results show that, somewhat surprising, the players have no need to hide or randomize their bargaining strategies, even in the zero-sum case.
READ FULL TEXT