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