Dynamic schedulling auction using
time-expanded decision diagram
Takuma Murahashia , Eiji Hatoa,∗a Department of Civil Engineering, University of Tokyo, Tokyo, Japanmurahashi@bin.t.u-tokyo.ac.jp, hato@bin.t.u-tokyo.ac.jp∗ Corresponding author

March 31, 2022
Keywords: (Discrete optimization, tradable permit, VCG mechanism, ZDD)

1Introduction

Recent advances in information technology have led to the development of new transportation
services. In a tradable permit system as a method to improve the operational efficiency of theseservices, it is assumed that permits are distributed to users, mutual transactions are conductedamong users, and users purchase permits to use transportation services. Several tradable permit
system models have been proposed in extant studies (Yang and Wang; 2012, Wu, et al.; 2012,Akamatsu and Wada; 2017, Hara and Hato; 2017). In general, there are many issues to beaddressed in terms of extensibility to system dynamics and traffic assignment models.
In a tradable permit system, the operational efficiency is increased as a result of mutual
trading of permits. However, the allocation is dependent on transactions and autonomous optimal
matching is almost impossible. We introduce the auction mechanism as a method for determining
the allocation of permits. The auction system is a mechanism for autonomously achieving adesirable allocation of goods in society.

2The Framework and the Solution Method

Assuming that traffic flow in the near future is sufficiently predictable and the road network
can be time-structured by using timesteps to represent time discretely. The number of vehicles
that can pass through each edge in each timestep can be calculated. In this study, the permit iscorresponds to each edge in the time-structured network as in Fig.1.

Figure 1 – Distribution of permits to a capacity-constrained time-structured network
TRISTAN XI Symposium

Original abstract submittal

Takuma Murahashi, Eiji Hato

2

When allocating permits based on an auction, the service provider needs each user’s valuefunction for permits. However, it is almost impossible for users to directly express their valuations
to a lot of edges in a time-structured network. We devised a system for mechanically estimating
the value function based on a Discounted Recursive Logit(dRL) model. The immediate utility
and the value function to the destination are processed by the Bellman equation. The service
provider interpret the utility for each edge as a valuation from each user. With accumulated user
data, service providers can estimate the value function for the entire time-structured networkfrom limited user information with high accuracy.
An auction is a mechanism that uniquely determines the allocation of goods based on bidding
information. The paths in a time-structured network is determined by a scheduling problem. In
the system envisioned in this research, bidding information changes sequentially in the form of
new bids or schedule changes, so it is necessary to determine the allocation dynamically. This
dynamic scheduling auction is based on updated bidding information, and the allocations at eachtimestep must be consistent with the results of previous toll allocations.
We consider an auction at timestep t. Assuming that all users’ valuations for each edge inthe time-structured network G are accurate. We summarize them as a value vector v t = {vi,e }.
The distribution of the permits is similarly denoted as the allocation vector xt = {xi,e }. Let Ebe the number of all edges in G, V be the number of all nodes, and Nt be the number of allusers in the auction at timestep t. Then, optimal allocation problem of permits can formulated
as Eqs.(1), (2), (3), (4) and (5); 0-1 integer programming problem.
v t xtmaximizext ∈{0, 1}(1)

0 0 
..
 xt =  .. 
.
 . 
OB10

1B2O
 1 
..
 xt ≤  .. .
 . OB21
µ1 µ2 
IE · · · IE xt ≤  .  .. µE

subject toB1O

C t xt = g t

(2)

(3)

(4)

(5)

Eq.(2) guarantees the continuity of the spatio-temporal transition and Eq.(3) ensures that single
or less movement is achieved for each user. Eq.(4) ensures that the allocation pattern satisfies
the capacity constraint and Eq.(5) guarantees the consistency with the results of the auction
conducted at timestep t − 1. Here, B1 ∈ Z (V −2)×E is a submatrix of the incidence matrix A(G),which consists of rows other than those corresponding to the origin and destination, B2 ∈ N 1×E
is the submatrix of A(G) consisting of a row corresponding to the origin, and IE is the unit
matrix of size E. µe is the maximum number that can be allocated for edge e in G. Also, Ct
is a diagonal matrix, and its diagonal component ci,e and the elements gi,e of the vector gt are
defined by Eq.(6). Let E ′ (t) be the edge set whose source nodes correspond to a timestep beforet, let Ei∗ (t − 1) be the edge set whose permits were allocated to user i at timestep t − 1, and let
Ei,origin be the edge set corresponding to the stay at the origin.
(ci,e =

10e ∈ E ′ (t) ∧ e ∈/ Ei,origin
otherwise(gi,e =

10e ∈ E ′ (t) ∧ e ∈ Ei∗ (t − 1) ∧ e ∈/ Ei,origin
otherwise(6)

Two important problems arise in the process the service provider solves the optimization problem
TRISTAN XI Symposium

Original abstract submittal

Takuma Murahashi, Eiji Hato3

through dynamic scheduling auction. The first problem is the strategy-proofness of the users’bidding. If there are users who intentionally state an invalid valuation through strategic bidding,
it is impossible to maximize the social welfare correctly. Therefore, auctions need to be designed
so that true bidding is the dominant strategy for each user. The second problem is the large
numerical cost involved in solving the optimal allocation problem. This 0-1 integer programming
problem is classified as NP-hard. Furthermore, the dynamic scheduling auctions envisioned inthis study involve repeated recalculations within a short span of time.

3VCG Mechanism of Dynamic Scheduling Auction

The VCG mechanism is an auction mechanism designed to motivate agents(system provider andusers) to select a socially efficient allocation of public goods. We designed the VCG mechanism
to accommodate dynamic scheduling auctions. Here, we show the VCG mechanism for dynamicscheduling auctions achieves efficient allocation and strategy-proofness.
If the user correctly represents his/her true information, the service provider assumed toaccurately get the value function through the dRL model, b1 · · · bt = v 1 · · · v t . First, when the
inner product of the correct bidding vector and the allocation vector is maximized with theconstraint equations, the state of the system corresponds to the social optimum.
Next, we show the mechanism satisfies the strategy-proofness. Let bt be the bidding vector attimestep t. The allocation in the auction at timestep t depends on the bidding vector at timestept, bt , and the bidding vectors for all previous auctions. Therefore, the allocation pattern isdenoted as S(b1 , · · · , bt ). Also, let W (·) denote the social welfare achieved by the auction. Under
the VCG mechanism, the payment of user i who placed a new bid at timestep t, Pi (b1 , · · · , bt ), isexpressed as Pi (b1 , · · · , bt ) = W (b1 , · · · , 0, bt′ ,−i , · · · , 0, bt,−i ) − W−i (·) where bt,−i denotes thebidding vector except user i. W−i (·) indicates W (·) minus user i’s value bt,i · Si (b1 , · · · , bt ).
Suppose a situation where all auction participants except user i bid true value vector b−i =v −i . Consider a domination strategy for user i. The surplus of user i is as follows:v i · Si (v 1 , · · · , bt′ ,i , v t′ ,−i , · · · , bt,i , v t,−i ) − Pi (v 1 , · · · , bt′ ,i , v t′ ,−i , · · · , bt,i , v t,−i )= v i · Si (v 1 , · · · , bt′ ,i , v t′ ,−i , · · · , bt,i , v t,−i ) + W−i (·) − W (v 1 , · · · , 0, v t′ ,−i , · · · , 0, v t,−i )= v · S(v 1 , · · · , bt′ ,i , v t′ ,−i , · · · , bt,i , v t,−i ) − W (v 1 , · · · , 0, v t′ ,−i , · · · , 0, v t,−i )W (v 1 , · · · , 0, v t′ ,−i , · · · , 0, v t,−i ) is independent of user i’s bid. The dominant strategy for user i
is to maximize v · S(v 1 , · · · , bt′ ,i , v t′ ,−i , · · · , bt,i , v t,−i ). Given the allocation pattern is calculatedwith the 0-1 integer programming problem, the following equation holds for bt′ ,i , · · · , bt,i .
v · S(v 1 , · · · , bt′ ,i , v t′ ,−i , · · · , bt,i , v t,−i ) ≥ v · S(v 1 , · · · , v t )The dominant strategy for user i is to make an honest bid so that bi = v i .

4

Calculation Algorithm and Numerical Resluts

The 0-1 integer programming problem consisting of Eqs.(1) - (5) is NP-hard and computationallydemanding. Dynamic auctions require frequent recalculations. Although we have succeeded toproof that linear relaxation can be applied to the formulation, the proof is omitted here.
The optimal allocation of permits is a combinatorial optimization problem, and the feasible
region is discrete. By enumerating the entire feasible region and indexing them by the socialwelfare, it is possible to determine the solution. However, because the size of the feasible region
grows exponentially due to the combinatorial explosion, the computer cannot handle the memory
load when using the general counting method. we use ZDD (Zero-suppressed Binary Decision
Diagram) which has high compression performance, especially for sparse combinatorial sets. TheTRISTAN XI Symposium

Original abstract submittal

Takuma Murahashi, Eiji Hato4

advantage of this method is that it can significantly reduce the numerical cost for recalculation.
By updating the ZDD sequentially, the number of enumerations can be greatly reduced while
maintaining solution continuity. In this study, we follow the flowchart shown in Fig.2 to solve
the optimal allocation problems in dynamic scheduling auctions.
We compare two methods, the enumeration-based method with ZDD and linear relaxation.
The computation time for the winner-determination problem in the auction at each timestep
is shown in Fig.3. The enumeration method using ZDDs shows high computing performanceagainst recalculation while the computation time increases monotonically with the method using
linear relaxation as time progresses and the number of participants in the auction increases.

Figure 2 – Flowchart of the method with ZDD

5Figure 3 – Change in calculation timeConclusion

This study examined tradable permit mechanism with dynamic scheduling auctions as a method
for sequential optimization of traffic flow for automated vehicles. There are two problems toachieve the socially optimum. The first is strategy-proofness and the second is the high demand for computational performance. In order to solve the first problem, we proposed a VCG
mechanism for dynamic scheduling auctions. This mechanism allowed the system to satisfy thestrategy-proof and efficient allocation for all sequential auctions. In order to solve the secondproblem, we proposed the ZDD-based complete enumeration method. This method shows highcomputing performance against recalculation while the scale of system is small. Moreover, thesuccessful formulation allows us to obtain the results of large auctions by linear relaxation.
This study considers the optimization of traffic assignment problem with tradable permit
system. However, when automated vehicles are introduced, the lanes in the road network will
be divided into some types. The optimal allocation problem for lanes will arise. In addition, thecomputational method proposed in this study is still not scalable to the scale of the system. Oneof the method is surrogate models, such as the GCN (Graph Convolutional Network) model.

References
H. Yang and X. Wang, 2012. Bisection-based trial-and-error implementation of marginal cost pricing
and tradable credit scheme, Transportation Research Part B: Methodological, 46(9), 1085-1096.
D. Wu, Y. Yin, S. Lawphongpanich, and H. Yang, 2012. Design of more equitable congestion pricing
and tradable credit schemes for multimodal transportation networks, Transportation Research Part
B: Methodological, 46(9), 1273-1287.
T. Akamatsu and K. Wada, 2017. Tradable network permits: A new scheme for the most efficient useof network capacity, Transportation Research Part C: Emerging Technologies, 79, 178-195.
Y. Hara and E. Hato, 2017. A car sharing auction with temporal-spatial OD connection conditions,
Transportation Research Procedia, 23, pp. 22-40.

TRISTAN XI Symposium

Original abstract submittal