1 of 55

Decentralized multilateral bargaining

1

Yuan Ju (University of York)

Juan Vidal-Puga (Universidade de Vigo)

2 of 55

Motivation and contribution

  1. A decentralized mechanism of multilateral negotiation:
    1. Generalizing the alternating-offer bargaining to n-player coalitional environment
    2. Counteroffers, partial agreements, local unanimity, no one excluded
  2. Implement the Shapley NTU value
  3. A solution theory synthesizes the Nash solution and Shapley value

2

3 of 55

Outline

  • Introduction: Nash program and NTU games
  • Non-cooperative game and the Shapley NTU value
  • Conclusion

3

4 of 55

Section 1: Introduction

Nash program and NTU games

4

5 of 55

Game theory

Cooperative game theory

Non-cooperative game theory

5

6 of 55

Game theory

Cooperative game theory

Non-cooperative game theory

6

  • Implementation
  • Nash program: Survey by Serrano (2005, 2021)
  • Non-cooperative approach

7 of 55

NTU games

7

Transferable utility (TU) games

  • Partial agreements
  • Transferable utility
  • Shapley value (1953)

8 of 55

NTU games

8

Transferable utility (TU) games

  • Partial agreements
  • Transferable utility
  • Shapley value (1953)

Bargaining problems

  • Unanimity required
  • Non-transferable utility
  • Nash solution (1950)

9 of 55

NTU games

9

Non transferable utility (NTU) games

  • Partial agreements
  • Non-transferable utility
  • Harsanyi value (1963), Shapley NTU value (1969), consistent value (1989, 1992)

Transferable utility (TU) games

  • Partial agreements
  • Transferable utility
  • Shapley value (1953)

Bargaining problems

  • Unanimity required
  • Non-transferable utility
  • Nash solution (1950)

10 of 55

The model

A Non-Transferable Utility (NTU) game is a pair (N, V) where:

  • N = {1, 2, ..., n} is a set of players
  • V: S βŠ† N⟢V(S)βŠ‚β„S correspondence satisfying:
    • V(S) non-empty, closed, convex, comprehensive, and bounded-above.
    • Superadditivity: V(S)xV(T) βŠ‚ V(S U T) for all S, T βŠ‚ N, S ∩ T = βˆ….
    • V(S) nonlevel: For each x in the frontier of V(S), there exists a unique normalized vector πœ† orthogonal to V(S) on x with all its coordinates positive.

A rule is a function 𝛷 that assigns to each NTU game (N,V) a payoff allocation 𝛷(N,V) ∈ V(N).

10

11 of 55

Example

Pure exchange economy with three players.

Coffee beans and water are required to prepare coffee. Sugar is optional.

  • Player 1 has coffee beans, and prefers coffee with sugar.
  • Player 2 has water.
  • Player 3 has sugar.

​

​

12 of 55

Example

Pure exchange economy with three players.

Coffee beans and water are required to prepare coffee. Sugar is optional.

  • Player 1 has coffee beans, and prefers coffee with sugar.
  • Player 2 has water.
  • Player 3 has sugar.

​

​

V({i}) = {x ∈ ℝ{i}: xi ≀ 0}

V({1,2}) = {x ∈ ℝ{1,2} : 2x1 + x2 ≀ 1}

V({1,3}) = {x ∈ ℝ{1,3} : x1, x3 ≀ 0}

V({2,3}) = {x ∈ ℝ{2,3} : x2, x3 ≀ 0}

V(N) = {x ∈ ℝN : x1 + x2 + x3 ≀ 1}

13 of 55

The model

A Transferable Utility (TU) game is a pair (N, v) where:

  • N = {1, 2, ..., n} is a set of players
  • v: S βŠ† N⟢v(S)βˆˆβ„ correspondence satisfying v(βˆ…) = 0.

​

​

13

14 of 55

The model

A Transferable Utility (TU) game is a pair (N, v) where:

  • N = {1, 2, ..., n} is a set of players
  • v: S βŠ† N⟢v(S)βˆˆβ„ correspondence satisfying v(βˆ…) = 0.

Shapley value for TU games: It can be obtained from many different approaches:

  • Axiomatic
  • Marginalistic
  • Potential
  • Dividends

​

14

15 of 55

The model

A Transferable Utility (TU) game is a pair (N, v) where:

  • N = {1, 2, ..., n} is a set of players
  • v: S βŠ† N⟢v(S)βˆˆβ„ correspondence satisfying v(βˆ…) = 0.

Shapley value for TU games: It can be obtained from many different approaches:

  • Axiomatic (too loose)
  • Marginalistic
  • Potential (too strict)
  • Dividends

​

15

16 of 55

The model

A Transferable Utility (TU) game is a pair (N, v) where:

  • N = {1, 2, ..., n} is a set of players
  • v: S βŠ† N⟢v(S)βˆˆβ„ correspondence satisfying v(βˆ…) = 0.

Shapley value for TU games:

​

16

Shi(N,v) = βˆ‘SβŠ‚N:i∈S dv(S)/|S|

where dv(S)βˆˆβ„ are the Harsanyi dividends of v.

​

Shi(N,v) = βˆ‘Ο€βˆˆΞ  miΟ€(v)/|Ξ |

where mΟ€(v)βˆˆβ„N are the marginal contributions vectors of v under order Ο€.

17 of 55

TU games

​

​

Any TU game is also an NTU game.

17

18 of 55

TU games

​

​

Any TU game is also an NTU game.

​

18

v({i})=0

v({1,2}) = 6

v({1,3}) = 6

v({2,3}) = 0

v(N) = 6

19 of 55

TU games

​

​

Any TU game is also an NTU game.

​

19

v({i})=0

v({1,2}) = 6

v({1,3}) = 6

v({2,3}) = 0

v(N) = 6

Sh(N,v) = (4,1,1)

20 of 55

TU games

​

​

Any TU game is also an NTU game.

20

v({i})=0

v({1,2}) = 6

v({1,3}) = 6

v({2,3}) = 0

v(N) = 6

V({i}) = {x ∈ ℝ{i}: xi ≀ 0}

V({1,2}) = {x ∈ ℝ{1,2} : x1 + x2 ≀ 6}

V({1,3}) = {x ∈ ℝ{1,3} : x1 + x3 ≀ 6}

V({2,3}) = {x ∈ ℝ{2,3} : x2 + x3 ≀ 0}

V(N) = {x ∈ ℝN : x1 + x2 + x3 ≀ 6}

Sh(N,v) = (4,1,1)

21 of 55

TU games

​

​

Any TU game is also an NTU game.

21

v({i})=0

v({1,2}) = 6

v({1,3}) = 6

v({2,3}) = 0

v(N) = 6

V({i}) = {x ∈ ℝ{i}: xi ≀ 0}

V({1,2}) = {x ∈ ℝ{1,2} : x1 + x2 ≀ 6}

V({1,3}) = {x ∈ ℝ{1,3} : x1 + x3 ≀ 6}

V({2,3}) = {x ∈ ℝ{2,3} : x2 + x3 ≀ 0}

V(N) = {x ∈ ℝN : x1 + x2 + x3 ≀ 6}

Sh(N,v) = (4,1,1)

Sh(N,V) = (4,1,1)

22 of 55

TU games

​

​

Any TU game is also an NTU game.

If the utility is interchangeable at a fixed rate, the game is still (essentially) TU:

22

v({i})=0

v({1,2}) = 6

v({1,3}) = 6

v({2,3}) = 0

v(N) = 6

V({i}) = {x ∈ ℝ{i}: xi ≀ 0}

V({1,2}) = {x ∈ ℝ{1,2} : x1 + x2 ≀ 6}

V({1,3}) = {x ∈ ℝ{1,3} : x1 + x3 ≀ 6}

V({2,3}) = {x ∈ ℝ{2,3} : x2 + x3 ≀ 0}

V(N) = {x ∈ ℝN : x1 + x2 + x3 ≀ 6}

V({i}) = {x ∈ ℝ{i}: πœ†ixi ≀ 0}

V({1,2}) = {x ∈ ℝ{1,2} : πœ†1x1 + πœ†2x2 ≀ 6}

V({1,3}) = {x ∈ ℝ{1,3} : πœ†1x1 + πœ†3x3 ≀ 6}

V({2,3}) = {x ∈ ℝ{2,3} : πœ†2x2 + πœ†3x3 ≀ 0}

V(N) = {x ∈ ℝN : πœ†1x1 + πœ†2x2 + πœ†2x3 ≀ 6}

Sh(N,v) = (4,1,1)

Sh(N,V) = (4,1,1)

23 of 55

TU games

​

​

Any TU game is also an NTU game.

If the utility is interchangeable at a fixed rate, the game is still (essentially) TU:

23

v({i})=0

v({1,2}) = 6

v({1,3}) = 6

v({2,3}) = 0

v(N) = 6

V({i}) = {x ∈ ℝ{i}: xi ≀ 0}

V({1,2}) = {x ∈ ℝ{1,2} : x1 + x2 ≀ 6}

V({1,3}) = {x ∈ ℝ{1,3} : x1 + x3 ≀ 6}

V({2,3}) = {x ∈ ℝ{2,3} : x2 + x3 ≀ 0}

V(N) = {x ∈ ℝN : x1 + x2 + x3 ≀ 6}

V({i}) = {x ∈ ℝ{i}: πœ†ixi ≀ 0}

V({1,2}) = {x ∈ ℝ{1,2} : πœ†1x1 + πœ†2x2 ≀ 6}

V({1,3}) = {x ∈ ℝ{1,3} : πœ†1x1 + πœ†3x3 ≀ 6}

V({2,3}) = {x ∈ ℝ{2,3} : πœ†2x2 + πœ†3x3 ≀ 0}

V(N) = {x ∈ ℝN : πœ†1x1 + πœ†2x2 + πœ†2x3 ≀ 6}

Sh(N,v) = (4,1,1)

Sh(N,V) = (4,1,1)

Sh(N,V) = (4/πœ†1,1/πœ†2,1/πœ†3)

24 of 55

Money as utility

  1. We give players money with exchange rates given by some πœ†βˆˆπš«N.

24

25 of 55

Money as utility

  • We give players money with exchange rates given by some πœ†βˆˆπš«N.
  • With such money acting as (transferable) utility, we have a TU game (N,vπœ†).

25

26 of 55

Money as utility

  • We give players money with exchange rates given by some πœ†βˆˆπš«N.
  • With such money acting as (transferable) utility, we have a TU game (N,vπœ†).
  • We compute Sh(N,vπœ†) using with this πœ† either the Harsanyi procedure or the average of marginal contributions vectors.

26

27 of 55

Money as utility

  • We give players money with exchange rates given by some πœ†βˆˆπš«N.
  • With such money acting as (transferable) utility, we have a TU game (N,vπœ†).
  • We compute Sh(N,vπœ†) using with this πœ† either the Harsanyi procedure or the average of marginal contributions vectors.
  • If Sh(N,vπœ†) ∈ V(N), we say that Sh(N,vπœ†) is a Shapley NTU value of (N,V).

27

28 of 55

The Shapley NTU value (Shapley, 1969)

Pure exchange economy with three players.

Coffee beans and water are required to prepare coffee. Sugar is optional.

  • Player 1 has coffee beans, and prefers coffee with sugar.
  • Player 2 has water.
  • Player 3 has sugar.

28

29 of 55

Money as utility (alternative 1)

  • We give players money with exchange rates given by (πœ†S)SβŠ†N with πœ†S∈𝚫S for all SβŠ†N.οΏ½(Exchange rates depend on which players participate).

29

30 of 55

Money as utility (alternative 1)

  • We give players money with exchange rates given by (πœ†S)SβŠ†N with πœ†S∈𝚫S for all SβŠ†N.οΏ½(Exchange rates depend on which players participate).
  • With such money acting as (transferable) utility in each coalition, we can use the Harsanyi procedure with πœ†N in order to compute a payoff allocation H(N,vπœ†).

30

31 of 55

Money as utility (alternative 1)

  • We give players money with exchange rates given by (πœ†S)SβŠ†N with πœ†S∈𝚫S for all SβŠ†N.οΏ½(Exchange rates depend on which players participate).
  • With such money acting as (transferable) utility in each coalition, we can use the Harsanyi procedure with πœ†N in order to compute a payoff allocation H(N,vπœ†).
  • If H(N,vπœ†) ∈ V(N), we say that H(N,vπœ†) is a Harsanyi value of (N,V).

31

32 of 55

The Harsanyi value (Harsanyi, 1963)

Pure exchange economy with three players.

Coffee beans and water are required to prepare coffee. Sugar is optional.

  • Player 1 has coffee beans, and prefers coffee with sugar.
  • Player 2 has water.
  • Player 3 has sugar.

33 of 55

Money as utility (alternative 2)

  • We give players money with exchange rates given by (πœ†S)SβŠ†N with πœ†S∈𝚫S for all SβŠ†N.οΏ½(Exchange rates depend on which players participate).

33

34 of 55

Money as utility (alternative 2)

  • We give players money with exchange rates given by (πœ†S)SβŠ†N with πœ†S∈𝚫S for all SβŠ†N.οΏ½(Exchange rates depend on which players participate).
  • With such money acting as (transferable) utility in each coalition, we can use the average of marginal contributions vectors with each πœ†S in order to compute a payoff allocation C(N,vπœ†).

34

35 of 55

Money as utility (alternative 2)

  • We give players money with exchange rates given by (πœ†S)SβŠ†N with πœ†S∈𝚫S for all SβŠ†N.οΏ½(Exchange rates depend on which players participate).
  • With such money acting as (transferable) utility in each coalition, we can use the average of marginal contributions vectors with each πœ†S in order to compute a payoff allocation C(N,vπœ†).
  • If C(N,vπœ†) ∈ V(N), we say that C(N,vπœ†) is a consistent value of (N,V).

35

36 of 55

The consistent value (Maschler and Owen, 1992)

Pure exchange economy with three players.

Coffee beans and water are required to prepare coffee. Sugar is optional.

  • Player 1 has coffee beans, and prefers coffee with sugar.
  • Player 2 has water.
  • Player 3 has sugar.

37 of 55

Generalizations of the Shapley value

37

​

Exchange rate

Coalition dependent (πœ†S)SβŠ†N, πœ†S∈𝚫S βˆ€SβŠ†N

Constant πœ†βˆˆπš«N

procedure

Harsanyi dividends

πœ†S

​

​

πœ†N

​

average of marginal contributions vectors

​

38 of 55

Generalizations of the Shapley value

38

​

Exchange rate

Coalition dependent (πœ†S)SβŠ†N, πœ†S∈𝚫S βˆ€SβŠ†N

Constant πœ†βˆˆπš«N

procedure

Harsanyi dividends

πœ†S

​

Shapley NTU value

πœ†N

​

average of marginal contributions vectors

​

39 of 55

Generalizations of the Shapley value

39

​

Exchange rate

Coalition dependent (πœ†S)SβŠ†N, πœ†S∈𝚫S βˆ€SβŠ†N

Constant πœ†βˆˆπš«N

procedure

Harsanyi dividends

πœ†S

​

Shapley NTU value

πœ†N

Harsanyi value

average of marginal contributions vectors

​

40 of 55

Generalizations of the Shapley value

40

​

Exchange rate

Coalition dependent (πœ†S)SβŠ†N, πœ†S∈𝚫S βˆ€SβŠ†N

Constant πœ†βˆˆπš«N

procedure

Harsanyi dividends

πœ†S

​

Shapley NTU value

πœ†N

Harsanyi value

average of marginal contributions vectors

Consistent value

41 of 55

Generalizations of the Shapley value

41

​

Exchange rate

Coalition dependent (πœ†S)SβŠ†N, πœ†S∈𝚫S βˆ€SβŠ†N

Constant πœ†βˆˆπš«N

procedure

Harsanyi dividends

πœ†S

(Consistent Harsanyi value)

Shapley NTU value

πœ†N

Harsanyi value

average of marginal contributions vectors

Consistent value

42 of 55

Section 2

Non-cooperative game

42

43 of 55

Implementation of the Nash solution in bargaining games

  • Nash (Econometrica, 1953)
  • Rubinstein (Econometrica, 1982)
  • van Damme (JET, 1986)
  • Binmore (β€œThe economics of bargaining”, ed. by Binmore and Dasgupta, 1987)
  • Maschler, Owen and Peleg (β€œThe Shapley value”, ed. by Roth, 1988)
  • Hart and Mas-Colell (Econometrica, 1996)

43

44 of 55

Implementation of the Shapley value in TU games

  • Gul (Econometrica, 1989)
  • Hart and Moore (J Pol Ec, 1990)
  • Winter (ET, 1994)
  • Evans (GEB, 1992)
  • Hart and Mas-Colell (Econometrica, 1996)
  • Dasgupta and Chiu (IJGT, 1998)
  • PΓ©rez-Castrillo and Wettstein (JET, 2001)
  • Vidal-Puga (EJOR, 2008)
  • Ju (JME, 2012)

44

45 of 55

Common features when dealing with partial agreements

  • Players β€œplay” (make offers and counteroffers, agree or disagree, vote, make partial payoffs, ...) in N.
  • Eventually, players split (or some are simply excluded) and the bargaining goes on in some (or several) subcoalition S, without possibility to rejoin.
  • The risk of these splits is the tool that make players in N to reach an agreement in equilibrium.

45

46 of 55

Alternative features when dealing with partial agreements

  • Players β€œplay” (make offers and counteroffers, agree or disagree, vote, make partial payoffs, ...) in N, but their offers also consider the payoffs in case of disagreement.
  • Players never split (nor are excluded) nor the bargaining goes on in some (or several) subcoalition S.
  • The risk of disagreement is the tool that make players in N to reach an agreement in equilibrium.

46

47 of 55

Common and alternative features when dealing with partial agreements

  • Players β€œplay” (make offers and counteroffers, agree or disagree, vote, make partial payoffs, etc) in N.
  • Eventually, players split (or some are simply excluded) and the bargaining goes on in some (or several) subcoalition S, without possibility to rejoin.
  • The risk of these splits is the tool that make players in N to reach an agreement in equilibrium.
  • Players β€œplay” (make offers and counteroffers, agree or disagree, vote, make partial payoffs, etc) in N, but their offers also consider the payoffs in case of disagreement.
  • Players never split (nor are excluded) nor the bargaining goes on in some (or several) subcoalition S.
  • The risk of disagreement is the tool that make players in N to reach an agreement in equilibrium.

47

48 of 55

The non-cooperative game: Rounds 1 and 2

An order of the players is randomly chosen (assume 12...n).

  1. Player 1 presents a rule f{1}: SβŠ†N⟢f{1}(S)∈V(S).
  2. Player 2 either
    1. agrees on f{1} and joins {1} (so coalition {1,2} is formed), or
    2. disagrees and proposes a new rule f{2} to player 1.
      1. If player 1 accepts, {1,2} forms with rule f{2}, and the turn passes to player 3.
      2. If player 1 rejects, the two player set apart for now, and the turn passes to player 3.

48

49 of 55

The non-cooperative game: Round r

Player r faces ((S1, f 1),...,(Sk, f k)) where

  • {S1,...,Sk} is a partition of {1,...,r-1} and
  • (f 1,...,f k) is the vector of rules they have respectively agreed upon.

Player r either

  • agrees on some (Sl,f l) and joins Sl, or
  • disagrees and proposes a new rule f* to everyone.
    • If some coalitions accept (unanimity required inside), they form a new merged coalition with r and rule f*, and the turn passes to player r + 1.
    • If all coalitions reject, player r does not join any coalition and the turn passes to r + 1 with ((S1,f 1),...,(Sk,f k),({r},f*)).

49

50 of 55

Round r

Player r faces

Player r + 1 faces

50

({S1,..., Sk), (f 1,..., f k)})

({S1,...,Slβˆͺ{r},...,Sk), (f 1,..., f l’,..., f k)})

({S1,...,Sk,{r}), (f 1,...,f k,f*)})

({S1,...,S*), (f 1,..., f*)})

51 of 55

Last round (n + 1)

  • If we face (({N}),(f )), i.e., all coalitions have unanimously agreed on a single rule f, then each i∈N receives fi(N) and the game finishes.
  • If we face ((S1,f 1),...,(Sk,f k)) with k > 1, i.e., there is no unanimity, then
    • With 𝜌∈[0,1), the whole process is repeated with a (new) random order.
    • With 1 βˆ’ 𝜌, each i∈Sl receives fil(Sl) and the game ends.

​

51

52 of 55

Main result

There exists a stationary subgame perfect equilibrium payoff allocation for each order. Moreover, this payoff allocation is efficient and individually rational.

Furthermore, as 𝜌 approaches 1, the expected final payoff allocation approaches a Shapley NTU value.

Corollary:

  • For TU games, the Shapley value is the unique expected equilibrium payoff.
  • For bargaining problems, the unique expected equilibrium payoff approaches the Nash bargaining solution as 𝜌 approaches 1.

52

53 of 55

Section 3

Conclusion

53

54 of 55

Summary

Summary:

1. We design a decentralized protocol of bargaining (non-cooperative game) where no players are ever excluded.

2. We determine the final payoffs in equilibrium.

3. The final payoffs approach the Shapley NTU value.

54

55 of 55

Non-cooperative approaches

  • Consistent value: Hart and Mas-Colell (Econometrica, 1996)
  • Shapley NTU value: This research.
  • Harsanyi value: Open question.

55