capbtabboxtable[][]

# Balancing Fairness and Efficiency in Traffic Routing via Interpolated
Traffic Assignment

Devansh Jalota1, Kiril Solovey2, Matthew Tsao1, Stephen Zoepf3, and Marco
Pavone1 1 Stanford University, USA; {djalota, kirilsol, mwtsao,
<EMAIL_ADDRESS>Technion - Israel Institute of Technology, Israel;
<EMAIL_ADDRESS>Lacuna AI, USA<EMAIL_ADDRESS>
###### Abstract

System optimum (SO) routing, wherein the total travel time of all users is
minimized, is a holy grail for transportation authorities. However, SO routing
may discriminate against users who incur much larger travel times than others
to achieve high system efficiency, i.e., low total travel times. To address
the inherent unfairness of SO routing, we study the ${\beta}$-fair SO problem
whose goal is to minimize the total travel time while guaranteeing a
${\beta\geq 1}$ level of unfairness, which specifies the maximum possible
ratio between the travel times of different users with shared origins and
destinations.

To obtain feasible solutions to the ${\beta}$-fair SO problem while achieving
high system efficiency, we develop a new convex program, the Interpolated
Traffic Assignment Problem (I-TAP), which interpolates between a fairness-
promoting and an efficiency-promoting traffic-assignment objective. We
evaluate the efficacy of I-TAP through theoretical bounds on the total system
travel time and level of unfairness in terms of its interpolation parameter,
as well as present a numerical comparison between I-TAP and a state-of-the-art
algorithm on a range of transportation networks. The numerical results
indicate that our approach is faster by several orders of magnitude as
compared to the benchmark algorithm, while achieving higher system efficiency
for all desirable levels of unfairness. We further leverage the structure of
I-TAP to develop two pricing mechanisms to collectively enforce the I-TAP
solution in the presence of selfish homogeneous and heterogeneous users,
respectively, that independently choose routes to minimize their own travel
costs. We mention that this is the first study of pricing in the context of
fair routing for general road networks (as opposed to, e.g., parallel road
networks).

##  1 Introduction

Traffic congestion has soared in major urban centres across the world, leading
to widespread environmental pollution and huge economic losses. In the US
alone, almost 90 billion US dollars of economic losses are incurred every
year, with commuters losing hundreds of hours due to traffic congestion [21].
A contributing factor to increasing road traffic levels is the often sub-
optimal route selection by users due to the lack of centralized traffic
control [34, 33]. In particular, selfish routing, wherein users choose routes
to minimize their travel times, results in a user equilibrium (UE) traffic
pattern that is often far from the system optimum (SO) [38, 46]. To cope with
the efficiency loss due to the selfishness of users, several methods including
the control of a fraction of compliant users [37] and marginal cost tolls,
where users pay for the externalities they impose on others, have been used to
enforce the SO solution as a UE [30, 42].

While determining SO tolls is of fundamental theoretical importance, it is of
limited practical interest [44] since SO traffic patterns are often unfair
with some users incurring much larger travel times than others. This
discrepancy among user travel times is referred to as unfairness, which, more
formally, is the maximum possible ratio across all origin-destination (O-D)
pairs of the experienced travel time of a given user to the travel time of the
fastest user between the same O-D pair. The unfairness of the SO solution can
be quite high in real-world transportation networks, since users may spend
nearly twice as much time as others travelling between the same O-D pair [25].
Moreover, a theoretical analysis established that the SO solution can even
have unbounded unfairness [32].

The lack of consideration of user-specific travel times in the global SO
problem has led to the design of methods that aim to achieve a balance between
the total travel time of a traffic assignment and the level of fairness that
it provides. In a seminal work, Jahn et al. [25] introduced the Constrained
System Optimum (CSO) to reduce the unfairness of traffic flows by bounding the
ratio of the normal length of a path of a given user to the normal length of
the shortest path for the same O-D pair. Here, normal length is any metric for
an edge that is fixed _a priori_ and is independent of the traffic flow, e.g.,
edge length or free-flow travel time. While many approaches to solve the CSO
problem have been developed [3, 4, 5], they suffer from the inherent
limitation that the level of experienced unfairness in terms of user travel
times can be much higher than the bound on the ratio of normal lengths that
the CSO is guaranteed to satisfy. In addition to this drawback, the
algorithmic approaches to solve the CSO problem are often computationally
prohibitive and do not provide theoretical guarantees in terms of the
resulting solution fairness and efficiency. Furthermore, it is unclear how to
develop a pricing scheme to enforce such proposed traffic assignments in
practice.

In this work, we study a problem analogous to CSO that differs in the
problem’s unfairness constraints. In particular, we explicitly consider the
experienced unfairness in terms of user travel times as in [6], which,
arguably, is a more accurate representation of user constraints as it accounts
for costs that vary according to a traffic assignment. Our work further
addresses the algorithmic concerns of existing approaches to solve fairness-
constrained traffic routing problems by developing (i) a computationally-
efficient approach that trades off efficiency and fairness in traffic routing,
(ii) theoretical bounds to quantify the performance of our algorithm, and
(iii) a pricing mechanism to enforce the resulting traffic assignment.

Contributions. We study the $\beta$-fair System Optimum ($\beta$-SO) problem,
which involves minimizing the total travel time of users subject to unfairness
constraints, where a $\beta\geq 1$ bound on unfairness specifies the maximum
allowable ratio between the travel times of different users with shared
origins and destinations.

We develop a simple yet effective approach for $\beta$-SO that involves
solving a new convex program, the interpolated traffic assignment problem
(I-TAP). I-TAP interpolates between the fair UE and efficient SO objectives to
achieve a solution that is simultaneously fair and efficient. This allows us
to approximate the $\beta$-SO problem as an unconstrained traffic assignment
problem, which can be solved quickly. We further present theoretical bounds on
the total system travel time and unfairness level in terms of the
interpolation parameter of I-TAP.

We then exploit the structure of I-TAP to develop two pricing schemes which
enforce users to selfishly select the flows satisfying the $\beta$ bound on
unfairness computed through our approach. In particular, for homogeneous users
with the same value of time we develop a natural marginal-cost pricing scheme.
For heterogeneous users, we exploit a linear-programming method [20] to derive
prices that enforce the optimal flows computed through I-TAP. We mention that
our work is the first to study road pricing in connection with fair routing
for general road networks as opposed to, e.g., parallel networks.

Finally, we evaluate the performance of our approach on real-world
transportation networks for the above (Section 6) and other valid notions of
unfairness (Appendix B) . The numerical results indicate significant
computational savings as well as superior performance for all desirable levels
of unfairness $\beta$, as compared to the algorithm in [25]. Moreover, our
results demonstrate that our approach can reduce the level of unfairness by
50% while increasing the total travel time by at most 2%, which indicates that
a huge gain in user fairness can be achieved for a small loss in efficiency,
making our approach a desirable option for use in route guidance systems.

This paper is organized as follows. Section 2 reviews related literature. We
introduce in Section 3 the $\beta$-SO problem and metrics to evaluate the
fairness and efficiency of a feasible traffic assignment. We introduce the
I-TAP method and discuss its properties in Section 4, and develop pricing
schemes to enforce the computed traffic assignments as a UE in Section 5. We
evaluate the performance of the I-TAP method through numerical experiments in
Section 6 and provide directions for future work in Section 7. Furthermore, in
the appendix we also present an extension of our work to additional fairness
notions beyond the one considered in the main text.

##  2 Related Work

The trade-off between system efficiency and user fairness has been widely
studied in applications including resource allocation, reducing the bias of
machine-learning algorithms, and influence maximization. While different
notions of fairness have been proposed, the level of fairness is typically
controlled through the problem’s objective or constraints. For instance,
fairness parameters that trade-off the level of fairness in the objective can
be tuned to investigate the loss in system efficiency in the context of
influence maximization [31] and resource allocation [11] problems. On the
other hand, fairness parameters that bound the degree of allowable inequality
between different user groups through the problem’s constraints have been
proposed to reduce bias towards disadvantaged groups [40]. For example, group-
based fairness notions [24] have been studied to reduce the bias of machine-
learning algorithms, and diversity constraints have been introduced to ensure
that the benefits of social interventions are fairly distributed [41].

In the context of traffic routing, several traffic assignment formulations
have been proposed to achieve a balance between multiple performance criteria
[16, 17], with a particular focus on fairness considerations in traffic
routing [25]. Since Jahn et al. [25] introduced the CSO problem, there have
been both theoretical studies [35] as well as the development of heuristic
approaches to solve the NP-hard CSO problem. For instance, [25] proposed a
Frank-Wolfe based heuristic, wherein the solution to the linearized CSO
problem is obtained by solving a constrained shortest-path problem, while
another work [10] developed a second-order cone programming technique. Several
subsequent approaches for CSO have considered linear relaxations of the
original problem [3, 4, 5]. Each of these approaches bounds the level of
unfairness in terms of normal lengths of paths by restricting the set of
eligible paths on which users can travel to those that meet a specified level
of normal unfairness. However, the experienced unfairness in terms of the
travel times on the restricted path set may be much higher than the specified
level of normal unfairness, which is an _a priori_ fixed quantity.

This inherent drawback of the CSO problem in limiting the experienced
unfairness in terms of user travel times was overcome by [6], which proposed
two Mixed Integer Non-Linear Programming models to capture traffic-dependent
notions of unfairness. Their approach to solve these models relies on a
linearization heuristic for the edge travel-time functions, which are in
general _non-linear_. Achieving a high level of accuracy of the linear
relaxations in approximating the true travel-time functions, however, requires
solving a large MILP which is computationally _expensive_. Unlike [6], our
I-TAP method is computationally _inexpensive_ , while directly accounting for
non-linear travel-time functions.

A further limitation of the existing methods for fair traffic routing is that
there are limited results in providing pricing schemes to induce selfish users
to collectively form the proposed traffic patterns, e.g., those satisfying a
certain bound on unfairness. For instance, [19] provides tolling mechanisms to
enforce fairness constrained flows which applies only to the simplified model
of a parallel network. In more general networks, [28] proposes an auction-
based bidding mechanism for users to be assigned to precomputed paths.
However, this approach cannot be applied as-is to our setting as users are
unconstrained with respect to a specific path set. Thus, we develop road
tolling mechanisms to induce selfish users to collectively form traffic
assignments guaranteeing a specified level of unfairness.

##  3 Model and Problem Definition

We model the road network as a directed graph $G=(V,E)$, with the vertex and
edge sets $V$ and $E$, respectively. Each edge $e\in E$ has a normal length
$\eta_{e}$, which represents a fixed quantity such as the physical length of
the corresponding road segment, and a flow-dependent travel-time function
$t_{e}:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{>0}$, which maps $x_{e}$, the
rate of traffic on edge $e$, to the travel time $t_{e}(x_{e})$. As is standard
in the traffic routing literature, we assume that the function $t_{e}$, for
each $e\in E$, is differentiable, convex, locally Lipschitz continuous, and
monotonically increasing.

Users make trips between a set of O-D pairs, and we model users with the same
origin and destination as one commodity, where $K$ is the set of all
commodities. Each commodity $k\in K$ has a demand rate $d_{k}>0$, which
represents the amount of flow to be routed on a set of directed paths
$\mathcal{P}_{k}$ between its origin and destination. Here $\mathcal{P}_{k}$
is the set of all possible paths between the origin and destination
corresponding to commodity $k$. The edge flow of each commodity $k$ is given
by $\mathbf{x}^{k}=\\{x_{e}^{k}\\}_{e\in E}$, while the aggregate edge flow of
all commodities is denoted as $\mathbf{x}:=\\{x_{e}\\}_{e\in E}$. For an edge
flow $\mathbf{x}:=\\{x_{e}\\}_{e\in E}$ and a path $P\in\mathcal{P}=\cup_{k\in
K}\mathcal{P}_{k}$, the amount of flow routed on the path is denoted as
$\mathbf{x}_{P}$, where the vector of path flows
$\mathbf{f}=\\{\mathbf{x}_{P}:P\in\mathcal{P}\\}$. Then, the travel time on
path $P$ is $t_{P}(\mathbf{x})=\sum_{e\in P}t_{e}(x_{e})$, while
$\eta_{P}=\sum_{e\in P}\eta_{e}$ is its normal length.

We assume users are selfish and thus choose paths that minimize their total
travel cost that is a linear function of tolls and travel time. For a value of
time parameter $v>0$, and a vector of edge prices (or tolls)
$\bm{\tau}=\\{\tau_{e}\\}_{e\in E}$, the travel cost on a given path $P$ under
the traffic assignment $\mathbf{x}$ is given by
$C_{P}(\mathbf{x},\bm{\tau})=vt_{P}(\mathbf{x})+\sum_{e\in P}\tau_{e}$.

###  3.1 Traffic Assignment

In this work we will consider several variants of the traffic assignment
problem (TAP). The goal of the SO traffic assignment problem (SO-TAP) is to
route users to minimize the total system travel time. This behavior is
captured in the following convex program:

######  Definition 1 (Program for SO-TAP [38]).

|s|[2]<b> fh^SO(x):=∑_e ∈E x_e t_e(x_e), ∑_k ∈K ∑_P ∈P_k: e ∈P x_P= x_e, ∀e ∈E
, ∑_P ∈P_k x_P= d_k, ∀k ∈K , x_P ≥0, ∀P ∈P, with edge flow Constraints (1),
demand Constraints (1), and non-negativity Constraints (1).

We mention that the total travel time objective is only a function of the
aggregate edge flow $\mathbf{x}$, which is related to the path flow
$\mathbf{f}$ through Constraint (1). Note for any given path flow $\mathbf{f}$
that both the edge flow $\mathbf{x}$ and the commodity-specific edge flows
$\mathbf{x}^{k}$ for each commodity $k\in K$ are uniquely defined.

Closely related to SO-TAP is the UE traffic assignment problem (UE-TAP) that
emerges from the selfish behavior of users, where each user strives to
minimize its own travel time, without regard to the effect that it has on the
overall travel time of all the users in the system. This behavior is captured
through the following convex program:

######  Definition 2 (Program for UE-TAP [38]).

|s|[2]<b> fh^UE(x):=∑_e∈E∫_0^x_e t_e(y) dy, (1)-(1).

While the integral objective used to define UE-TAP has not found a clear
economic or behavioral interpretation within the transportation and game-
theory communities [38], the optimal solution of UE-TAP corresponds to an
equilibrium, which can be seen through the KKT conditions of this optimization
problem. That is, UE-TAP provides a polynomial time computable method to
determine the user equilibrium flows. A defining property of the UE solution
is that it is fair for all users since the travel time of all the flow that is
routed between the same O-D pair is equal. In contrast, at the SO solution the
sum of the travel time and marginal cost of travel is the same for all users
travelling between the same O-D pair. Thus, marginal cost pricing is used to
induce selfish users to collectively form the SO traffic pattern. While the
number of constraints, which depend on the path sets $\mathcal{P}_{k}$, can be
exponential in the size of the transportation network, both SO-TAP and UE-TAP
are efficiently computable since they can be formulated without explicitly
enumerating all the path level flows and constraints [38].

###  3.2 Fairness and Efficiency Metrics

We evaluate the quality of any given traffic assignment $\mathbf{x}$, which
satisfies Constraints (1)-(1), using two metrics, namely: (i) efficiency,
which is of importance to a traffic authority as well as all users
collectively, and (ii) fairness, which is of direct importance to each user.

We evaluate the efficiency of a traffic assignment by comparing its total
travel time to that of the SO edge flow $\mathbf{x}^{SO}$. Recalling that
$h^{SO}(\mathbf{x})$ denotes the total travel time of the edge flow
$\mathbf{x}$, the inefficiency ratio of $\mathbf{x}$ is

$\rho(\mathbf{x}):=\frac{h^{SO}(\mathbf{x})}{h^{SO}(\mathbf{x}^{SO})}.$ (1)

Note that for the UE solution $\mathbf{x}^{UE}$, the inefficiency ratio is the
Price of Anarchy (PoA) [27], which we denote as $\bar{\rho}$.

To evaluate the fairness of a traffic assignment, we first introduce the
notion of a positive path from [9].

######  Definition 3 (Positive Path).

For any path flow $\mathbf{f}$ with corresponding commodity-specific edge
flows $\mathbf{x}^{k}$, a path $P\in\mathcal{P}_{k}$ is positive for a
commodity $k\in K$ if for all edges $e\in P$, $x_{e}^{k}$ is strictly
positive. The set of all positive paths for a flow $\mathbf{f}$ and commodity
$k$ is denoted as
$\mathcal{P}_{k}^{+}(\mathbf{f})=\\{P:P\in\mathcal{P}_{k},x_{e}^{k}>0,\text{
for all }e\in P\\}$.

The importance of the notion of a positive path is that the path decomposition
of the commodity-specific edge flows $\mathbf{x}^{k}$ may be non-unique;
however the set of positive paths is always uniquely defined for such edge
flows. That is, for commodity specific edge flows $\mathbf{x}^{k}$ the set of
positive paths for any two path decompositions $\mathbf{f}_{1}$ and
$\mathbf{f}_{2}$ are equal, i.e.,
$\mathcal{P}_{k}^{+}(\mathbf{f}_{1})=\mathcal{P}_{k}^{+}(\mathbf{f}_{2})$.

We evaluate the fairness of a traffic flow $\mathbf{f}$ with an edge
decomposition $\mathbf{x}$ through its corresponding unfairness $U$, which is
defined as the maximum ratio across all O-D pairs of (i) the travel time on
the slowest, i.e., highest travel time, positive path to (ii) the travel time
on the fastest positive path between the same O-D pair:

$\displaystyle U(\mathbf{f}):=\max_{k\in
K}\max_{Q,R\in\mathcal{P}_{k}^{+}}\frac{t_{Q}(\mathbf{x})}{t_{R}(\mathbf{x})}.$

That is, $U(\mathbf{f})$ returns the maximum possible ratio of travel times on
positive paths across all commodities with respect to the path flow
$\mathbf{f}$. As a result, the unfairness $U$ is a number between one and
infinity, and a traffic assignment has a high level of fairness if its
unfairness is close to one while it has a low level of fairness if the
corresponding unfairness is much larger than one. A discussion on numerically
computing the above defined notion of unfairness is presented in Section 6. In
contrast, other valid notions of unfairness could also be considered. For
instance, for a given path flow decomposition $\mathbf{f}$ with a
corresponding edge flow $\mathbf{x}$, the unfairness $\tilde{U}(\cdot)$ of the
path flows can be evaluated as the maximum ratio between the travel times of
any two users travelling between the same O-D pair, i.e.,
$\tilde{U}(\mathbf{f})=\max_{k\in
K}\max_{Q,R\in\mathcal{P}_{k}:\mathbf{x}_{Q},\mathbf{x}_{R}>0}\frac{t_{Q}(\mathbf{x})}{t_{R}(\mathbf{x})}$.
Note here that we only consider a ratio of travel times on paths with strictly
positive flow for the path decomposition $\mathbf{f}$ rather than the ratio of
travel times for all positive paths. We defer a detailed treatment of path-
based unfairness measures to Appendix B and highlight here some key features
of the positive path based unfairness measure $U$.

The unfairness measure $U(\mathbf{f})$ can be efficiently computed and has the
benefit that it applies to all possible path decompositions of the commodity
specific edge flows $\mathbf{x}^{k}$. As a result, in the context of a single
O-D pair travel demand, the unfairness measure $U(\mathbf{f})$ has the benefit
that it is a property of the unique edge flow $\mathbf{x}$ and is relevant
when users are not constrained to a specific path decomposition, as happens in
practice. In contrast, path decomposition specific unfairness measures, e.g.,
$\tilde{U}(\mathbf{f})$, are likely to be more sensitive to the method used to
compute the path decomposition. Furthermore, we note that the positive path
based unfairness notion serves as an upper bound on the ratio of travel times
for any two users travelling between the same O-D pair for the path flow
$\mathbf{f}$, i.e., $\tilde{U}(\mathbf{f})\leq U(\mathbf{f})$ for all
$\mathbf{f}$. As a result, our theoretical bounds on unfairness obtained for
the positive path-based unfairness notion will naturally extend to path
decomposition specific unfairness measures such as $\tilde{U}(\mathbf{f})$.
Thus, in the rest of this paper we focus on the positive path-based unfairness
measure and, for numerical comparison, we present other path decomposition
specific unfairness measures, e.g., $\tilde{U}(\mathbf{f})$, in Appendix B.

###  3.3 Toy Network Example

To illustrate the fairness and efficiency properties of the two optimization
problems, SO-TAP and UE-TAP, studied in this work, we present a toy example of
a two-edge Pigou network, as depicted in Figure 1. In particular, consider a
demand of one that needs to be routed from the origin $v_{1}$ to the
destination $v_{2}$, with two edges ($e_{1}$ and $e_{2}$) connecting the
origin to the destination. Observe that if the travel time functions on the
two edges are given by $t_{1}(x_{1})=1$ and $t_{2}(x_{2})=x_{2}$, then under
the UE-TAP solution all users will be routed on edge two, while the SO-TAP
solution that minimizes the total travel time will route $0.5$ units of flow
on both edges. The level of unfairness and the total travel time of the two
traffic assignments are presented in the following table, which indicates that
the UE-TAP solution is fair but inefficient while the SO-TAP solution is
efficient but unfair.

| UE-TAP | SO-TAP
---|---|---
Total Travel Time | 1 | $3/4$
Unfairness | 1 | 2

Figure 1: A two-edge Pigou network example to illustrate the fairness and
efficiency properties of the SO-TAP and UE-TAP optimization problems. For a
demand of one, the UE-TAP solution routes all the flow on edge $e_{2}$
resulting in a fair solution but a total travel time of one. On the other
hand, the SO-TAP solution routes $0.5$ units of flow on both edges, resulting
in an efficient solution with the minimum total travel time, but an unfair
solution with an unfairness of two.

###  3.4 $\beta$-Fair System Optimum

Our focus in this work is in solving the following problem where we impose an
upper bound on the maximum allowable level of unfairness in the network. In
particular, for an unfairness parameter $\beta\in[1,\infty)$, any feasible
path flow $\mathbf{f}$ must satisfy $U(\mathbf{f})\leq\beta$. To trade-off
between user fairness and system efficiency, we consider the following
$\beta$-fair System Optimum ($\beta$-SO) problem.

######  Definition 4 (Program for $\beta$-Fair System Optimum).

|s|[2]<b> f∑_e ∈E x_e t_e(x_e), (1)-(1), U(f) ≤β.

Note that without the unfairness Constraints (4) (or when $\beta=\infty$), the
above problem exactly coincides with SO-TAP. Furthermore, the $\beta$-SO
problem is always feasible for any $\beta\in[1,\infty)$, since a solution to
UE-TAP exists and achieves an unfairness of $\beta=1$.

We also note that the difference between the $\beta$-SO and CSO problems is in
the unfairness Constraints (4). While the $\beta$-SO problem explicitly
imposes an upper limit on the ratio of travel times on positive paths, the CSO
problem imposes normal unfairness constraints for each path
$P\in\mathcal{P}_{k}$ and any commodity $k\in K$ of the form
$\eta_{P}\leq\phi\min_{P^{*}\in\mathcal{P}_{k}}\eta_{P^{*}}$ for some normal
unfairness parameter $\phi\geq 1$. That is, the CSO problem minimizes the
total travel time subject to flow conservation constraints over the set of
paths with a normal unfairness level of at most $\phi$. The authors of [25]
use normal unfairness, which is a fixed quantity, as a proxy to limit the
maximum possible ratio of user travel times. Note that the experienced user
travel times accounts for costs that vary according to a traffic assignment
unlike normal unfairness.

The optimal solution of the $\beta$-SO problem corresponds to the highest
achievable system efficiency whilst meeting unfairness constraints. However,
solving $\beta$-SO directly is generally intractable as the unfairness
Constraints (4) are non-convex if the travel time function is non-linear.
Moreover, since the unfairness metric studied in this work accounts for user
costs that vary according to a traffic assignment, unlike normal unfairness
that is an apriori fixed quantity, the NP-hardness of the CSO problem [25]
suggests the computational hardness of $\beta$-SO [9, 6].

Finally, we mention that we consider a setting wherein the travel demand is
time invariant and fractional user flows are allowed, as is standard in the
traffic routing literature. Also, for notational simplicity, we consider for
now a model where all users are homogeneous, i.e., they have an identical
value of time $v$, and present an extension of our pricing result to the
setting of heterogeneous users in Section 5.2.

##  4 A Method for $\beta$-Fair System Optimum

In this section, we develop a computationally-efficient method for solving
$\beta$-SO with edge-based unfairness constraints, to achieve a traffic
assignment with a low total travel time, whose level of unfairness is at most
$\beta$. In particular, we propose a new formulation of TAP, which we term
interpolated TAP (or I-TAP), wherein the objective function linearly
interpolates between the objectives of UE-TAP and SO-TAP. Our main insight is
that the UE solution achieves a high level of fairness, whereas the SO
solution achieves a low total travel time, and we wish to get the best of both
worlds—high level of fairness at a low total travel time.

In this section, we describe the I-TAP method and evaluate its efficacy for
the $\beta$-SO problem by addressing three key concerns regarding the solution
efficiency, feasibility and computational tractability. In particular, we
establish a relationship between I-TAP and $\beta$-SO through theoretical
bounds on the inefficiency ratio (Section 4.2) and its optimality for two-edge
Pigou networks (Section 4.3). We also establish the feasibility of I-TAP for
$\beta$-SO by finding the range of values of the interpolation parameter such
that the unfairness of the optimal I-TAP solution is guaranteed to be less
than $\beta$ (Section 4.2). Finally, we present an equivalence between I-TAP
and UE-TAP to show that I-TAP can be computed efficiently (Section 4.4). These
results indicate that we can approximate $\beta$-SO as an unconstrained
traffic assignment problem that can be solved quickly. We also mention that we
perform a sensitivity analysis to establish the continuity of the optimal
traffic assignment and its total travel time in the interpolation parameter of
I-TAP in Section 4.5.

###  4.1 Interpolated Traffic Assignment

We provide a formal definition of interpolated TAP:

######  Definition 5 (I-TAP).

For a convex combination parameter $\alpha\in[0,1]$, the interpolated traffic
assignment problem, denoted as I-TAPα, is given by: |s|[2]<b> fh^I_α(x) :=
αh^SO(x) + (1-α) h^UE(x), (1)-(1).

A few comments are in order. First, it is clear that I-TAP0 and I-TAP1
correspond to UE-TAP and SO-TAP, respectively. Next, under the assumption that
the travel time functions are strictly convex, we observe that for any
$\alpha\in[0,1]$ the program I-TAPα has a strictly convex objective with
linear constraints, and so I-TAPα is a convex optimization problem with a
unique edge flow solution $\mathbf{x}(\alpha)$.

For numerical implementation purposes, we propose a _dense sampling_ procedure
to compute a solution for $\beta$-SO with a low total travel time while
guaranteeing a $\beta$ bound on unfairness.

#### Algorithm for Computation of Optimal Interpolation Parameter

To compute a good solution for $\beta$-SO, we evaluate the optimal solution
$\mathbf{f}(\alpha)$ of I-TAPα (with corresponding edge flows
$\mathbf{x}(\alpha)$) for $\alpha$ taken from a finite set
$\mathcal{A}_{s}:=\\{0,s,2s,\ldots,1\\}$ for some step size $s\in(0,1)$. That
is, in $O(\frac{1}{s})$ computations of I-TAP, we can return the path flow
$\mathbf{f}(\alpha^{*})$ (with unique edge decomposition
$\mathbf{x}(\alpha^{*})$), for some $\alpha^{*}\in\mathcal{A}_{s}$, with the
lowest total travel time that is at most $\beta$-unfair, i.e.,
$U(\mathbf{f}(\alpha^{*}))\leq\beta$, and the value
$h^{SO}(\mathbf{x}(\alpha^{*}))$ is minimized.

We observe experimentally (Section 6.2) that this method of computing the
I-TAP solution for a finite set of convex combination parameters achieves a
good solution for $\beta$-SO in terms of fairness and total travel time. We
note here that our approach also naturally extends to other unfairness notions
wherein the user equilibrium achieves the highest possible level of fairness,
while the system optimum achieves the lowest total travel times (see Appendix
B). Finally, we restrict $\alpha$ to lie in the finite set $\mathcal{A}_{s}$
since the exact functional form of the optimal solution $\mathbf{f}(\alpha)$
(with edge flow $\mathbf{x}(\alpha)$), and thus the unfairness
$U(\mathbf{f}(\alpha))$ and the total travel time $h^{SO}(\mathbf{f}(\alpha))$
functions, in $\alpha$ is not directly known, though we show that
$\mathbf{x}(\alpha)$ and $h^{SO}(\mathbf{x}(\alpha))$ are continuous in
$\alpha$ in Section 4.5.

We also test (Section 6) an alternative approach to I-TAP, which instead of
taking a convex combination of the SO-TAP and UE-TAP objectives, interpolates
between their solutions. That is, we first compute the optimal solutions of
UE-TAP ($\mathbf{x}^{UE}$) and SO-TAP ($\mathbf{x}^{SO}$), and return the
value $(1-\gamma)\mathbf{x}^{UE}+\gamma\mathbf{x}^{SO}$ for $\gamma\in[0,1]$.
While this Interpolated Solution (I-Solution) method only requires two traffic
assignment computations as compared to $O(\frac{1}{s})$ computations of the
I-TAP method, it leads to poor performance in comparison with the I-TAP method
(see Section 6) and does not induce a natural marginal-cost pricing scheme, as
I-TAP does (see Section 5). Thus, we focus our attention on I-TAP for this and
the next sections.

###  4.2 Solution Efficiency and Fairness of I-TAP

In this section, we study the influence of the convex combination parameter
$\alpha$ of I-TAP on the efficiency and fairness of the optimal solution
$\mathbf{f}(\alpha)$ (and edge flow $\mathbf{x}(\alpha)$). In particular, we
characterize (i) an upper bound on the inefficiency ratio as we vary $\alpha$,
and (ii) a range of values of $\alpha$ that are guaranteed to achieve a
specified level of unfairness $\beta$ for any optimal solution
$\mathbf{f}(\alpha)$.

We first evaluate the performance of I-TAP by establishing an upper bound on
the inefficiency ratio as a function of $\alpha$. Theorem 1 shows that the
upper bound of the inefficiency ratio $\rho(\mathbf{x}(\alpha))$ of the
optimal traffic assignment of I-TAPα is the minimum between two terms: (i) the
Price of Anarchy (PoA) $\bar{\rho}$, and (ii) a more elaborate bound that is
monotonically non-increasing in $\alpha$.

######  Theorem 1 (I-TAP Solution Efficiency).

For any $\alpha\in(0,1)$, let $\mathbf{x}(\alpha)$ be the optimal solution to
I-TAPα. Then, the inefficiency ratio

$\rho(\mathbf{x}(\alpha))\\!\leq\\!\min\\!\left\\{\bar{\rho},1\\!+\\!\frac{1-\alpha}{\alpha}\\!\cdot\\!\frac{h^{UE}(\mathbf{x}(1))\\!-\\!h^{UE}(\mathbf{x}(0))}{h^{SO}(\mathbf{x}(1))}\right\\}.$

###### Proof.

To prove this result, we show that (i)
$\rho(\mathbf{x}(\alpha))\leq\bar{\rho}$ and (ii)
$\rho(\mathbf{x}(\alpha))\leq
1+\frac{1-\alpha}{\alpha}\frac{h^{UE}(\mathbf{x}(1))-h^{UE}(\mathbf{x}(0))}{h^{SO}(\mathbf{x}(1))}$.

We first prove (i) by establishing that $h^{SO}(\mathbf{x}(\alpha))\leq
h^{SO}(\mathbf{x}(0))$ for all $\alpha\in[0,1]$. Since $\mathbf{x}(\alpha)$ is
the optimal solution to I-TAPα

$\displaystyle h^{I_{\alpha}}(\mathbf{x}(\alpha))$ $\displaystyle=\alpha
h^{SO}(\mathbf{x}(\alpha))+(1-\alpha)h^{UE}(\mathbf{x}(\alpha))$
$\displaystyle\leq h^{I_{\alpha}}(\mathbf{x}(0))$ $\displaystyle=\alpha
h^{SO}(\mathbf{x}(0))+(1-\alpha)h^{UE}(\mathbf{x}(0)).$

Next from the UE-TAP objective, it is the case that

$h^{UE}(\mathbf{x}(0))\leq h^{UE}(\mathbf{x}(\alpha)).$

From these two inequalities, it follows that $h^{SO}(\mathbf{x}(\alpha))\leq
h^{SO}(\mathbf{x}(0))$ for all $\alpha\in[0,1]$. Dividing both sides of the
inequality by the minimum possible system travel time $h^{SO}(\mathbf{x}(1))$
establishes that the inefficiency ratio
$\rho(\mathbf{x}(\alpha))\leq\bar{\rho}$ proving claim (i).

Now, to prove claim (ii), we note that $h^{I_{\alpha}}(\mathbf{x}(\alpha))\leq
h^{I_{\alpha}}(\mathbf{x}(1))$ since $\mathbf{x}(\alpha)$ is an optimal
solution to I-TAPα. It thus follows that

$\displaystyle\alpha
h^{SO}(\mathbf{x}(\alpha))+(1-\alpha)h^{UE}(\mathbf{x}(\alpha))\leq\alpha
h^{SO}(\mathbf{x}(1))+(1-\alpha)h^{UE}(\mathbf{x}(1)).$

Dividing this expression by $\alpha h^{SO}(\mathbf{x}(1))$ and rearranging
gives us that

$\displaystyle\frac{h^{SO}(\mathbf{x}(\alpha))}{h^{SO}(\mathbf{x}(1))}$
$\displaystyle\leq
1+\frac{1-\alpha}{\alpha}\cdot\frac{h^{UE}(\mathbf{x}(1))-h^{UE}(\mathbf{x}(\alpha))}{h^{SO}(\mathbf{x}(1))}$
$\displaystyle\leq
1+\frac{1-\alpha}{\alpha}\cdot\frac{h^{UE}(\mathbf{x}(1))-h^{UE}(\mathbf{x}(0))}{h^{SO}(\mathbf{x}(1))},$

where the second inequality follows from the fact that
$h^{UE}(\mathbf{x}(0))\leq h^{UE}(\mathbf{x}(\alpha))$ for any
$\alpha\in[0,1]$. This proves claim (ii). ∎

Theorem 1 establishes that, even in the worst case, the ratio between the
total travel time of the edge flow $\mathbf{x}(\alpha)$ of I-TAPα and that of
the system optimal solution is at most the PoA. This result is not guaranteed
to hold for other state-of-the-art CSO algorithms, which may output traffic
assignments with much larger total travel times than the UE solution. For
instance, in Section 6 we show through numerical experiments that the
algorithm proposed by Jahn et al. [25] achieves total travel times much higher
than that of the user equilibrium solution for certain ranges of unfairness.
Further, Theorem 1 shows that the upper bound on the inefficiency ratio
becomes closer to one as the objective $h^{I_{\alpha}}$ gets closer to
$h^{SO}$.

The bound on the inefficiency ratio obtained from Theorem 1 is depicted in
Figure 2. Note that in order to obtain the value of the convex combination
parameter $\alpha^{*}$ at which the two upper bounds on the inefficiency ratio
are equal we need to impose the constraint
$\bar{\rho}=\frac{1-\alpha^{*}}{\alpha^{*}}\cdot\frac{h^{UE}(\mathbf{x}(1))-h^{UE}(\mathbf{x}(0))}{h^{SO}(\mathbf{x}(1))}$,
which yields that
$\alpha^{*}=\frac{h^{UE}(\mathbf{x}(1))-h^{UE}(\mathbf{x}(0))}{h^{SO}(\mathbf{x}(0))+h^{UE}(\mathbf{x}(1))-h^{UE}(\mathbf{x}(0))}$.

Figure 2: Upper bound on the inefficiency ratio of the optimal solution
$\mathbf{x}(\alpha)$ of the problem I-TAPα for $\alpha\in[0,1]$

Having established a worst case performance guarantee for I-TAP in terms of
the inefficiency ratio, we now establish a range of values of $\alpha$ at
which any optimal solution $\mathbf{f}(\alpha)$ of I-TAPα is guaranteed to
attain a $\beta$ bound on unfairness. In particular, we specialize the
following result to polynomial travel time functions, e.g., the commonly used
BPR function [38].

######  Theorem 2 (Feasibility of I-TAP for $\beta$-SO).

Suppose that the largest degree of the polynomial travel time functions
$t_{e}(x_{e})$ is $m$ for some $e\in E$. Then, the unfairness of any optimal
solution $\mathbf{f}(\alpha)$ of I-TAPα is upper bounded by $\beta$, i.e.,
$U(\mathbf{f}(\alpha))\leq\beta$, for any $\alpha\leq\frac{\beta-1}{m}$.

The proof of Theorem 2 leverages the fact that at an equilibrium flow, under a
given vector of tolls, the travel cost on all positive paths is equal for all
users in any commodity $k$, as was established in [9, Lemma 2]. We provide a
proof of this claim here for completeness.

######  Lemma 1 (Equality of Travel Costs on Positive Paths [9]).

Let the cost on an edge be given by
$c_{e}(x_{e},\tau_{e})=t_{e}(x_{e})+\tau_{e}$, where the value-of-time $v$ of
users is normalized to one. Then, under any equilibrium flow induced by the
edge tolls $\bm{\tau}$, the total travel cost of any two positive paths $P,Q$
are equal, i.e., $\sum_{e\in P}c_{e}(x_{e},\alpha)=\sum_{e\in
Q}c_{e}(x_{e},\alpha)$.

###### Proof.

To prove this claim, we consider a network with travel time functions
$c_{e}(x_{e},\tau_{e})=t_{e}(x_{e})+\tau_{e}$ for all $e\in E$, which is valid
since the travel time function is polynomial and so $c_{e}(x_{e},\tau_{e})$ is
still differentiable, convex and monotonically increasing in $x_{e}$. Next,
the equilibrium solution under a vector of tolls $\bm{\tau}$ is given by the
UE-TAP with objective $\sum_{e\in
E}\int_{0}^{x_{e}}c_{e}(y,\alpha)\mathrm{d}y$, where
$c_{e}(x_{e},\tau_{e})=t_{e}(x_{e})+\tau_{e}$. By the first order necessary
and sufficient conditions of this UE-TAP, for any two positive flow paths
$P,Q$ between the same O-D pair $k$, it holds that $\sum_{e\in
P}c_{e}(x_{e},\alpha)=\sum_{e\in Q}c_{e}(x_{e},\alpha)=\mu_{k}$ for some
$\mu_{k}$. We now show that any positive path $R$ between the same O-D pair
that is not a path with positive flow, i.e., $\mathbf{x}_{R}=0$, also has the
same travel cost as any path $P$ with positive flow, i.e., $\sum_{e\in
R}c_{e}(x_{e},\alpha)=\sum_{e\in P}c_{e}(x_{e},\alpha)=\mu_{k}$.

Suppose by contradiction that there is a path $R$ for a commodity $k$ whose
travel cost is not equal to $\mu_{k}$. From the equilibrium condition of UE-
TAP it must hold that $\sum_{e\in R}c_{e}(x_{e},\tau_{e})>\mu_{k}$. Next, let
$e_{1},\ldots,e_{r}$ denote the edges in path $R$ in the order of traversal,
and for each edge $e_{i}\in R$, consider a path used by commodity $k$ using
that edge, i.e., a path $P_{i}=R_{i}^{s}-e_{i}-R_{i}^{t}$ where $R_{i}^{s}$ is
the component of that path preceding edge $e_{i}$ and $R_{i}^{t}$ is the
component of that path following edge $e_{i}$. Observe that the sum of the
costs of these used paths $P_{i}$ is given by $\sum_{i=1}^{r}\sum_{e\in
P_{i}}c_{e}(x_{e},\tau_{e})=r\mu_{k}$. Next, considering the paths
$P_{1}^{\prime},\ldots,P_{r-1}^{\prime}$, where
$P_{1}^{\prime}=R_{i+1}^{s}-R_{i}^{t}$, we obtain that

$\displaystyle r\mu_{k}=\sum_{i=1}^{r}\sum_{e\in
P_{i}}c_{e}(x_{e},\tau_{e})=\sum_{i=1}^{r-1}\sum_{e\in
P_{i}^{\prime}}c_{e}(x_{e},\tau_{e})+\sum_{e\in R}c_{e}(x_{e},\tau_{e}).$

Since it holds from the KKT conditions of UE-TAP that $\sum_{e\in
P_{i}^{\prime}}c_{e}(x_{e},\tau_{e})\geq\mu_{k}$ for each
$i\in\\{1,\ldots,r-1\\}$, the above equality implies that $\sum_{e\in
R}c_{e}(x_{e},\tau_{e})\leq\mu_{k}$, a contradiction. Thus, we must have that
the total cost on all positive paths is exactly equal to $\mu_{k}$, thereby
proving our claim. ∎

We now leverage Lemma 1 to complete the proof of Theorem 2.

###### Proof.

Without loss of generality, we normalize the value of time $v$ to $1$ and for
notational simplicity denote $x_{e}=x_{e}(\alpha)$ and
$\mathbf{f}=\mathbf{f}(\alpha)$. We now establish this result in two steps.
First, we show that if $c_{e}(x_{e},\alpha)=t_{e}(x_{e})+\alpha
x_{e}t_{e}^{\prime}(x_{e})\in[t_{e}(x_{e}),\beta t_{e}(x_{e})]$ for all edges
$e$ then the unfairness satisfies $U(\mathbf{f})\leq\beta$. Next, we show for
$\alpha\leq\frac{\beta-1}{m}$ that the cost satisfies
$c_{e}(x_{e},\alpha)\in[t_{e}(x_{e}),\beta t_{e}(x_{e})]$, which, together
with the first claim, implies the result.

To prove the first claim, we consider a network with travel time functions
$c_{e}(x_{e},\alpha)$ for all $e\in E$, which is valid since the travel time
function is polynomial and so $c_{e}(x_{e},\alpha)$ is still differentiable,
convex and monotonically increasing in $x_{e}$. Next, from Lemma 1 it holds
that the total cost on any two positive paths $P$ and $Q$ are also equal,
i.e., $\sum_{e\in P}c_{e}(x_{e},\alpha)=\sum_{e\in Q}c_{e}(x_{e},\alpha)$
since at an equilibrium flow the cost of any two used paths are equal. This
result implies for any commodity $k$ and any two positive paths $P,Q$ that

$\displaystyle\sum_{e\in P}t_{e}(x_{e})$ $\displaystyle\leq\sum_{e\in
P}c_{e}(x_{e},\alpha)=\sum_{e\in Q}c_{e}(x_{e},\alpha)$
$\displaystyle\leq\beta\sum_{e\in Q}t_{e}(x_{e}),$

i.e., the ratio of the travel times on positive paths can never exceed
$\beta$. Thus, $U(\mathbf{f})\leq\beta$.

Next, to prove the second claim, we note that since the travel time function
is a polynomial function of degree $m$, we can let
$t_{e}\left(x_{e}\right)=\sum_{i=0}^{m}\gamma_{i}x_{e}^{i}$. Then, we have:

$\displaystyle x_{e}t_{e}^{\prime}\left(x_{e}\right)$
$\displaystyle=x_{e}\sum_{i=1}^{m}i\gamma_{i}x_{e}^{i-1}=\sum_{i=1}^{m}i\gamma_{i}x_{e}^{i}$
$\displaystyle\leq m\sum_{i=1}^{m}\gamma_{i}x_{e}^{i}\leq
m\sum_{i=0}^{m}\gamma_{i}x_{e}^{i}$ $\displaystyle=mt_{e}\left(x_{e}\right).$

Note that we used the fact that $\gamma_{0}\geq 0$ in the second inequality,
which follows since $t_{e}(x_{e})\geq 0$ for all $x_{e}\in\mathbb{R}_{\geq
0}$. From the above inequalities, we note that $\alpha
x_{e}t_{e}^{\prime}(x_{e})\leq\alpha mt_{e}\left(x_{e}\right)$. Now, if we set
$\alpha mt_{e}\left(x_{e}\right)\leq(\beta-1)t_{e}(x_{e})$, then we have for
any $\alpha\leq\frac{\beta-1}{m}$ that the cost
$c_{e}(x_{e},\alpha)\in[t_{e}(x_{e}),\beta t_{e}(x_{e})]$ and thus the
resulting flow $\mathbf{f}$ has an unfairness of at most $\beta$. ∎

Theorem 2 establishes a relation between the convex combination parameter
$\alpha$ and the level of unfairness of any optimal path flow
$\mathbf{f}(\alpha)$ when the edge travel-time functions are polynomial.

We can further show that the bound obtained in Theorem 2 is in fact tight by
demonstrating an instance such that for any $\alpha>\frac{\beta-1}{m}$ the
unfairness of the solution $\mathbf{f}(\alpha)$ of I-TAPα is strictly greater
than $\beta$.

######  Lemma 2 (Tightness of Unfairness Bound).

Suppose $\mathbf{f}(\alpha)$ is an optimal solution to I-TAPα for any
$\alpha\in[0,1]$. Then, there exists a two-edge parallel network with
polynomial travel time functions of degree at most $m$ such that for any
$\alpha>\frac{\beta-1}{m}$, the unfairness $U(\mathbf{f}(\alpha))>\beta$.

###### Proof.

Consider a demand of one in a two edge Pigou network, with two nodes—an origin
and a destination node—connected by two parallel edges $e_{1}$ and $e_{2}$.
For edge $e_{1}$, let $t_{1}(x_{1})=1+\epsilon x$ for some small $\epsilon>0$,
and let $t_{2}(x_{2})=x_{2}^{m}$ for some $m\in\mathbb{N}$. Then, the first
order necessary and sufficient KKT conditions of I-TAPα for any
$\alpha\in[0,1]$ imply that

$\displaystyle t_{2}(x_{2})+\alpha
x_{2}t_{2}^{\prime}(x_{2})=t_{1}(x_{1})+\alpha x_{1}t_{1}^{\prime}(x_{1}).$

Substituting $t_{2}(x_{2})=x_{2}^{m}$ and $t_{1}(x_{1})=1+\epsilon x_{1}$
gives the following ratio between the travel times on the two links:

$\displaystyle\frac{t_{1}(x_{1})}{t_{2}(x_{2})}=\frac{1+\epsilon
x_{1}}{x_{2}^{m}}-\frac{\alpha\epsilon
x_{1}}{x_{2}^{m}}=1+m\alpha-\frac{\alpha\epsilon x_{1}}{x_{2}^{m}}.$

By the unfairness constraint that
$\frac{t_{1}(x_{1})}{t_{2}(x_{2})}\leq\beta$, it follows that if
$\alpha>\frac{\beta-1}{m}$, then

$\displaystyle\frac{t_{1}(x_{1})}{t_{2}(x_{2})}=1+m\alpha-\frac{\alpha\epsilon
x_{1}}{x_{2}^{m}}>1+m\frac{\beta-1}{m}-\frac{\alpha\epsilon
x_{1}}{x_{2}^{m}}=\beta-\frac{\alpha\epsilon x_{1}}{x_{2}^{m}}.$

Taking $\epsilon\rightarrow 0$, we have that
$\frac{t_{1}(x_{1})}{t_{2}(x_{2})}\geq\beta$ for any
$\alpha>\frac{\beta-1}{m}$. Thus, the unfairness of the optimal flow
$\mathbf{f}(\alpha)$, which is identical to the edge flow $\mathbf{x}(\alpha)$
in a parallel network setting, is at least $\beta$.∎

Together, Theorem 2 and Lemma 2 imply that a $\beta$ level of unfairness can
be guaranteed using I-TAP on all traffic networks only when
$\alpha\leq\frac{\beta-1}{m}$, where $m$ is the maximum degree of the
polynomial corresponding to the travel time functions for each edge $e\in E$.

###  4.3 Optimality of I-TAP

In this section, we show that I-TAP exactly computes the minimum total travel
time solution for any desired level of unfairness $\beta$ in any two edge
Pigou network. That is, there is some convex combination parameter
$\alpha^{*}$ for which the solution of I-TAP${}_{\alpha^{*}}$ is also a
solution to the $\beta$-SO problem for any two edge Pigou network.

######  Lemma 3 (Optimality of I-TAP).

Consider a two edge Pigou network where the optimal solution of the $\beta$-SO
problem is $\mathbf{x}_{\beta}^{*}$ for any $\beta\in[1,\infty)$. Then, there
exists a convex combination parameter $\alpha^{*}$ such that
$\mathbf{x}(\alpha^{*})=\mathbf{x}_{\beta}^{*}$, i.e., the solution of
I-TAP${}_{\alpha^{*}}$ and the optimal solution of the $\beta$-SO problem
coincide.

For a proof of Lemma 3, see Appendix A. We mention that Lemma 3 compares only
the edge flows of I-TAP and $\beta$-SO since the path and edge flows coincide
for a two edge Pigou network. We also note that while the optimality for a
Pigou network may appear restrictive, such networks are of both theoretical
[30, 34] and practical significance [13].

###  4.4 Computational Tractability of I-TAP

Having established that we can solve I-TAP to obtain an approximate solution
to $\beta$-SO, we now establish that I-TAP can be computed efficiently due to
its equivalence to a parametric UE-TAP program.

######  Observation 1 (UE Equivalency of I-TAP).

For any $\alpha\in[0,1]$, I-TAPα reduces to UE-TAP with objective function
$\sum_{e\in E}\int_{0}^{x_{e}}c_{e}(y,\alpha)\mathrm{d}y$, where
$c_{e}(y,\alpha)=t_{e}(y)+\alpha yt_{e}^{\prime}(y)$.

To see Observation 1, note that by the fundamental theorem of calculus,
$h^{SO}(\mathbf{x})$ can be written as

$h^{SO}(\mathbf{x})=\sum_{e\in E}x_{e}t_{e}(x_{e})=\sum_{e\in
E}\int_{0}^{x_{e}}t_{e}(y)+yt_{e}^{\prime}(y)\mathrm{d}y.$

Then, taking a convex combination of the SO-TAP and UE-TAP objectives, it is
clear that

$h^{I_{\alpha}}(\mathbf{x})=\sum_{e\in E}\int_{0}^{x_{e}}t_{e}(y)+\alpha
yt_{e}^{\prime}(y)\mathrm{d}y.$

Note that for each $\alpha\in[0,1]$, the differentiability, monotonicity, and
convexity of many typical travel time functions $t_{e}$, e.g., any polynomial
function such as the BPR function [38], imply that the corresponding
properties hold for the cost functions $c_{e}(x_{e},\alpha)$ in $x_{e}$. For
numerical implementation, the equivalency of I-TAPα and UE-TAP implies that
I-TAPα inherits the useful property that the linearization step of the Frank-
Wolfe algorithm [38], when applied to I-TAPα, corresponds to solving multiple
unconstrained shortest path queries. The latter motivates the highly efficient
approach which we employ in Section 6 to solve I-TAPα.

###  4.5 Sensitivity Analysis of I-TAP

To obtain a solution that is simultaneously of low cost while keeping within a
$\beta$ bound of unfairness, it is instructive to study the sensitivity of the
optimal edge flow solution $\mathbf{x}(\alpha)$ of I-TAPα in the convex
combination parameter $\alpha$. Specifically, performing such a sensitivity
analysis is important since it allows us to characterize the continuity of the
SO-TAP objective $h^{SO}(\mathbf{x}(\alpha))$, which we are looking to
minimize in the $\beta$-SO problem. In this section, we leverage the
equivalency of I-TAP and UE-TAP to establish continuity properties of the
optimal edge flow solution $\mathbf{x}(\alpha)$ of I-TAPα and the SO-TAP
objective $h^{SO}(\mathbf{x}(\alpha))$.

We first establish the Lipschitz continuity of the optimal edge flow solution
$\mathbf{x}(\alpha)$ of I-TAPα in the convex combination parameter $\alpha$.
This result follows from the UE-TAP reformulation of I-TAP as in Observation 1
and a direct application of the Lipschitz continuity of the optimal solution
of a parametric UE-TAP [39, Theorem 8.6a].

######  Corollary 1.

(Lipschitz Continuity of $\mathbf{x}(\alpha)$) For any $\alpha\in(0,1)$, the
edge flow solution $\mathbf{x}(\alpha)$ of the problem I-TAPα is Lipschitz
continuous in $\alpha$.

Corollary 1 implies a desirable property that small changes in $\alpha$ will
only result in small changes in the optimal edge flows of I-TAPα. We now use
Corollary 2 to establish the Lipschitz continuity of the SO-TAP objective.

######  Corollary 2.

(Lipschitz Continuity of $h^{SO}$) For any $\alpha\in(0,1)$, let
$\mathbf{x}(\alpha)$ be the optimal edge flow solution to I-TAPα. Then,
$h^{SO}(\mathbf{x}(\alpha))$ is Lipschitz continuous in $\alpha$.

###### Proof.

We prove the Lipschitz continuity of $h^{SO}(\mathbf{x}(\alpha))$ in $\alpha$
through the observation that the composition of Lipschitz continuous functions
is Lipschitz continuous. First, observe that $\mathbf{x}(\alpha)$ is Lipschitz
continuous by Corollary 1. Next, the SO-TAP objective
$h^{SO}(\mathbf{x})=\sum_{e\in E}x_{e}t_{e}(x_{e})$ is continuous in its
argument $\mathbf{x}$. Furthermore, $h^{SO}(\mathbf{x})$ is locally Lipschitz
over a bounded set since the SO-TAP has a finite derivative as long as
$\mathbf{x}$ is bounded. Since both $h^{SO}(\mathbf{x})$ and
$\mathbf{x}(\alpha)$ are Lipschitz continuous, it follows that
$h^{SO}(\mathbf{x}(\alpha))$ is Lipschitz continuous. ∎

While Corollary 2 establishes the continuity of $h^{SO}(\mathbf{x}(\alpha))$
in $\alpha$, this relation is not necessarily monotone, which we show through
numerical experiments in Section 6. We also note that, unlike the SO-TAP
objective, the unfairness function $U(\mathbf{f}(\alpha))$ is discontinuous in
$\alpha$. Its discontinuity stems from the fact that the optimal solutions
$\mathbf{f}(\alpha_{1})$ and $\mathbf{f}(\alpha_{2})$ for convex combination
parameters $\alpha_{1}$ and $\alpha_{2}$ that are arbitrarily close may not
have the same set of positive paths. In particular, it may happen for some
convex combination parameter $\alpha_{1}$ that path $P$ is a positive path,
but for some $\epsilon>0$ and for any $\alpha_{2}$ such that
$||\alpha_{1}-\alpha_{2}||_{2}\leq\epsilon$ we have that $P$ is not a positive
path. Since the travel time on path $P$ could be very different from the
travel times on other paths, the unfairness function is in general
discontinuous in $\alpha$, which we validate through experiments in Section 6.

##  5 Pricing to Implement Flows

In the previous section we presented a method for computing a solution to
$\beta$-SO that keeps within a $\beta$ bound of unfairness and strives to
minimize the total travel time. In this section, we leverage the structure of
I-TAP to develop pricing mechanisms to collectively enforce the I-TAP solution
in the presence of selfish users that independently choose routes to minimize
their own travel costs. That is, the prices are set such that the travel cost
for users in the same commodity is equivalent, ensuring the formation of an
equilibrium. We first consider the case of homogeneous users and show that
I-TAP results in a natural marginal-cost pricing scheme. Then, we leverage a
linear programming methodology of [20] to set road prices to enforce the flows
computed through the I-TAP method for the setting of heterogeneous users.

In this section, for the ease of exposition, we focus our discussion on
inducing the optimal edge flow $\mathbf{x}(\alpha)$ of I-TAPα. We mention that
our approach can naturally be extended to enforcing optimal path flows
$\mathbf{f}(\alpha)$ that satisfy a given level of unfairness. In particular,
we can consider a setting wherein users are recommended to use a specified
path set, e.g., by traffic navigational applications, as given by
$\mathbf{f}(\alpha)$ and the tolls set are such that no user will have an
incentive to deviate from their recommended paths. Finally, we also mention by
the result of Theorem 2 that focusing on the edge flow solution
$\mathbf{x}(\alpha)$ is without loss of generality for certain ranges of
$\alpha$ since the unfairness bound for any optimal path flow solution
$\mathbf{f}(\alpha)$ is guaranteed to be satisfied.

###  5.1 Homogeneous Pricing via Marginal Cost

In the setting where all users have the same value of time $v$, the structure
of I-TAPα yields an interpolated variant of marginal-cost pricing to induce
selfish users to collectively form the optimal edge flow $\mathbf{x}(\alpha)$
of I-TAPα. This result is a direct consequence of the equivalence between
I-TAP and UE-TAP from Observation 1.

######  Lemma 4 (Prices to Implement Flows).

Suppose that the edge flow $\mathbf{x}(\alpha)$ is a solution to I-TAPα for
some $\alpha\in[0,1]$. Then $\mathbf{x}(\alpha)$ can be enforced as a UE by
setting the prices as $\tau_{e}=\alpha
x_{e}(\alpha)t_{e}^{\prime}(x_{e}(\alpha))$ for each $e\in E$.

###### Proof.

Without loss of generality, normalize $v$ to 1 and for notational convenience,
denote $x_{e}=x_{e}(\alpha)$. To prove this result, note from Observation 1
that I-TAPα is equivalent to UE-TAP with objective $\sum_{e\in
E}\int_{0}^{x_{e}}t_{e}(y)+\alpha yt_{e}^{\prime}(y)\mathrm{d}y$. From the
first-order necessary and sufficient KKT conditions [38] of this UE-TAP, for
any two paths $P,Q\in\mathcal{P}_{k}$ with positive flow for a commodity $k\in
K$, it must be that $\sum_{e\in P}\left(t_{e}(x_{e})+\alpha
x_{e}t_{e}^{\prime}(x_{e})\right)=\sum_{e\in Q}\left(t_{e}(x_{e})+\alpha
x_{e}t_{e}^{\prime}(x_{e})\right)$. Thus, if the prices on each edge are set
as $\tau_{e}=\alpha x_{e}t_{e}^{\prime}(x_{e})$, then all users in each
commodity incur the same travel cost when using any two paths
$P,Q\in\mathcal{P}_{k}$, establishing that $\mathbf{x}$ is a UE. ∎

Note from Lemma 4 that the edge prices are equal to $\alpha$ multiplied by the
marginal cost of users on the edges. For this pricing scheme, Lemma 4
guarantees that selfish users will be induced to collectively form the
solutions satisfying a specified bound on unfairness obtained through the
I-TAP method.

######  Remark 1.

We note that road tolling is not the only mechanism that can be used to induce
selfish users to collectively form the flows computed through I-TAP. One of
the notable mechanisms beyond road tolling to enforce the SO solution as a UE
is that of tradable credit schemes, wherein users can trade initially issued
credits freely in a competitive market and spend these credits to use roads
with predetermined credit charges [45]. As with the marginal cost pricing
scheme in Lemma 4, the equivalence between I-TAP and UE-TAP for any
$\alpha\in[0,1]$ enables us to derive a tradable credit scheme. In particular,
following a similar line of reasoning to that used by Yang and Wang [45,
Proposition 5], it can be shown that the optimal edge flow
$\mathbf{x}(\alpha)$ of I-TAPα for any $\alpha\in[0,1]$ can be enforced as a
user equilibrium through a tradable credit scheme.

###  5.2 Heterogeneous Pricing via Dual Multipliers

The pricing mechanism in Section 5.1 is inapplicable to the heterogeneous user
setting as it would require unrealistically imposing different prices for
users with different values of time for the same edges. In this section, we
consider heterogeneous users and leverage a linear-programming method [20] to
provide a necessary and sufficient condition to induce selfish users to
collectively form the edge flow $\mathbf{x}(\alpha)$. We further establish
that $\mathbf{x}(\alpha)$ satisfies this condition for each $\alpha\in[0,1]$.
That is, appropriate tolls can be placed on the roads of the network to induce
heterogeneous selfish users to collectively form the equilibrium edge flow
$\mathbf{x}(\alpha)$.

Before presenting the pricing scheme, we first extend the notion of a
commodity to a heterogeneous user setting. In particular, each user belongs to
a commodity $k\in K$ when making a trip on a set of paths $\mathcal{P}_{k}$
between the same O-D pair and has the value of time $v_{k}>0$. Then, under a
vector of edge prices $\bm{\tau}=\\{\tau_{e}\\}_{e\in E}$ the travel cost that
users in commodity $k$ incur on a given path $P\in\mathcal{P}_{k}$ under the
traffic assignment $\mathbf{x}$ is given by
$C_{P}(\mathbf{x},\bm{\tau})=\sum_{e\in
P}\left(v_{k}t_{e}(x_{e})+\tau_{e}\right)$. Note that more than one commodity
may make trips between the same O-D pair, and a user equilibrium forms when
the travel cost for all users in a particular commodity is equal. We further
note that we maintain the unfairness notion presented in the work thus far
even for heterogeneous users. That is, irrespective of the value of time of
two users travelling between the same O-D pair, the maximum possible ratio
between their travel times can be no more than $\beta$.

We now leverage the following result to provide a necessary and sufficient
condition that the optimal edge flow $\mathbf{x}(\alpha)$ of I-TAPα for any
$\alpha\in[0,1]$ must satisfy for it to be enforceable as a UE through road
pricing.

######  Lemma 5.

(Condition for Flow Enforceability [20, Theorem 3.1]) Suppose that the flow
$\mathbf{x}$ satisfies the feasibility Constraints (1)-(1). Further, consider
the linear program with the variables $d_{P}^{k}$, which represents the flow
of commodity $k$ routed on path $P\in\mathcal{P}_{k}$, where $\mathcal{P}_{k}$
denotes the set of all possible paths for commodity $k$: |s|[2] d_P^k, ∀P
∈P_k, ∀k ∈K ∑_k ∈K v_k ∑_P ∈P_k t_P(x) d_P^k, ∑_P ∈P_k d_P^k= d_k, ∀k ∈K,
d_P^k ≥0, ∀P ∈P_k, k ∈K, ∑_k ∈K ∑_P ∈P_k: e ∈P d_P^k ≤x_e, ∀e ∈E, with demand
Constraints (5), non-negativity Constraints (5) and capacity Constraints (5).
Then $\mathbf{x}$ can be enforced as a user equilibrium if and only if
Constraint (5) is met with equality for each edge $e\in E$ at the optimal
solution of the linear Program (5)-(5).

In particular, if $\mathbf{x}(\alpha)$ satisfies the above necessary and
sufficient condition then it can be enforced as a user equilibrium through
edge prices set based on the dual variables of the capacity constraints of the
above linear program. We now show that $\mathbf{x}(\alpha)$ satisfies the
necessary and sufficient condition in Lemma 5.

######  Lemma 6.

[Heterogeneous User Flow Enforceability] Suppose that the edge flow
$\mathbf{x}(\alpha)$ is a solution for I-TAPα for some $\alpha\in[0,1]$. Then
for the heterogeneous user setting, $\mathbf{x}(\alpha)$ can be enforced as a
user equilibrium.

###### Proof.

To prove this result, from Lemma 5 it suffices to show that Constraints (5)
are met with equality at the optimal solution of the linear Program (5)-(5)
for the flow $\mathbf{x}(\alpha)$. We now suppose by contradiction that the
optimal solution $\tilde{\mathbf{x}}$ to the linear Program (5)-(5) for the
edge flow $\mathbf{x}(\alpha)$ is such that for at least one edge $e^{*}\in E$
the Constraint (5) is met with a strict inequality, i.e.,
$\tilde{x}_{e^{*}}<x_{e^{*}}(\alpha)$. Since the flow $\tilde{\mathbf{x}}$ is
optimal for this linear program it follows that $\tilde{\mathbf{x}}_{P}\geq 0$
for all paths $P\in\mathcal{P}_{k}$ for all commodities $k\in K$, and that
$\sum_{P\in\mathcal{P}_{k}}\tilde{\mathbf{x}}_{P}=d_{k}$ for each commodity
$k\in K$ by the constraints of the linear program. Note here that the demand
constraints satisfy $\sum_{P\in\mathcal{P}_{k}}\tilde{\mathbf{x}}_{P}=d_{k}$
and the non-negativity constraints $\tilde{\mathbf{x}}_{P}\geq 0$ imply that
the corresponding demand and non-negativity constraints for I-TAPα are also
satisfied for the flow $\tilde{\mathbf{x}}$. By the edge decomposition of path
flows it must further hold that $\sum_{k\in K}\sum_{P\in\mathcal{P}_{k}:e\in
P}\tilde{\mathbf{x}}_{P}=\tilde{x}_{e}$. Thus, we observe that the flow
$\tilde{\mathbf{x}}$ is a feasible solution to I-TAPα.

Next, from the capacity constraint of the linear program it follows that for
each $e\in E$ that $\tilde{x}_{e}\leq x_{e}(\alpha)$ and that for at least one
edge $e^{*}$ that $\tilde{x}_{e^{*}}<x_{e^{*}}(\alpha)$ by assumption. Then,
by the monotonicity of the I-TAPα objective in the edge flows, we observe that
$h^{I_{\alpha}}(\tilde{\mathbf{x}})<h^{I_{\alpha}}(\mathbf{x}(\alpha))$,
implying that $\mathbf{x}(\alpha)$ is not an optimal solution to I-TAPα, a
contradiction. Thus, the flow $\tilde{\mathbf{x}}$ cannot exist, proving our
claim that any optimal solution to the Program (5)-(5) for the edge flow
$\mathbf{x}(\alpha)$ must meet the capacity constraint with equality. ∎

Lemma 6 implies that even when users are heterogeneous the edge flow
$\mathbf{x}(\alpha)$ can be enforced as an equilibrium flow using tolls set
through the dual variables of the capacity constraints of a linear program.

######  Remark 2.

We note that in the proof of Lemma 6, all that we required was that the
objective function of I-TAPα is monotonically increasing in the flow on each
edge of the network. This suggests a more general sufficient condition for
enforcing flows as a user equilibrium. In particular, any flow that satisfies
the flow conservation constraints and is the solution of a convex program with
some convex objective $f(\mathbf{x})$ that is monotonically increasing in
$x_{e}$ for each $e\in E$ can be induced as a user equilibrium. Note that the
I-TAPα objective is a special case of such a function $f(\mathbf{x})$.

##  6 Numerical Experiments

We now evaluate the performance of our I-TAP method for $\beta$-SO on several
real-world transportation networks. The results of our experiments not only
characterize the behavior of I-TAP but also highlight that, compared to the
algorithm in [25], our approach has much smaller runtimes while achieving
lower total travel times for most levels $\beta$ of unfairness. In the
following, we describe the implementation details of the I-TAP method and the
unfairness metric as well as the data-sets we use. We further present the
corresponding results to evaluate the performance of our approach.

###  6.1 Implementation Details and Data Sets

We tested our I-TAP method using a single-thread C++ implementation of the
Conjugate Frank-Wolfe algorithm [29], which we made publicly available along
with our data sets and results (github.com/StanfordASL/{frank-wolfe-traffic,
fair-routing}). Our implementation is based on a previous repository which was
developed for [12]. While there is a rich literature on algorithm design to
solve the traffic assignment problem [7, 8], we decided to use the Frank-Wolfe
algorithm which was shown recently to be superior in terms of running time
[12]. For shortest-path computation in the all-or-nothing routine, we used the
LEMON Graph Library [15]. Within the same framework we implemented the
solution method for CSO that was presented in [25], where we used
r_c_shortest_paths within the Boost C++ Libraries [2] for constrained
shortest-path search.

To compute the resulting unfairness level for a given path flow $\mathbf{f}$
from those approaches we first recover a path-based solution by recording the
paths computed for each commodity $k$ in every Frank-Wolfe iteration, and
discarding paths whose relative weight in the final solution is negligible.
Denote by $\mathcal{P}^{+}_{k}$ the resulting collection of paths for a given
commodity $k$ with strictly positive flow. We also maintain for each path
$P\in\mathcal{P}^{+}_{k}$ the volume of flow used by the path for this
commodity. Then we recover for each commodity $k$ the edge-based solution by
computing for each edge $e\in E$ the total flow resulting from the paths
$\mathcal{P}^{+}_{k}$. Then we discard edges from the graph whose flow is $0$
for the commodity $k$, which yields the DAG $G_{k}=(V_{k},E_{k})$, with
vertices $V_{k}$ and edges $E_{k}$.

Finally, to compute the unfairness level for this commodity, we compute the
shortest and longest paths from origin to destination over the graph
$G_{k}=(V_{k},E_{k})$, where a weight for a given edge $e\in E_{k}$ is set to
be $t_{e}(x_{e})$, i.e., the travel time on the edge given the flows of all
the commodities combined with respect to the edge flow solution $\mathbf{x}$
corresponding to the path flow $\mathbf{f}$. To compute the shortest path over
$G_{k}$ we simply run a Dijkstra search, whose running time is
$\Theta(|E_{k}|+|V_{k}|\log|V_{k}|)$. Although for general graphs computing
the longest path is NP-hard, for the case of a DAG, we can compute it for the
same running time as Dijkstra by negating the edge weights, i.e., using the
weights $-t_{e}(x_{e})$ and then finding the shortest path [36].

All results were obtained using a commodity laptop equipped with 2.80GHz
4-core i7-7600U CPU, and 16GB of RAM, running 64bit Ubuntu 20.04 OS. We ran
the Frank-Wolfe algorithm for $100$ iterations on each data-set, both for
I-TAP and the method in [25]. We mention that this number of iterations
generally allows the Frank-Wolfe algorithm to achieve a relative error of at
most $10^{-5}$ when searching for UE and SO solutions over larger scenarios of
the traffic assignment problem [29].

Table 1 shows the six instances we use for our study, which were obtained from
[22]. We use the BPR travel time function [38], defined as

$\displaystyle
t_{e}(x_{e})=\xi_{e}\left(1+a\left(\tfrac{x_{e}}{\kappa_{e}}\right)^{b}\right),$
(2)

where $a,b$ are constants, $\xi_{e}$ is the free-flow travel time on edge $e$,
and $\kappa_{e}$ is the capacity of edge $e$, which is the number of users
beyond which the travel time on the edge rapidly increases. Since the
constants $a=0.15$ and $b=4$ are typically chosen, we use these constants for
the numerical experiments.

Table 1: Problem instance attributes and computation time. For each instance we report the number of vertices $|V|$, edges $|E|$, and OD pairs $|K|$. In addition, we report the computation time of each instance for the previous method of Jahn et al. [25] and our I-TAP method using 100 iterations of the Frank-Wolfe algorithm.  | attributes | runtime (sec.)
---|---|---
Region Name | $|V|$ | $|E|$ | $|K|$ | Jahn et al. | I-TAP
Sioux Falls (SF) | 24 | 76 | 528 | 20.0 | 0.03
Anaheim (A) | 416 | 914 | 1406 | 74.0 | 0.33
Massachusetts (M) | 74 | 258 | 1113 | 24.3 | 0.09
Tiergarten (T) | 361 | 766 | 644 | 18.2 | 0.20
Friedrichshain (F) | 224 | 523 | 506 | 19.8 | 0.12
Prenzlauerberg (P) | 352 | 749 | 1406 | 74.4 | 0.32

###  6.2 Results

Assessment of Theoretical Upper Bounds. We first assess the theoretical upper
bounds on the inefficiency ratio and level of unfairness that were obtained in
Section 4.2 with respect to the convex combination parameter $\alpha$. The
latter is obtained using a dense sampling method with increments of $0.01$. We
present the results for the Prenzlauerberg data-set and note that the results
and the following discussion extend to other problem instances in Table 1 as
well.

Figure 3 (left) depicts both (i) the change in the inefficiency ratio of the
solution $\mathbf{x}(\alpha)$ using dense sampling and (ii) the theoretical
upper bound of the inefficiency ratio (Theorem 1). As expected, the dense
sampling procedure results in an inefficiency ratio that is below the
theoretical upper bound for every value of $\alpha$.

The comparison between the theoretically guaranteed level of unfairness for
every value of $\alpha$ as obtained in Theorem 2 and the actual unfairness
level of the I-TAP method is depicted in Figure 3 (right). Since the BPR
travel time function we used in this work has a degree of four, we have that
for any value of $\alpha$, we can guarantee a level of unfairness of
$4\alpha+1$ by Theorem 2. Figure 3 (right) suggests that the theoretical upper
bound is even more conservative for the case of unfairness as there is an even
larger gap between the actual solution and the theoretical bound.

These findings further highlight the efficacy of the I-TAP approach for
practical applications.

0.00.20.40.60.81.01.001.021.04Convex Combination Parameter
$\displaystyle\alpha$Inefficiency Ratio
$\rho(\mathbf{x}(\alpha))$SamplingTheory Bound

0.00.20.40.60.81.0$1$$2$$3$$4$$5$Convex Combination Parameter
$\displaystyle\alpha$Unfairness $U(\mathbf{x}(\alpha))$

Figure 3: Comparison between the inefficiency ratio of the solution
$\mathbf{x}(\alpha)$ of I-TAP on the Prenzlauerberg data-set and the
theoretical bound on the inefficiency ratio obtained in Theorem 1 (left). The
comparison between the theoretical upper bound of the level of unfairness for
any convex combination parameter $\alpha$ and the unfairness level of the
solution $\mathbf{x}(\alpha)$ of I-TAP on the Prenzlauerberg data-set is shown
on the right. The values of the convex combination parameter were chosen at
increments of $0.01$.

Behavior of I-TAP. For each of the transportation networks in Table 1, we now
study the relationship between the convex combination parameter $\alpha$ and
the (i) total travel time, and (ii) unfairness. To review these relationships,
we consider $\alpha$ to lie in the set $\mathcal{A}_{s}$ with $s=0.01$
increments.

Figure 4 (left) shows the relationship between the inefficiency ratio and
$\alpha$. Note that when $\alpha=1$, the inefficiency ratio is one, since the
interpolated objective is the SO-TAP objective, and when $\alpha=0$, the
inefficiency ratio is the Price of Anarchy (PoA), since the interpolated
objective is the UE-TAP objective. As shown on the left in Figure 4, the
inefficiency ratio is always between one and the PoA for each of the
transportation networks, which corroborates the bound on the total travel time
for any convex combination parameter, as obtained in Theorem 1. Furthermore,
the inefficiency ratio varies continuously in $\alpha$, which further aligns
with the continuity of the total travel time function $h^{SO}$ in $\alpha$, as
is characterized in Section 4.5. The jumps in the inefficiency ratio that can
be observed for certain values of $\alpha$ for Sioux Falls aligns with the
continuity result since the relative magnitude of the jumps is small. In
particular, the change in the total travel time is less than 2% for a 1%
change in the value of $\alpha$.

The relationship between unfairness and $\alpha$ is depicted on the right in
Figure 4. For readability of this figure, we marked outliers as points where
large changes in the unfairness occur for small changes in $\alpha$. For an
explanation of the jumps in the unfairness at certain values of $\alpha$, see
the discussion in Section 4.5.

Finally, for each transportation network the general trend of a decrease in
the inefficiency ratio and an increase in the unfairness with an increase in
$\alpha$ suggests that decreasing the total travel time comes at the cost of
an increase in the unfairness and vice versa.

0.00.20.40.60.81.01.001.021.041.061.08Convex Combination Parameter
$\displaystyle\alpha$Inefficiency Ratio
$\rho(\mathbf{x}(\alpha))$TiergartenFriedrichshainAnaheimMassachusettsSioux
FallsPrenzlauerberg

0.00.20.40.60.81.01.01.21.41.61.8Convex Combination Parameter
$\displaystyle\alpha$Unfairness U($\mathbf{f}(\alpha)$)

Figure 4: Variation in the inefficiency ratio (left) and the level of
unfairness (right) of the optimal solution $\mathbf{x}(\alpha)$ of I-TAPα with
the parameter $\alpha\in[0,1]$ for six different transportation networks from
Table 1. The values of the convex combination parameter were chosen at
increments of $0.01$.

Solution Quality Comparison. We now explore the efficiency-fairness tradeoff
through a comparison of the Pareto frontier of the I-TAP method to the
approach in [25], which is a benchmark solution for fair traffic routing, and
the I-Solution method described in Section 4.1. To this end, we depict the
Pareto frontier of the (i) I-TAP method for $0.01$ and $0.05$ increments of
the parameter $\alpha$, (ii) I-Solution method for $0.01$ increments of the
convex combination parameter $\gamma$, and (iii) Jahn et al.’s approach [25]
for $0.05$ increments of the normal unfairness parameter $\phi$ lying between
one and two.

1.001.051.101.151.201.001.021.04Inefficiency Ratio
$\displaystyle\rho(\mathbf{x}(\alpha))$I-TAP-0.01I-TAP-0.05I-SolutionJahn et
al. Anaheim

1.01.21.41.001.011.021.031.04 Massachusetts

1.01.11.21.001.011.021.03Tiergarten Tiergarten

1.01.21.41.61.001.021.041.061.081.10Unfairness
U($\mathbf{f}(\alpha)$)Inefficiency Ratio
$\displaystyle\rho(\mathbf{x}(\alpha))$ Friedrichshain

1.01.21.41.61.001.011.021.031.04Unfairness U($\mathbf{f}(\alpha)$) Sioux Falls

1.01.21.41.61.81.001.011.021.031.04Unfairness U($\mathbf{f}(\alpha)$)
Prenzlauerberg

Figure 5: Pareto frontier depicting the trade-off between efficiency and
fairness for the (i) I-TAP method with a step size $s=0.01$, (ii) I-TAP method
with $s=0.05$, (iii) I-Solution method with $s=0.01$, and (iv) Jahn et al.’s
method [25] with $s=0.05$.

Figure 5 depicts the Pareto frontiers, i.e., the set of all Pareto efficient
combinations of system efficiency and user fairness, for the six
transportation networks in Table 1. In particular, observe that the Pareto
frontiers of the I-TAP method are below that of the other two approaches for
most values of unfairness. This observation indicates that the I-TAP method
outperforms the other two approaches since the inefficiency ratio of the I-TAP
solution is the lowest for most desired levels of unfairness. Only for the
Sioux Falls and Prenzlauerberg data-sets, the algorithm in [25] achieved lower
inefficiency ratios than both the I-TAP and I-Solution methods for higher
values of unfairness, which, in practice, would be undesirable. Furthermore,
note that, unlike the two convex-combination approaches, the solution of the
algorithm in [25] can result in inefficiency ratios that are much greater than
the PoA for low levels of unfairness. The I-TAP method outperforms the
I-Solution method since the set of paths that users can traverse is not
restricted to the union of the routes under the UE and SO solutions as is the
case for the I-Solution method. In particular, there may be traffic
assignments with lower total travel times that use paths not encapsulated by
the restricted set of paths corresponding to the I-Solution method.
Furthermore, while the PoA for each of the data-sets is quite low, some real-
world transportation networks may have much higher PoA values (even as high as
two) [46], which would make the trade-off between efficiency and fairness even
more prominent.

Finally, the Pareto frontiers of the I-TAP method for the $0.01$ and $0.05$
increments of the convex combination parameter almost overlap each other for
all the transportation networks other than Sioux Falls. Since Sioux Falls has
a highly discontinuous unfairness function (cf. Figure 4), it is likely that
the $0.05$ increments of $\alpha$ values may not capture all the low total
travel time solutions that keep within a $\beta$ bound of unfairness that the
$0.01$ increments of $\alpha$ may be able to capture. For all the other
datasets, the near equivalence of the Pareto frontiers for the two $\alpha$
discretizations suggests that a good performance of the I-TAP method can be
achieved with coarse discretizations of the convex combination parameter set.
Thus, we only need to compute a solution to the convex program I-TAPα for
relatively few values of $\alpha$ to characterize the Pareto frontier,
implying the computational efficiency of the I-TAP method.

Runtime Comparison. We report in Table 1 the runtime of the Jahn et al. method
[25] and our I-TAP method. For each instance we report the average runtime
over the parameters $\phi$ and $\alpha$ for the competitor and our method,
respectively. We observe that our approach is faster by at least three orders
of magnitude. This is unsurprising since our method solves _unconstrained_
shortest-path queries, which can be implemented in $O(|E|+|V|\log|V|)$ time,
within each Frank-Wolfe iteration, whereas [25] solves _constrained_ shortest-
path queries which are known to be NP-hard. We do mention that a more
efficient implementation of constrained shortest-path query can be achieved by
directly implementing a label-correcting algorithm rather than using the
r_c_shortest_paths routine from Boost, which is overly general for our setting
and hence less efficient. Nevertheless, even with this improvement it would
still be much slower than the unconstrained near-linear algorithm. Notice that
both approaches can be sped up via parallel computation of shortest-path
queries, and our method can be made even faster through modern heuristics for
shortest-path queries in transportation networks, such as contraction
hierarchies [23], as in [12].

##  7 Conclusion and Future Work

In this paper, we developed (i) a computationally efficient method for traffic
routing that trades-off system efficiency and user fairness, and (ii) pricing
schemes to enforce fair traffic assignments as a UE. We introduced the I-TAP
method, which involves solving interpolated traffic assignment problems by
taking a convex combination between the UE-TAP and SO-TAP objectives, to find
an efficient feasible traffic assignment to the $\beta$-SO problem. We then
established various solution properties of I-TAP, including computational
tractability and solution continuity, and developed theoretical bounds on the
inefficiency ratio and unfairness level in terms of the convex combination
parameter of I-TAP. To enforce the traffic assignments outputted by the I-TAP
method as a UE, we developed a marginal-cost pricing scheme when users are
homogeneous, and a linear programming based pricing scheme when users are
heterogeneous. Finally, we presented numerical experiments to evaluate the
performance of our approach on real-world transportation networks. The results
indicated that our algorithm is not only very computationally efficient but
also generally results in traffic assignments with lower total travel times
for most levels of unfairness as compared to the algorithm in [25].

There are various directions for future research. First, it would be
worthwhile to develop theoretical bounds for I-TAP to demonstrate its
applicability to other notions of unfairness, some of which are studied in
Appendix B, and extend its optimality beyond two-edge Pigou networks. Next, it
would be interesting to investigate fairness notions that compare user travel
times across different O-D pairs. Finally, given the significant computational
advantages of the I-TAP method, it would be interesting to study the
generalizability of our approach when accounting for costs beyond the travel
times of users, such as environmental pollution and user discomfort.

##  8 Acknowledgements

We thank Kaidi Yang and anonymous reviewers for their detailed inputs and
insightful feedback on an earlier version of this work. This work was
supported in part by the National Science Foundation (NSF) CAREER Award
CMMI1454737, NSF Award 1830554, Toyota Research Institute, the Israeli
Ministry of Science and Technology grants no. 3-16079 and 3-17385, and the
United States-Israel Binational Science Foundation grants no. 2019703 and
2021643.

## References

  * [1]
  * Boo [2010] 2010\.  Boost C++ Libraries.  www.boost.org.
  * Angelelli et al. [2016] Enrico Angelelli, Idil Arsik, Valentina Morandi, Martin Savelsbergh, and Maria Grazia Speranza. 2016\.  Proactive route guidance to avoid congestion.  _Transportation Research Part B: Methodological_ 94 (2016), 1–21.  https://doi.org/10.1016/j.trb.2016.08.015
  * Angelelli et al. [2020b] Enrico Angelelli, Valentina Morandi, Martin Savelsbergh, and Maria Grazia Speranza. 2020b.  System optimal routing of traffic flows with user constraints using linear programming.  _European Journal of Operational Research_ (2020).  https://doi.org/10.1016/j.ejor.2020.12.043
  * Angelelli et al. [2018] Enrico Angelelli, Valentina Morandi, and Maria Grazia Speranza. 2018.  Congestion avoiding heuristic path generation for the proactive route guidance.  _Computers & Operations Research_ 99 (2018), 234–248.  https://doi.org/10.1016/j.cor.2018.07.009
  * Angelelli et al. [2020a] Enrico Angelelli, Valentina Morandi, and Maria Grazia Speranza. 2020a.  Minimizing the total travel time with limited unfairness in traffic networks.  _Computers & Operations Research_ 123 (2020), 105016.  https://doi.org/10.1016/j.cor.2020.105016
  * Bar-Gera [2002] Hillel Bar-Gera. 2002\.  Origin-Based Algorithm for the Traffic Assignment Problem.  _Transportation Science_ 36, 4 (2002), 398–417.  http://www.jstor.org/stable/25769124
  * Bar-Gera [2010] Hillel Bar-Gera. 2010\.  Traffic assignment by paired alternative segments.  _Transportation Research Part B: Methodological_ 44, 8 (2010), 1022–1046.  https://doi.org/10.1016/j.trb.2009.11.004
  * Basu et al. [2017] Soumya Basu, Ger Yang, Thanasis Lianeas, Evdokia Nikolova, and Yitao Chen. 2017.  Reconciling Selfish Routing with Social Good.  _CoRR_ abs/1707.00208 (2017).
  * Bayram et al. [2015] Vedat Bayram, Barbaros Tansel, and Hande Yaman. 2015\.  Compromising system and user interests in shelter location and evacuation planning.  _Transportation Research Part B: Methodological_ 72 (2015), 146–163.  https://doi.org/10.1016/j.trb.2014.11.010
  * Bertsimas et al. [2012] Dimitris Bertsimas, Vivek Farias, and Nikolaos Trichakis. 2012\.  On the Efficiency-Fairness Trade-off.  _Management Science_ 58, 12 (2012), 2234–2250.  https://doi.org/10.1287/mnsc.1120.1549
  * Buchhold et al. [2019] Valentin Buchhold, Peter Sanders, and Dorothea Wagner. 2019\.  Real-Time Traffic Assignment Using Engineered Customizable Contraction Hierarchies.  _ACM J. Exp. Algorithmics_ 24, Article 2.4 (Dec. 2019), 28 pages.  https://doi.org/10.1145/3362693
  * Caltrans [2010] Caltrans. 2010.  US 101 South, corridor system management plan, 2010.  Accessed July 01, 2020.
  * Correa et al. [2007] José Correa, Andreas Schulz, and Nicolás Stier-Moses. 2007\.  Fast, Fair, and Efficient Flows in Networks.  _Operations Research_ 55, 2 (2007), 215–225.  https://doi.org/10.1287/opre.1070.0383
  * Dezső et al. [2011] Balázs Dezső, Alpár Jüttner, and Péter Kovács. 2011.  LEMON–an open source C++ graph template library.  _Electronic Notes in Theoretical Computer Science_ 264, 5 (2011), 23–45.
  * Dial [1996] Robert Dial. 1996\.  Bicriterion Traffic Assignment: Basic Theory and Elementary Algorithms.  _Transportation Science_ 30, 2 (1996), 93–111.  https://doi.org/10.1287/trsc.30.2.93
  * Dial [1997] Robert Dial. 1997\.  Bicriterion traffic assignment: Efficient algorithms plus examples.  _Transportation Research Part B: Methodological_ 31, 5 (1997), 357–379.  https://doi.org/10.1016/S0191-2615(96)00034-3
  * Farris [2010] Frank Farris. 2010\.  The Gini Index and Measures of Inequality.  _The American Mathematical Monthly_ 117, 10 (2010), 851–864.  https://doi.org/10.4169/000298910X523344
  * Ferguson and Marden [2021] Bryce Ferguson and Jason Marden. 2021.  The Impact of Fairness on Performance in Congestion Networks. In _2021 American Control Conference (ACC)_. 4521–4526.  https://doi.org/10.23919/ACC50511.2021.9483197
  * Fleischer et al. [2004] Lisa Fleischer, Kamal Jain, and Mohammad Mahdian. 2004\.  Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games. In _IEEE Symp. on Foundations of Computer Science_.  https://doi.org/10.1109/FOCS.2004.69
  * Fleming [2019] Sean Fleming. 2019\.  Traffic congestion cost the US economy nearly $87 billion in 2018.  https://www.weforum.org/agenda/2019/03/traffic-congestion-cost-the-us-economy-nearly-87-billion-in-2018/ Accessed February 19, 2021.
  * for Research Core Team [2016] Transportation Networks for Research Core Team. 2016.  Transportation Networks for Research.  github.com/bstabler/TransportationNetworks.  Accessed January 20, 2021.
  * Geisberger et al. [2012] R. Geisberger, P. Sanders, D. Schultes, and C. Vetter. 2012\.  Exact Routing in Large Road Networks Using Contraction Hierarchies.  _Transportation Science_ 46, 3 (2012), 388–404.
  * Hu and Chen [2020] Lily Hu and Yiling Chen. 2020.  Fair Classification and Social Welfare. In _Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency_ (Barcelona, Spain) _(FAT* ’20)_. Association for Computing Machinery, New York, NY, USA, 535–545.  https://doi.org/10.1145/3351095.3372857
  * Jahn et al. [2005] O. Jahn, R. Möhring, A. Schulz, and N. Stier-Moses. 2005\.  System-Optimal Routing of Traffic Flows with User Constraints in Networks with Congestion.  _Operations Research_ 53, 4 (2005), 600–616.  https://doi.org/10.1287/opre.1040.0197
  * Jalota et al. [2021] Devansh Jalota, Kiril Solovey, Karthik Gopalakrishnan, Stephen Zoepf, Hamsa Balakrishnan, and Marco Pavone. 2021.  When Efficiency meets Equity in Congestion Pricing and Revenue Refunding Schemes.  _CoRR_ abs/2106.10407 (2021).
  * Koutsoupias and Papadimitriou [1999] Elias Koutsoupias and Christos Papadimitriou. 1999.  Worst-Case Equilibria. In _Theoretical Aspects of Computer Science_.
  * Lujak et al. [2014] Marin Lujak, Stefano Giordani, and S. Ossowski. 2014\.  Route Guidance: Bridging System and User Optimization in Traffic Assignment.  _Neurocomputing_ 151 (09 2014).  https://doi.org/10.1016/j.neucom.2014.08.071
  * Mitradjieva and Lindberg [2013] Maria Mitradjieva and Per Olov Lindberg. 2013.  The Stiff Is Moving - Conjugate Direction Frank-Wolfe Methods with Applications to Traffic Assignment.  _Transp. Sci._ 47, 2 (2013), 280–293.
  * Pigou [1912] Arthur Pigou. 1912\.  _Wealth and Welfare_ (1 ed.).  London, Macmillan and Co.
  * Rahmattalabi et al. [2020] Aida Rahmattalabi, Shahin Jabbari, Himabindu Lakkaraju, Phebe Vayanos, E. Rice, and Milind Tambe. 2020\.  Fair Influence Maximization: A Welfare Optimization Approach.  _CoRR_ abs/2006.07906 (2020).
  * Roughgarden [2002] Tim Roughgarden. 2002\.  How unfair is optimal routing?. In _ACM-SIAM Symp. on Discrete Algorithms_.
  * Roughgarden and Éva Tardos [2004] Tim Roughgarden and Éva Tardos. 2004.  Bounding the inefficiency of equilibria in nonatomic congestion games.  _Games and Economic Behavior_ 47, 2 (2004), 389 – 403.  https://doi.org/10.1016/j.geb.2003.06.004
  * Roughgarden and Tardos [2002] Tim Roughgarden and Éva Tardos. 2002.  How Bad is Selfish Routing?  _J. ACM_ 49, 2 (March 2002), 236–259.  https://doi.org/10.1145/506147.506153
  * Schulz and Stier-Moses [2006] Andreas Schulz and Nicolás Stier-Moses. 2006.  Efficiency and fairness of system-optimal routing with user constraints.  _Networks_ 48, 4 (2006), 223–234.  https://doi.org/10.1002/net.20133
  * Sedgewick and Wayne [2011] Robert Sedgewick and Kevin Wayne. 2011.  _Algorithms, 4th Edition._ Addison-Wesley. I–XII, 1–955 pages.
  * Sharon et al. [2018] Guni Sharon, Michael Albert, Tarun Rambha, Stephen Boyles, and Peter Stone. 2018.  Traffic Optimization For a Mixture of Self-interested and Compliant Agents. In _ISAIM_.
  * Sheffi [1985] Yossi Sheffi. 1985\.  _Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods_ (1 ed.).  Prentice-Hall, Englewood Cliffs, New Jersey.
  * Still [2018] Georg Still. 2018\.  Lectures on Parametric Optimization: An Introduction.  Optimization Online.
  * Stoica et al. [2020] Ana-Andreea Stoica, Jessy Xinyi Han, and Augustin Chaintreau. 2020.  Seeding Network Influence in Biased Networks and the Benefits of Diversity. In _Proceedings of The Web Conference 2020_ (Taipei, Taiwan) _(WWW ’20)_. Association for Computing Machinery, New York, NY, USA, 2089–2098.  https://doi.org/10.1145/3366423.3380275
  * Tsang et al. [2019] Alan Tsang, Bryan Wilder, Eric Rice, Milind Tambe, and Yair Zick. 2019.  Group-Fairness in Influence Maximization.  _CoRR_ abs/1903.00967 (2019).
  * Wardrop [1952] John Glen Wardrop. 1952\.  Some Theoretical Aspects of Road Traffic Research.  _Proceedings of the Institution of Civil Engineers_ 1, 3 (1952), 325–362.  https://doi.org/10.1680/ipeds.1952.11259
  * Wu et al. [2012] Di Wu, Yafeng Yin, Siriphong Lawphongpanich, and Hai Yang. 2012.  Design of more equitable congestion pricing and tradable credit schemes for multimodal transportation networks.  _Transportation Research Part B: Methodological_ 46, 9 (2012), 1273–1287.
  * Yang and Huang [2005] Hai Yang and Hai-Jun Huang. 2005.  _Mathematical and Economic Theory of Road Pricing_ (1 ed.).  Emerald Publishing.
  * Yang and Wang [2011] Hai Yang and Xiaolei Wang. 2011.  Managing network mobility with tradable credits.  _Transportation Research Part B: Methodological_ 45, 3 (2011), 580–594.  https://doi.org/10.1016/j.trb.2010.10.002
  * Zhang et al. [2018] Jing Zhang, Sepideh Pourazarm, Christos Cassandras, and Ioannis Paschalidis. 2018.  The Price of Anarchy in Transportation Networks: Data-Driven Evaluation and Reduction Strategies.  _Proc. IEEE_ 106, 4 (2018), 538–553.  https://doi.org/10.1109/JPROC.2018.2790405

## Appendix

##  Appendix A Proof of Lemma 3

To prove the claim, we first note that in a two edge Pigou network the sum of
the traffic flows on the two edges must add up to the traffic demand $D$.
Thus, we can reduce the problem of determining a two-dimensional vector of
edge flows to a single dimensional problem of determining the flow $x_{1}$ on
the first edge, with the flow on the other edge given by $D-x_{1}$ for a
traffic demand $D$. With slight abuse of notation, we denote $h^{SO}(x_{1})$,
$h^{UE}(x_{1})$ and $h^{I_{\alpha}}(x_{1})$ to denote the system optimum, user
equilibrium and I-TAP objectives, respectively.

We now complete the proof in two steps. First we show that the optimal
solutions of I-TAP for any $\alpha\in[0,1]$ and the $\beta$-SO problem lie
between the user equilibrium and system optimum solutions, i.e.,
$x_{1}(\alpha),x_{1}^{\beta}\in[x_{1}(0),x_{1}(1)]$ for all $\alpha\in[0,1]$
and $\beta\in[1,\infty)$, where we assume without loss of generality that
$x_{1}(0)\leq x_{1}(1)$. Note here that we only compare the edge flows of
I-TAP and $\beta$-SO since both the path and edge flows coincide for a two
edge Pigou network. We then extend the result of Corollary 1 to show that the
optimal solution $x_{1}(\alpha)$ is continuous in the closed interval $[0,1]$.
Note that both the above claims jointly imply by the intermediate value
theorem that for any $\beta\in[1,\infty)$ there exists some
$\alpha^{*}\in[0,1]$ such that $x_{1}(\alpha^{*})=x_{1}^{\beta}$. We now
proceed to prove the two claims.

We begin by establishing that $x_{1}(\alpha)\in[x_{1}(0),x_{1}(1)]$ for any
$\alpha\in[0,1]$. In particular, we will show that for any point not in the
interval $[x_{1}(0),x_{1}(1)]$ that we can find another feasible point with a
lower I-TAP objective value. To see this, we proceed by contradiction. Fix
some $\alpha\in[0,1]$ and suppose that $x_{1}(\alpha)<x_{1}(0)$. Then, we
observe by the optimality of $x_{1}(0)$ for the user equilibrium traffic
assignment problem that $h^{UE}(x_{1}(\alpha))>h^{UE}(x_{1}(0))$ and by the
strict convexity of $h^{SO}$ that $h^{SO}(x_{1}(\alpha))>h^{SO}(x_{1}(0))$.
Together, both the strict inequalities imply that
$h^{I_{\alpha}}(x_{1}(\alpha))>h^{I_{\alpha}}(x_{1}(0))$, a contradiction.
Through an almost identical argument, we can show that
$x_{1}(\alpha)>x_{1}(1)$ is also not possible. Thus, we have shown that
$x_{1}(\alpha)\in[x_{1}(0),x_{1}(1)]$ for any $\alpha\in[0,1]$.

Next, we show that $x_{1}^{\beta}\in[x_{1}(0),x_{1}(1)]$ for any
$\beta\in[1,\infty)$. In particular, we will show that for any point not in
the interval $[x_{1}(0),x_{1}(1)]$ that we can find another feasible point
with a lower system optimum objective value. To see this, we again proceed by
contradiction. First suppose that $x_{1}^{\beta}<x_{1}(0)$. In this case, note
that $h^{SO}(x_{1}^{\beta})>h^{SO}(x_{1}(0))$ by the strict convexity of
$h^{SO}$. Since $x_{1}(0)$ is a feasible solution to the $\beta$-SO problem
for any $\beta\in[1,\infty)$ this implies that $x_{1}^{\beta}<x_{1}(0)$ cannot
be an optimal solution to the $\beta$-SO problem. This implies that
$x_{1}^{\beta}\geq x_{1}(0)$. Next, suppose by contradiction that
$x_{1}^{\beta}>x_{1}(1)$. If $x_{1}^{\beta}=D$, then
$h^{SO}(x_{1}^{\beta})=Dt_{1}(D)>Dt_{1}(x_{1}(0))=x_{1}(0)t_{1}(x_{1}(0))+(D-x_{1}(0))t_{2}(x_{2}(0))=h^{SO}(x_{1}(0))$
since $x_{1}(0)<x_{1}^{\beta}=D$. Thus, $x_{1}(0)$ achieves a lower total
travel time and is feasible for any $\beta\in[1,\infty)$, and so
$x_{1}^{\beta}=D$ cannot be a solution to the $\beta$-SO problem. Next,
suppose that $x_{1}(1)<x_{1}^{\beta}<D$. In this case, we have that
$\frac{t_{1}(x_{1}^{\beta})}{t_{2}(D-x_{1}^{\beta})}>\max\\{\frac{t_{1}(x_{1}(1))}{t_{2}(D-x_{1}(1))},1\\}$,
and thus the ratio of travel times is strictly greater than than that under
the system optimal traffic assignment. Thus, we have that for any
$\beta\in[1,\infty)$ it must be the case that $x_{1}^{\beta}\leq x_{1}(1)$,
thereby proving our claim that $x_{1}^{\beta}\in[x_{1}(0),x_{1}(1)]$.

We now prove the second claim that $x_{1}(\alpha)$ is continuous in the closed
interval $[0,1]$. First observe by Corollary 1 that $x_{1}(\alpha)$ is
continuous in the open interval $(0,1)$. Thus, we just need to prove the
continuity of $x_{1}(\alpha)$ for $\alpha=0,1$. To do so, we introduce a
problem instance specific constant $C(G,D,\\{t_{e}\\}_{e=1}^{2})$ that denotes
the system optimum objective value when $x_{1}=x_{2}=D$. We note that
$C(G,D,\\{t_{e}\\}_{e=1}^{2})$ is an upper bound on the system optimal
objective for any feasible traffic assignment and it is a constant that
depends on the graph $G$, the demand $D$ and the travel time functions. We
prove the continuity for $\alpha=0$ in what follows. First, observe that

$\displaystyle h^{I_{\alpha}}(x_{1}(0))-h^{I_{\alpha}}(x_{1}(\alpha))$
$\displaystyle=\alpha\left(h^{SO}(x_{1}(0))-h^{SO}(x_{1}(\alpha))\right)$
$\displaystyle+(1-\alpha)\left(h^{UE}(x_{1}(0))-h^{UE}(x_{1}(\alpha))\right),$
$\displaystyle<\alpha\left(h^{SO}(x_{1}(0))-h^{SO}(x_{1}(\alpha))\right),$
$\displaystyle\leq\alpha C(G,D,\\{t_{e}\\}_{e=1}^{2}),$

where the strict inequality follows since
$h^{UE}(x_{1}(0))<h^{UE}(x_{1}(\alpha))$, and the last inequality follows by
the boundedness of $h^{SO}$ due to the finite demand $D$. Finally, by the
strict convexity of the objective $h^{I_{\alpha}}(\cdot)$ it must follow that
$x_{1}(\alpha)\rightarrow x_{1}(0)$ as $\alpha\rightarrow 0$ since
$h^{I_{\alpha}}(x_{1}(0))\rightarrow h^{I_{\alpha}}(x_{1}(\alpha))$ as
$\alpha\rightarrow 0$ by the above analysis. Thus, we have continuity of
$x_{1}(\alpha)$ for $\alpha=0$. Through an analogous analysis we can also
obtain continuity for $\alpha=1$.

Finally, we note that both the above claims jointly imply by the intermediate
value theorem that for any $\beta\in[1,\infty)$ there exists some
$\alpha^{*}\in[0,1]$ such that $x_{1}(\alpha^{*})=x_{1}^{\beta}$, thereby
proving our result.

##  Appendix B Additional Unfairness Measures

While we presented an unfairness notion in Section 3.2 that compares the ratio
of the travel times on positive paths, there have been many other unfairness
notions that have been investigated in the fair traffic routing literature as
well as in other economic applications to evaluate the distribution of a
resource among users. In this section, we present a few other commonly-used
unfairness measures used in the traffic routing and economics literature
(Section B.1) and a numerical study of these unfairness measures (Section B.2)
on the six instances in Table 1.

###  B.1 Unfairness Measures for Path Flows

In this section, we present several measures that can be used to evaluate the
level of unfairness of a traffic assignment. While many unfairness measures
for traffic routing have been proposed, most notions rely on a quantification
of the discrepancy between user travel times. For instance, Correa et al. [14]
measure unfairness through the maximum ratio of the travel times between two
users for a given set of path flows $\mathbf{f}$ of the edge flow
$\mathbf{x}$. This definition of unfairness is termed as “envy-free” by Basu
et al. [9] since one user can envy another’s path by a factor no more than
$\beta$. An analogous notion to the envy-free definition is that of a “Used
Nash Equlibrium”, wherein the level of unfairness is calculated through the
maximum ratio between the experienced travel time for any given user to the
travel time on any other positive path between the same O-D pair. Note that
the “Used Nash Equlibrium” serves as an intermediary to the unfairness notion
presented Section 3.2 and the envy-free notion. There are also several other
definitions of max-min fairness proposed in the traffic routing literature,
and we defer the interested reader to a discussion of some of these notions to
Jahn et al. [25].

Beyond the fairness notions considered in the traffic routing literature,
there have also been other measures proposed to evaluate fairness or equity in
the distribution of a given resource amongst users. One such popular measure
is the Gini coefficient [18], which is used to evaluate the level of
dispersion of wealth in society. Applying this idea in context of traffic
routing, we can use the discrete Gini coefficient measure [43, 26] to evaluate
the spread in the travel times of users travelling between the same O-D pair.
We summarize the above mentioned unfairness measures in Table 2.

Note that some path decompositions may be more fair according to one metric as
compared to another. For instance, consider the situation when a small group
of users incur an exceedingly large travel time while the remaining users
travelling between the same O-D pair incur a small travel time. In this case,
the level of unfairness for the Envy Free and Used Nash measures will
typically be high but the level of unfairness as measured according to the
Gini measure will be quite low. As a result, each of these metrics has their
own merit as well as limitations when applied to measuring the level of
unfairness of specific path flow decompositions.

Table 2: Path-based unfairness Measures that depend on the realization of a specific path flow decomposition $\mathbf{f}$ of an edge flow $\mathbf{x}$.  Unfairness Measure |  Formula ($\tilde{U}(\mathbf{f})$)
---|---
Envy Free | $\max_{k\in K}\max_{Q,R\in\mathcal{P}_{k}:\mathbf{x}_{Q},\mathbf{x}_{R}>0}\frac{t_{Q}(\mathbf{x})}{t_{R}(\mathbf{x})}$
Used Nash | $\max_{k\in K}\max_{R\in\mathcal{P}_{k}^{+},Q\in\mathcal{P}_{k}:\mathbf{x}_{Q}>0}\frac{t_{Q}(\mathbf{x})}{t_{R}(\mathbf{x})}$
Discrete Gini Coefficient | $\max_{k\in K}\frac{\sum_{P,Q\in\mathcal{P}_{k}}\mathbf{x}_{Q}\mathbf{x}_{P}|t_{Q}(\mathbf{x})-t_{P}(\mathbf{x})|}{2d_{k}\sum_{P\in\mathcal{P}_{k}}\mathbf{x}_{P}t_{P}(\mathbf{x})}$

Finally, observe that each of the above defined notions of unfairness involve
taking a maximum of the unfairness measure for each O-D pair. We note that
different methods of aggregating across O-D pairs can also be used, e.g.,
averaging the unfairness measure. Furthermore, there is a key aspect of the
above defined unfairness measures that makes the I-TAP a particularly natural
approach for balancing efficiency and fairness. In particular, for each of the
above defined unfairness notions, the user equilibrium achieves the highest
possible level of fairness, while the system optimum achieves the lowest total
travel times. Thus, interpolating between the UE and SO objectives can
potentially achieve the best of both worlds, i.e., a low total travel time
with a high level of fairness.

###  B.2 Numerical Results

We now present some numerical results to demonstrate the performance of I-TAP
with respect to the above defined path-based unfairness measures. In
particular, we use the Frank Wolfe method to compute a specific path
decomposition for I-TAP and use this to evaluate the level of unfairness based
on the Envy-Free and discrete Gini coefficient metrics. Figures 6 and 7 depict
the trade-off between system efficiency and unfairness for the two metrics,
Envy-Freeness and the discrete Gini coefficient, respectively.

1.001.051.101.151.201.001.011.021.031.04Inefficiency Ratio
$\displaystyle\rho(\mathbf{x}(\alpha))$I-TAP-0.01Jahn et al. Anaheim

1.01.21.41.001.011.021.031.04 Massachusetts

1.01.11.21.001.011.021.03Tiergarten Tiergarten

1.01.21.41.61.001.021.041.061.081.10Envy-Free Unfairness
$\tilde{U}(\mathbf{f})$Inefficiency Ratio
$\displaystyle\rho(\mathbf{x}(\alpha))$ Friedrichshain

1.01.21.41.61.001.011.021.031.04Envy-Free Unfairness $\tilde{U}(\mathbf{f})$
Sioux Falls

1.01.21.41.61.81.001.011.021.031.04Envy-Free Unfairness
$\tilde{U}(\mathbf{f})$ Prenzlauerberg

Figure 6: Pareto frontier depicting the trade-off between efficiency and
“envy-freeness” for the (i) I-TAP method with a step size $s=0.01$, and (ii)
Jahn et al.’s method with $s=0.05$.

0.000.010.020.030.041.001.011.021.031.04Inefficiency Ratio
$\displaystyle\rho(\mathbf{x}(\alpha))$I-TAP-0.05Jahn et al. Anaheim

0.000.020.040.060.081.001.011.021.031.04 Massachusetts

0.000.010.020.031.001.011.021.03 Tiergarten

0.000.050.101.001.021.041.061.081.10Discrete Gini Coefficient
$\tilde{U}(\mathbf{f})$Inefficiency Ratio
$\displaystyle\rho(\mathbf{x}(\alpha))$ Friedrichshain

0.000.050.101.001.011.04Discrete Gini Coefficient $\tilde{U}(\mathbf{f})$
Sioux Falls

0.000.050.101.001.011.021.031.04Discrete Gini Coefficient
$\tilde{U}(\mathbf{f})$ Prenzlauerberg

Figure 7: Pareto frontier depicting the trade-off between efficiency and
discrete Gini coefficient for the (i) I-TAP method with a step size $s=0.05$,
and (ii) Jahn et al.’s method with $s=0.05$.

We note that the Pareto-frontier depicting the Envy-Free metric in Figure 6 is
almost identical to the Pareto frontier of the edge-based unfairness metric
presented in Section 3.2. This observation suggests that for many practical
instances these two notions of unfairness are quite close to each other. We
note this despite the fact that the Envy-Free notion involves the maximum
ratio between experienced travel times for a given flow decomposition while
the edge-based unfairness metric involves the maximum possible ratio between
travel times on positive paths and is thus independent of the realized path
decomposition. Since the Used Nash measure is an intermediary between the
Envy-Free and the edge-based unfairness measure in Section 3.2, we note that
it would also correspond to near identical Pareto frontiers for the six tested
instances. Thus, we do not depict the Used Nash unfairness measure.

For the discrete Gini coefficient metric, we first note that at the user
equilibrium solution the discrete Gini coefficient is zero, rather than having
unfairness of one for the earlier explored unfairness measures. This is
because all users travelling between the same O-D pair have equal travel times
at the user equilibrium and thus the numerator of the discrete Gini
coefficient is 0. Note that the further the discrete Gini coefficient is away
from zero the more unfair the solution.

We observe from Figure 7 that, modulo numerical errors, the discrete Gini
coefficient of the user equilibrium for all the scenarios is very close to
zero. As with the earlier explored unfairness measures, we also observe that
the I-TAP method outperforms the approach used in Jahn et al. [25] even on the
discrete Gini coefficient metric for low levels of desired Gini coefficients
for all data-sets but Prenzlauerberg.