Solving a Simultaneous Behavioral Decision Problem
During Interactions Using Quantum Optimization
J. Urataa,∗a Department of Civil Engineering, University of Tokyo, Japanurata@bin.t.u-tokyo.ac.jp∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium onTransportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

January 15, 2022
Keywords: social interaction, quantum computing, behavior simulation

1PROBLEM STATEMENT

For smooth control of an autonomous vehicle, it is necessary to select acceleration/deceleration/lanes
while considering the interactions with other vehicles. In particular, during merging at a ramp,
vehicles that affect an agent are also affected by other vehicles. The propagation of these vehiclevehicle interactions is illustrated in Figure 1. However, simulating the simultaneous selections
made by vehicles during interactions is challenging.
Interaction

Figure 1 – Example: Interaction between vehicles
To solve the problem of simultaneous selection, we must determine the most likely probabilities of all interacting agents from all possible combinations of their choices:â = arg max P (z),∀z(1)where â, z represent the combination of behavioral choices for all the agents, and P is thesimultaneous probability of the behavioral combination. The number of possible combinations amagent
is the exponent of the number of alternatives to the number of agents: Nalternative. Hence, theoptimization problem is NP-hard.
In this study, we solve this problem using quantum computing. For this, we formulate thesimultaneous probability during interactions in such a manner that a quantum optimization technique can be applied. The optimization approach, which can help solve this problem quickly,
enables us to obtain the most likely behavior choice for all the agents. A recently developed quantum computation approach was based on the Ising model. This approach can be reformulated
as a quadratic unconstrained binary optimization (QUBO) with the least possible constraints.
TRISTAN XI Symposium

Original abstract submittal

A. Coauthor, B. Coauthor, C. Coauthor and D. Coauthor

2Our formulations, based on a traditional social interaction model (Brock & Durlauf (2001)), canbe transformed to a QUBO, and consequently, we propose a method to simulate simultaneousselections when the agents interact with each other.
Some existing activity simulators, for example, CEMDAP (Bhat et al. (2013)), evaluate
interactions amongst a family or a small group. To the best of our knowledge, a longer chainof interactions has not been evaluated in previous studies. These chains of interactions can beobserved in the vehicle movement on a ramp, two-dimensional choice of pedestrians in public
spaces, and participation decisions during car-sharing, among others. The proposed method
makes it possible to compute many similar phenomena involving social interactions.

2FORMULATION

Brock & Durlauf (2001) proposed a local interaction model, wherein social utility S is given byS(ai , a) = −E 
XJij (ai − aj )2 (2)j∈ciwhere a is a behavioral choice, ci represents agents interacting with the decision-maker i, andJij is the weight of the interaction between agents i and j. When the social utility S is added
to the observed utility u of the logit model, the probability of the choice is expressed as
Pi (ai ) =exp (u(ai ) + S(ai , a))exp (u(ai ) + S(ai , a)) + exp (u(a0i ) + S(a0i , a))(3)where a0i 6= ai . In this study, we defined our problem as a binary choice problem. Equivalently,
the numerator of Eq. (3) can be changed tou(ai ) Jij−(ai − aj )2
exp|c||c|
iij∈c


Y



(4)

i

When a potential function Wij (ai , aj ) is defined as!

u(ai ) − Jij (ai − aj )2
Wij (ai , aj ) = exp|ci |u(aj ) − Jji (ai − aj )2× exp|cj |!

,(5)

the simultaneous probability P (a) isQP (a) =YPi (ai ) = Pij∈B Wij (ai , aj )∀a∀iQij∈B Wij (ai , aj ),(6)

where B is a set of interactions among agents, and the denominator represents a normalizing
constant. The maximization of P (a) can be transformed to a QUBO formulation, as follows:
max P (a) ⇒ maxaaY

Wij (ai , aj )ij∈B!

⇒ maxaXij∈Blog (Wij (ai , aj )) = maxaX
ij∈Bu(ai ) − Jij (ai − aj )2 u(aj ) − Jji (ai − aj )2+(7)
.
|ci |
|cj |

On representing the observed utility u asu(ai ) = ai ui1 + (1 − ai )ui0 = a2i ui1 + (1 − a2i )ui0 = (ui1 − ui0 )a2i + ui0 ,TRISTAN XI Symposium(8)

Original abstract submittal

A. Coauthor, B. Coauthor, C. Coauthor and D. Coauthor

3

where u(ai = 0) = ui0 and u(ai = 1) = ui1 , Eq. (7) becomes!

max P (a) ⇒ maxaaXij∈BJjiui − Jij−a2i +|ci ||cj |2Jij2Jji+|ci ||cj |!

!

ai aj +!

uj − JjiJij−a2j ,|cj ||ci |(9)where ui = ui1 − ui0 . Eq. (9) is in the form of a QUBO, and this enables us to obtain a solution
for the optimal choice combination â using a heuristic quantum annealing algorithm.
In general, by formulating it as a QUBO, any problem can be solved using quantum computation. However, quantum annealing is a natural computing mechanism that calculates theoptimal solution using the unrestrained quantum behavior . Therefore, to efficiently solve theseproblems, it is desirable to include as few constraints as possible. The problem addressed in thisstudy is a problem with no constraints; hence, it is a more suitable model to be solved using
quantum computation.

3NUMERICAL EXAMPLE

The numerical example presented herein verifies that our formulation for the behavioral decision
problem during interactions can be solved using quantum optimization. The interaction network
is considered as a clique network where the utility ui and weight Jij are randomly chosen in
the intervals [-1, 1] and [0, 1], respectively. Considering a binary behavioral choice, simulations
were conducted for different numbers of agents (5, 10, 20, 40, and 100). We used D-wave
Leap, a real-time Quantum Application Environment, to solve the numerical examples. The
quantum processing unit (QPU) used was an Advantage system 1.1 with 5436 working qubits.
We also used the Python packages “dwave.system” and “dimod.” For the simulations with 5, 10,and 20 agents, we verified that the optimal combinations obtained via quantum annealing areconsistent with the exact solutions obtained by the enumeration of all possible combinations.
This verifies the applicability of quantum optimization for the solution of this type of problem.
Cases involving more than 20 agents cannot be solved by the enumeration method. Table 1 shows
the computation time with respect to the number of agents. Despite the power-law scaling in thenumber of possible combinations (2magent ), owing to the use of quantum annealing, the differencein computation time is small, even when the number of agents increases. The number of samples
in Table 1 refers to the number of trials required to solve the problem. The quantum annealing
results are dependent on the initial setting, and hence, several trials are performed before theselection of the optimal one. Table 2 indicates that the computation time depends on the numberof samples. Figure 2 depicts the distribution of the objective function (energy) and illustrates
that the optimal result can be obtained even if the number of trials is small.
Table 1 – QPU computation time based on number of agents# of agents
51020
40100

TRISTAN XI Symposium

time (ms)
8.41
8.55
9.45
12.85
14.25

# of samples100100100100100

Original abstract submittal

A. Coauthor, B. Coauthor, C. Coauthor and D. Coauthor

4Table 2 – QPU computation time based on number of samples
time (ms)
5.07
12.85
25.43
51.24

# of samples
50
100
200
4001.0# of agents
40
40
40
40

0.6
0.4
0.0

0.2

Sample−ratio

0.8

50
100
200
400

−1.0−0.8

−0.6

−0.4

−0.20.0

EnergyFigure 2 – Energy distribution with respect to number of samples

4CONCLUSION

This paper proposed a method to determine the optimal selection of multi-agent behavior during social interactions by using quantum computation. The combination of actions with themaximum likelihood in a stochastic action selection problem is dependent on the probability
maximization of the simultaneous probability, because of an interaction chain. However, thisproblem is NP-hard to compute. This study transformed the simultaneous selection probability
during interactions to a QUBO that can be solved using quantum computation. This makes
it possible to calculate the combination of behaviors that maximize the simultaneous selectionprobability. Our numerical calculations demonstrate that an exact solution can be obtained using quantum annealing. In addition, even in a situation where the number of agents is as large
as 100 (the number of solution candidates is 2100 ), it is possible to calculate the results quickly( 15 ms) using the D-wave leap machine.

References
Bhat, Chandra R, Goulias, Konstadinos G, Pendyala, Ram M, Paleti, Rajesh, Sidharthan, Raghuprasad,Schmitt, Laura, & Hu, Hsi-Hwa. 2013. A household-level activity pattern generation model with anapplication for Southern California. Transportation, 40(5), 1063–1086.
Brock, William A., & Durlauf, Steven N. 2001. Chapter 54 - Interactions-Based Models. Handbook ofEconometrics, vol. 5. Elsevier.

TRISTAN XI Symposium

Original abstract submittal