Mechanism design for Mobility-as-a-Service platform considering
travelers’ strategic behavior and multidimensional requirements
X. Dinga, Q. Qib, S. Jianc*a<Department of Civil and Environmental Engineering, The Hong Kong University of Science andTechnology>, <Clear Water Bay>, <Hong Kong SAR>
xdingac@connect.ust.hkb< Gaoling School of Artificial Intelligence, Renmin University of China>, <Beijing>, <China>
qi.qi@ruc.edu.cnc<Department of Civil and Environmental Engineering, The Hong Kong University of Science andTechnology>, <Clear Water Bay>, <Hong Kong SAR>
cesjian@ust.hk* Corresponding author

Extended abstract submitted for presentation at the 11 th Triennial Symposium
onTransportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius IslandApril 12, 2022
Keywords: Mobility-as-a-Service (MaaS), mechanism design, resource allocation, online algorithm

1INTRODUCTION

Mobility-as-a-Service (MaaS) is an emerging transport model which provides access to any combinationof travel modes through a single platform. A MaaS operator sits between travelers and TSPs, acting asa broker who purchases mobility resources from individual TSPs, constructs seamless transport services,then sells them to travelers in response to their demand. To ensure the sustainability of such platforms,
the key challenge lies in matching travelers to TSPs so that travelers’ individual needs are satisfied,
TSPs gain nonnegative profits and system efficiency is achieved. However, individual travelers’ travel
requirements and valuations are not readily available and difficult to obtain. In this study, we develop
an auction-based mobility resource allocation and pricing mechanism to elicit travelers’ true
requirements and valuations, and solve this matching problem within the transport network context. Themechanism takes travelers’ strategic behavior into account and applies VCG-based pricing scheme toensure incentive compatibility, individual rationality and system efficiency. We adopt a columngeneration based solution algorithm to solve the offline (static) matching and pricing problem. For theonline (dynamic) problem, we develop a dynamic learning algorithm to obtain near optimal solution andcompare it to the classic greedy-based algorithm. The efficiency of the proposed mechanisms is tested
through a case study.

2METHODOLOGY

2.1

Offline auction mechanism with column generation

We start by formulating and solving the offline (static) mobility resource matching problem. Consider
a multimodal network 𝐺(𝒩, ℒ) operated by a MaaS platform where 𝒩 denotes node set and ℒ denotes
mode-specific link set. Each link is associated with length 𝐿𝑖𝑗 , ∀𝑖, 𝑗 ∈ 𝒩, 𝑖 ≠ 𝑗, travel time 𝑇𝑖𝑗 , capacity
𝑊𝑖𝑗 , the maximum number of riders sharing a vehicle on that link 𝑅𝑖𝑗 and operational cost 𝐶𝑖𝑗 . Theselinks construct 𝒦 multimodal paths with heterogeneous performance, measured by travel time 𝑇𝑘 ,TRISTAN XI SymposiumOriginal abstract submittal

X. Ding, Q. Qi and S. Jian

2

operational cost 𝐶𝑘 and weighted number of shared riders 𝑅𝑘 , where 𝑇𝑘 and 𝐶𝑘 are the summation of𝑇𝑖𝑗 and 𝐶𝑖𝑗 of all links on path 𝑘. 𝑅𝑘 is the weighted average number of allowable shared riders of alllinks on path 𝑘. Let 𝒮 denote the set of travelers who bid for mobility service. A bid from traveler 𝑠
includes his or her origin 𝑂𝑠 , destination 𝐷𝑠 , requested travel time 𝒯𝑠 , preferred number of shared ridersℛ𝑠 and bidding price ℬ𝑠 . Traveler’s requested travel time and number of shared riders are regarded assoft constraints, which means violation on these requirements are allowed but will lead to a loss in thevalue they can obtain. The true valuation of traveler 𝑠 towards path 𝑘 can be calculated as:(1)
𝑉𝑠𝑘 = 𝑉𝑠 − 𝛾𝑠 max{𝑇𝑘 − 𝒯𝑠 , 0} − 𝛽𝑠 max{𝑅𝑘 − ℛ𝑠 , 0}∀𝑠 ∈ 𝒮, 𝑘 ∈ 𝒦
where 𝑉𝑠 is the true willingness-to-pay of traveler 𝑠 and it equals to ℬ𝑠 only if traveler bids truthfully. 𝛾𝑠and 𝛽𝑠 represent the unit monetary penalty of traveler 𝑠 due to late arrival and exceeding the preferrednumber of shared riders. Our goal is to maximize social welfare, defined as the total utility of all travelersand TSPs. Travelers’ utility 𝑢𝑠 equals to his or her true valuation obtained from traveling on theallocated path 𝑘 minus the payment, denoted by 𝑝𝑠 , i.e., 𝑢𝑠 = 𝑉𝑠𝑘 − 𝑝𝑠. TSPs’ utility equals the total
payments received from travelers minus the total operational costs. The social welfare maximization
problem is then formulated as follows:max ∑ ∑ (𝑉𝑠𝑘 − 𝐶𝑘 )𝑥𝑠𝑘𝑥𝑠𝑘(2)𝑠∈𝒮 𝑘∈𝒦

subject to∑ 𝑥𝑠𝑘 ≤ 1∀𝑠 ∈ 𝒮(3)∀𝑖, 𝑗 ∈ 𝒩, 𝑖 ≠ 𝑗(4)𝑘∈𝒦𝑘∑ ∑ 𝑥𝑠𝑘 𝛿𝑖𝑗≤ 𝑊𝑖𝑗 𝑅𝑖𝑗𝑠∈𝒮 𝑘∈𝒦(5)𝑥𝑠𝑘 ∈ {0,1}∀𝑠 ∈ 𝒮, 𝑘 ∈ 𝒦
where 𝑥𝑠𝑘 = 1 if traveler 𝑠 is assigned to path 𝑘. Note that path 𝑘 is feasible for traveler 𝑠 only if it isbetween 𝑂𝑠 and 𝐷𝑠 . Constraints (3) guarantee that each traveler can be allocated to at most one path.
Constraints (4) ensure that the number of travelers on each link does not exceed the link capacity.
Constraints (5) set the feasible domains of decision variables.
Considering that number of decision variables associated with paths are much larger than number ofcapacity constraints of links, we adopt column generation algorithm, which has been widely applied insolving combinatorial optimization problems (e.g., Akyüz, et al., 2016; Gendron, et al., 2014). The idea
is to start by solving a linear restricted master problem (RMP) with only a subset of paths, then iteratively
we find paths that have the potential to increase the objective function and add them to the network until
no such paths exist. Finally, we conduct the branch-and-bound process to obtain the integer solution.
To determine the payment for each traveler, we have to ensure incentive compatibility and individual
rationality, which means travelers bid truthfully and gain non-negative utility from using the MaaSservice. We adopt the VCG-like payment rule:∗ − (𝑍𝑋 ∗ − 𝑣𝑠 (𝑋𝑠∗ ))𝑝𝑠 = 𝑍𝑋−𝑠𝑠∀𝑠 ∈ 𝒮(6)∗ are optimal solutions to the social welfare maximization problem with and without
where 𝑋𝑠∗ and 𝑋−𝑠∗ denote corresponding social welfare. 𝑣𝑠 (𝑋𝑠∗ ) is the valuation
the request of traveler 𝑠 and 𝑍𝑋𝑠∗ and 𝑍𝑋−𝑠of traveler 𝑠 obtained under solution 𝑋𝑠∗ . Such payment rule prevents travelers from misreporting since
the payment of traveler 𝑠 does not depend on his or her reported bidding price.

2.2

Online auction mechanism with dynamic learning algorithm

When setting the problem in online (dynamic) scenario, column generation algorithm and VCG-likepayment rule will take exponential time with the increase of travelers, and thus cannot give immediate
response. To this end, we propose a dynamic learning algorithm to solve the online resource allocation

TRISTAN XI Symposium

Original abstract submittal

X. Ding, Q. Qi and S. Jian

3problem, which is extended from a general version (Agrawal, et al., 2014). The idea is to use some initial
inputs to solve a small-scale partial linear programing, obtain the optimal shadow (dual) price ofmobility resources and treat that shadow price as a threshold price such that only travelers whose bids
are above the threshold price will be accepted. The threshold price is updated continuously.
We assume travelers’ arrival order follows the random permutation model, which lies between the worst
case and a known distribution. We also need to know the total number of travelers a priori to decide theproper quantity of requests for learning threshold price. The competitive ratio of this algorithm is thentheoretically proved. In general, we solve shadow price of each link from history bids and determine theallocation for future bids subject to capacity constraints. The payment of allocated traveler is the shadow
price of the matched path, which equals to the summation of shadow prices of all link on that path.

2.3

Online auction mechanism with greedy algorithm

For comparison purpose, we propose another online algorithm based on the classic greedy algorithm.
Greedy algorithm is a popular solution method to online (dynamic) resource allocation problems due its
time efficiency and satisfactory competitive ratio (e.g., Zhang, et al., 2018). The basic idea is to rank
travelers based on their bids and determine allocation according to this rank. Our ranking criteria is bid
density 𝜔𝑠𝑘 , defined to be the social welfare contributed by traveler 𝑠 if he or she is allocated to path 𝑘
divided by his or her integrated travel requirements.
In each time slot, the greedy algorithm first sorts requesting travelers according to their bid density in a
non-ascending order. Then following this rank, the algorithm greedily processes travelers’ requests
considering the capacity constraint. Travelers’ payment is calculated based on the critical bid density,
defined to be the lower bound that the traveler’s bid density must exceed to be accepted in the auction.
Since this critical bid density is independent from the traveler’s own bid information, such payment rulealso guarantees truthfulness.

3RESULTS

We demonstrate the performance of our proposed offline and online mechanisms using a numerical
study on Sioux-Falls network as is shown in Figure 1. We assume there are three origins (𝑂1 to 𝑂3 ) andseven destinations (𝐷1 to 𝐷7 ) with two TSPs operating in this network: a ridesourcing company and an
on-demand bus company.

Figure 1 Sioux-Falls network
TRISTAN XI Symposium

Original abstract submittal

X. Ding, Q. Qi and S. Jian

4

In the offline numerical experiment, we simulate 50 travelers requesting for mobility service from theMaaS platform. Our mechanism accepts 35 travelers’ requests, achieving a matching rate of 70%.
Incentive compatibility and individual rationality are confirmed in this case.
For the online case, we use the same network setting and set the total time span to be 120 minutes (whichwill be divided to 20 time slots for the greedy algorithm). We compare the performance of the proposed
dynamic learning algorithm and the customized greedy algorithm to the first-arrive-first-serve (FAFS)
matching rule, which simply assigns travelers based on their arriving order. The result obtained fromthe offline scenario is treated as benchmark to calculate two major metrics: ratio of social welfare (RSW)
and ratio of matching rate (RMR). Both uniform and Poisson distributions are applied to generate thearrival order of travelers. Table 1 summarizes results of 50 generated instances with 800 travelers. As isshown, both greedy algorithm and dynamic learning algorithm can achieve high approximation ratios
on social welfare and matching rate (above 0.85). In terms of RSW, dynamic learning algorithm
performs the best in both uniform and Poisson distributions. Though it takes the longest computation
time (CT), compared to the operation time span, it is acceptable for the online matching problem.

Arriving
Distribution
UniformPoisson

Table 1 Performance of Online Solution Algorithms with 800 Travelers
GreedyDynamic Learning
MeasureStatistic
FAFS
Algorithm
Algorithm
RSW
Mean (Std)0.804(0.010)
0.875(0.012)
0.898(0.034)
RMR
Mean (Std)0.929(0.008)
0.856(0.008)
0.922(0.041)
CT
Mean
266.757s
561.160s
979.782s
RSW
Mean (Std)0.807(0.013)
0.874(0.011)
0.900(0.036)
RMR
Mean (Std)0.927(0.009)
0.854(0.010)
0.925(0.038)
CTMean267.263s
554.440s
987.616s

We also tested other demand scenarios: 200, 400, 600, and 1000 travelers and found that no matter underwhich demand scenario, the dynamic learning algorithm always outperforms the other two algorithms,
which demonstrates its robustness and effectiveness.

4DISCUSSION

In this paper, we present an auction-based mobility resource allocation and pricing mechanism for theMaaS platform under transport network context. To provide seamless and personalized services fortravelers, our proposed mechanisms allow travelers to report their multidimensional travel requirements(bidding price, travel time, preferred number of shared riders). All proposed offline and online
mechanisms can ensure incentive compatibility and individual rationality of travelers, system efficiency
and payment non-negativity of the platform.

REFERENCE
Agrawal, S., Wang, Z., & Ye, Y. (2014). A dynamic near-optimal algorithm for online linear
programming. Operations Research, 62(4), 876-890.
Akyüz, M. H., & Lee, C. (2016). Service type assignment and container routing with transit time
constraints and empty container repositioning for liner shipping service networks. Transportation
Research Part B: Methodological, 88, 46-71.
Gendron, B., & Larose, M. (2014). Branch-and-price-and-cut for large-scale multicommodity
capacitated fixed-charge network design. EURO Journal on Computational Optimization, 2(1), 55-75.
Zhang, T., & Xin, Y. (2018). A truthful online auction mechanism for deadline-aware cloud resource
allocation. Paper presented at the NOMS 2018-2018 IEEE/IFIP Network Operations and Management
Symposium, 1-9.

TRISTAN XI Symposium

Original abstract submittal