T h e 2 1 st S u m m e r C o u r s e“ Behavior Modeling in Transportation Networks”
Lecture Series 1 (16:00-16:30 Sep. 23, 2022)

Recursive structure of decision making
in networks: Modeling and estimation

Yuki Oyama
Shibaura Institute of Technology
Activity Landscape Design Lab.
oyama@shibaura-it.ac.jp

Sequential choice problemEx.) A trip is completed by using a sequence of multiple modes:→→→

Travel behavior decisions often involve sequential choices• Mode choice (Walk – Train 1 – Train 2 - Bike)•Activity pattern (Home – Work – Other – Other - Home)••

Spatial movement (Place 1 – Place 3 – Place 4 – Place 9)
Timing decision (Stay – Stay – Stay – Action)

Challenges:
1. Hard/impossible to enumerate available sequences (Computation)
2. Travelers may not perceive all elements in a sequence at once(Decision-making structure)2Sequential path choice in a state network
Define choice elements as states and their network

s3
s1
s0

s6
ds4
s2

Absorbingstates7s5• A sequential choice is described as a path in the network• An elemental choice corresponds to a substructure of network whosechoice set is tractable (easy to count)• E.g., the choice set available to S2 is {S4, S5}
3

Sequential path choice in a state network
Define choice elements as states and their network

s3
s1
s0

s6
ds4
s2

Absorbing
state

s7
s5

Recursive structure of decision-making:• Not direct choice of a sequence, but sequential choices of states•

Elemental choice is the choice of next state given the current state• When choosing a state, travelers consider their possible future choices•

Trade-off between the current stage utility and the future expected utility4Sequential path choice in a state network
Define choice elements as states and their network
Instantaneous utility

Value function of states3s1s0s6ds4s2s7s5

Recursive logit (RL) model (i.e., deterministic MDP with i.i.d. Gumbel utilities)

System of linear equations

Dynamic decision-making description & Efficient computation

5

Recursive model’s feasibility
The value functions are the solution of a fixed point problem:
whereis the Bellman operator

1. Hawkins-Simon / spectral radius condition
is invertible when the maximum absolute of
eigenvalues ofis strictly less than one
2. Utility condition (Mai and Frejinger, 2022)
is a contraction mapping if:
where(The nested RL (NRL) case)where6

Model estimation with recursive structure
Nested Fixed Point (NFXP) algorithm (Rust, 1987)
Outer algorithm
maximizes the likelihood function over the parameter spacee.g.

Inner algorithm
solves the value functions for each parameter valueor(until convergence)

Inner algorithm must be feasible for ALL parameter values
searched during the estimation
7

Why is the issue more critical during estimation?
Feasible region

True parameter
value

Infeasible region

does not have a fixed
point solution
Outeralgorithm

8Estimation problem of recursive models
1.

Even if the true and initial parameter values satisfy thefeasibility condition, parameter values during theestimation process can often violate the condition (andthe estimation fails).

2.

Moreover, unknown true parameter does not necessarily
satisfy the condition.
E.g., if there exist state pairs with positive utilities

Then the following condition clearly does NOT hold:

9What have been done
Ad hoc manipulation of utility function
To somehow satisfy the utility conditions, previous studies•••

Include ONLY negative attributes (e.g., travel time, turn penalties)
Add a fixed large penalty term
Start estimation with a parameter value with large negative magnitude

Two problems:
1.

Limit the practical applicability of RL models (cannot capture positivenetwork attributes)
2. This manipulation does not ensure a solution or stable estimation.

This study proposes the use of

Prism-based approach (Oyama and Hato, 2019)10The idea of prism-based approach
To interpret, the value function can be viewed as:
Expectation of ALL path utilities
connecting state k to destination dPower series as implicit calculation
process of the path utilitiesex.) Unrealistic cycles that explosively gain utilities+++

Prism-based approach efficiently and behaviorally restricts
unrealistic paths that cause the numerical issue11Prism-based path set restriction
State = (Choice-stage, Node/Link)

4 from o
1 to d1.

Define a state-extended network based on choice-stage

2.

Define the choice-stage constraint T, and evaluate state existence
conditions
based on the minimum number of steps from oand to d3.

States connection condition:

4.

The reduced set of states forms into a prism.
12Prism-constrained RL model
Redefine the value function*ex)for each state:• Evaluation function of the prism for each state• In upper stage, higher probability of actions
leading to destination more efficiently

13Prism-constrained RL model
Solve the value function by backward induction→ Efficiently solved and a unique solution is always foundregardless of parameter value and magnitude of utility*As long as T is finite,

is theoretically upper bounded by a real vector because, for finite t,

14

Prism-constrained RL model
Action choice probability

×
outside of prism

within prism

15

Maximum likelihood estimation
Translation of path observations
Original:
Translated:
Stay at destination after the arrival(*Set T so that)

Likelihood function

16

Numerical experiments
Questions
1. Can the Prism-RL model reproduce the true parameter of the RL
model even when positive attributes are included ?
2. If yes, how stable is the estimation w.r.t. starting points ?

Experimental setup•

Sioux Falls network route choice•Observations simulated by the RL model with known true parameters(24 OD x 1000 samples)•Estimate both the RL and Prism-RL model using the same observations•

Prism-RL model•

Define a state network for each destination•Set T = 15 (*did not affect the results)
17

Numerical experiments

18

Numerical experiments | Estimation Resultβ*RL(-2.5, 2.0)

N/A(-2.5, 1.5)

Prism-RL(-2.493**, 2.002**)
3.36s / LL=-4919.0(-2.505**, 1.509**)(-2.505**, 1.509**)

0.99s / LL=-5420.5

2.87s / LL=-5420.5(-1.5, 1.5)

N/A(-1.5, 1.0)

N/A(-1.511**, 1.522**)
2.99s / LL=-7778.3(-1.492**, 0.994**)
2.64s / LL=-8366.9* All true params are feasible solution to the RL model; estimation started with (-1, -1)•Prism-RL model reproduced the true values with high accuracy
even for the cases where RL model failed•

In the case where RL was successfully estimated, the estimation
results of both models were consistent19

Numerical experiments | Estimation Process
RL

Prism-RLRLInfeasibleregion•

RL model depends on starting point and often diverge during theestimation•

Prism-RL model converges to the true value regardless of starting
point (*update to infeasible region was not observed)
20

Numerical experiments | Estimation Process
Prism-RL•

Stably converged to the true parameter even when starting point is
outside the RL feasible region•No prior information on the true value is needed (you can set aninitial point as you like)21Real application to pedestrian route choice•

Kannai, Yokohama (a mile square centered on Kannai station)• 724 Nodes, 2398 Links, 8434 Link pairs•

PP Survey in H30 PT survey••

410 observed paths of 159 pedestrians, 164 destinations
Diverge walking paths including large detours
Kannai sta.
St. w. green
CrosswalkLongitude

22Real application | Definition of choice-stage constraint T•

Define T for each d based onobserved detour rate:•••: Set of observed paths for d: min. steps b/w observed OD pair: observed no. of steps of n•

75 percentile value (=1.34) to include
diverse paths in the path set•

All observations satisfy the prism
constraint23

Real application | Utility specification• Compare two different utility specifications:(a)(b)• Length: length of link (m/10)• Crosswalk: 1 if the link is a crosswalk and 0 otherwise• Green: On-street green presence (1/0; interacted with link length)

To clarify:
1. Street greenery produces a positive effect on utility forpedestrian route choice? Can Prism-RL model capture it?
2. How different are the estimation results of RL/Prism-RL models?

24

Real application | Estimation result• For specification (a), both RL and Prism-RL models obtained estimation
results with statistical significance• Length, Crosswalk are both negative → Pedestrians do not like paths withlong distance and crosswalks• Prism-RL model fits better (details later)• For (b), ONLY Prism-RL model obtained the result and captured thepositive utility of green presence on streets• RL model failed with all the tested starting points• Adding the attribute improved goodness-of-fit (with 99% significance)
25

Real application | Estimation result - Nested models• Prism-based approach also suited the NRL model as well
• Same signs as RL models; Prism-NRL fits better than NRL• Captured correlation: scale (variance) decreases on links close to destination• NRL could be estimated for spec. (b) but depended on starting point• Prism-NRL was successfully estimated with all initial points tested• Prism-based approach can also be viewed as a good approximation toprovide a nice starting point for original RL models
26Real application | Model validation

Prism-RL/NRLRL/NRL#1: RL (a)#2: NRL (a)#3: NRL (b)#4: Prism-RL (a)#5: Prism-NRL (a)#6: Prism-RL (b)#7: Prism-NRL (b)• Compare model performance of out-of-sample prediction• 10 sets of randomly split estimation and validation samples (8:2)• Prism-RL model shows a higher prediction performance for all samples• Universal set (RL/NRL) vs Prism-based path set (Prism-RL/NRL)• Inclusion of positive attribute & nesting also improved the performance27

Real application | Impact of T (Prism-RL results)
Test different detour rates γ inSmall

Path setsizeLarge*Corresponds to RL
when T goes to infinity• The signs and scales of the estimates remained unchanged• The ratio of negative parameters systematically increased as γ grew
• Prism-RL model adjusted the parameter to keep little probability of
detour/cyclic paths• Model fits better with smaller γ values (i.e., tighter constraints)• Due to the exclusion of behaviorally unrealistic paths• Trade-off with out-of-sample prediction (choice set consistency)
28

Conclusion• Recursive model describes the decision-making structure and is
a computationally efficient method in a dynamic/sequential
choice context• Recursive model entails a numerical issue with respect to thevalue function which is critical during the estimation• Prism-based approach solves the issue and stably captures
positive network attributes• Expanded the practical applicability of recursive models

29

Thank you for your attention!

Cite/more details:“Capturing positive network attributes during the estimation ofrecursive logit models: A prism-based approach”
arXiv:2204.01215 [econ.EM]

References
RL model and its numerical issues• Fosgerau, M., Frejinger, E., Karlstrom, A. (2013). A link based network routechoice model with unrestricted choice set. Transportation Research Part B:
Methodological 56: 70–80.
• Oyama, Y., Hato, E., (2017) A discounted recursive logit model for dynamic
gridlock network analysis. Transportation Research Part C: Emerging
Technologies 85: 509–527.
• Mai, T., Frejinger, E. (2022). Undiscounted recursive path choice models:
Convergence properties and algorithms. Transportation Science.

Prism-constrained RL model• Oyama, Y. (2022) Capturing positive network attributes during the estimation ofrecursive logit models: A prism-based approach. arXiv: 2204.01215 [econ.EM].
• Oyama, Y., Hato, E. (2019) Prism-based path set restriction for solving
Markovian traffic assignment problem. Transportation Research Part B:
Methodological 122: 528-546.
• ⼤⼭雄⼰, ⽻藤英⼆ (2017) 時間構造化ネットワーク上の確率的交通配分. ⼟⽊学会
論⽂集 D3(⼟⽊計画学) 73(4): 186-200.
• ⼤⼭雄⼰, ⽻藤英⼆ (2016) 時空間制約と経路相関を考慮した歩⾏者の活動配分問
題. 都市計画論⽂集 51(3): 680-687.
31

Appendix | CPU time for estimation

Average CPU time (s) over 10 samples in validation• RL model is very fast due to the linear system• Advantage of prism-constrained models is independence of themodel linearity: the scale of required CPU time does not change verymuch between Prism-RL and Prism-NRL models

32