Cost‐sharing in directed networks: Experimental study of equilibrium choice and system dynamics

• Published date: 01 November 2015
• Date: 01 November 2015
• DOI: http://doi.org/10.1016/j.jom.2015.07.004

Cost-sharing in directed networks: Experimental study of equilibrium

choice and system dynamics

Caiyun Liu

a

, Vincent Mak

b

, Amnon Rapoport

c

,

*

a

Northwestern University, Kellogg School of Management, 2001 Sheridan Road, Evanston, IL 60208, USA

b

University of Cambridge, Cambridge Judge Business School, Trumpington Street, Cambridge CB2 1AG, United Kingdom

c

University of California, Riverside, A. Gary Anderson Graduate School of Management, 900 University Ave.,Riverside, CA 92521, USA

article info

Article history:

Available online 26 July 2015

Accepted by Daniel. R. Guide

Keywords:

Cost-sharing

System dynamics

Positive externalities

Experiment

abstract

This study reports the results of an experiment on directed networks with positive externalities induced

by cost-sharing. Subjects participated in a network game in which they had to choose between private

and public transportations. If a player chose public transportation, then she shared the travel cost equally

with other players making the same choice, whereas if she chose private transportation, then her travel

cost was fixed. Travel costs on the private route were manipulated across the two experimental condi-

tions. In one condition, these costs were homogeneous among players; in the other condition, they were

heterogeneous among players and only privately known. We found that half (none) of the player groups

in the homogeneous (heterogeneous) condition converged toward the efficient equilibrium. Examination

of the system dynamics shows that convergence toward efficiency was facilitated by: (1) the existence of

an intermediate equilibrium choice; and (2) strategic teaching by which a farsighted player chooses

strategies with poor short-term payoff in order to shift group decisions to the efficient equilibrium and

thereby increase her own long-term benefit.

©2015 Elsevier B.V. All rights reserved.

1. Introduction

Transportation networks provide the foundation for the move-

ment of people and goods across space and time, and are essential

to the functioning of modern societies. The design and control of

such networks requires thorough understanding of fundamental

physical, behavioral,and social issues that are major researchtopics

in the management, transportation research, economics, and

computer sciences. Focusing on cost-sharing in directed networks,

our study is positioned at the intersection of these disciplines.

In many settings in transportation networks, the overall

behavior of the system is a complex product of the actions of

multiple independent agents (e.g., drivers, commuters, etc) who

can generally be labeled as network users. These agents typically

attempt to optimize their objective functions with no regard for the

welfare of others. The externalities resulting from the decisions of

each user are negative if individual benefits are a decreasing func-

tion of the number of other group members making similar choices.

Examples include choice of routes in congestible networks

(Cominetti et al., 2006, 2009; Correa and Stier-Moses, 2011;

Rapoport et al., 2009, 2014; Mak et al., 2015), and choice of time of

departure in directed traffic networks with multiple bottlenecks

(Daniel et al., 2009). In many other settings, the externalities are

positive, as when the benefit of a choice of route is an increasing

function of the number of other users making the same choice. This

could happen, for example, when users of the same mode of

transportation share the travel cost, as could happen with carpool

and shuttle taxi. Previous experimental research on interactive

decision behavior in networks (e.g., Daniel et al., 2009; Gisches and

Rapoport, 2012; Mak et al., 2015; Morgan et al., 2009; Rapoport

et al., 2006, 2009, 2014; Selten et al., 2007) has focused on

network games with negative externalities. In contrast, ours is the

first experimental study of cost-sharing in traffic network games

with positive externalities.

Our study is particularly concerned with whether eand if so,

how enetwork users might achieve collectively the efficient (so-

cially optimal) Nash equilibrium through repeated play of a cost-

sharing network game when the stage game has Pareto rankable

equilibria. The socially optimal equilibrium may naturally be

viewed as the optimal outcome subject to the constraint that the

solution is “stable”in the sense that no agent has an incentive to

unilaterally deviate from it once it is proposed (e.g., by a network

*Corresponding author.

E-mail addresses: c-liu@kellogg.northwestern.edu (C. Liu), v.mak@jbs.cam.ac.uk

(V. Mak), amnonr@ucr.edu (A. Rapoport).

Contents lists available at ScienceDirect

Journal of Operations Management

journal homepage: www.elsevier.com/locate/jom

http://dx.doi.org/10.1016/j.jom.2015.07.004

0272-6963/©2015 Elsevier B.V. All rights reserved.

Journal of Operations Management 39-40 (2015) 31e47

designer) or, alternatively, reached by some process of adaptive

learning. Our findings show that the likelihood of subjects

converging toward the efficient equilibrium depends crucially on

whether the payoff functions are common knowledge. In Condition

Homogeneous, where travel costs were the same and commonly

known among users, half of the groups converged toward the so-

cially efficient equilibrium. In Condition Heterogeneous, where the

variable travel cost of private transportation was only privately

known, nine of the ten groups converged toward the inefficient

equilibrium. Wefurther suggest that convergence toward efficiency

was facilitated by: (1) the existence of an intermediate equilibrium

choice, and; (2) strategic teaching by which farsighted (sophisti-

cated) players made route choices that significantly decreased their

short-run payoff in order to signal their willingness to join public

transportation and thereby achieve long-run benefits. These signals

could facilitate the migration of the route choices of other group

members over iterations of the stage game toward the efficient

equilibrium.

We place special emphasis on the dynamics of play, in particular

dynamics that converge to socially optimal outcomes (see, e.g.,

Balcan et al., 2013; Charikar et al., 2008). We note that when

experimental games are iterated in time, players may change their

behavior over iterations, exhibiting behavior that simultaneously

depends on their growing understanding of the structure of the

game and on revisions of their beliefs about future behavior of

other players in the system. Most of the previous literature

attempted to explain the dynamics of play in experimental games

in terms of reinforcement learning, belief learning, regret minimi-

zation, and best-response behavior (cf. Balcan, 2011; Balcan et al.,

2013; Camerer 2003; Chapter 6; Erev et al., 2010; Nisan et al.,

2007; among other examples). As noted by Balcan et al. (2013),

these learning models are myopic and therefore do not fully cap-

ture the information that the players may have prior tothe game or

possibly acquire during the game about its overall structure, or the

farsighted behavior of the users when the stage game is iterated in

time. Balcan et al. (2013) mention two barriers to simple dynamics

performing well in accounting for decision behavior. The first is

computational; we do not know how convergence to some

outcome, if reached at all, depends on the particular parameters of

the experiment. The second barrier is incentive-based. Even if an

efficient solution is known by the players, there is the issue of

whether the players would individually be willing to play it. This

may depend on the beliefs that the players acquired in previous

periods about the rationality of the other players,the strategies that

other players may be expected to employ in the future, and the

degree that other players may be trusted to adhere to tacit agree-

ments if, indeed, they have been reached. Moreover, to gain trac-

tability, existing models often assume homogenous agents,

whereas the experimental literature on repeated interactive

behavior in large groups presents ample evidence for considerable

individual differences (e.g., Gisches and Rapoport, 2012; Selten

et al., 2007). Our perspective is that if a network game has multi-

ple equilibria that are Pareto rankable, as in our study, then players

have the option of sending signals, frequently at a high short-term

cost to themselves, about their intention to shift group behavior

from an inferior equilibrium to a more efficient equilibrium. We

later refer to such behavior as strategic teaching. Some players may

intrinsically be more inclined to send such signals than others.

Depending on their number, these players may be critical in the

convergence of the group toward an efficient outcome. We shall be

reporting evidence in support of this kind of dynamics.

The rest of the paper is organized as follows. Section 2outlines

the theoretical background of fair cost-sharing allocation mecha-

nism that we employed in our experiment and the general design

of our experiment. Section 3reviews recent relevant literature on

route choice. Section 4describes the experiment. Sections 5and 6

report the results of the experiment, including basic data analysis

followed by in-depth analysis of the dynamics of play.We conclude

the paper with Section 7, which includes further discussion of our

findings and proposes ideas for future research.

2. Theoretical background and general experimental design

2.1. Fair cost-sharing allocation mechanisms

A cost-sharing allocation mechanism may be viewed as the

underlying protocol of play that determines how much a network

that serves multiple users will cost to each of them. Theoretical

research in this area has been mostly conducted by computer sci-

entists interested in communication networks (e.g., Anshelevich

et al., 2003, 2008; Balcan et al., 2013; Harks and Miller 2011). In

the simplest protocol, each user i,i¼1, 2, .., k, has a pair of nodes

(O

i

,D

i

) in a directed graph that she wishes to connect. She does so

by choosing a path S

i

that originates at O

i

and terminates at D

i

. The

cost-sharing allocation mechanism then charges user ia cost of

C

i

(S

1

,S

2

,…,S

k

), implying that the cost of user imay depend on the

choice of paths by the other users. In our experiment, we focus on a

very natural allocation mechanism where the cost of each edge is

shared equally by all the users whose paths contain it. That is:

C

i

ðS

1

;S

2

; :::; S

k

Þ¼ S

e2S

i

c

e



j:e2S

j





;

where c

e

is the cost associated with traversing edge eand jxjis the

number of elements in set x. This equal (“fair”) cost-sharing allo-

cation mechanism can be rationalized by economic theorizing in

the following ways: (1) it can be derived from the Shapley value,

possibly the best known solution concept for cooperative games (cf.

the theoretical discussion in Moulin and Shenker, 2001; Chen and

Roughgarden, 2009); and (2) it can be shown to be the unique

cost-sharing scheme that satisfies a set of different axioms (see

Feigenbaum et al., 2001; Herzoget al., 1997). The sum of the costs in

the union of all paths S

i

, is completely paid for by the users under

this mechanism:

S

k

i¼1‘

C

i

ðS

1

;S

2

;…;S

k

Þ¼ S

e2∪

i

S

i

c

e

,

In our experimental setup, we take the fair cost-sharing allo-

cation mechanism as given, and study behavioral route choices in

anticipation of the fact that travelers on the same route would end

up sharing costs equally. The cost-sharing stage, in the context of

our experimental setup, may therefore be seen as a sequential

game’sfinal stage that was not actually played by the subjects,

while the cooperative- solution-based outcome of that stage de-

termines the functional forms of the game payoffs.

2.1.1. Example

Following examples in Anshelevich et al. (2008) and

Roughgarden and Tardos (2007), consider a directed network with

kplayers. All the players share the same destination D, but each

player istarts from her specific origin O

i

. Each player may choose a

private path (O

i

/D) and incur the cost of travel 1/i. This choice

and its outcome are not affected by the choices of other group

members. Alternatively, player imay choose the public path

(O

i

/V/D) and incur the endogenously determined cost (1 þe)/

m, where e>0 is arbitrarily small, and m(1 mk) is the number

of players choosing this path. Weassume that decisions are made in

the order 1, 2, …,k, and that each player is fully informed of the

decisions made by the players who precede her in the sequence. It

is to the benefit of all the kplayers to choose the public path

C. Liu et al. / Journal of Operations Management 39-40 (2015) 31e4732