Monotone bargaining is Nash-solvable

Abstract: Given two finite ordered sets

A = a_{1}, l d o t s, a_{m}

and

B = b_{1}, l d o t s, b_{n}

, introduce the set of

m n

outcomes of the game

. Two players, Alice and Bob, have the sets of strategies

X

and

Y

that consist of all monotone non-decreasing mappings

x : A i g h t a r r o w B

and

y : B i g h t a r r o w A

, respectively. It is easily seen that each pair

(x, y) i n X i m e s Y

produces at least one {em deal}, that is, an outcome

(a, b) i n O

such that

x (a) = b

and

y (b) = a

. Denote by

G (x, y) s u b s e t e q O

the set of all such deals related to

(x, y)

. The obtained mapping

G = G_{m, n} : X i m e s Y i g h t a r r o w 2^{O}

is a game correspondence. Choose an arbitrary deal

g (x, y) i n G (x, y)

to obtained a mapping

g : X i m e s Y i g h t a r r o w 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 i g h t a r r o w m a t h b b R

of Alice and

u_{B} : O i g h t a r r o w m a t h b b 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) i n 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

and

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.

Recommendations

Cites Work

Cited In (7)

Uses Software

This page was built for publication: Monotone bargaining is Nash-solvable