A subsidy-stabilized assignment game for Mobility-as-a-Service
markets with both fixed route and on-demand operators
Bingqing Liu, Joseph Chow*
C2SMART University Transportation Center, Department of Civil and Urban Engineering, New York
University Tandon School of Engineering, Brooklyn, United States
bl2453@nyu.edu, joseph.chow@nyu.edu* Corresponding author

Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island
January 15, 2022
Keywords: Branch-and-bound, Mobility-as-a-Service, Mobility-on-demand, Assignment
Game1INTRODUCTION

New mobility services are emerging rapidly in recent years, such as bikeshare,
micromobility, carshare, ride-hail, and microtransit, which have given rise to the concept ofMobility-as-a-Service (MaaS). MaaS platforms provide mobility services through a joint
digital channel that enables users to plan and pay for multiple types of mobility services.
Services include both fixed route and mobility on-demand (MOD). There’s a growing needto develop analytical tools to help design different MaaS platforms: for the platforms, which
operators to include, what mechanisms to use to allocate costs; for operators, which service
regions or routes to serve, what service capacities to operate, what prices to charge
passengers. MaaS systems are two-sided markets, with two mutually exclusive sets ofagents, i.e., users and operators. Assignment models in MaaS systems need to depend on
both users’ route choices in the multimodal service network context and operators’ pricing
and operation decisions.
A cooperative game-theoretic framework has been proposed to model the stablematching between operators and users in a two-sided market. Pantelidis et al. (2020)
proposed a many-to-many assignment game to model MaaS systems, where each route canbe operated by one or more operators and the solution is mechanism-agnostic (so long as amechanism falls between a buyer-optimal or seller-optimal stable outcome space). Theassignment game is a special case bilevel problem in which the lower level is the matching
and the upper level is the cost allocation design; unlike conventional bilevel problems there
is no dependency from the lower level on the upper level decisions except for solution
feasibility (i.e. stable outcome space is non-empty). Existence of a feasible and stableoutcome depends on the complicated relationship between trip utility, travel cost, operation
cost, and ownership of different parts of the network. If some matching pairs do not provide
enough gain to be allocated between users and operators, the users may deviate from theroutes selected in optimal matching or just end up unserved. The solution provided in
Pantelidis et al. (2020) is only to the lower-level problem: a matching solution may be foundthat does not exhibit any stable outcomes and is hence not the solution to the bilevelproblem. The best stable assignment can be improved upon with subsidy to make an
unstable solution stable. The MaaS platform can intervene by injecting subsidies to theinfeasible/unstable matching pairs to increase their gain to make sure that no user deviates

TRISTAN XI Symposium

Original abstract submittal

B. Liu and Y. J. Chow

2

from the matching. Tafreshian and Masoud (2020) used a minimum subsidy problem toobtain a stable outcome for an infeasible/unstable matching in peer-to-peer ridesharing
matching games, which showed that subsidization is an effective way of stabilizing
matchings. The more generalized assignment game with subsidy-stabilization (without
subsidy is a more constrained variant) is considered.
Secondly, the model from Pantelidis et al. (2020) only considers fixed route services.
MaaS markets include many MOD services: microtransit, shared bikes, taxis, etc. These
services cannot be modeled using service links and capacities, but instead need to consider
service region design (which zones are served), fleet size, and the resulting matching
frictions (e.g. Zhou et al., 2021). The matching subproblem from Pantelidis et al. (2020)
needs to be changed from a conventional multicommodity network design problem to one
that includes nonlinear matching friction functions as the continuous approximation of zonal
performance functions for MOD service, resulting in a nonlinear integer programming
problem within a special case bilevel optimization.
We propose a branch-and-bound based solution algorithm to find a subsidystabilized solution to this many-to-many assignment game that ensures stability for a MaaS
market, considering both fixed-route services and MOD. This contribution significantly
extends the model proposed by Pantelidis et al. (2020) making it applicable to a much wider
set of MaaS networks and guaranteeing stability through platform intervention.

2METHODOLOGY

Traditional fixed-route transit services and MOD services operate with different strategies
but should be both considered in MaaS systems.
To model the 2 types of services, we create a joint service network by connecting
MOD complete subgraphs with a fixed-route network with access and egress links (the latterof which is modeled in Pantelidis et al., 2020). Let (𝑁, 𝐴) be the joint network, 𝐹 be the setof all operators and 𝐹𝑀𝑂𝐷 be the set of MOD operators. Travel cost of access links andoperation costs of MOD operators are modeled with Cobb-Douglas production functions.
Travel costs of access links are shown in Eq. (1), where 𝑡𝑖𝑗,𝑎𝑐𝑐 is a user’s cost to access link(𝑖, 𝑗) ∈ 𝐴, ℎ𝑓 is the fleet size of MOD operator 𝑓 ∈ 𝐹𝑀𝑂𝐷 that operates in a service region
that includes node 𝑗 ∈ 𝑁, 𝑥𝑖𝑗 is the flow of access link (𝑖, 𝑗) ∈ 𝐴, and 𝑎𝑎𝑐𝑐 , 𝑏1 , 𝑏2 areparameters (𝑏1 < 0, 𝑏2 > 0) that can fit the function to specific operators that account for
their matching algorithms, travel patterns, and built environment structure. Operation costof MOD operator is shown in Eq. (2), where 𝑐𝑓,𝑀𝑂𝐷 is the operation cost of MOD operator𝑓 ∈ 𝐹𝑀𝑂𝐷 , 𝑁𝑓 is the set of nodes operated by 𝑓 ∈ 𝐹𝑀𝑂𝐷 , , ∑𝑗∈𝑁𝑓 𝑥𝑖𝑗 is the sum of all the flows
served by 𝑓 ∈ 𝐹𝑀𝑂𝐷 , 𝑎𝑓 , 𝑏3 , 𝑏4 are similarly calibrated parameters (𝑏3 , 𝑏4 > 0).
𝑏𝑏𝑡𝑖𝑗,𝑎𝑐𝑐 = 𝑎𝑎𝑐𝑐 ℎ𝑓 1 𝑥𝑖𝑗2𝑏𝑐𝑓,𝑀𝑂𝐷 = 𝑎𝑓 ℎ𝑓 3 (∑𝑗∈𝑁𝑓𝑥𝑖𝑗 )𝑏4(1)(2)

The objective function of the lower-level matching problem (𝐿1 ) is written as the sum of theusers’ travel cost, operators’ operation cost (both fixed-route and MOD), where theoperation costs of MOD include costs of operating fleets (𝑐𝑓,𝑀𝑂𝐷 ) and fixed infrastructure
costs at the MOD nodes in their services. The MOD operators’ choices (service region withgiven fleet size), fixed route operators’ choices (which links to operate with given service
capacity), and users’ choices (multimodal service path flows) are solved from 𝐿1 . The upper
level of the model is pricing and cost allocation (𝐿2 ). The formulation is similar to Pantelidis

TRISTAN XI Symposium

Original abstract submittal

B. Liu and Y. J. Chow3et al. (2020). Since the matching from 𝐿1 is link-based, path-based flows are not unique, but
the model is still meaningful due to the uniqueness of system-level measures such as total
operation costs and network flows. If infeasibility or instability is encountered in 𝐿2 , subsidy
stabilization is introduced. 𝐿3 solves for minimum amount of subsidy to either users oroperators subject to the cost allocation constraints, which is the minimum of subsidy needed
to stabilize an unstable matching from 𝐿1 .
An original branch-and-bound algorithm is proposed to solve the assignment gamewith subsidy. 𝐿1 is a nonlinear integer program, which can be solved with the branch-andbound algorithm (Land and Doig, 2010); at each branch, a convex nonlinear optimization issolved. The bound used to prune branches is the sum of system cost and subsidies, i.e., thesubsidized system cost. When an integer solution is found, we solve the cost allocation
problem (𝐿2) for the corresponding matching. If a stable outcome is achieved, whose systemcost is lower than lowest subsidized system cost found yet, the upper bound is updated. If
infeasibility or instability is reached instead, we solve the minimum subsidy problem (𝐿3)to find the subsidized system cost to see if the upper bound needs updating. All brancheswith an objective value larger than the upper bound of the subsidized system cost are pruned.
When all branches are closed, the corresponding matching of the current upper bound (andcorresponding stable outcome space) is output as the optimal solution of the bilevel problemwith subsidy. The algorithm can be further extended into a branch-and-cut algorithm.
Analogies to system optimal (solution from Pantelidis et al., 2020), user equilibrium
without pricing (optimal stable outcome without subsidy), and user equilibrium with optimal
pricing (subsidy-stabilized optimum) solutions are presented, where the first best subsidy is
not guaranteed to attain the system optimum.

3NUMERICAL EXAMPLE

We use a toy network shown in Fig. 1 to illustrate how the method works. In Fig.1(a), thesolid links represent the fixed-route services, the same color are operated by the sameoperator. There are 3 MOD operators (blue, green, brown). The circles represent the nodes
that MOD operators can choose from (blue: A,B,C; green: B,C; brown: B,D). The network
can be expanded into the network in Fig.1(b) by adding access link and egress link of MOD.
Travel cost, operation cost, and capacities are labelled in Fig.1. The values of the parameters
are set as follows: 𝑎𝑎𝑐𝑐 = 1, 𝑏1 = −2, 𝑏2 = 1, 𝑎𝑓 = 2, 𝑏3 = 2, 𝑏4 = 1. The fleet sizes aregiven in Table 1. The infrastructure cost of MOD nodes 7, 8, 9, 10, 11, 12, and 13 are 3, 3,0, 0, 1, 1, and 3, respectively. Demand is 1,000 from nodes 1 to 3, and 500 from nodes 1 to4. The branch-and-bound algorithm found 18 integer solutions before closing all branches.
Each branch is solved using Gurobi. The top 5 solutions are shown in Table 1.

4

COMPUTATIONAL EXPERIMENTS

Several in-depth computational experiments will be presented. These include:••

Randomized instances of varying sizes to evaluate computational efficiency of solutionalgorithm
A case study with a network instance drawn from a parametric city design (Fielbaum et al.,2017) in which three scenarios are investigated:o Only fixed route service provided (with two different service frequency options), under
different utility levels to illustrate operators’ incentive to enter to the platformo The same service network with added MOD operators (with two different fleet sizelevels) to illustrate the model’s sensitivity to identify conditions where MOD operations

TRISTAN XI Symposium

Original abstract submittal

B. Liu and Y. J. Chowo4

work better as first/last mile, and sensitivity of operators’ revenues and ridership to fleet
size and service frequencies
Splitting of the user demand into two population segments to demonstrate the effect ofuser heterogeneity and assessment of service equity

The algorithm is a powerful tool of evaluating MaaS system performance, which canfacilitate the decision-making and intervention of MaaS platforms and other regulators. The
framework can be further applied to two-sided market use-cases under a network setting,such as freight logistics and airline revenue management problems.

(a) Original Network(b) Joint Network
Figure 1 – Toy Network

Table 1 – Top 5 Solutions of the Toy Network
Fixed-route links operated
1(23,4),(1,3),(1,5),(5,4),(1,21),(21,23)

2
3
4
5

(23,4),(1,3),(1,5),(5,4),(1,21),(21,23)(23,4),(1,3),(1,5),(5,4),(1,21),(21,23)(23,4),(1,3),(1,5),(5,4),(1,21),(21,23)(23,4),(1,3),(1,5),(5,4),(1,21),(21,23)

MODNodesOpened7,11,12,13
7,13
11,12
7,12,13

MOD Fleet Sizes(blue, green,brown)
0.96, 0.21, 0.87
0.96, 0, 00, 0, 0.79
0, 0.11, 00.95, 0.35, 0System
Cost

SubsidiesneededSubsidized
SystemCost

11,854.63

2.50

11,857.13

1st11,854,71
11,854.92
11,855.00
11,855.70

2.50
2.50
2.50
2.50

11,857.21
11,857.42
11,857.49
11,858.20

2nd
6th
11th
3rdFoundReferences
Fielbaum, A., Jara-Diaz, S., & Gschwender, A. (2017). A parametric description of cities for thenormative analysis of transport systems. Networks and Spatial Economics, 17(2), 343-365.
Land, A.H. and Doig, A.G., 2010. An automatic method for solving discrete programming
problems. In 50 Years of Integer Programming 1958-2008 (pp. 105-132). Springer, Berlin,Heidelberg.
Pantelidis, T.P., Chow, J.Y. and Rasulkhani, S., 2020. A many-to-many assignment game andstable outcome algorithm to evaluate collaborative mobility-as-a-service
platforms. Transportation Research Part B: Methodological, 140, pp.79-100.
Tafreshian, A. and Masoud, N., 2020. Using subsidies to stabilize peer-to-peer ridesharing markets
with role assignment. Transportation Research Part C: Emerging Technologies, 120, p.102770.
Zhou, Y., Yang, H., Ke, J., Wang, H., & Li, X. (2021). Competition and third-party platformintegration in ride-sourcing markets. Transportation Research Part B: Methodological.

TRISTAN XI Symposium

Original abstract submittal