A Simple, Fast, and Safe Mediator for Congestion Management
Kei Ikegami,1 Kyohei Okumura,1 Takumi Yoshikawa1
1

Graduate School of Economics, The University of Tokyo{ikegami-kei0120, k-okumura, takumi-yoshikawa157}@g.ecc.u-tokyo.ac.jp

Abstract
Congestion is a severe problem in cities. A large population with little information about each other’s preferences
hardly reaches equilibrium and causes unexpected congestion. Controlling such congestion requires us to collect information dispersed in the market and to coordinate actions
among agents. We aim to design a mediator that a) induces agame with high social welfare in equilibrium, b) computes anequilibrium efficiently, c) works without common prior, andd) performs well even when only some of the agents in themarket use the mediator. We propose a mediator based on a
version of best response dynamics (BRD). We prove that, in a
simple setting with two resources, “good behavior” (reporting
truthfully and following the recommendation) forms an (approximate) ex-post Nash equilibrium in the mediated game;in the equilibrium, the welfare is close to the first-best whenpreferences diverge enough. Furthermore, under a certain behavioral assumption, those who are not using the mediator
can always enjoy non-negative payoff gain by joining it even
without the full participation of others. Additionally, our experimental results suggest that such results remain valid formore general settings.

1

Introduction

Congestion is a severe problem in cities. For example, traffic congestion not only impedes the smooth transfer of inhabitants (Kreindler 2018) or causes air pollution (Gibson
and Carnovale 2015), but it also increases people’s mental
burden (Anderson et al. 2016). Congestion in public transportation also decreases productivity, as it results in many
delays and accidents. The social cost caused by congestionin Tokyo’s railway is estimated at $3.03 billion per year
(Okano, Ota, and Hirota 2017; NAVITIME 2018). Other examples of congestion include those in museums, amusement
parks, tourist spots, or restaurants. Without a doubt, a practical solution to such congestion is urgently needed.
The crowded markets are usually large, and then, eachagent may know little to nothing about each other’s preferences, making it difficult for agents to reach equilibrium,
which causes unexpected congestion. Congestion games areextensively studied in algorithmic game theory literature,
Copyright c 2020, Association for the Advancement of Artificial
Intelligence (www.aaai.org). All rights reserved.

but many papers consider a complete information setting,which seems to be unrealistic in our context. Even if we
admit the complete information, the coordination problem
still exists: there may be multiple equilibria, and agents will
have difficulty agreeing on which one to play. It is also possible that agents will have difficulty computing equilibrium,
as they are boundedly rational. Additionally, previous work
has shown that agents following a simple learning algorithm
may not reach equilibrium (Palaiopanos, Panageas, and Piliouras 2017). In any case, we cannot always expect agentsin the crowded market to play an equilibrium.
In order to mitigate the congestion, it is crucial to collect information from agents and coordinate their actions.
It is well known that Nash equilibria are often near-optimal
in congestion games with complete information under relatively weak assumptions; hence, it is worth investigating
how we implement such equilibria. To this end, we introduce a mediator to the large crowded market.
The mediator listens to the reports from agents and sends
back individual recommendations. For the moment, it may
be helpful to think of the mediator as a web application.
Each agent tells the mediator his preference over resources
and his opportunity cost (i.e., the degree of congestion aversion). Given this reported type profile, the mediator computes a Nash equilibrium in the induced complete information game via best response dynamics (BRD); then, the mediator recommends that each agent take action in the computed equilibrium. We design the mediator so that good behavior (opt-in the mediator, report their type truthfully, andfollow the recommendation) forms an approximate ex-post
Nash equilibrium. By this property, the mediator can guidepeople to the state in which each agent can use his preferredresource with reduced congestion.
One notable feature of our mediator is that its power isvery weak: it cannot compel obedience from agents, andagents can opt-out of the mediator, misreport their types,
and ignore the recommendation if they want. This property
makes it easy to introduce the mediator to the market.
Our mediator differs from the existing countermeasuresfor congestion. First, peak-load pricing (Vickrey 1963) isthe most popular and influential way of handling congestion, but in practice, institutional barriers or regulations of-Simplicity

Running-timeClass of Games

Safe Participation

PRESL(Cummings et al. 2015)

Parameter tuning
RandomExponential in# of resources

Aggregative?

P-BR(Kearns et al. 2015)

Parameter tuning
RandomPolynomial in# of agents and resources

Congestion?

No tuning
Deterministic

Polynomial in# of agents and resources

Congestion w/
individual preference

Yes

CRAB

Table 1: Comparison of the mediators. Note that “Random” means random mechanism based on differential privacy techniques;
CRAB is almost deterministic except that ties are broken uniformly at random (see Algorithm 1). “?” appears in the last column
because the listed previous work does not consider the existence of outsiders.
ten prevent such pricing. For example, public transportation
fares are often regulated by law and hard to change flexibly. Our mediator does not need a monetary transfer so it
is more widely applicable. Second, moral suasion is sometimes used for energy conservation in peak-demand hours,
but empirical studies show that its effect, particularly thelong-run effect, is ambiguous (Allcott and Rogers 2014;
Ito, Ida, and Tanaka 2018). By contrast, our mediator has
an incentive guarantee. Third, the congestion information isdisclosed to control the crowd (e.g., Google Maps). Whileeach agent changes his behavior individually under such information, our mediator alters the behavior of agents as awhole. Moreover, our mediator recommends action to eachagent; this solves the coordination problem and helps boundedly rational agents to play equilibrium. In summary, ourmediator is supposed to be more widely applicable thanpeak-load pricing and more effective than moral suasion andnaive information disclosure.

costs, the approximation rate of ex-post Nash equilibrium isbounded by the value inferred from the theoretical results on
simple cases.
Our experiments also confirm that our mediator does satisfy the safe participation property in the general cases.
Moreover, in the experiments, more outsiders can enjoystrictly positive payoff gain by joining the mediator as a) the
larger fraction of people use the mediator and b) the market
gets larger. These results suggest that our mediator performs
better in larger markets.
Our second set of experiments investigates the effect ofdifferent specifications of BRD. In the usual definition of
BRD, the initialization and the rule to pick a mover at eachstep are not defined. There are several possible ways of implementation. We observe that our specification of BRD outperforms other versions both in the realized social welfare
and in the computation time.

Our contribution
Our results
For theoretical analysis, we first focus on a simple settingwith two resources where agents have the same opportunity
cost, and both resources have the same throughput rate. We
show that good behavior forms an approximate ex-post Nashequilibrium where the approximation rate tends to zero as
the market gets large. Secondly, those who opt-out the mediator, or outsiders, can enjoy nonnegative payoff gain byjoining the mediator even when only some of the agents use
the mediator if all outsiders choose their favorites. We also
generalize these results to the case where agents have different opportunity costs, and resources differ in the throughput
rates.
Furthermore, we conduct a welfare analysis. We introduce
the notion of the price of mediation (POM), which is the ratio between the welfare attained in the equilibrium inducedby the mediator and the first-best. We compute the POM explicitly; in the large market, POM attains 1 at best, and it
keeps close to 1 as long as preferences diverge enough. (NB:
POM is 1 iff the mediated equilibrium attains the first-best.)
We also conduct multiple kinds of experiments. Our first
set of experiments shows that the mediator works wellin more general settings. Even when there are more than
two resources and agents have heterogeneous opportunity

This paper is directly motivated by previous work that has
proposed weak mediators, P-BR (Kearns et al. 2015) and
PRESL (Cummings et al. 2015); both are applicable to congestion games. They rely on algorithms based on differential
privacy techniques. Though their mediators have various favorable theoretical properties, we face difficulties when implementing it in practice, as we will discuss shortly. We aim
at an implementation-oriented mediator.
Our conceptual contribution is the introduction of a mediator named Credible Recommender based on Agent-madeBillboard (hereafter called CRAB), based on a simple BRD.
The previous work argues that a mediator who naively computes a Nash equilibrium of the complete information game
induced by reported types may fail (Kearns et al. 2014). In
order to prevent such failure, it is crucial to ensure that eachagent can hardly affect the output of the mediator by misreporting; this is why they use differentially private algorithms. However, we show that, in congestion games (withplayer-specific utilities), the mediator based on a simple
BRD performs well. CRAB has the following distinctive
features (see also Table 1):
Simplicity CRAB is simple in the following two senses:
First, given a reported type profile, CRAB returns an equi-librium action profile with certainty. In contrast, both P-BR
and PRESL return a non-equilibrium action profile, which
can result in poor social welfare with a small probability.
This property is sometimes problematic when we persuade
practitioners to use the mediator. Second, unlike CRAB, weneed hyperparameter tuning for P-BR and PRESL. This
point also makes them hard to deploy.
Fast computation The running time of CRAB is polynomial in both the number of agents and resources (Proposition 1) since it relies on a simple -BRD. In contrast,
PRESL takes time exponential in the number of resources.
P-BR’s running time is also polynomial, but we show
through experiments that ours is more efficient. Table 2
shows the running time of CRAB and P-BR.
(n, k)

CRAB

P-BR(100, 5)(100, 10)(200, 5)(200, 10)(500, 5)0.003s
0.005s
0.013s
0.022s
0.0647s2.326s
3.522s
29.332s
71.988s
466.132s

Table 2: CRAB vs. P-BR: Running time comparison. (n, k)
is a pair of the number of agents n and the number of resources k.

Generality CRAB can deal with singleton congestion
games with player-specific utilities (Milchtaich 1996). This
game class is a subclass of multi-dimensional aggregative games, but a superclass of simple singleton congestion
games (Ieong et al. 2005), and general enough to treat allocation problems with negative externality.
Safe participation When we consider introducing a newmechanism to the existing market, it is quite likely that only
some of the people will start to use it. Even if a mechanism has favorable theoretical properties, assuming that all
the agents in the market use it, the existence of outsiders canpotentially negatively affect its excellence. Although few papers have carefully considered such problem, CRAB guarantees that each outsider can always enjoy nonnegative payoff gain by joining it even without the full participation ofothers.
Welfare guarantee To our knowledge, there is no welfare guarantee, such as POA (Roughgarden 2005), applicable to our case: agent-specific affine edge costs with possibly negative constants. In a simple setting with two resources, we evaluate the social welfare attained by CRAB.
Notably, the welfare under CRAB is near-optimal when
agents’ preferences diverge enough. Moreover, the experimental results are also of interest: Our specific initialization
rule and choice rule contribute to high welfare under various
parameters.

Related work
The notion of a mediator in a game-theoretic setting has along history (Aumann 1974; Forges 1986; Myerson 1986;
Bergemann and Morris 2019). Recent works consider several versions of mediation tailored to specific settings, including recommendation system, auction, and routing (Ashlagi, Monderer, and Tennenholtz 2009; Monderer and Tennenholtz 2004; 2009; Kakade et al. 2003; Rozenfeld andTennenholtz 2007; Rogers and Roth 2014). In particular, as away to mediate in congestion games, a weak mediator is introduced (Cummings et al. 2015; Kearns et al. 2015). Weak
mediators are supposed to be easier to introduce to the realmarket than one with stronger power (Rozenfeld and Tennenholtz 2007). Thus, this paper focuses on the weak mediator.
Congestion games have also been studied extensively inthe field of algorithmic game theory (Nisan et al. 2007).
Many versions have been proposed, and our formulation
lies in congestion games with player-specific costs (Milchtaich 1996). The existence of pure Nash equilibrium is guaranteed in this game class even when each agent has his
own weight (Mavronicolas et al. 2007; Milchtaich 2009;
Ackermann, Roglin, and Vocking 2009).
In reality, it is quite likely that only some of the agentswill participate in the mechanism after its introduction to
the market; it is worth investigating whether outsiders want
to start using the mechanism without the full participation ofothers. However, few papers have carefully considered thissafe participation problem (Roth and Shorrer 2018). One notable exception is a routing mediator (Rozenfeld and Tennenholtz 2007), in which the authors let the mediator be
informed of the behavior of all agents, including outsiders.
Though the assumption is acceptable in their setting, it may
not be the case in our large market setting.

2

Model

In this section, we introduce our mathematical model ofgames and equilibrium concepts. We consider a congestion
game with incomplete information where agents have private preferences over resources. We call this original oneshot game the underlying game: the strategic situation where
agents somehow make their decisions without a mediator.
Formally, our underlying game is defined as a tuple G =hI, {Ai , Ti , ui }i∈I i, where each element is defined as follows:• Let I be the finite set of all agents in the market. |I| = n.
• Let Ai ≡ A be the finite set of resources. The parametertk > 0 represents the throughput rate of resource k. 1
• xi ∈ A denotes the action of agent i: xi = k iff agent ichooses k. We call x = (xi )i∈I action profile.
• Let nk (x) be the number of agents choosing k given action profile x:
nk (x) := |{i ∈ I : xi = k}| .
1

When resources are trains, for example, we may regard tk as
the capacity of train k. In such cases, λi represents agent i’s degreeof congestion aversion.

• The payoff of each agent i given action profile x is:
ui (x) :=vi (xi )| {z }

preference term

−

λi
|{z}

opportunity cost·nxi (x)tx| {zi }

waiting time

where λi > 0 represents the opportunity cost of agent
i: the larger λi is, the more congestion-averse agent i is.
vi (k) ∈ R is agent i’s utility of using resource k. The
payoff is measured in terms of money.
• τi := vi (·), λi is agent i’s type, which is i’s private information. Let Ti ≡ T = RA × R>0 be the type space.

Mediator and mediated gameFirst, we introduce a mediator to the underlying game described above. The mediator collects private informationfrom each agent and suggests an action to each agent, hoping
for mitigating congestion and attaining high social welfare.
The introduction of the mediator induces an extensive form
game named mediated game; the timing is as follows:
1. Each agent decides whether to use the mediator or not.
2. If he uses the mediator, he reports his type to it.
3. The mediator sends back a recommendation to each agent.
Only those who report their type receive the recommendation.
4. All agents in the market, including those who opt-out, simultaneously decide which resource to choose; the payoff
is realized.
Each agent can decide whether to utilize the mediator;even when he opts in, he can misreport his type; he is also
free to ignore the suggestion. What the mediator can do isjust listen to agents’ reports and send back a non-binding
recommendation. In this sense, we say the mediator is weak.
Formally, mediator is a tuple M = h{Ri }i∈I , µi, where:• Ri ≡ R = {T ∪ {⊥}} is the message space of agent i
where ⊥ means opting out of the mediator. Agent i reportsri ∈ Ri to the mediator.
• µ : Rn → ∆ (An ) is the recommendation rule: it defines
how the mediator sends back a recommendation given thereported profile r = (ri )i ∈ Rn .
The mediated game is defined as a tuple G M =M
hI, {AM≡ AM = A0 ∪ A⊥ is
i , Ti , ui }, Mi, where Ai
the new action space where:• A0 := T × AA is the action space of those who opt-in the
mediator. The function f ∈ AA determines which action
to choose given the suggestion.
• A⊥ := {⊥} × A is the action set for those who opt-out.
They can freely choose the resource based on their private
information.
We do not assume any prior distribution over type spacebecause our solution concept is ex-post Nash equilibrium.
This concept of equilibrium is more robust than BayesianNash equilibrium, which is usually adopted as a solution
concept of an incomplete information game. Weak assumptions on information enables the mediator to be introduced
to a variety of situations in the real world.

Definition 1 (Approximate Ex-Post Nash Equilibrium).
Given  > 0, a pure strategy profile σ := (σi )i∈I , whereσi : T → AM for each i, is -approximate ex-post purestrategy Nash equilibrium in the mediated game if:∀τ ∈ T n ∀i ∈ I ∀xi ∈ A;
ui (σi (τi ), σ−i (τ−i )) ≥ ui (xi , σ−i (τ−i )) − .
Next, we define a specific strategy in the mediated gamenamed good behavior: when following good behavior, an
agent uses the mediator, reports his type truthfully, and follows the recommendation. The formal definition is as follows:
Definition 2 (Good behavior). Let id : A → A be the identity function. The strategy σi of agent i in the mediated gameis said to be good behavior if σi (τi ) = (τi , id) for any
τi ∈ T .
Suppose that the mediator can compute a Nash equilibrium of the complete information game induced by the reported type profile and send it back to agents. Then, if good
behavior forms an ex-post Nash equilibrium in the mediated game, agents can agree to play one specific equilibrium. Moreover, particularly in a congestion game, we can
expect that the social welfare under such equilibrium is nearoptimal. Thus, our agenda is to design a mediator with thisproperty.

Credible Recommender based on Agent-madeBillboard (CRAB)

Figure 1: Whole process of CRAB
Now we introduce our mediator, CRAB. Given Ri , weconstruct the recommendation rule µ. Suppose that, amongn agents in the market, m agents use the mediator. Given thereport profile (τ1 , . . . , τm ), the algorithm runs BRD for the
induced game played with m agents.
We adopt a version of the famous BRD as our recommendation rule (see Algorithm 1). 2 In the usual definition of
BRD, an initialization rule (which resource agents initiallychoose) and a choice rule (who moves in each iteration) are
undefined, and there is room for exploration. We adopt best
as our initialization rule, and max increment as our choice
rule: best puts each agent on his best resource initially; max
increment chooses the agent who can increase his payoff
2
BRi (x) ∈ argmaxx0 ui (x0i , x−i ) denotes agent i’s best rei
sponse to x−i .

most by a deviation (in case multiple agents meet this criterion, ties are broken at random). This specification simplifies
the theoretical analysis of the algorithm. Moreover, it contributes to the better performance of CRAB as we will seein the experimental results section.
Algorithm 1 -BRD(τ = (τ1 , · · · , τn ) , )xi := argmaxk vi (k) for all i.
while ∃ i? s.t. ui? (BRi? (x), x−i? ) ≥ ui? (x) +  doM ← argmaxi {ui (BRi (x), x−i ) − ui (x)}Choose i from M uniformly at random.
Let xi ← BRi (x)end while
The next proposition guarantees that CRAB always computes equilibrium, and its calculation is fast.
Proposition 1. For any reported type profile and  > 0,
CRAB computes a pure -Nash equilibrium in polynomial
time (polynomial in the number of agents and resources).
Proof. LetX  vi (xi )1
Φ(x) :=
2·(nxi (x) + 1) .
+
λi
txi
i
Then, for any i, x, xi and x0i , we have2[ui (xi , x−i ) − ui (x0i , x−i )] .
λi(This follows from Theorem 6 of Mavronicolas et al.
(2007)). We observe that the range of Φ is polynomial in
the number of agents and goods. Moreover, in each iteration, the value of Φ decreases by at least 2/(mini λi ). The
claim follows.

Φ(xi , x−i ) − Φ(x0i , x−i ) =3

Theoretical Results

In this section, we focus on the simple two-resource caseand prove the theoretical results. Though we only give theproof for the relatively simple cases, in the following section, we confirm that similar results hold in more general
settings through numerical experiments. Due to space constraints, we defer all proofs to Appendix.
For our analysis, we pose some assumptions. The first assumption is that the throughput rates go to infinity as thenumber of agents gets large. Naturally, the capacity of eachresource is high in a market with a large population (or we
may think that there appear to be many similar resources).
This assumption is commonly adopted in the literature ofcongestion games with a large population. (Feldman et al.
2016).
Assumption 1. For any resource k, tk → ∞ as n → ∞.
Next, we assume the behavior of outsiders: each agent
chooses his favorite when he opts-out. This can occur as a result of agents’ rational decision making when, for example,
agents are optimistic enough to believe that their favorites
will not be too crowded. More realistic is that they cannot
help doing so due to scarce information about each other’s
preferences.

Assumption 2. If an agent opts out of the mediator, hechooses his favorite resource. 3
Homogeneous setting There are two resources 1 and 2.
In our homogeneous setting, they have the same throughput
rate t in common. Moreover, agents have the same opportunity cost λ.
There are two types of agents, τ 1 and τ 2 : an agent withk
τ prefers resource k to another. If an agent uses his favorite,
his payoff is v1 minus the congestion cost; if he uses the lesspreferred one, it is v2 minus the congestion cost. The values
v1 , v2 are common across agents. For example, if an agent
with type τ 2 uses resource 1, his payoff is v2 − (λ/t) · n1 .
First, we can show that good behavior forms an equilibrium with CRAB, assuming the participation of all agents inthe market.
Theorem 1 (Implementation [homogeneous case]). Assume
that all agents opt-in the mediator. In a homogeneous setting, good behavior forms (λ/t)-approximate ex-post Nashequilibrium in the mediated game. The approximation factor
tends to zero as the market gets large under Assumption 1.
Proof sketch. Let sk be the number of agents with τ k (k ∈{1, 2}). Wlog, assume s1 ≥ s2 . The simplicity of the setting
allows us to analyze the behavior of CRAB in detail. We
can show that what our BRD does is to move agents with τ 1from 1 to 2 until it reaches equilibrium. By this property, we
can divide the proof into subtle cases and obtain the statement. See the Appendix for further details.
Next, we consider the case where only some of the agentscurrently uses the mediator. We show that it is safe for eachoutsider to start using CRAB.
Theorem 2 (Safe participation [homogeneous case]). Suppose that all users of CRAB follow good behavior. Then, ina homogeneous setting, each outsider enjoys non-negative
payoff gain when joining the mediator under Assumption 2.
Lastly, we conduct a welfare analysis. It is well known
that the welfare under a pure Nash equilibrium in congestion
games and its variants are often near-optimal (POA is close
to 1 (Roughgarden 2016)); it is naturally expected that thesame is true in the settings with individual preference, v1
and v2 .
Below, we additionally assume that throughput rates (tk )kcannot increase as rapidly as population n. This seems natural given the law of diminishing marginal returns.
Assumption 3. tk = o(n) for any k.
The following theorem provides the welfare guarantee:
the price of mediation (POM) is the ratio between the social welfare under the good behavior equilibrium and thefirst-best, which is the maximized social welfare, ignoring
the incentive constraints. Formally:P
i ui µ((τi )i )P
POM =maxx i ui (x)3

We use Assumption 2 only when proving Theorem 2 and 5.

Let s ∈ [0, 1] be the fraction of agents with τ 1 . Wlog, we
assume s ∈ [1/2, 1]. Note that the social welfare can be both
positive and negative in general. However, if n is so largethat v1 < 2s2 − 2s + 1 nc, we can show that the first-best
takes a negative value (see the Appendix for details). As wefocus on the large market, we restrict our attention to suchcase where POM is more than or equal to 1.
We can compute the upper bound of POM in the large
market explicitly (see the Appendix for the details):
Theorem 3 (POM bound in the large market). For a sufficiently large market, POM is bounded from above by:11
13(2s − 1)4 + (2s − 1)3 + (2s − 1)2 + 1.
4
2
4
POM attains its minimum 1 at s = 1/2 and attains
its maximum 5 at s = 1. It is increasing on [1/2, 1].
Moreover, it is convex and increases slowly when s is not
close to 1. This means that as long as the agents’ preferences diverge enough, the social welfare attained at theequilibrium induced by the mediator is close to the firstbest. Table 3 expresses the exact POM value at each s ={0.5, 0.6, 0.7, 0.8, 0.9, 1.0}.
s
POM

0.5
1.00

0.6
1.13

0.7
1.56

0.8
2.31

0.9
3.44

1.0
5.00

Table 3: POM increases slowly as long as s is not very close
to 1.

Figure 2: The maximum payoff gain by deviation from good
behavior is bounded from above by the value inferred from
Theorem 4, even with more than two resources.

4

Experimental Results

In this section, we show the results of our series of experiments. The experimental details, including the precise parameter settings, are provided in the Appendix.

Extensions to general cases
Heterogeneous setting Our heterogeneous setting is moregeneral than the homogeneous setting in two senses: First,
resources differ in throughput rates, or t1 6= t2 . Second,
agents have different opportunity costs λH and λL , where
λH > λL .
There are four types of agents: (τ 1 , λH ), (τ 1 , λL ),2(τ , λH ), and (τ 2 , λL ). Again, agents with τ k prefer resource k. For instance, the payoff of an agent with (τ 2 , λH )choosing resource 1 is v2 − (λH /t1 )n1 .
We have the generalizations of Theorem 1 and Theorem 2
for this setting:
Theorem 4 (Implementation [heterogeneous case]). Assume that all agents opt-in the mediator. In a heterogeneous setting, good behavior forms (λH / min{t1 , t2 })approximate ex-post Nash equilibrium in the mediatedgame. The approximation factor tends to zero as the market gets large under Assumption 1.
Theorem 5 (Safe participation [heterogeneous case]). Suppose that all users of CRAB follow good behavior. Then, ina heterogeneous setting, each outsider enjoys non-negative
payoff gain when joining the mediator under Assumption 2.
In the following section, we confirm that the results ofthese theorems can be extended to more general settings
with experiments. In particular, Theorem 4 leads us to guess
about the upper-bound of the payoff gain by deviation: weguess the bound is λ̄/t, where λ̄ := maxi λi and t =mink tk , which also tends to zero under Assumption 1.

We confirm that the theoretical results we have shown in theprevious section can be extended to more general cases.
First of all, we check whether the payoff gain by deviation from good behavior is bounded from above. From Theorem 4, we guess that the upper bound should be λ̄/t whereλ̄ := maxi λi and t = mink tk . We conduct simulations in alarge number of different parameter settings with 3 or moreresources to check this hypothesis.
Figure 2 summarizes the results. The horizontal line corresponds to the inferred upper bound λ̄/t, and the verticalline is the maximum payoff gain. Each instance represented
by a dot comes below the 45-degree line, which indicates theinferred upper bound is valid when the number of resources
is more than two.
We also check if the safe participation property holds inthe more general cases. We conduct simulations in various
parameter settings with up to 10 resources.
The first remarkable observation is that no outsider decreases his payoff by entering the mediator regardless of themarket size and the participation rate. Furthermore, we findtwo general trends; more outsiders get strictly positive payoff gains by joining the mediator as:
1. the participation rate gets higher for any market size; and2. the number of existing agents gets larger for any participation rate.
Figure 3 summarizes the simulation results. These features suggest that CRAB can benefit the individual morewhen the market size is large and more people use CRAB.

Figure 3: Plot the average rate of outsiders with positive gainat each participation rate. We take an average of 20 experiments with 4 resources.

Figure 4: Histogram of necessary iterations for each initialstate. We consider only the max increment picking rule.

Close study of the detail of BRD

the picking rule to the former and compare the required steps
for each initialization rule. Figure 4 gives the histogram of
the number of iterations to reach an equilibrium: the CRAB
rule requires a fewer number of iterations than the others.

With the actual implementation in mind, we analyze how thedetails of BRD affect the performance of the mediator. Our
objective is to make the mediator faster, more robust, andmore efficient.
In order to define BRD precisely, we need to fix the choicerule and the initialization rule, neither of which the usual
definition of BRD precisely determines. The choice rule
specifies who moves at each step of BRD. Here, we consider two options: (1) to pick the agent with the maximum
payoff gain (max increment), or (2) to pick the one withthe minimum payoff gain (min increment). As for the initialization rule, we compare three alternatives: initially, allagents choose (1) their best preferred resources (best), (2)their worst preferred ones (worst), and (3) the same one
resource (oneside). The BRD used by CRAB adopts thepair of rules max increment and best. We call this pair the
CRAB rule. The CRAB rule not only simplifies the theoretical analysis, as shown in Appendix, but also enables CRAB
to perform better in practice.
We conduct experiments in a two-resource setting. We try
2, 160 parameters made from reasonable values. For all pairsof rules, we compare the realized social welfare, which isthe summation of the payoffs of all agents, and the iteration
numbers required to reach equilibrium.

MAX INCREMENTMIN INCREMENT

BEST

WORST

ONESIDE

0.904
0.823

0.826
0.812

0.830
0.830

Table 4: Equilibrium selection. CRAB rule (top, left) gives
the highest rate of obtaining the best equilibrium among thesix pairs. The different rules may converge to the same best
equilibrium; the sum of all cell values may not be 1.
Each cell in Table 4 indicates the fraction of parameter
sets in which a corresponding pair of rules attain the highest
social welfare among the six rules. The CRAB rule obtains
the highest social welfare in 90% of the parameters, which
outperforms the other pairs of rules.
In the experiments, we observe that the max increment
demands fewer iterations than the min increment. We fix

5Discussion and Future Directions

We prove our theoretical results for the two-resource case.
One natural extension is to provide the proofs for generalcases; for the moment, we observe that the results are likely
to hold just experimentally. It is worth exploring whether
similar results hold when (1) there are more than two resources, (2) the number of sets of opportunity costs is morethan two, or (3) the values of the utility of resources differ
among agents (NB: we assume that agents have v1 and v2 incommon).
We are now planning to implement CRAB as a web application in a real crowded market to evaluate its practical
performance (see also the Appendix). Such empirical work
is also one possible research direction.
However, to this end, we need to resolve the report costproblem, the classical problem in the mechanism design literature: it is too demanding for agents to report their preferences over all the alternatives. It is unrealistic to require people to rank all available alternatives and report that ordering;
it is not only burdensome but also cognitively challenging.
Another problem regarding report costs, which is uniqueto the congestion problem, is that the mediator needs toknow not only the agents’ valuations about resources, vi (·),
but also their opportunity costs λi . We cannot expect themto report their opportunity costs in addition to the preference
list. It is nearly impossible to ask questions like: “Which do
you prefer, a) resource 1 with a waiting time of 10 minutes,b) resource 2 with a waiting time of 30 minutes, or c) resource 3 with a waiting time of 25 minutes?”
We believe that the mediator incorporating statistical analysis enables us to handle the report cost problems. CRAB,
in real markets, estimates the true parameter values and retrieves the full preference lists, utilizing the data collected
through the repeated use of the application. This topic must
be of interest from both theoretical and practical perspectives.

References
Ackermann, H.; Roglin, H.; and Vocking, B. 2009. Pure
Nash Equilibria in Player-Specific and Weighted Congestion Games. Theoretical Computer Science 410(17):1552– 1563.
Allcott, H., and Rogers, T. 2014. The Short-Run and LongRun Effects of Behavioral Interventions: Experimental Evidence from Energy Conservation. American Economic Review 104(10):3003–37.
Anderson, M. L.; Lu, F.; Zhang, Y.; Yang, J.; and Qin, P.
2016. Superstitions, Street Traffic, and Subjective Wellbeing. Journal of Public Economics 142:1–10.
Ashlagi, I.; Monderer, D.; and Tennenholtz, M. 2009. Mediators in Position Auctions. Games and Economic Behavior
67(1):2–21.
Aumann, R. J. 1974. Subjectivity and Correlation in Randomized Strategies. Journal of Mathematical Economics
1(1):67–96.
Bergemann, D., and Morris, S. 2019. Information Design: A Unified Perspective. Journal of Economic Literature
57(1):44–95.
Cummings, R.; Kearns, M.; Roth, A.; and Wu, Z. S. 2015.
Privacy and Truthful Equilibrium Selection for Aggregative
Games. In Proceedings of the 11th International Conferenceon Web and Internet Economics - Volume 9470, 286–299.
Feldman, M.; Immorlica, N.; Lucier, B.; Roughgarden, T.;
and Syrgkanis, V. 2016. The Price of Anarchy in Large
Games. In Proceedings of the Forty-eighth Annual ACM
Symposium on Theory of Computing, 963–976.
Forges, F. 1986. An Approach to Communication Equilibria. Econometrica 54(6):1375–1385.
Gibson, M., and Carnovale, M. 2015. The Effects of Road
Pricing on Driver Behavior and Air Pollution. Journal of
Urban Economics 89:62–73.
Ieong, S.; McGrew, R.; Nudelman, E.; Shoham, Y.; and Sun,
Q. 2005. Fast and Compact: A Simple Class of Congestion
Games. In Proceedings of the 20th National Conference on
Artificial Intelligence - Volume 2, 489–494.
Ito, K.; Ida, T.; and Tanaka, M. 2018. Moral Suasion andEconomic Incentives: Field Experimental Evidence fromEnergy Demand. American Economic Journal: Economic
Policy 10(1):240–67.
Kakade, S.; Kearns, M.; Langford, J.; and Ortiz, L. 2003.
Correlated Equilibria in Graphical Games. In Proceedingsof the 4th ACM Conference on Electronic Commerce, 42–47.
Kearns, M.; Pai, M.; Roth, A.; and Ullman, J. 2014. Mechanism Design in Large Games: Incentives and Privacy. In
Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, 403–410.
Kearns, M.; Pai, M. M.; Rogers, R.; Roth, A.; and Ullman, J.
2015. Robust Mediators in Large Games. arXiv:1512.02698[cs]. arXiv: 1512.02698.
Kreindler, G. E. 2018. The Welfare Effect of Road Congestion Pricing: Experimental Evidence and Equilibrium Implications. MIT Working paper.

Mavronicolas, M.; Milchtaich, I.; Monien, B.; and Tiemann,
K. 2007. Congestion Games with Player-Specific Constants.
In Kuera, L., and Kuera, A., eds., Mathematical Foundationsof Computer Science 2007, Lecture Notes in Computer Science, 633–644.
Milchtaich, I. 1996. Congestion Games with PlayerSpecific Payoff Functions. Games and Economic Behavior
13(1):111–124.
Milchtaich, I. 2009. Weighted Congestion Games with
Separable Preferences. Games and Economic Behavior
67(2):750–757.
Monderer, D., and Tennenholtz, M.
2004.
KImplementation. Journal of Artificial Intelligence Research
21:37–62.
Monderer, D., and Tennenholtz, M. 2009. Strong MediatedEquilibrium. Artificial Intelligence 173(1):180–195.
Myerson, R. B. 1986. Multistage Games with Communication. Econometrica 54(2):323–358.
NAVITIME, J.
2018.
Hatsushisan! Man-in Densha No Keizai Sonshitsu Wa Nenkan 3240 Okuen. (October 18, 2018) Available at TOYO KEIZAI ONLINE:
https://toyokeizai.net/articles/-/243263.
Nisan, N.; Roughgarden, T.; Tardos, E.; and Vazirani, V. V.,
eds. 2007. Algorithmic Game Theory. Cambridge University Press.
Okano, H.; Ota, K.; and Hirota, M. 2017. Estimation of
the Railway Congestion. 55th Committee of Infrastructure
Planning and Management.
Palaiopanos, G.; Panageas, I.; and Piliouras, G. 2017. Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos. In
Advances in Neural Information Processing Systems 30.
5872–5882.
Rogers, R. M., and Roth, A. 2014. Asymptotically Truthful Equilibrium Selection in Large Congestion Games. In
Proceedings of the Fifteenth ACM Conference on Economics
and Computation, EC ’14, 771–782.
Roth, B., and Shorrer, R. I. 2018. Making it Safe to Use Centralized Marketplaces: Dominant Individual Rationality andApplications to Market Design (October 1, 2018). Available
at SSRN: https://ssrn.com/abstract=3073027.
Roughgarden, T. 2005. Selfish Routing and the Price ofAnarchy. The MIT Press.
Roughgarden, T. 2016. Twenty Lectures on Algorithmic
Game Theory. Cambridge University Press.
Rozenfeld, O., and Tennenholtz, M. 2007. Routing Mediators. In Proceedings of the 20th International Joint Conference on Artifical Intelligence, IJCAI’07, 1488–1493.
Vickrey, W. S. 1963. Pricing in Urban and Suburban Transport. American Economic Review Proceedings 452–65.