Reliable Intersection Control in Non-cooperative Environments*

arXiv:1802.08138v1 [] 22 Feb 2018

Muhammed O. Sayin1,2 , Chung-Wei Lin2 , Shinichi Shiraishi2 , and Tamer Başar1

Abstract— We propose a reliable intersection control mechanism for strategic autonomous and connected vehicles (agents)
in non-cooperative environments. Each agent has access to
his/her earliest possible and desired passing times, and reports
a passing time to the intersection manager, who allocates
the intersection temporally to the agents in a First-ComeFirst-Serve basis. However, the agents might have conflicting
interests and can take actions strategically. To this end, we
analyze the strategic behaviors of the agents and formulate
Nash equilibria for all possible scenarios. Furthermore, among
all Nash equilibria we identify a socially optimal equilibrium
that leads to a fair intersection allocation, and correspondingly
we describe a strategy-proof intersection mechanism, which
achieves reliable intersection control such that the strategic
agents do not have any incentive to misreport their passing
times strategically.

I. INTRODUCTION
Instead of classical yet inefficient traffic lighting systems, a First-Come-First-Serve (FCFS) based autonomous
intersection control, which utilizes the connectivity of the
autonomous agents with each other and the infrastructure,
e.g., an intersection manager, has been introduced in [1].
Each agent requests the usage of the intersection at a certain
time slot, he/she has desired, and the intersection manager
confirms the request if it is available, i.e., not has already
been allocated for other agents, or proposes a counter request.
This simple approach improves the efficiency of the intersections substantially in terms of travel time of the agents.
However, the requests of the agents are evaluated one by
one. In order to increase the efficiency further, Reference [2]
proposes a combinatorial auction based approach, in which
the intersection is allocated to the agent who values the most,
instead of the agent who has requested the earliest. This
approach leads to relatively complex algorithms to compute
the intersection allocation and requires a payment system. In
[3], the authors have proposed a chicken-game [4] inspired
intersection control. The proposed game includes two players, where the players aim to minimize their delay while
also avoiding any collision; and the intersection manager
controls their actions, i.e., swerve or not, to achieve a Nash
equilibrium [5] of the game. Recently, in [6], the authors have
proposed an information driven intersection management
mechanism, which improves the quality of transportation
by prioritizing certain vehicles based on the information
reported by them and ensures truthful disclosure of that
information via a payment mechanism.

In this paper, we introduce an intersection game formulation. Different from the widely known chicken game [4],
here, we consider an intersection control scenario, where
two non-cooperative autonomous agents (drivers) seek to
use a single intersection resource at a specific time they
desire. In that respect, a desired passing time for an agent
can be considered as an estimated time such that he/she
can pass through the intersection with minimum loss of
comfort, e.g., without acceleration or deceleration (excluding
the deceleration necessary to pass through the intersection
safely). However, there is a certain time that the agents will
need while using the intersection resource. Therefore, there
can be a conflict between their desired intersection usage.
In order to avoid conflicts which might lead to accidents,
the intersection manager provides a FCFS based resource
allocation protocol so that the agent who desires to pass
through the intersection earlier will pass earlier, and if
both desire to pass at the same time, then both have the
same chance to pass first. To this end, the agents report
their desired passing times to the intersection manager and
the manager allocates the resources accordingly [1]. We
note that, here, in order to increase the efficiency of the
intersection usage, the request of two agents are evaluated
together, which is different from the proposed approach in
[1], where the agents’ requests are evaluated one by one.
However, while the evaluations of more than one request can
increase the efficiency, in a non-cooperative environment, the
agents can also report strategically, e.g., they may not reveal
their true desired passing times, in order to minimize the
deviation of the times that the manager allows them to use
the intersection from their desired passing times. Hence, we
aim to formulate the strategic behavior of the agents in this
non-cooperative environment. Furthermore, instead of any
Nash equilibrium as in [3], we seek to select the socially
optimal one among multiple equilibria, while designing the
intersection control mechanism.
The main contributions of the paper are as follows:
•

•

•

*This work was not supported by any organization.
1 University of Illinois at Urbana-Champaign, Urbana, IL 61801

{sayin2,basar1}@illinois.edu
2 Toyota

InfoTechnology

Center,

Mountain

View,

CA

94043

{msayin,cwlin,sshiraishi}@us.toyota-itc.com

We model the strategic behavior of the non-cooperative
agents in FCFS based intersections and formulate the
corresponding equilibrium points analytically.
We provide socially optimal intersection usage allocations and compute the socially optimal equilibrium
strategies for the agents.
We propose a reliable intersection control mechanism,
which ensures that the strategic agents reveal their
private information truthfully, i.e., cannot rig the intersection control mechanism by misreporting their private
information strategically.

The rest of this paper is organized as follows: In Section
II, we formulate the problem for two strategic autonomous
agents and a single intersection resource. In Section III, we
analyze the equilibrium scenarios in a strategic environment.
We provide a strategy-proof intersection mechanism, where
the agents reveal their private information truthfully, in
Section IV. We conclude the paper with several remarks in
Section V. Appendices include proofs of technical results.
II. PROBLEM FORMULATION
Consider two non-cooperative autonomous agents, agent1 and agent-2, seeking to pass through a single intersection,
which is equipped with a roadside unit that has communication radios. In close proximity of the intersection, agents,
equipped with communication radios, can request the temporal intersection usage from the roadside unit, which reserves
the intersection temporally to the agents according to a FCFS
protocol and certain safety constraints. As an example of
safety constraints, the roadside unit considers the necessary
time for the agents to pass through the intersection while
scheduling the intersection usage.
Each agent-i, for i = 1, 2, has access to private information: θe,i , θd,i ∈ Θ, denoting the earliest possible and the
desired passing times through the intersection, respectively,
where Θ ⊂ R is a totally ordered finite set such that for any
consecutive elements θ, θ0 ∈ Θ we have |θ − θ0 | = ∆ and
for all θ ∈ Θ, θ ≤ θ ≤ θ̄, where θ and θ̄ are specified upper
and lower bounds, respectively, with, e.g., θ = 0. ∆ can
be viewed as the highest precision for time reporting. Each
agent needs certain amount of time while passing through the
intersection, which is denoted by δt ∈ Θ, and we assume that
δt/2 ∈ Θ.
Agents report their passing times and the manager controls
the intersection usage according to FCFS protocol. In particular, if agents report θ̂1 > θ̂2 , then the allocated times would
be given by t2 = θ̂2 , since agent-2 comes to intersection
first, and t1 = max{θ̂1 , t2 +δt+∆}. Furthermore, in case of
equality, i.e., θ̂1 = θ̂2 , the manager allocates the intersection
to one of them first randomly, e.g., by flipping a fair coin,
for the sake of fairness. Therefore, for given reported times
(θ̂1 , θ̂2 ), the protocol computes the corresponding allocated
times, i.e., (t1 , t2 ) = FCFS(θ̂1 , θ̂2 ), uniquely.
Note that if the agent, who has the right to pass first,
starts to use the resource after his/her allocated time, the
time he/she will need to pass through the intersection might
violate the allocated time for the other agent. Or if that agent
does not use the intersection before the time allocated for
the other agent, then the agent who has the right to pass
second cannot start to use the intersection at his/her allocated
time due to a security precaution. Therefore, without certain
regulations, the agents would reveal practically unhelpful information. As an example, in the case of conflicting interests,
if the agent with later desired passing time reports that his/her
desired passing time is just now, then the manager would
allocate the intersection to that agent to use starting from now
unless the other agent has also reported to pass now. In order
to avoid such cases, we consider that there is a regulation that

the agents must use the intersection exactly at the allocated
time. Since the allocated times are computed based on the
reported desired passing times, it is the agents’ responsibility
to ensure that they will pass through the intersection as early
as their reported times. However, even though this regulation
can prevent the aforementioned cases, as we show later,
this is not sufficient to incentivize the agents to reveal their
desired passing times truthfully.
We consider that the agents are identical and have payoff
functions penalizing the deviation of the allocated times ti
from the desired passing times θd,i :
ui = c(|ti − θd,i |),

(1)

where c : R → R is a strictly increasing, strictly convex
function on [0, ∞), e.g., c(x) = x2 . We consider Nash
equilibrium [5], in which agents do not have any incentive
to change their actions unilaterally, and an agent has an
incentive to change his/her action if he/she can have a
reduced payoff. Therefore, an action pair (θ̂10 , θ̂20 ) leads to
an equilibrium provided that
θ̂10 ∈ arg min c(|t1 − θd,1 |),
θ̂1 ∈Θ

θ̂20

∈ arg min c(|t2 − θd,2 |),
θ̂2 ∈Θ

where (t1 , t2 ) = FCFS(θ̂1 , θ̂2 ). In the next section, we
examine these equilibrium scenarios in detail.
III. EQUILIBRIUM SCENARIOS IN A STRATEGIC
ENVIRONMENT
Without loss of generality, we can consider that θd,1 is
earlier than or equal to θd,2 , i.e., θd,1 ≤ θd,2 . In such
cases, if both agents reveal their desired times truthfully and
θd,1 < θd,2 , agent-1 would pass through the intersection
first at his/her desired time θd,1 and agent-2 would pass
at the time max{θd,1 + δt + ∆, θd,2 }, and if θd,1 = θd,2
then both agents would have equal chances to pass through
the intersection first. However, the agents are strategic and
a strategic agent would reveal the information truthfully if
it is the best strategy according to his/her objective, e.g.,
minimizing the payoff function (1).
We point out that the agents do not have conflicting
interests if θd,1 + δt < θd,2 . Hence in such cases, the agents
would report their desired passing times truthfully and the
manager would be able to allocate the intersection exactly at
their reported times. Otherwise the agents have conflicting
interests and in those cases, truthfulness is not an equilibrium
achieving strategy for the agents in general. In that respect,
the following cases lead to interesting equilibrium scenarios,
e.g., even though θd,1 < θd,2 , agent-2 can incentivize agent-1
to report an earlier passing time than θd,1 and under certain
conditions, the intersection might even be allocated to agent2 first. Next, we examine these scenarios in detail.
Lemma 1. Let θd := θd,1 = θd,2 . Without loss of generality,
suppose θe,1 ≤ θe,2 . Then, the action pairs {θ̂1 = θ, θ̂2 =
θ + ∆} lead to an equilibrium if there exists θ ∈ Θ such that
θ ∈ M1 := [max{θe,1 , θd − δt/2}, max{θe,2 , θd − δt/2}).

Sub1
Sub3

Fig. 1. Equilibria in the cases that θd,1 = θd,2 , and without loss of
generality we assume θe,1 ≤ θe,2 . The blue and red bars show a distance
of δt/2 from the desired passing times. Dark and light coloring is used
to represent how distant it is. As an example, right end of the bars are δt
away from θd,i , i = 1, 2. Additionally, the green bars and dot show the set
of equilibrium achieving actions of agent-1, i.e., set of θ̂1 ∈ Θ such that
thereSub2
is a θ̂2 ∈ Θ and the pair {θ̂1 , θ̂2 } leads to an equilibrium, which are
explained in Lemma 1 in detail.

Fig. 2. Equilibria in the cases that θe,1 , θe,2 ≤ θd,1 < θd,2 ≤ θd,1 + δt
and θd,2 − δt ≤ θd,1 < θd,2 − δt/2.

If M1 is empty, i.e., max{θe,1 , θd − δt/2} = max{θe,2 , θd −
δt/2}, then the action pair {θ̂1 = θ0 , θ̂2 = θ0 }, where θ0 :=
max{θe,2 , θd − δt/2}, leads to an equilibrium.
Proof. The proof is provided in Appendix A.

At equilibria of certain cases, interestingly, the reported
time of the agents can even be less than their earliest passing
time even if there is a regulation making sure that each agent
must pass through the intersection at his/her allocated time.
However, since the reported time can be different from the
allocated time, even though that agent knows that he/she
cannot pass through the intersection that early, by reporting
in that way, he/she incentivizes the other agent to report
a far earlier time such that his/her allocated time will not
be the reported time. We also note that the deviation of
this allocated time from the desired passing time can be
less than the one when he/she has reported as early as the
earliest passing time. Therefore, such equilibria can be more
preferable for the agent that has a later desired passing time.
Lemma 2. Let θe,1 , θe,2 ≤ θd,1 < θd,2 ≤ θd,1 + δt and
θd,2 − δt ≤ θd,1 < θd,2 − δt/2, then the actions pairs {θ̂1 =
θ, θ̂2 = θ + ∆} lead to an equilibrium if there exists θ ∈ Θ
such that θ ∈ [max{θd,2 − δt, θe,1 }, θd,1 ). Additionally, the
action pairs {θ̂1 = θd,1 , θ̂2 }, where θ̂2 ∈ Θ such that θ̂2 ∈
(θd,1 , θd,1 + δt + ∆], also lead to an equilibrium.
Proof. The proof is provided in Appendix B.

Lemma 3. Let θe,1 ≤ θe,2 ≤ θd,1 < θd,2 ≤ θd,1 + δt and
θd,1 ≥ θd,2 −δt/2, then the action pairs {θ̂1 = θ, θ̂2 = θ+∆}
lead to an equilibrium if there exists θ ∈ Θ such that

Fig. 3. Equilibria in the cases that θe,1 ≤ θe,2 ≤ θd,1 < θd,2 and
θd,1 Sub4
≥ θd,2 − δt/2.

Fig. 4.
Equilibria in the cases that θe,2 < θe,1 ≤ θd,1 < θd,2
and θd,1 ≥ θd,2 − δt/2. Distinctively, yellow bars represent the set of
equilibrium achieving actions of agent-2 since at those equilibria, agent-2
passes through the intersection first in spite of θd,1 < θd,2 .

θ ∈ M2 := [max{θe,1 , θd,1 −δt/2}, max{θd,2 −δt/2, θe,2 }).
However, if M2 is empty, then the action pair {θ̂1 =
θ0 , θ̂2 = θ0 }, where θ0 := max{θd,2 − δt/2, θe,2 }, leads to
an equilibrium.
Proof. The proof is provided in Appendix C.

Lemma 4. Let θe,2 < θe,1 ≤ θd,1 < θd,2 ≤ θd,1 + δt and
θd,1 ≥ θd,2 − δt/2, then we have two different cases, where
the first passing agent differs. If θe,1 ≤ θd,2 − δt/2, the
action pairs {θ̂1 = θ, θ̂2 = θ + ∆} lead to an equilibrium if
there exists θ ∈ Θ such that θ ∈ M3 := [max{θe,1 , θd,1 −
δt/2}, θd,2 − δt/2). However, if M3 is empty, then the action
pair {θ̂1 = θ0 , θ̂2 = θ0 }, where θ0 := θd,2 − δt/2, leads to
an equilibrium. On the contrary, if θd,2 − δt/2 < θe,1 ≤
θd,1 , the action pairs1 {θ̂1 = θ + ∆, θ̂2 = θ} lead to an
equilibrium if there exists θ ∈ Θ such that θ ∈ M4 :=
[max{θd,2 − δt/2, θe,2 }, θe,1 ). However, if M4 is empty, then
the action pair {θ̂1 = θ0 , θ̂2 = θ0 }, where θ0 := θe,1 , leads
to an equilibrium.
Proof. The proof is provided in Appendix D.

Lemma 5. Let θe,1 ≤ θd,1 < θe,2 ≤ θd,2 ≤ θd,1 + δt,
then there exist multiple equilibria such that the equilibrium
achieving action pairs are given by {θ̂1 = θ, θ̂2 = θ + ∆}
provided that there exists θ ∈ Θ such that
h



θ ∈ max θd,2 −δt, θd,1 −δt/2, θe,1 , min θd,2 −δt/2, θd,1 .
(2)
1 Here,

agent-2 passes through the intersection first at the equilibria.

Sub5

Projection

Agent‐1
passes first

Actions of agent‐1, passing
first at equilibria

Set of Allocations at Equilibria
Allocations at Socially
Optimal Equilibrium

Fig. 5. Equilibria in the cases that θe,1 ≤ θd,1 < θe,2 ≤ θd,2 ≤ θd,1 +δt.

Tree





Optimal when
no conflict

Agent‐2
passes first

Lemma 1





Lemma 5





Fig. 7. Possible allocated times (shaded area) due to the safety constraints
for the case represented at the top of the figure. Here, θd,1 < θd,2 such
that (θd,2 − θd,1 )/2 ∈ Θ, therefore t∗1 = θd,1 − (δt − (θd,2 − θd,1 ))/2,
t∗2 = θd,2 + (δt − (θd,2 − θd,1 ))/2, and agent-1 passes first at equilibria.

Lemma 2


Lemma 3

social choice function:



2
X

Lemma 4

c(|ti − θd,i |).

(3)

i=1

Fig. 6. Binary tree for the conflicting cases addressed in Lemmas 1-5
when θd,1 ≤ θd,2 and θd,2 ≤ θd,1 + δt.

Otherwise, there exists a unique
equilibrium, where {θ̂1 =

θ0 , θ̂2 = θ0 } and θ0 := min θd,2 − δt/2, θd,1 .
Proof. The proof is provided in Appendix E.

Based on Lemmas 1-5, we have the following proposition.
Proposition 1. There exists at least one pure equilibrium
point in the two-agent intersection game.
Proof. As seen in Fig. 6, Lemmas 1-5 cover all the
conflicting cases and at each case, there exists at least one
pure equilibrium. Furthermore, if there are no conflicts, then
truthfulness leads to pure unique equilibrium.

We note that in general there are multiple equilibria. However, in the case of multiple equilibria, certain equilibrium
points are more preferable for certain agents. Additionally,
since there are multiple equilibrium points, taken actions
might not yield an equilibrium. In the following section, we
design a mechanism to mitigate such issues.
IV. STRATEGY-PROOF INTERSECTION
MECHANISM
We seek to design an intersection mechanism between
the agents and the intersection manager, where the strategic
agents report their private information to the mechanism and
the mechanism plays on their behalf, i.e., reports certain
times to the intersection manager based on the agents’
reports. Note that the agents have selfish objectives, which is
to minimize their own payoff functions. However, we seek
to design a mechanism which leads to minimization of the

Note that our social objective (3), as a mechanism designer,
can lead to different allocations from the FCFS protocol.
Particularly, the socially optimal allocated times would be
given by the following minimization problem:
min

t1 ,t2 ∈Θ

2
X

c(|ti − θd,i |) subject to

|t1 − t2 | ≥ δt. (4)

i=1

If there is no conflict of interest, i.e., |θd,1 − θd,2 | > δt,
then the allocated times by the manager according to FCFS
protocol also lead to the socially optimal ones. However, if
there is a conflict of interest, since c(·) is strictly increasing
and strictly convex function, the socially optimal allocated
times t∗1 , t∗2 are such that the deviations of the allocated times
from the corresponding desired times are the same for each
agent. In particular, we have2 i) if θd,1 = θd,2 , t∗1 = b(θd,1 −
δt/2) + (1 − b)(θd,1 + δt/2 + ∆), t∗2 = (1 − b)(θd,1 − δt/2) +
b(θd,1 + δt/2 + ∆)), where b ∼ Ber(1/2); ii) if θd,i < θd,j
and (θd,j − θd,i )/2 ∈ Θ, t∗i = θd,i − (δt − (θd,j − θd,i ))/2,
t∗j = θd,j + (δt − (θd,j − θd,i ))/2 + ∆, where i 6= j; iii) if
θd,i < θd,j and (θd,j − θd,i )/2 ∈
/ Θ, t∗i = θd,i − (δt − (θd,j −
0
0
∗
θd,i ) + b ∆ − (1 − b )∆)/2, tj = θd,j + (δt − (θd,j − θd,i ) +
b0 ∆ − (1 − b0 )∆)/2 + ∆, where b0 ∼ Ber(1/2).
Remark 1. We emphasize that the socially optimal time
allocations t∗1 , t∗2 do not depend on the payoff functions
directly due to the assumption that agents are identical and
c(·) is a strictly increasing and strictly convex function.
Therefore, as a mechanism designer, we do not need to know
the exact payoff functions except the assumption about their
structure.
2 Note

that we have assumed δt/2 ∈ Θ.

Projection2

Actions of agent‐2, passing
first at equilibria

Agent‐1
passes first

case when θd,1 = θd,2 and θe,1 = θe,2 , then this is also the
socially optimal equilibrium point. Otherwise, the socially
optimal equilibrium leads to the allocations (to1 , to2 ), which
are given by
min
(t1 ,t2 )∈Tγ

Set of Allocations
at Equilibria
Allocations at
Socially Optimal
Equilibrium

Agent‐2
passes first

Fig. 8. Possible allocated times for the case represented at the top of the
figure. Here, θd,1 < θd,2 such that (θd,2 − θd,1 )/2 ∈ Θ, yet agent-2
passes first at equilibria.

Furthermore, in the cases of conflicting interests, the
socially optimal allocated times cannot be achieved if both
agents reveal their desired passing times truthfully since the
manager cannot allocate a time before the reported times.
If the agents behave strategically and not necessarily reveal
the information truthfully, the socially optimal allocation
may also not be achievable at any of the equilibria due to
the earliest passing times of the agents. As an example, in
Figs. 7 and 8, we demonstrate all the possible pair of time
allocations, i.e., a point in the shaded areas of the graphs,
for the cases on the top of each figure. Then, the socially
optimal allocation is at t∗1 = θd,1 − (δt − (θd,2 − θd,1 ))/2 and
t∗2 = t∗1 + δt + ∆ while the action pair {θ̂1 = θ, θ̂2 = θ + ∆},
where θ ∈ Θ ∩ [θe,1 , θd,2 − δt/2) leads to an equilibrium in
Fig. 7 and the action pair {θ̂1 = θ0 + ∆, θ̂2 = θ0 }, where
θ0 ∈ Θ ∩ [θd,2 − δt/2, θe,1 ) leads to an equilibrium in Fig. 8.
Therefore the corresponding time allocations at equilibria are
given by t1 = θ and t2 = θ + δt + ∆ in Fig. 7 and given by
t1 = θ0 + δt + ∆ and t2 = θ0 in Fig. 8. However, for the case
in Fig. 7, there does not exist a θ ∈ Θ∩[θe,1 , θd,2 −δt/2) such
that t∗1 = θ and t∗2 = θ + δt + ∆. Additionally, for the case in
Fig. 8, there does not exist a θ0 ∈ Θ ∩ [θd,2 − δt/2, θe,1 ) such
that t∗1 = θ0 + δt + ∆ and t∗2 = θ0 . Existence of such θ, θ0
would imply that the socially optimal allocation is in the set
of allocations at equilibria. Therefore the socially optimal
time allocation may not lead to an equilibrium. However, in
such a case, since the set of equilibrium points is finite, there
exists at least one equilibrium that is socially more preferable
than, or equally preferable with, the other equilibrium points.
We call such an equilibrium “socially optimal equilibrium”
and denote the corresponding time allocations by (to1 , to2 )
(e.g., see Figs. 7 and 8).
Let γ := {θd,1 , θe,1 , θd,2 , θe,2 }, and given γ, let Mγ ⊂
Θ × Θ denote the set of all the corresponding equilibrium
points and Tγ ⊂ Θ × Θ be the corresponding set of allocated
passing times. If there is a unique pure equilibrium, e.g., the

2
X

c(|ti − θd,i |).

(5)

i=1

The following theorem characterizes these allocations.
Theorem 1. Suppose that there are multiple pure equilibria, and yet the socially optimal allocations cannot be
achieved at any of these equilibria. If θd,1 = θd,2 , let
i = arg mink=1,2 θe,k and j = arg maxk=1,2 θe,k ; otherwise
let i = arg mink=1,2 θd,k and j = arg maxk=1,2 θd,k . Then,
the allocations in the socially optimal equilibrium are given
by

(θe,j , θe,j + δt + ∆) θd,i = θd,j ,



θe,j < θe,i ≤ θd,i < θd,j
(to1 , to2 ) =
(θ̄ + δt + ∆, θ̄)
and θd,j − δt/2 < θe,i



(θe,i , θe,i + δt + ∆) otherwise.
(6)
where θ̄ := max{θd,j − δt/2, θe,j }.
Proof. The proof is provided in Appendix F.

We reemphasize that also the time allocations in the
socially optimal equilibrium, to1 , to2 , do not depend on the
payoff function directly. The following corollary provides
the socially optimal equilibrium points (θ̂1o , θ̂2o ) such that
(to1 , to2 ) = FCFS(θ̂1o , θ̂2o ).
Corollary 1. If θd,1 = θd,2 , let i = arg mink=1,2 θe,k and
j = arg maxk=1,2 θe,k ; otherwise let i = arg mink=1,2 θd,k
and j = arg maxk=1,2 θd,k . Let θ∗ ∈ R be defined by
θ∗ := θd,i − (δt − (θd,j − θd,i ))/2. Then, the socially optimal
equilibrium is given in Table I.
Proof. These results follow from Theorem 1 and Lemmas
1-5. We select the equilibrium point within Tγ such that
the corresponding time allocation is closest to the socially
optimal allocation.

Next, the following corollary provides a truthful mechanism for intersection control in strategic environments.
Corollary 2. Consider an intersection mechanism, which
asks the agents to report both their earliest possible and
desired passing times, θ̂e,i , θ̂d,i , for i = 1, 2; and plays for
them the corresponding socially optimal equilibrium actions,
i.e., reports passing times to the intersection manager: θ̂1o , θ̂2o ,
which are formulated in Corollary 1. Then, this intersection
mechanism is a strategy-proof mechanism, i.e., it incentivizes
the selfish agents to reveal their private information truthfully.
Proof. This follows from the revelation principle [7],
which implies that the socially optimal equilibrium can be
implemented by an incentive-compatible-direct-mechanism,
in which both agents reveal their private information truthfully. The intersection mechanism already plays the best
actions strategically for both agents, which lead to the
corresponding socially optimal equilibrium; therefore the
agents do not have any incentive to misreport their private

TABLE I
T HE CASES IN C OROLLARY 1, WHERE b ∼ Ber(1/2).
Assignment of (θ̂io , θ̂jo )

Case

Condition

No Conflict
Lemma 1

θd,i + δt < θd,j
θd := θd,i = θd,j
if
max{θe,i , θd − δt/2} = max{θe,j , θd − δt/2}
else if
θ∗ ∈ Θ
else if
θe,j ≤ θ∗ − ∆/2
else
θe,i , θe,j ≤ θd,i < θd,j ≤ θd,i + δt and θd,j − δt ≤ θd,i < θd,j − δt/2
if3
max{θd,j − δt, θe,i } = θd,i
else if
θ∗ ∈ Θ
else if
θ∗ + ∆/2 ≤ θe,i
else
θe,i ≤ θe,j ≤ θd,i < θd,j ≤ θd,i + δt and θd,j − δt/2 ≤ θd,i
if
max{θe,i , θd,i − δt/2} = max{θd,j − δt/2, θe,j }
else if
θ∗ ∈ Θ
else if
θ∗ + ∆/2 ≤ θe,i
else
θe,j < θe,i ≤ θd,i < θd,j and θe,i ≤ θd,j − δt/2 ≤ θd,i
if
max{θe,i , θd,i − δt/2} = θd,j − δt/2
else if
θ∗ ∈ Θ
else if
θ∗ + ∆/2 ≤ θe,i
else
θe,j < θe,i ≤ θd,i < θd,j and θd,j − δt/2 < θe,i ≤ θd,i
if
max{θe,j , θd,j − δt/2} = θe,i
else
θe,i ≤ θd,i < θe,j ≤ θd,j ≤ θd,i + δt
if
max{θd,j − δt, θd,i − δt/2, θe,i } = min{θd,j − δt/2, θd,i }
else if
θ∗ ∈ Θ
else if
θ∗ + ∆/2 ≤ θe,i
else

Lemma 2

Lemma 3

Former Case
in Lemma 4

Latter Case
in Lemma 4
Lemma 5

information with the aim of reducing their own payoff
function further.

V. CONCLUSION
In this paper, we have studied the truthfulness of intersection control, when the intersection manager evaluates the
requests of more than one agent, specifically two agents,
in a non-cooperative environment. We analyze equilibria for
the agents’ actions such that at an equilibrium, given that the
other agent has taken that action against his/her action, he/she
has no incentive to change his/her action unilaterally. We
have formulated all equilibria for all possible scenarios. We
have shown that there always exists a pure equilibrium and
there even exist multiple pure equilibria in general. We have
then characterized the socially preferable equilibrium within
all the equilibria with respect to a certain social objective.
Finally, we have designed a strategy-proof mechanism, where
the agents cannot exploit the intersection control to get
benefit in terms of their selfish objectives. We point out
that the intelligent intersection control process in a noncooperative environment even with two agents requires a
3 Note that this is one of the essentially unique equilibria, which lead to
the same time allocations. Furthermore, truthfulness of both agents leads to
the socially optimal equilibrium.

(θd,i , θd,j )
(θ, θ), where θ = max{θe,j , θd − δt/2}
(min{θ∗ , θe,j }, θ̂io + ∆)
(θe,j , θ̂io + ∆)
(b(θ∗ − ∆/2) + (1 − b)(θ∗ + ∆/2), θ̂io + ∆)
(θd,i , θd,j )
(max{θ∗ , θe,i }, θ̂io + ∆)
(θe,i , θ̂io + ∆)
(b(θ∗ − ∆/2) + (1 − b)(θ∗ + ∆/2), θ̂io + ∆)
(θ, θ), where θ = max{θd,j − δt/2, θe,j }
(max{θ∗ , θe,i }, θ̂io + ∆)
(θe,i , θ̂io + ∆)
(b(θ∗ − ∆/2) + (1 − b)(θ∗ + ∆/2), θ̂io + ∆)
(θ, θ), where θ = θd,j − δt/2
(max{θ∗ , θe,i }, θ̂io + ∆)
(θe,i , θ̂io + ∆})
(b(θ∗ − ∆/2) + (1 − b)(θ∗ + ∆/2), θ̂io + ∆)
(θe,i , θe,i )
(θ̂jo + ∆, min{θd,j − δt/2, θe,j })
(θ, θ), where θ = min{θd,j − δt/2, θd,i }
(max{θ∗ , θe,i }, θ̂io + ∆)
(θe,i , θ̂io + ∆)
(b(θ∗ − ∆/2) + (1 − b)(θ∗ + ∆/2), θ̂io + ∆)

careful consideration of all the possible cases with respect
to earliest and desired passing times of the agents, and the
time that the agents need to pass through the intersection.
By formulating the strategy-proof mechanism, this paper has
also provided a straight-forward, yet non-trivial, guideline to
extend to scenarios where there are more than two agents.
R EFERENCES
[1] K. Dresner and P. Stone, “A multiagent approach to autonomous
intersection management,” Journal of Artificial Intelligence Research,
vol. 31, pp. 591–656, 2008.
[2] M. Vasirani and S. Ossowski, “A market-inspired approach for intersection management in urban road traffic networks,” Journal of Artificial
Intelligence Research, vol. 43, pp. 621–659, 2012.
[3] M. Elhenawy, A. A. Elbery, A. A. Hassan, and H. A. Rakha, “An
intersection game-theory-based traffic control algorithm in a connected
vehicle environment,” in IEEE International Conference on Intelligent
Transportation Systems (ITSC), Sept. 2015, pp. 343–347.
[4] Z. Han, D. Niyato, W. Saad, and T. Başar, Game Theory in Wireless and
Communication Networks: Theory, Models, and Applications. Cambridge, UK: Cambridge University Press, 2012.
[5] T. Başar and G. J. Olsder, Dynamic Noncooperative Game Theory.
Philadelphia: SIAM Series in Classics in Applied Mathematics, 1999.
[6] M. O. Sayin, C.-W. Lin, S. Shiraishi, and T. Başar, “Informationdriven intersection management: Truthfulness via payments,” Submitted
to IEEE Transactions on Intelligent Transportation Systems, 2017.
[7] V. V. Vazirani, N. Nisan, T. Roughgarden, and E. Tardos, Algorithmic
Game Theory. Cambridge, UK: Cambridge University Press, 2007.

A PPENDIX I
A. Proof of Lemma 1
Given that θd,1 = θd,2 =: θd and θe,1 ≤ θe,2 , we have the
following cases, which are partially demonstrated in Fig. 1: i)
If both θe,1 and θe,2 are less than or equal to θd −δt/2, there
exists a unique pure equilibrium, where both agents report
θ̂1 = θ̂2 = θd − δt/2, and the intersection is allocated to
one of the agents at θd − δt/2 with equal probability and the
other agent is allowed to pass through the intersection when
θd + δt/2 + ∆. The action pair {θ̂1 = θd − δt/2, θ̂2 = θd −
δt/2} leads to an equilibrium since if agent-1 reports θ̂1 =
θd − δt/2, then the best response of agent-2 is to report θ̂2 =
θd − δt/2, and given agent-2 has reported θ̂2 , agent-1 has no
incentive to change his/her action. Furthermore, this is the
only pure equilibrium. ii) If θe,2 > θd −δt/2 and θe,1 ≤ θd −
δt/2, then there exist multiple pure equilibria. In particular,
if agent-2 reports θ̂2 = θ + ∆, where θ ∈ Θ such that θ ∈
[θd −δt/2, θe,2 ), then the best response of agent-1 is to report
θ̂1 = θ and given that agent-1 has reported that, agent-2 has
no incentive to change his/her action since agent-2 cannot
pass through the intersection before θe,2 . Note that the set
[θd − δt/2, θe,2 ) is not empty since θe,2 > θd − δt/2. iii)
Finally, if θe,2 ≥ θe,1 > θd − δt/2, then there exist multiple
pure equilibria. Correspondingly, the equilibrium achieving
action pairs are given by {θ̂1 = θ, θ̂2 = θ + ∆}, where
θ ∈ Θ such that θ ∈ [θe,1 , θe,2 ). If there is no such θ, i.e.,
θe := θe,1 = θe,2 , then we have a unique pure equilibrium,
where both agents report θ̂1 = θ̂2 = θe .
B. Proof of Lemma 2
Given that θe,1 , θe,2 ≤ θd,1 < θd,2 ≤ θd,1 + δt and
θd,2 − δt ≤ θd,1 < θd,2 − δt/2, we have the following cases,
which are partially demonstrated in Fig. 2: i) If both θe,1 and
θe,2 are less than or equal to θd,2 − δt, there exist multiple
equilibria, where the equilibrium achieving action pairs are
given by {θ̂1 = θ, θ̂2 = θ + ∆}, where θ ∈ Θ such that
θ ∈ [θd,2 − δt, θd,1 ). Additionally, the action pair {θ̂1 =
θd,1 , θ̂2 }, where θ̂2 ∈ Θ such that θ̂2 ∈ (θd,1 , θd,1 + δt + ∆],
also leads to an equilibrium. Note that if agent-2 reports
a time earlier than θd,2 − δt, e.g., θ0 < θd,2 − δt, the best
response of agent-1 is to report a far earlier time, e.g., θ0 −∆.
However, given that agent-1 has reported θ0 −∆, now, agent2 has an incentive to change his/her action since by reporting
θd,2 , agent-2 can pass through the intersection exactly at
his/her desired passing time, which is the least possible
payoff he/she can get. Therefore, such action pairs do not
lead to an equilibrium. ii) If θd,2 − δt ≤ θe,1 ≤ θe,2 ≤ θd,1 ,
then there exist multiple equilibria, where the equilibrium
achieving action pairs are given by {θ̂1 = θ, θ̂2 = θ + ∆},
where θ ∈ Θ such that θ ∈ [θe,1 , θd,1 ). Correspondingly,
the action pair {θ̂1 = θd,1 , θ̂2 }, where θ̂2 ∈ Θ such that
θ̂2 ∈ (θd,1 , θd,1 + δt + ∆], also leads to an equilibrium.
C. Proof of Lemma 3
Given that θe,1 ≤ θe,2 ≤ θd,1 < θd,2 ≤ θd,1 + δt and
θd,1 ≥ θd,2 − δt/2, we have the following cases, which are

partially demonstrated in Fig. 3: i) If θe,1 ≤ θd,1 − δt/2
and θe,2 ≤ θd,2 − δt/2, then there exist multiple pure
equilibria, where the equilibrium achieving action pairs are
given by {θ̂1 = θ, θ̂2 = θ + ∆}, where θ ∈ Θ such
that θ ∈ [θd,1 − δt/2, θd,2 − δt/2). Note that the set
[θd,1 − δt/2, θd,2 − δt/2) is not empty since θd,1 > θd,2 .
ii) If θd,1 − δt/2 ≤ θe,1 ≤ θe,2 ≤ θd,2 − δt/2, we have
two cases. If θe,1 < θd,2 − δt/2, there exist multiple pure
equilibria, where the equilibrium achieving action pairs are
given by {θ̂1 = θ, θ̂2 = θ + ∆}, where θ ∈ Θ such that
θ ∈ [θe,1 , θd,2 − δt/2). Or if θe,1 = θd,2 − δt/2, there exists
a unique pure equilibrium, where {θ̂1 = θe,1 , θ̂2 = θe,1 }. iii)
If θd,1 −δt/2 ≤ θe,1 ≤ θd,2 −δt/2 < θe,2 , there exist multiple
pure equilibria, where the equilibrium achieving action pairs
are given by {θ̂1 = θ, θ̂2 = θ + ∆}, where θ ∈ Θ such that
θ ∈ [θe,1 , θe,2 ). Note that the set [θe,1 , θe,2 ) is not empty
since θe,2 > θe,1 . iv) Finally, if θd,2 − δt/2 < θe,1 ≤ θe,2 ,
we have two cases. If θe,1 < θe,2 , there exist multiple pure
equilibria, where the equilibrium achieving action pairs are
given by {θ̂1 = θ, θ̂2 = θ + ∆}, where θ ∈ Θ such that
θ ∈ [θe,1 , θe,2 ). Or if θe,1 = θe,2 , there exists a unique pure
equilibrium, where {θ̂1 = θe,1 , θ̂2 = θe,1 }.
D. Proof of Lemma 4
Given that θe,2 < θe,1 ≤ θd,1 < θd,2 ≤ θd,1 + δt
and θd,1 ≥ θd,2 − δt/2, we have interesting equilibrium
scenarios, which are partially demonstrated in Fig. 4, e.g.,
at equilibrium, agent-2 might be allowed to pass first even
though his/her desired passing time is later: i) If θe,1 ≤
θd,1 − δt/2, then there exist multiple pure equilibria, where
the equilibrium achieving action pairs are given by {θ̂1 =
θ, θ̂2 = θ+∆}, where θ ∈ Θ such that θ ∈ [θd,1 −δt/2, θd,2 −
δt/2). Note that the set [θd,1 −δt/2, θd,2 −δt/2) is not empty
since θd,1 > θd,2 . ii) If θd,1 − δt/2 < θe,1 ≤ θd,2 − δt/2, we
have two cases. If θe,1 < θd,2 − δt/2, there exist multiple
equilibria such that the equilibrium achieving action pairs
are given by {θ̂1 = θ, θ̂2 = θ + ∆}, where θ ∈ Θ such that
θ ∈ [θe,1 , θd,2 −δt/2). Or if θe,1 = θd,2 −δt/2, there exists a
unique pure equilibrium, where {θ̂1 = θe,1 , θ̂2 = θe,1 }. iii)
Interestingly, if θe,2 ≤ θd,2 − δt/2 < θe,1 ≤ θd,1 , we have
two cases. If θd,2 − δt/2 < θe,1 , multiple equilibria such that
the equilibrium achieving action pairs are given by {θ̂1 =
θ+∆, θ̂2 = θ}, where θ ∈ Θ such that θ ∈ [θd,2 −δt/2, θe,1 ).
And at these equilibrium points, agent-2 passes through the
intersection first. Or if θd,2 − δt/2 = θe,1 , there exists a
unique pure equilibrium, where {θ̂1 = θe,1 , θ̂2 = θe,1 }. iv)
Furthermore, if θd,2 − δt/2 < θe,2 < θe,1 ≤ θd,1 , then there
exist multiple equilibria such that the equilibrium achieving
action pairs are given by {θ̂1 = θ +∆, θ̂2 = θ}, where θ ∈ Θ
such that θ ∈ [θe,2 , θe,1 ). And again at these equilibrium
points, agent-2 passes through the intersection first.
E. Proof of Lemma 5
Finally, we consider the cases that θe,1 ≤ θd,1 < θe,2 ≤
θd,2 ≤ θd,1 + δt, which are partially represented in Fig. 5. i)
If θe,1 ≤ θd,2 − δt ≤ θd,1 ≤ θd,2 − δt/2, then we have two
cases. If θd,2 − δt/2 < θd,1 , there exist multiple equilibria

Projection3

previous case. Then, the optimization problem (5) can be
written as
min

∗
||:(t∗
2 +,t1 +)∈Tγ

c(|t∗2 +  − θd,1 |) + c(|t∗1 +  − θd,2 |). (9)

Since at equilibria, agent-2 would not pass through the
intersection after θd,2 or before θd,2 − δt/2 while he/she is
passing first, (9) can also be written as
Fig. 9. The distance between the allocations in socially optimal equilibrium
and the socially optimal allocations in distinct equilibrium scenarios, where
both agents can pass through the intersection first (on the left figure, agent1 passes first while on the right figure agent-2 passes first) in spite of
θd,1 < θd,2 .

such that the equilibrium achieving action pairs are given
by {θ̂1 = θ, θ̂2 = θ + ∆}, where θ ∈ Θ such that θ ∈
[θd,2 − δt/2, θd,1 ). Or if θd,2 − δt/2 = θd,1 , there exists a
unique pure equilibrium, where {θ̂1 = θd,1 , θ̂2 = θd,1 }. ii)
If θd,2 − δt < θe,1 ≤ θd,1 ≤ θd,2 − δt/2, then we have two
cases. If θe,1 < θd,1 , there exist multiple equilibria such that
the equilibrium achieving action pairs are given by {θ̂1 =
θ, θ̂2 = θ + ∆}, where θ ∈ Θ such that θ ∈ [θe,1 , θd,1 ). Or
if θd,2 − δt/2 = θd,1 , there exists a unique pure equilibrium,
where {θ̂1 = θd,1 , θ̂2 = θd,1 }. iii) If θd,2 − δt/2 < θd,1 ,
then there exist multiple equilibria such that the equilibrium
achieving action pairs are given by {θ̂1 = θ, θ̂2 = θ + ∆},
where θ ∈ Θ such that θ ∈ [θd,1 − δt/2, θd,2 − δt/2). Note
also that the set [θd,1 − δt/2, θd,2 − δt/2) is not empty since
θd,1 > θd,2 .
F. Proof of Theorem 1
We seek to solve (5) in order to formulate the allocations
at the socially optimal equilibrium. To this end, we provide
the illustrations in Fig. 9. first, consider the illustration on
the left of Fig. 9. Here, all the allocation pairs in Tγ can be
written as (t∗1 + , t∗2 + ) for certain  ∈ R. Note that  < 0
would imply Tγ stands on the left of (t∗1 , t∗2 ), i.e., such cases
are also considered. Then, the optimization problem (5) can
be written as
min

∗
∈R:(t∗
1 +,t2 +)∈Tγ

c(|t∗1 +  − θd,1 |) + c(|t∗2 +  − θd,2 |). (7)

Since at equilibria, agent-1 would not pass through the
intersection after θd,1 or before θd,1 − δt/2 while he/she is
passing first, (7) can also be written as
min

∗
||:(t∗
1 +,t2 +)∈Tγ

c(σ1 − ) + c(σ1 + ),

(8)

where σ1 := θd,1 − t∗1 = t∗2 − θd,2 > 0. This would imply
that the minimizer ∗ = min{ ∈ R : (t∗1 + , t∗2 + ) ∈ Tγ }
since c(·) is a strictly increasing strictly convex function over
[0, ∞). In particular, in these scenarios, the pair of allocations
(to1 , to2 ) in socially optimal equilibrium is a point in Tγ , which
is closest to the socially optimal allocation (t∗1 , t∗2 ).
Next, consider the illustration on the right of Fig. 9. Here,
all the allocation pairs in Tγ can be written as (t∗2 + , t∗1 + )
for certain  ∈ R. We emphasize the difference from the

min

∗
∈R:(t∗
2 +,t1 +)∈Tγ

c(σ2 + ) + c(σ2 − ),

(10)

where σ2 := θd,2 − t∗1 = t∗2 − θd,1 > 0. Correspondingly,
this would imply that the minimizer ∗ = min{ ∈ R :
(t∗2 + , t∗1 + ) ∈ Tγ } since c(·) is a strictly increasing
strictly convex function over [0, ∞). Note that the pair of
allocations (to1 , to2 ) in socially optimal equilibrium is also a
point in Tγ , which is closest to the socially optimal allocation
(t∗1 , t∗2 ) in addition to (t∗2 , t∗1 ). This also implies that the
pair of allocations (to1 , to2 ) in socially optimal equilibrium
when θd,1 = θd,2 is also a point in Tγ , which is closest
to the socially optimal allocation (t∗1 , t∗2 ). Hence, under the
conditions in Theorem 1, we can conclude that the pair of
allocations (to1 , to2 ) in socially optimal equilibrium is a point
in Tγ , which is “closest” to the socially optimal allocation
(t∗1 , t∗2 ). Based on this conclusion and Lemmas 1-5, the
allocations that are in socially optimal equilibrium are given
by (6).

