Figure 7. Series of snapshots of global state in a minority power biased voting experiment, showing an instance in which a minority player
(upper left vertex R) acquiesces at various times though eventually wins out.
greedy algorithm for approximating
the maximum social welfare solution,
summarized in Figure 5. This centralized greedy algorithm simply selects random edges in the network on
which to close bargains, subject to any
deal limits in the experiment, until no
further deals could be closed without
violating some deal limit. The social
welfare obtained (which does not require specifying how the edge deals
are split between the two players) is
then simply $2 times the number of
closed deals, as it is for the behavioral
experiments as well.
The blue dots in Figure 5 each rep-
resent averages over several trials of
one of the network topologies exam-
ined (thus each dot corresponds to a
different topological family). The x
value shows the social welfare of the
greedy algorithm as a percentage of
the maximum social welfare (optimal)
solution, while the y value shows the
same measure for the human sub-
jects. Averaged over all topologies,
both humans and greedy perform
rather well—roughly 92% of optimal
(blue open circle). However, while the
greedy solutions are maximal and thus
cannot be locally improved, much of
the inefficiency of the subjects can be
attributed to what we might call the
Price of Obstinacy: at the end of many
experiments, there were a number of
deals that still could have been closed
given the deal limits on the two end-
points, but on which the two human
subjects had not been able to agree to
a split. If we simply apply the greedy
algorithm to the final state of each
behavioral experiment, and greed-
Figure 6. From independent-set experiments: Average income disparity between neighbors
(x-axis) vs. average time neighbors are conflicting kings (y-axis), both with (blue) and without (orange) side payments. Grouped by network structure. the side payments uniformly
reduced conflict and disparity.
no tipping tips allowed
0.30
0.25
conflict
0.20
Dense PA
erdos-Renyi
Clique Chain
RewiredChain
Pairs
bipartite
PA Tree
0.15
0.00
0.02
0.04 0.06 0.08
average income disparity
0.10
0.12
ily close as many remaining deals as
possible, the potential performance of
the subjects on each topology, absent
obstinacy, rises to the orange dot connected to the corresponding blue dot
in the figure. This hypothetical subject performance is now well above
the performance of pure greedy (all orange points above the diagonal now),
and the average across topologies is
close to 97% of optimal (orange open
circle). In other words, the human
subjects are consistently finding better underlying solutions than those
obtained by simply running greedy on
the initial graph, but are failing to realize those better solutions due to unclosed deals. While humans may show
aversion to inequality of payoffs, they
can also be stubborn to the point of
significant lost payoffs.
Independent set. Another set of
experiments required subjects to
declare their vertex to be either a
“king” or a “pawn” at each moment,
with the following resulting payoffs:
any player who is the only one that
has declared kingship in his neighborhood enjoys the highest possible
rate of pay; but if one or more of
their neighbors are also kings, the
player receives nothing. On the other
hand, pawns receive an intermediate
rate of pay regardless of the states of
their neighbors. It is easily seen that
the Nash equilibria of the one-shot,
simultaneous move version of this
game are the maximal independent
sets (corresponding to the kings) of
the graph, while the maximum social
welfare state is the largest independent set, whose centralized computation is NP-hard. Because we were concerned that computing payoffs based
on only the final state of the gain