ISSN (Print) 0473-453X

Discussion Paper No. 1176

ISSN (Online) 2435-0982

COST OF COMPLEXITYIN IMPLEMENTING THE SHAPLEY VALUEBY CHOOSING A PROPOSER
THROUGH A BIDDING PROCEDURE
Michela Chessa
Nobuyuki Hanaki
Aymeric Lardon
Takashi Yamada

May 2022

The Institute of Social and Economic Research
Osaka University
6-1 Mihogaoka, Ibaraki, Osaka 567-0047, Japan

Cost of complexity in implementing the Shapley value bychoosing a proposer through a bidding procedure*
Michela Chessa†

Nobuyuki Hanaki‡

Aymeric Lardon§

Takashi Yamada¶May 31, 2022

Abstract
We experimentally compare a simplified version of two mechanisms that implement the Shapley value as an (ex ante) equilibrium outcome of a noncooperative
bargaining procedure: one proposed by Hart and Mas-Colell (1996, H-MC) and theother by Pérez-Castrillo and Wettstein (2001, PC-W). While H-MC induces the
Shapley value only on average, PC-W does so as a unique equilibrium outcome byintroducing an additional bidding stage on top of H-MC. We investigate the effectof this additional complexity that PC-W introduces on the resulting outcomes suchas the frequency of grand coalition formation, efficiency, and the distance between
the realized allocation and the Shapley value. Our experiment shows that H-MC
not only results in significantly greater efficiency than PC-W, but also the average
allocation is closer to the Shapley value for those groups that formed the grandcoalition.

JEL codes: C70, C71, C92
Keywords: Nash program, Bargaining procedures, Shapley value, Experiments* The experiments reported in this paper have been approved by the IRB of Yamaguchi University(No. 5). We gratefully acknowledge financial support from the Joint Usage/Research Center at ISER,
Osaka University, and Grants-in-aid for Scientific Research, Japan Society for the Promotion of Science(15K01180, 18K19954, 20H05631), Fund for the Promotion of Joint International Research (Fostering
Joint International Research) (15KK0123), and the French government-managed l’Agence Nationale dela Recherche under Investissements d’Avenir UCAJEDI (ANR-15-IDEX-01). In particular, we thank the
UCAinACTION project.
†
Université Côte d’Azur, CNRS, GREDEG, France. E-mail: michela.chessa@univ-cotedazur.fr‡
Institute of Social and Economic Research, Osaka University, Japan.
E-mail:nobuyuki.hanaki@iser.osaka-u.ac.jp§
GATE Lyon Saint-Etienne, UMR 5824 CNRS, Université de Lyon.
France.
E-mail:aymeric.lardon@univ-st-etienne.fr¶
Faculty of Global and Science Studies, Yamaguchi University, Japan. E-mail: tyamada@yamaguchiu.ac.jp1

1

Introduction

The Nash program (Nash, 1953) provides a noncooperative foundation for cooperative
solution concepts. In this seminal work, Nash showed that the solution to the cooperative bargaining problem (Nash, 1950) can be obtained as an equilibrium outcomeof a noncooperative game, and noted that the fact that a different approach yielding thesame solution “indicates that the solution is appropriate for a wider variety of situations”(Nash, 1953, p. 136). Indeed, the main idea of the Nash program “is both simple andimportant: the relevance of a concept [...] is enhanced if one arrives at it from different
points of view” (Serrano, 2005, p. 220).
Many authors have contributed to the development of the Nash program (see, Serrano, 2005, 2008, 2014, 2021, for surveys). Since the inception of the Nash program,the cooperative solution that has attracted most attention is the Shapley value (Shapley, 1953). Indeed, various papers (for example, Gul, 1989; Harsanyi, 1981; Hart andMoore, 1990; Krishna and Serrano, 1995; Winter, 1994; Hart and Mas-Colell, 1996;
Pérez-Castrillo and Wettstein, 2001) have proposed its implementation.
Chessa et al. (2022, 2021) contributed to this literature by providing experimental
comparisons between Winter (1994) and Hart and Mas-Colell (1996) in Chessa et al.
(2022) and among three versions of Winter (1994) in Chessa et al. (2021). Chessa et al.
(2022) found that the demand-based mechanism proposed by Winter (1994) resulted in
an allocation that better reflects players’ effective bargaining power, while the efficiency
and the frequency of the grand coalition formation are lower than those from an offerbased mechanism proposed by Hart and Mas-Colell (1996). However, because thisresult was obtained from a simplified version of the approach of Winter (1994), Chessa
et al. (2021) investigated the robustness of the outcome by comparing the outcome of the2

simplified one-period version of Winter (1994) considered in Chessa et al. (2022) witha more complex—but closer to the original theoretical analysis—two-period version of
Winter (1994). Chessa et al. (2021) found that the results were very similar between the
one-period and two-period versions.
In this paper, we extend the experimental analyses of Chessa et al. (2022, 2021) bycomparing the mechanisms proposed by Hart and Mas-Colell (1996) and Pérez-Castrillo
and Wettstein (2001). Both mechanisms are offer-based. Namely, in both mechanisms,
there will be a proposer who proposes an allocation, which is voted on by the remaining
players sequentially. The key difference between the two is the way the proposer ischosen. On the one hand, a proposer is chosen randomly among the players in Hart
and Mas-Colell (1996). On the other hand, in Pérez-Castrillo and Wettstein (2001), theproposer is determined through a bidding procedure. While Hart and Mas-Colell (1996)
implements the Shapley value as an ex ante equilibrium payoff (i.e., it is only achieved
as an expected outcome), Pérez-Castrillo and Wettstein (2001) implements it as a uniqueequilibrium outcome of the game.
While it is a nice theoretical investigation, the complexity of the bidding procedure introduced by Pérez-Castrillo and Wettstein (2001) makes one wonders whether it
would indeed result in the Shapley value if the game was played by participants in alaboratory experiment. Various experimental studies on extensive form games (see, forexample, Kagel and Roth, 1995, Ch.4) show that participants have difficulty behaving inaccordance with the prediction of the subgame perfect Nash equilibrium. Furthermore,
as demonstrated by the idea of “obviously strategy proofness” (Li, 2017), a mechanism
needs to be extremely simple for it to result in the outcome intended by its designer.
Indeed, our experiment shows that the simpler mechanism à la Hart and Mas-Colell(1996) not only results in greater efficiency than that by Pérez-Castrillo and Wettstein3

(2001), but also that the average allocation is closer to the Shapley value for those groups
that formed a grand coalition. Thus, the complexity of the mechanism of Pérez-Castrillo
and Wettstein (2001) imposes substantial costs to implementing the Shapley value.
The rest of the paper is organized as follows. We present the two mechanisms considered in our experiment in the next section. Section 3 describes the experiment procedure, while the results are presented in Section 4. Section 5 concludes.

2

Two mechanisms

In this section, we present the H-MC mechanism (Section 2.1) and the PC-W mechanism (Section 2.2) in more detail.

2.1

The Hart and Mas-Colell mechanism

The bargaining procedure proposed by Hart and Mas-Colell (1996) implements the
Shapley value in monotonic cooperative games.1 In this mechanism, the bargaining
starts with a randomly chosen proposer making an offer to the other players (responders). The responders, sequentially, may either accept or reject the offer. If the offer
is accepted by all responders, it is implemented. If one of the responders rejects theoffer, the game moves to the next stage. If the offer is rejected, the proposer leaves thegame with the worth of her stand-alone coalition with probability p and the bargaining
continues with the remaining players, with a new player randomly chosen as the new
proposer. In our laboratory implementation, we set p = 1 to make it comparable with
the PC-W mechanism.
1

See Peleg and Sudhölter (2007) as well as Chessa et al. (2022) for the general definition and theproperties of a cooperative transferable utility (TU) game (a cooperative game), as well as the Shapley
value.

4

We present here a more formal description of the H-MC mechanism. A decision
point position at time t is given simply by the vector (S t , j), where:
S t ⊆ N is the set of players still in the game, andj ∈ S t is the player making an offer to the remaining players (ti )i∈S t \{j} suchP
that i∈S t \{j} ti ≤ v(S t ).
With j’s offer, the game proceeds now in the following way:
1) if all i ∈ S t \ {j} accept the offer one after the other, then players in S t \ {j}P
are paid (ti )i∈S t \{j} , player j is paid v(S t ) − i∈S t \{j} ti , and the game ends;
2) if at least one player i ∈ S t \ {j} refuses the offer, then there are two possibilities:2a) if |S t | = 2 (only one more player is left, together with j), then they both get
the worth of their own stand-alone coalition v({i}) for each i ∈ S t , and the gameends;2b) if |S t | > 2, then player i is removed from the game, she gets her individual
payoff v({i}), a new proposer k ∈ S t+1 = S t \ {j} is randomly selected and thenew position is (S t+1 , k).
The game starts with a randomly chosen proposer j ∈ N , so that the initial positionis (N, j). It terminates either when there are no more players in the game (see point 2aabove), or when the offer is unanimously accepted (see point 1 above).
Hart and Mas-Colell (1996) showed that this game has a unique subgame perfectequilibrium. At this equilibrium, the grand coalition forms and the a priori expectedequilibrium payoff coincides with the Shapley value.
5Given a specific initial proposer j ∈ N , the a posteriori equilibrium payoff assigns
to each other player her Shapley value in the cooperative game reduced to the set ofplayers N \ {j}, and to the proposer, the marginal contribution to the grand coalitionv(N ) − v(N \ {j}).

2.2

PC-W mechanism

Pérez-Castrillo and Wettstein (2001) proposed a bidding mechanism to implement the
Shapley value for zero-monotonic cooperative games.2 In this mechanism, unlike Hart
and Mas-Colell (1996), the bargaining starts with a bidding stage where each of theplayers makes a bid to each of the other players. The proposer is chosen as the player
making the highest net bid, calculated as the difference between the sum of the bids aplayer makes to the others minus the sum of the bids the others make to her. If several
players make the highest net bid, the proposer is then selected randomly among them.
At the end of the bidding stage, the proposer pays the promised bids to the other players.
In the second stage, the proposer makes an offer to the other players (responders). This
offer is sequentially accepted or rejected by the responders. If all the responders accept,
the game ends and the proposer pays the other players according to her offers, andreceives what remains of the worth of the coalition. If one of the responders rejects theoffer, the proposer leaves the game and obtains the worth of her stand-alone coalition
minus the bids she has already paid in the first stage. The rest of the players keep what
they have received and a new bargaining starts among them.
We present here a more formal description of the PC-W mechanism. A decision
point position at time t is given simply by the set of players S t ⊆ N remaining in the2

In zero-monotonic games, there are no negative externalities when a single player joins a coalition.
Formally, we have v(S) + v({i}) ≤ v(S ∪ {i}) for any subset S ⊆ N with i 6∈ S. Note that all the fourgames we consider in experiments respect this assumption.

6

game, (when t = 1, S t = N ). The game is described as follows:(1) Each player i ∈ S t makes bids bij to the other players j ∈ S t \{i}. Player i withP
the highest net bid j∈S\{i} (bij − bji ) is chosen to be the proposer and pays bij
to every j ∈ S t \{i}; if several players make the highest net bid, the proposer ischosen randomly among them.
(2) If player i is the proposer, she makes an offer yji to the other players j ∈ S t \{i}.
(3) With i’s offer, the game proceeds now in the following way:(3a) If the offer is sequentially accepted by the other players, each player j ∈P
S t \{i} receives bij + yji , the proposer obtains v(S t ) − j∈S t \{i} (bij + yji ),and the game ends.
(3b) If at least one player j ∈ S t \{i} refuses the offer, then proposer i is removedP
and obtains v({i}) − j∈S t \{i} bij ; the new set of players becomes S t+1 =S t \{i} in which each member j receives bij and a new bidding mechanism
starts among them (if only one player remains in the game, i.e. |S t+1 | = 1,
then that player just obtains the worth of her stand-alone coalition and thegame ends).
Pérez-Castrillo and Wettstein (2001) showed that any subgame perfect equilibriumof this game implements the Shapley value as the a posteriori equilibrium payoff. At
these equilibria, the bid of player i to player j corresponds to her Shapley value of theoriginal game minus her Shapley value in the cooperative game reduced to the set ofplayers N \ {i}. The balanced contribution property (Myerson, 1980) then ensures that
all net bids are equal to zero, leading to a random selection of the proposer among all7

the players. Moreover, player i, if she is randomly selected to be the proposer, offers
to player j her Shapley value in the reduced cooperative game with player set N \ {i}.
It is worth noting that when the game is strictly zero-monotonic,3 the grand coalition
always forms. Otherwise, rejection of some offers could also constitute a subgame
perfect equilibrium (this is the case, for example, in game 2 when player 1 is chosen as
the proposer).

3

The experimental setting

We consider the four games that are studied in (Chessa et al., 2022, 2021). These games
and their corresponding Shapley values are reported in Table 1.

3.1

ProcedureUpon arrival, participants received a copy of the instruction slides. The instructions
were divided into two parts: an explanation of the rules of the game and an explanationof the computer interface. First, a prerecorded video of the first part of the instructions (explanation of the rules of the game) was played. Then, a comprehension quiz(computerized) was administered to make sure participants understood the rules of thegame. They needed to answer each question correctly before proceeding to the next one.
Once all the participants finished answering the quiz questions, two practice rounds ofa game in which the Shapley value for all the players was 25 was run to familiarize theparticipants with the software before the real experiment started. During these practice rounds, participants were asked to look at the second part of the instructions about
3
A game is strictly zero-monotonic if v(S) + v({i}) < v(S ∪ {i}) for any nonempty subset S ⊆ Nwith i 6∈ S. Note that only games 1, 3, and 4 that we consider in our experiments are strictly zeromonotonic.

8

Table 1: Four games and corresponding Shapley values
Game 1v1 (S)

Game 2v2 (S)

Game 3v3 (S)= v1 (S) + v2 (S)Game 4v4 (S)= 2v1 (S)

0
5
5
10
20
20
25
20
25
25
50
60
60
60
100

0
20
20
30
20
20
30
45
55
60
45
55
60
100
100

0
25
25
40
40
40
55
65
80
85
95
115
120
160
200

0
10
10
20
40
40
50
40
50
50
100
120
120
120
200

S
1
2
3
4
1,2
1,3
1,4
2,3
2,4
3,4
1,2,3
1,2,4
1,3,4
2,3,4
N

Shapley values for each player
φ1 (v)
φ2 (v)
φ3 (v)
φ4 (v)

22.08
23.75
23.75
30.42

0
28.33
30.83
40.83

22.08
52.08
54.58
71.25

44.16
47.5
47.5
60.84

the computer interface. In the first round of the practice, the experimenter explained
each screen following the instructions. See Appendix A for English translations of the
instruction slides and the comprehension quiz.
In the actual experiment, just as in Chessa et al. (2022, 2021), each participant played
all four games twice in one of the following four orderings: 1234, 2143, 3412, and 4321.
Between each play of a game (called a round), players were randomly rematched into
groups of four players, and participants were randomly assigned a new role within the
newly created group. At the end of the experiment, two rounds (one from the first four
rounds and another from the last four rounds) were randomly selected for payments.

9Participants received cash rewards based on the points they earned in these two selectedrounds with an exchange rate of 20 JPY = 1 point in addition to 1500 JPY and 1900 JPY
participation fees for H-MC and PC-W. The participation fee for PC-W was set larger
to compensate for the longer experiment, as well as to cover possible losses participants
may have made.

3.2

Simplification of, and an additional difference between, the mechanisms

In our experiment, we simplified both the H-MC and PC-W mechanisms. Namely, after
a proposer makes an offer, instead of the remaining players (responders) approving or
rejecting the offer one by one sequentially, all responders decided simultaneously.
Coalition formation processes may perform differently in the two settings, sequential versus simultaneous. For example, recently, Abe et al. (2021) compared experimentally the efficiency of (a) a mechanism in which participants decide to join the coalition
sequentially as in the original theoretical analysis of Hart and Mas-Colell (1996) andPérez-Castrillo and Wettstein (2001) and (b) an analogous mechanism in which participants decide to join the coalition simultaneously as in our experimental implementation,and found that the former resulted in higher efficiency than the latter. However, Chessa
et al. (2022) investigated the effect of this simplification in H-MC in the same fourgames we consider in this paper (see their Appendix V). This simplification gives rise
to other Nash equilibria, in which two or more players refuse the proposal. However,they reported that the simplified H-MC indeed resulted in a significantly lower frequency of grand coalition formation and efficiency in game 2, but not in the remaining
three games, such that the performances of the two implementation resulted as compara-10ble. Moreover, in our experiment this simplification is done both for H-MC and PC-W.
Therefore, for the purpose of investigating the effect of the complexity introduced byadding the bidding stage to determine the proposer, the impact of this simplification, if
any, should be analogous on two mechanisms and should not affect their comparison.
In our experiment, in addition to the way the proposer is chosen, there is a differencein the way the simplified version of the H-MC and PC-W is implemented. Namely, on
the one hand, under our H-MC implementation, the responders observed the proposed
allocation to all the players when deciding to accept or reject the proposal. On theother hand, under our PC-W implementation, each responder observed only their own
proposed allocation and not those to other players (see the screenshots entitled “respondent’s input” for H-MC and “STEP 2 (Respondent)” for PC-W included in the English
translation of the instruction material available in Appendix A). The reason for introducing this difference is that in PC-W, responders are presented not only with the offer
in the second stage, but also the allocated amount in the first bidding stage and the sumof the two. Presenting the proposed allocation for all the responders in this manner for
PC-W substantially increases the amount of information participants have to process
when deciding to approve or reject the offer. While this difference in the presentationof the information does not influence the theoretical analyses (based on the standard setof assumptions), it may influence the results we report below, but it is not clear in whatway.

4

Results

The computerized experiment was conducted at the Institute of Social and Economic
Research (ISER), Osaka University, between June and December 2019. The experiment11was computerized and used z-Tree (Fischbacher, 2007). A total of 164 students among
those registered in the participants database managed by ORSEE (Greiner, 2015), who
had not participated in similar experiments previously, were recruited as subjects of theexperiment. Among these 164 participants, 84 played H-MC and 80 played PC-W. Notethat the data of H-MC used in this paper is the same as those reported in Appendix V of
Chessa et al. (2022) as H-MCsim .
The experiment lasted on average 1h30m for H-MC and 2h05m for PC-W including
the instructions, comprehension quiz, and payment. The average earning was 2780
JPY for H-MC and 2990 JPY for PC-W (approximately 25.7 and 27.7 USD using an
average exchange rate of 1 USD = 108 JPY for the period over which the experiment
was conducted.)

4.1

Grand coalition formation and efficiency

Figure 1 presents the results about the grand coalition formation, in the H-MC mechanism and in the PC-W mechanism, for the four games. The figure is created based on theestimated coefficients of the following linear regression: gci = β1 HM Ci + β2 P CWi +µi where gci is a dummy variable that takes the value 1 if the grand coalition is formed,
and zero otherwise, in group i, and HM Ci (P CWi ) is a dummy variable that takes thevalue 1 if the H-MC (PC-W) mechanism is used, and zero otherwise. The standard errors are corrected for any within-session clustering effect. The statistical tests are basedon the Wald test for the equality of the estimated coefficients of two treatment dummies.
For game 2, we also consider the case in which we allow a coalition without the nullplayer as the grand coalition (panel b’). We observe from Figure 1 that the frequencyof grand coalition formation is higher under H-MC than under PC-W; however, the12Figure 1: H-MC and PC-W mechanisms: proportion of times the grand coalition formed(a) Game 1(b) Game 2n.s.

(b’) Game 2, allow {2,3,4}

n.s.

1
0.8
0.6
0.4
0.2
0

n.s.

1
0.8
0.6
0.4
0.2
0
H-MC

1
0.8
0.6
0.4
0.2
0

PC-W

H-MC

PC-W

(c) Game 3

H-MC

PC-W

(d) Game 4

n.s.

n.s.

1
0.8
0.6
0.4
0.2
0

1
0.8
0.6
0.4
0.2
0
H-MC

PC-W

H-MC

PC-W

Note: Error bars show one standard error range. ***, **, and * indicate the proportion of times that grand coalition formation issignificantly different between the H-MC and the PC-W at the 0.1, 1, and 5% significance levels, respectively (Wald test).

difference is not statistically significant.
As a direct consequence of the grand coalition not always being formed, both mechanisms fail to achieve full efficiency. Figure 2 compares the efficiency between the two
mechanisms for four games. Efficiency is computed as the fraction of the sum of thepayoffs obtained by the four players compared with the value of the grand coalitionof the considered game (100 for games 1 and 2 and 200 for games 3 and 4). The figure is created based on the estimated coefficients of the following linear regressions:
P

π

i i
Ef fi = β1 HM Ci + β2 P CWi + µi where Ef fi ≡ v(Nis the efficiency measure for)group i, HM Ci (P CWi ) is a dummy variable that takes the value 1 if the H-MC (PCW) mechanism is used, and zero otherwise. The standard errors are corrected for any
within-session clustering effect. The statistical tests are based on the Wald test for theequality of the estimated coefficients of two treatment dummies.
13

Figure 2: Efficiency(a) Game 1(b) Game 2

n.s.

n.s.

1
0.8
0.6
0.4
0.2
0

1
0.8
0.6
0.4
0.2
0
H-MC

H-MC

PC-W

(c) Game 3

PC-W(d) Game 4
*

*
1
0.8
0.6
0.4
0.2
0

1
0.8
0.6
0.4
0.2
0
H-MC

H-MC

PC-W

PC-W

Note: Error bars show the one standard error range. ***, **, and * indicate the efficiency is significantly different between H-MCand PC-W at the 0.1, 1, and 5% significance levels, respectively (Wald test).

Figure 2 shows that the efficiency is higher under the H-MC mechanism than under
the PC-W mechanism, and that the difference is statistically significant at the 5% levelfor games 3 and 4.
The significantly lower efficiency under PC-W compared with H-MC (for game 3,
the mean efficiency is 0.747 and 0.858 for PC-W and H-MC, respectively, and for game
4, they are 0.788 and 0.871) demonstrates that the cost of complexity introduced by thebidding procedure of the former is not negligible.

4.2

Allocations

We denote by π HM C (vk ) a vector of payoffs obtained by the players in the H-MC mechanism in game k, with k = 1, 2, 3, 4. Analogously, we denote by π P CW (vk ) a vectorof payoffs obtained by the players in the PC-W mechanism. As noted above, H-MC
14

implements the Shapley value only on average, whereas PC-W, thanks to the bidding
stage, does so as a unique equilibrium outcome. Therefore, we first compare the averagerealized payoff vectors between the two mechanisms. However, when the players failto form the grand coalition, the total payoffs obtained by the players is smaller than thevalue of the grand coalition. This results in the average realized payoff vectors being
significantly different from the Shapley value. We therefore focus our analyses on thosegroups that formed the grand coalition.
Our main analyses are based on a set of OLS regressions (using only the data fromgroups that formed the grand coalition) for the following system of equations.
π1 = a1 g1 + a2 g2 + a3 g3 + a4 g4 + u1
π2 = b1 g1 + b2 g2 + b3 g3 + b4 g4 + u2(1)

π3 = c1 g1 + c2 g2 + c3 g3 + c4 g4 + u3
π4 = d1 g1 + d2 g2 + d3 g3 + d4 g4 + u4
where πi is the payoff of player i, gj is a dummy variable that takes the value 1 if thegame j ∈ {1, 2, 3, 4} is played, and zero otherwise. Because participants play all fourgames twice, we correct the standard errors for any within-group clustering effect. Notethat the estimated coefficients aj , bj , cj , and dj are the average payoffs in game j forplayers 1, 2, 3, and 4, respectively.
Table 2 reports the results of these regressions, with H-MC in the left panel and PCW in the right panel. These estimated coefficients and standard errors are also visualized
in Figure 3. In the figure, the horizontal lines indicate the Shapley values for each game.
The stars above each bar indicate that the average payoff is significantly different fromthe corresponding Shapley value at the 0.1, 1, or 5% levels. As one can observe, there

15

Table 2: Results of linear regression based only on the groups that formed the grandcoalition

g1
g2
g3
g4
R2
Obs.

π1
23.88
(0.70)
11.07(3.31)
45.88(1.70)
47.83(1.17)
0.96
97

H-MC
π2
π3
25.63 24.56(0.43) (0.11)
26.07 27.73(1.45) (0.97)
51.32 49.72(1.19) (0.50)
48.67 50.5
(0.89) (0.87)
0.99
0.99
97
97

π4
25.93
(0.42)
35.13(1.95)
53.08(1.84)
53.00(1.10)
0.97
97

g1
g2
g3
g4
R2
Obs.

π1
23.93
(0.39)
22.18(4.01)
50.76(0.44)
49.08(1.16)
0.98
67

PC-W
π2
π3
25.00 24.86(1.54) (0.72)
23.45 25.55(1.15) (0.99)
49.18 51.18(1.59) (0.41)
49.64 49.16(0.57) (0.75)
0.98
0.99
67
67

π4
26.21
(1.04)
28.82(3.78)
48.88(2.08)
52.12(1.46)
0.97
67

Note: The standard errors are corrected for any within-group clustering effect.

are only a few cases (players 2 and 3 in game 1 as well as player 2 in game 3 for PCW, and player 2 in games 2, 3, and 4 for H-MC) where the average payoffs are notsignificantly different from the Shapley value at the 5% level. Thus, neither H-MC nor
PC-W implements the Shapley values.
To better compare the two mechanisms in terms of how close their average payoffs
are to the Shapley value, we compute the following measure:

Disφ =sX(πi − φi )2(2)iwhere πi and φi are the average payoff and Shapley value for player i, respectively, inthe given game. As above, we focus on only those groups that formed a grand coalition.
Furthermore, we employ a bootstrapping technique to conduct statistical tests. Namely,in each interaction, we use a subsample (with replacement) of our data, run the system of16

Figure 3: Mean payoffs based only on the groups that formed the grand coalition
Game 1

Game 260

60

Player 1

Player 2

Player 3******

Player 1

Player 4***

Player 2

Game 3*****Player 3

**

**

PC-W

PC-W

H-MC

0
PC-W

10

0
H-MC

10
PC-W

20

H-MC

30

20

PC-W

30

H-MC

40

H-MC

***

PC-W

***

H-MC

***

PC-W

***

H-MC

***

PC-W

50
**

40

H-MC

50

Player4

Game 4120

120

Player 1

Player 2

Player 3

Player4*****

Player 1***

Player 2****

Player 3

***

***

PC-W

PC-W

0
H-MC

0
PC-W

20
H-MC

40

20
PC-W

40

H-MC

60

PC-W

60

H-MC

80

H-MC

***

PC-W

***

H-MC

***

PC-W

***

H-MC

***

PC-W

100
***

80

H-MC

100

Player4

Note: The horizontal lines indicate the Shapley values. Error bars show one standard error range. ***, **, and * indicate the average
payoff being significantly different from the Shapley value at the 0.1, 1, and 5% significance levels (χ2 test).

regressions presented above (Eq. 1), and compute Disφ based on the obtained estimatedcoefficients (i.e., the average payoffs for the subsample).
Figure 4 shows the results based on the outcomes of 1000 repetitions. As one canobserve, Disφ is significantly higher for games 2, 3 and 4 under PC-W than H-MC.4
4

Based on two-sample t-test with unequal variance using the sample generated by the bootstrap. The
means Disφ (standard errors) for the H–MC mechanism are 5.21 (0.041) in game 1, 13.11 (0.088) in game
2, 30.31 (0.089) in game 3, and 9.21 (0.058) in game 4. For the PC-W mechanism, the corresponding
values are 5.21 (0.041) for game 1, 26.34 (0.098) for game 2, 36.67 (0.053) for game 3, and 10.59 (0.077)
for game 4.

17

Figure 4: H-MC and PC-W mechanisms: distance from Shapley
Game 140

Game 2
40

n.s.

20

***

20

0

0
H-MC

H-MC

PC-W

Game 3

PC-W

Game 4

60

60
***

***

40

40

20

20

0

0
H-MC

PC-W

H-MC

PC-W

Note: Error bars show the one standard error range. ***, **, and * indicate significant difference between H-MC and PC-W at the
0.1, 1, and 5% significance levels (two-sample t-test).

Thus, the complexity introduced by the bidding stage of PC-W not only results in alower efficiency, but also a larger deviation from the Shapley value even among thosegroups that successfully formed the grand coalition.

4.3

Realized allocations and the a posteriori equilibria

Let us now analyze the realized payoffs in light of the a posteriori equilibrium payoff
vectors. We continue to focus only on the groups that formed the grand coalition. We
measure the distance between the realized payoff vectors and the equilibrium allocation
for the four games by the Euclidean distances between the two. Let eqi be the equilibrium payoff for player i for the given game and the mechanism. Note that eqi depends
also on the realized proposer in the case of H-MC. The distance of the realized paypP2
off from the equilibrium is computed as DisN E =i (πi − eqi ) . We also consider

18

Figure 5: Mean of the distances of the realized payoff vectors from the subgame perfect
nash equilbrium and the equal division(a) Game 1
**

***

40

(b) Game 2

***
n.s.

20

n.s.

n.s.

40

n.s.
n.s.

20

0

0
H-MC

PC-W

H-MC

DisN E

PC-W

H-MC

DisED

PC-W

(c) Game 3
***

n.s.

H-MC

PC-W

DisN E

PC-W

DisED

(d) Game 4

***

100
80
60
40
20
0

H-MC

DisN E

100
80
60
40
20
0

n.s.

H-MC

PC-W

H-MC

DisED

***

***

PC-W

DisN E

***
n.s.

H-MC

PC-W

DisED

Note: Error bars show the one standard error range. ***, **, and * indicate that the distance of the payoff vectors from theequilibrium allocations or from the equal division was significantly different between H-MC and PC-W at the 0.1, 1, and 5%
significance levels (Wald test).

the distance between the realized payoff vectors and equal division payoffs, defined by
pP
2
DisED =i (πi − EDi ) , where EDi is the equal division payoff for player i forthe given game.
Figure 5 shows the mean DisN E and the mean DisED for the two mechanisms
in the four games.5 Figure 5 shows that, except for game 2, the realized allocations
are closer to the equal division than the equilibrium one under both H-MC and PC-W.
The differences between DisN E and DisED are significant at the 1% significance level,
except for game 2. Because the allocation is closer to the equal allocation than the5

The figure is created based on the estimated coefficients of the following linear regressions: Disi =β1 HM Ci + β2 P CWi + µi where Disi is the relevant distance measure for group i, HM Ci (P CWi )is a dummy variable that takes the value 1 if the H-MC (P-WC) mechanism is used, and zero otherwise.
The standard errors are corrected for any within-session clustering effect. The statistical tests are basedon the Wald test for the equality of the estimated coefficients of the two treatment dummies.

19

equilibrium one, and the equilibrium allocation of PC-W is less extreme than those of
H-MC, we observe that PC-W results in an allocation closer to the equilibrium one than
H-MC for games 1 and 4 at the 0.1% significance level. For games 2 and 3, DisN E isnot significantly different between the two mechanisms.

5

Comparison of the first two games and the last twogames

So far, we have considered all the rounds and compared H-MC and PC-W. However,given that PC-W is more complex than H-MC, it is possible that it takes longer forparticipants to learn to play better. In this section, therefore, we separately investigate
the outcomes in the early rounds (i.e., the first two games participants played) and in
the late rounds (i.e., the last two games participants played). The figures below are
generated in the similar way as the corresponding figures presented above.6
Figure 6 shows the frequency of grand coalition formation in four games for the
early and the late rounds. For H-MC, the grand coalition is significantly more frequently
formed in the late rounds than in the early rounds for game 1 (at the 1% significancelevel). For PC-W, the frequency of grand coalition formation is significantly higher inthe late rounds than in the early rounds for games 3 and 4 (at the 0.1 and 1% significancelevels, respectively). A similar tendency can be observed for the efficiency shown in
Figure 7.
6

Namely, the figure are created based on the estimated coefficients of the following linear regression:yi = β1 HM Cie + β2 HM Cil + β3 P CWie + β4 P CWil + µi where yi is the outcome variable of interestin group i, and HM Ciτ (P CWiτ ) is a dummy variable that takes the value 1 for τ ∈ {e, l} where e and lstand for early and late rounds of the H-MC (PC-W) mechanism, and zero otherwise. The standard errors
are corrected for any within-session clustering effect. The statistical tests are based on the Wald test for
the equality of the estimated coefficients of two treatment dummies.

20

Figure 6: H-MC and PC-W mechanisms: proportion of times the grand coalition formedin early and late rounds
Game 2 ({2, 3, 4} allowed)

Game 1
n.s.

**

1

***
n.s.

1

0.8

0.8

0.6

0.6

0.4

0.4

0.2

0.2

0

n.s.

n.s.

n.s.

0
Early

Late

Early

H-MC

Late

Early

PC-W

Late

1

*

n.s.

Late

Early

H-MC

Game 3

0.8

n.s.

PC-W

Game 4

n.s.

1
***

0.8

0.6

0.6

0.4

0.4

0.2

0.2

0

n.s.

n.s.

n.s.
**

0
Early

Late

H-MC

Early

Late

Early

PC-W

Late

H-MC

Early

Late

PC-W

Note: Error bars show the one standard error range. ***, **, and * indicate that the two averages were significantly different at the
0.1, 1, and 5% significance levels (Wald test).

21

Figure 7: H-MC and PC-W mechanisms: efficiency in early and late rounds
Game 1
1

n.s.

***

Game 2

***
n.s.

1

0.8

0.8

0.6

0.6

0.4

0.4

0.2

0.2

0

n.s.

n.s.

n.s.

0
Early

Late

Late

Early

H-MC

Early

PC-W

Late

*

n.s.

Early

H-MC

Game 3
1

n.s.

Late

PC-W

Game 4
*
**

1

0.8

0.8

0.6

0.6

0.4

0.4

0.2

0.2

0

*

n.s.

n.s.
n.s.

0
Early

Late

H-MC

Early

Late

Early

PC-W

Late

H-MC

Early

Late

PC-W

Note: Error bars show the one standard error range. ***, **, and * indicate that the two averages were significantly different at the
0.1, 1, and 5% significance levels (Wald test).

22

Figure 8: Mean Dis2φ in early and late rounds(a) Game 1
***

***

40

(b) Game 2

***
***

20

***

***

40

***
***

20

0

0
Late

Early

Late

Early

H-MC

Late

Early

PC-W

H-MC

(c) Game 3
***

***

40

Late

Early

PC-W

(d) Game 4
***

***
***

20

***

***

40

***

20

0

0
Early

Late
H-MC

Early

Late

Early

PC-W

Late
H-MC

Early

Late

PC-W

Note: Error bars show the one standard error range. ***, **, and * indicate a statistically significant difference between the twomeans, at the 0.1, 1, and 5% significance levels (Wald test).

Figure 8 shows Disφ for the early and late rounds in H-MC and PC-W for the fourgames. While for H-MC, Disφ becomes smaller in the late rounds than in the earlyrounds for all four games, this is not the case for PC-W.7 For PC-W, Disφ becomes
smaller in the late rounds than in the early rounds only for games 3 and 4, whereas forgames 1 and 2, it becomes larger in the late rounds.8 Thus, gaining experience playing
the game does not necessarily lead to allocation according to the Shapley value under
PC-W.
This point can also be observed for DisN E . Figure 9 shows DisN E (top four panels)
and DisED (bottom four panels) in the early and the late rounds. For game 2, on the7

The mean Disφ (the standard errors) for H-MC in early and late rounds are 6.44 (0.013) and 4.78
(0.027) for game 1, 19.03 (0.09) and 7.38 (0.11) for game 2, 32.08 (0.13) and 29.18 (0.13) for game 3,
and 9.96 (0.09) and 8.78 (0.07) for game 4, respectively.
8
For PC-W, the mean Disφ (the standard errors) in early and late rounds are 4.38 (0.056) and 7.21
(0.057) for game 1, 18.18 (0.17) and 31.70 (0.05) for game 2, 37.16 (0.03) and 36.55 (0.08) for game 3,
and 11.68 (0.11) and 10.16 (0.10) for game 4, respectively.

23

Figure 9: Mean DisN E and DisED in early and late rounds
DisN E(a) Game 1
***

n.s.

40

(b) Game 2
***

***
n.s.

20

***

**

40

***

20

0

0
Late

Early

Late

Early

H-MC

Late

Early

PC-W

H-MC

(c) Game 3

***

80

n.s.
n.s.

60

PC-W

(d) Game 4

n.s.

80

Late

Early

n.s.

60

40

40

20

20

0

***

n.s.

*

0
Late

Early

Late

Early

H-MC

Late

Early

PC-W

Late

Early

H-MC

PC-W

DisED
(a) Game 1
40

n.s.

n.s.

(b) Game 2

**

40

n.s.

***

***

***
***

20

20

0

0
Late

Early

Late

Early

H-MC

Late

Early

(c) Game 3

PC-W(d) Game 4

n.s.

40

n.s.

***

n.s.

Late

Early

H-MC

PC-W

n.s.

40

n.s.

20

n.s.

n.s.

20

0

0
Early

Late
H-MC

Early

Late

Early

Late
H-MC

PC-W

Early

Late

PC-W

Note: Error bars show the one standard error range. ***, **, and * indicate a statistically significant difference between the twomeans at the 0.1, 1, and 5% significance levels (Wald test).

24

one hand, under H-MC, DisN E becomes significantly smaller (and correspondingly,
DisED becomes significantly larger) in the late rounds compared with the early rounds
at the 1% significance level. On the other hand, under PC-W, the opposite is observed.
Namely, DisN E becomes significantly larger (and correspondingly, DisED becomessignificantly smaller) in the late rounds compared with the early rounds at the 0.1%
significance level. Furthermore, for PC-W in game 4, DisN E in the late rounds issignificantly larger than in the early rounds at the 5% significance level.

6

Summary and conclusion

In this paper, we aim to experimentally contribute to the Nash program (Nash, 1953) byextending the experimental analyses of Chessa et al. (2022, 2021). We do so by comparing the simplified version of the mechanisms proposed by Hart and Mas-Colell (1996)
and Pérez-Castrillo and Wettstein (2001). In the original theoretical investigation, in
both mechanisms, there is a proposer who proposes an allocation, which is voted onsequentially by the remaining players (in our experiment, the voting is done simultaneously). The proposal is accepted if all the remaining players accept the proposal; if not,with some probability in H-MC and with probability one in PC-W (in our experiment,
both are set to be with probability 1 to be comparable), the proposer leaves the gamewith his/her individual value (minus the sum allocated in the bidding stage in PC-W),
and the game continues with the remaining players. The key difference between thetwo mechanisms is the way the proposer is chosen. On the one hand, a proposer is chosen randomly among the players in Hart and Mas-Colell (1996). On the other hand, inPérez-Castrillo and Wettstein (2001), the proposer is determined through a bidding procedure. While Hart and Mas-Colell (1996) implements the Shapley value as an ex ante25

equilibrium payoff (i.e., it is only achieved as an expected outcome), Pérez-Castrillo
and Wettstein (2001) implements it as a unique equilibrium of the game.
Our experiment shows that the simpler mechanism a la Hart and Mas-Colell (1996)
not only results in higher efficiency than the one by Pérez-Castrillo and Wettstein (2001),
but also the average allocation is closer to the Shapley value for those groups thatformed a grand coalition. Thus, the complexity of the mechanism of Pérez-Castrillo
and Wettstein (2001) imposes substantial costs for implementing the Shapley value.
This finding is consistent with the recent work on the “obviously strategy proof” mechanism of (Li, 2017) which convincingly showed that, for a mechanism to implement theoutcome intended by its designer, it must be extremely simple.
Chessa et al. (2022, 2021), as well as this paper, showed that participants have difficulty forming a grand coalition and achieving full efficiency under various noncooperative mechanisms (namely, Winter, 1994; Hart and Mas-Colell, 1996; Pérez-Castrillo
and Wettstein, 2001). A natural question is whether participants can better form the
grand coalition and achieve a higher efficiency if they can negotiate freely in an unstructured bargaining environment. Establishing such a benchmark in more “cooperative”
environments and comparing them with the results obtained under “noncooperative”
environments would be fruitful future research.

26

References
A BE , T., Y. F UNAKI , AND T. S HINODA (2021): “Invitation Games: An Experimental
Approach to Coalition Formation,” Games, 3, 64.
C HESSA , M., N. H ANAKI , A. L ARDON , AND T. YAMADA (2021): “An experiment on
the Winter demand commitment bargaining mechanism,” ISER DP 1152, Institute ofSocial and Economic Research, Osaka University.
——— (2022): “An experiment on the Nash program: Comparing two strategic mechanisms implementing the Shapley value,” ISER DP 1175, Institute of Social and Economic Research, Osaka University.
F ISCHBACHER , U. (2007): “z-Tree: Zurich toolbox for ready-made economic experiments,” Experimental Economics, 10, 171–178.
G REINER , B. (2015): “An Online Recruitment System for Economic Experiments,”
Journal of the Economic Science Association, 1, 114–125.
G UL , F. (1989): “Bargaining Foundations of Shapley Value,” Econometrica, 57, 81–95.
H ARSANYI , J. C. (1981): “The Shapley Value and the Risk Dominance Solutions of
Two Bargaining Models for Characteristic-Function Games,” in Essays in Game Theory and Mathematical Economics, ed. by R. J. A. et al., Mannheim: Bibliographisches Institut Mannheim, 43–68.
H ART, O. AND J. M OORE (1990): “Property Rights and the Nature of the Firm,” Journal of Political Economy, 98, 1119–1157.

27

H ART, S. AND A. M AS -C OLELL (1996): “Bargaining and Value,” Econometrica, 64,
357–380.
K AGEL , J. H. AND A. E. ROTH, eds. (1995): The Handbook of Experimental Economics, Princeton, NJ: Princeton University Press.
K RISHNA , V. AND R. S ERRANO (1995): “Perfect Equilibria of a Model of N-Person
Noncooperative Bargaining,” International Journal of Game Theory, 24, 259–272.
L I , S. (2017): “Obviously strategy-proof mechanisms,” American Economic Review,
107, 3257–3287.
M YERSON , R. B. (1980): “Conference structures and fair allocation rules,” International Journal of Game Theory, 9, 169–182.
NASH , J. F. (1950): “The Bargaining Problem,” Econometrica, 18, 155–162.
——— (1953): “Two person coooperative games,” Econometrica, 21, 128–140.
P ELEG , Z. AND P. S UDHÖLTER (2007): Introduction to the Theory of Cooperative
Games, Theory and Dcision Library C, Heidelberg: Springer-Verlag Berlin.
P ÉREZ -C ASTRILLO , D. AND D. W ETTSTEIN (2001): “Bidding for the Surplus : A
Non-cooperative Approach to the Shapley Value,” Journal of Economic Theory, 100,274–294.
S ERRANO , R. (2005): “Fifty Years of the Nash Program, 1953-2003,” Investigaciones
Economicas, 29, 219–258.
——— (2008): “Nash Program,” in The New Palgrave Dictionary of Economics, 2ndedition, ed. by S. Durlauf and L. Blume, McMillan, London.
28

——— (2014): “The Nash Program: A Broader Interpretation,” Ensayos, 33, 105–106.
——— (2021): “Sixty-Seven Years of the Nash Program: Time for Retirement?” SERIEs, 12, 35–48.
S HAPLEY, L. S. (1953): “A Value for n-Person Games,” in Contribution to the Theoryof Games, ed. by H. Kuhn and A. Tucker, Princeton, vol. II, 303–317.
W INTER , E. (1994): “The Demand Commitment Bargaining and Snowballing Cooperation,” Economic Theory, 4, 255–273.

A

English translations of the instruction materials

The instruction materials as well as screenshots of the quiz for• H-MC can be obtained from https://www.dropbox.com/s/78lf5bn6qi3qfwp/
HMChandout_sim.pdf?dl=0• PC-W can be obtained from https://www.dropbox.com/s/yc584hk4c58ceyr/
PCW_handout.pdf?dl=029