TITLE: Taylor series of $g(x)=f(cx)$, $c \in \mathbb{R}$?
QUESTION [0 upvotes]: I'm having slight difficulties in understanding the Taylor polynomial for
$$g(x)=f(cx), \space c \in \mathbb{R}$$
The way I look at it is to start with:
$$T_{n, x_0}g(x)=\sum_{m=0}^n \frac{g^{(m)}(x_0)}{m!}(x-x_0)^m$$
$$=\sum_{m=0}^n \frac{f^{(m)}(c x_0)}{m!}(x-x_0)^m$$
$$=f(cx_0) + f'(cx_0)(x-x_0)+\frac{f''(cx_0)}{2}(x-x_0)^2+ \cdot\cdot\cdot$$
But I'm having trouble understanding, what can I do with the derivatives $f'(cx_0)$, $f''(cx_0)$ ... ?
Like can I move the constant out? Because what I'm trying to show is that
$$T_{n, x_0} g(x) = T_{n, cx_0} f(cx)$$

OR do I have to "map" the $x_0$ so that
$$=\sum_{m=0}^n \frac{f^{(m)}(c x_0)}{m!}(x-x_0)^m$$
is actually
$$=\sum_{m=0}^n \frac{f^{(m)}(c x_0)}{m!}(x-cx_0)^m$$
because the $x_0$ has been shifted by $c$?

REPLY [0 votes]: Your Taylor series for $f$ is not correct.  To see this, put $y = cx$, and write out the Taylor series of $f$ w.r.t. $y$ at the point $y_{0} = cx_{0}$.  You get:
$$
f(y) = \sum_{m \geq 0} {f^{(m)} \over m!}(y_{0}) \; (y - y_{0})^{m}
= \sum_{m \geq 0} {f^{(m)} \over m!}(c x_{0}) \; (cx - cx_{0})^{m}.
$$
If I understand your question correctly, this should clear it up.


text:
\begin{document}

\begin{frontmatter}

\title{Spatial Pricing of Ride-sourcing Services in a Congested Transportation Network}

\author[mymainaddress]{Fatima Afifah}
\author[mymainaddress]{Zhaomiao Guo\corref{mycorrespondingauthor}}
\cortext[mycorrespondingauthor]{(Corresponding Author) Assistant Professor, 4353 Scorpius Street, Orlando, Florida 32816-0120, Phone: 407-823-6215, Email: guo@ucf.edu}

\address[mymainaddress]{Department of Civil, Environmental and Construction Engineering\\
Resilient, Intelligent and Sustainable Energy Systems Cluster\\
	University of Central Florida, FL 32766
}

\begin{abstract}
	 We investigate the impacts of spatial pricing for ride-sourcing services in a Stackelberg framework considering traffic congestion. In the lower level, we use combined distribution and assignment approaches to explicitly capture the interactions between drivers' relocation, riders' mode choice, and all travelers' routing decisions. In the upper level, a monopolistic transportation network company (TNC) determines spatial pricing strategies to minimize imbalance in a two-sided markets. We show the existence of the optimal pricing strategies for locational imbalance minimization, and propose effective algorithms with reliable convergence properties. Furthermore, the optimal pricing is unique, and can be solved in a convex reformulation when matching time can be ignored. We conduct numerical experiments on different scales of transportation networks with different TNC objectives to generate policy insights on how spatial pricing could impact transportation systems.
\end{abstract}

\begin{keyword}
ride-sourcing\sep transportation network company (TNC) \sep dynamic pricing \sep traffic equilibrium\sep Stakelberg game

\end{keyword}
\end{frontmatter}

\section{Introduction}

Since the first introduction of UBER services in 2010, ride-sourcing has become an encouraging new form of mobility. Transportation network companies (TNCs), also known as ride-sourcing companies, serve as both platform providers and operators, promising to increase reliability and efficiency of point-to-point transportation. Dynamic pricing\footnote{E.g., Uber surge pricing, Lyft prime time charges, and Didi Chuxing's dyanamic pricing.} is one of TNCs' key operational techniques to improve locational supply-demand balance in real-time. Conceptually, dynamic pricing sets a surge multiplier (SM) for each predefined geographic area, which dynamically raises (or reduces) the base trip fare when locational demand is higher (or lower) than available supply until demand and supply are balanced \footnote{In reality, prices for rides are dynamically calculated based on a variety of factors including route, time of day, ride type, number of available drivers, current demand for rides, and any local fees or surcharges. While actual pricing algorithm is unknown to public, \cite{chen2015peeking} reverse engineer the pricing strategies using high-resolution UBER data.}. While conceptually appealing, dynamic pricing receives critiques over the past years due to the opaque of pricing algorithm and concerns that TNCs may surge unnecessarily high or more frequently to exploit customers in an oligopolistic setting \citep{zha2018surge}.

Determining optimal pricing strategies may be challenging due to spatio-temporal couplings and potential conflict of interests between the society and TNCs. On one hand, dynamic pricing tries to balance supply and demand both in time and in space, but the most research attention has been paid to the temporal aspect \citep{bimpikis2019spatial}. Because pricing information (i.e., SM, base trip fare, etc.) are revealed to both demand and supply markets, which are interconnected through a transportation network, prices at one location affect services at all other locations potentially. In practice, TNCs also benefit from using spatial prices to account for long-term predictable unbalanced demand patterns\citep{bimpikis2019spatial}. Studying dynamic pricing from a network perspective is beneficial for both societal welfare and TNCs' mission. On the other hand, while TNCs are typically profit-driven, optimal prices for TNCs themselves may not be optimal for the whole society, which includes riders, drivers and other transportation users. Better understanding the impact of different TNCs' objectives on system welfare is critical to generate planning and regulation insights for policy makers.

In this paper, we focus on addressing the spatial effects of dynamic pricing considering traffic congestion. We investigate the impacts of spatial pricing \footnote{Spatial pricing is the average pricing of ride-sourcing services originated from predefined zones, such as census tracts or 1mi by 1mi blocks. We note that spatial pricing and surge multipliers are closely related. If we ignored the temporal aspect of surge multipliers, the ratio between spatial pricing and average trip fares in normal states should be close to surge multipliers.} for ride-sourcing services in an interconnected transportation network using a Stackelberg framework. In the lower level, we explicitly capture the interactions between drivers' relocation, riders' mode choice, and all travelers' routing decisions. In the upper level, a monopolistic TNC determines spatial pricing strategies to fulfill its own objective in a two-sided markets. The main contribution of this work is threefold. First, we explicitly consider the relocation of drivers and transportation congestion, which not only more accurately captures the ride-sourcing behaviors, but also allows for systematic analyses of the impacts of spatial pricing on transportation efficiency. Second, while optimal spatial pricing problems are challenging to solve due to a bi-level structure, we propose effective computational algorithms, with rigorous analyses on the existence and convergence of the optimal solutions. Third, when matching time can be ignored, we reformulate the optimal spatial pricing problem as a single-level convex optimization, which significantly improves the computational efficiency and guarantees a unique global optimal.

The remainder of this paper is organized as follows. Section 2 reviews the relevant literature on dynamic pricing in ride-sourcing context. Section 3 and section 4 propose the formulations and algorithms, respectively. We test the models and solution approaches using difference scales of transportation systems in section 5. Section 6 concludes the paper with main research findings and future research directions.

\section{Literature Review}

According to \cite{sae2018taxonomy}, ride-sourcing is defined as ``prearranged and on-demand transportation services for compensation in which drivers and passengers connect via digital applications''. This definition includes a broad range of mobility modes. In this paper, we focus on TNCs for automobiles.

As one of the key operational strategies, ride-sourcing pricing has attracted increasing attention from various research community, including transportation (e.g., \citep{zha2018surge, zha2018geometric}), economics (e.g., \citep{chen2016dynamic, bimpikis2019spatial}), management science (e.g., \citep{guda2019your}) and computer science (e.g., \citep{chen2015peeking}). In addition, some studies on ride-sourcing modeling are closely related to research on taxi (e.g., \citep{yang1998network, lagos2000alternative,  yang2010equilibria, yang2011equilibrium, he2018pricing}) and two-sided marketplace (e.g., \cite{rochet2006two, rysman2009economics}). Given an increasingly large body of literature, we focus on the pricing issues in the context of ride-sourcing from transportation perspective, with references to other domains as needed.

The impacts of dynamics pricing on ride-sourcing driver supply are still inconclusive. The first conjecture, denoted as income-target theory, is that drivers quit driving once a daily income target is reached. This theory is pioneered by \cite{camerer1997labor}, who find negative wage elasticity of cabdriver supply in New York City. In contrast, the second conjecture, denoted as the neoclassical theory\citep{farber2005tomorrow}, suggests that cabdrivers are greedy for higher income, and cabdrivers supply has a positive wage rate elasticity. \cite{farber2005tomorrow} also points out that the differences between income-target theory and neoclassical theory are in the conception and measurement of the daily wage rate.  \cite{chen2016dynamic} provide empirical evidence for neoclassical theory using high-resolution UBER data. The coexistence of these two competing theories may explain the empirical evidence that the effect of dynamic pricing on UBER drivers supply is limited\citep{chen2015peeking}.  \cite{zha2018surge} propose a bi-level modeling framework, with lower level equilibrium considering both income-target theory and neoclassical theory, and find that compared to static pricing, surge pricing leads to higher revenue for both the platform and drivers, but lower customer surplus during highly surged periods. However, the majority of these studies focus on temporal dimension of dynamic pricing without considering spatial linkages or driver relocations. In this paper, due to the inconclusive impacts of dynamic pricing on driver supply, we assume that total driver supply is inelastic to spatial pricing, but drivers will respond to spatial pricing by choosing their service location.

Another school of literature investigate the potential value of dynamic pricing when market condition is stochastic\citep{banerjee2015pricing, cachon2017role, castillo2017surge, taylor2018demand, gurvich2019operations}. \cite{banerjee2015pricing} adopt a queueing-theoretical approach and find that dynamic pricing only outperform static pricing when TNCs have imperfect knowledge of system parameters. Although network model is presented, the pricing policies only depend on number of idle drivers at individual locations. \cite{castillo2017surge} consider the problem of ``wild goose chase'' when price is set too low, and find that dynamic pricing can avoid this issue and maintaining prices within a reasonable range. In contrast, in a deterministic setting, \cite{zha2018geometric} adopt a geometric matching framework and find that dynamic pricing may still set price higher than the societal efficient level. However, idle vehicle relocation behaviors is not considered in \citep{zha2018geometric}.

\cite{bimpikis2019spatial} are among the first to consider the spatial dimension of ride-sourcing pricing, by modeling whether and where drivers will join the platform, and where to relocate themselves when they are idle. \cite{bimpikis2019spatial} find that spatial pricing contributes to balance supply and demand, and more balanced demand patterns lead to higher profits and higher consumer surplus, simultaneously. However, the equilibrium formulation in \citep{bimpikis2019spatial} is indeterminate and the conclusion is, therefore, best seen as an ideal bound\citep{zha2018geometric}. In addition, since \cite{bimpikis2019spatial} mainly focus on the equilibrium of ride-sourcing services rather than traffic equilibrium, transportation topology and congestion effects are ignored. \cite{nie2017can} has indicated the concerns of ride-sourcing services on worsening the traffic congestion. A more recent working paper by \cite{ban2018general} using general equilibrium model to formulate the multi-agent interactions in an e-hailing system, has explicitly modeled traffic congestion under path independent free-flow travel time assumption. However, pricing are treated as exogenous parameters and not a focus in \citep{ban2018general}. We aim to fill this gap by proposing a mathematical tractable modeling framework for spatial pricing considering traffic equilibrium in a congested transportation network.

\section{Methodologies}\label{sec:meth}

\subsection{Problem Settings and Key Assumptions}
We assume that only one TNC serves in our study area, who aims to optimally decide the spatial prices to minimize demand and supply imbalance. We will consider different objectives in Section \ref{sec:nume} to illustrate the impacts of different TNC objectives on spatial pricing strategies. Due to the uncoordinated behaviors of a large number of drivers and riders, individual driver and rider do not have market power, and only respond to the spatial prices set by the TNC. We assume drivers make their relocation/pickup decisions based on locational attractiveness, relocation time, waiting time, and locational prices. Locational attractiveness could include factors such as safety, rider density, easiness of getting returning trips. The modeling framework is flexible to incorporate more explanatory factors if needed.  While drivers have flexibility to relocate themselves to other locations, travelers are typically not able to change their travel origin. We assume that the travel demand not requesting TNC services will shift to car driving. The interactions of drivers, riders, and other passenger vehicles will endogeneously determine the mobility of the transportation system. Notice that although trips originated from one location may have different trip distances with different prices, we assume that drivers and travelers will take the average prices originating from one location into their decision making processes. This assumption is consistent with the current practice that SMs are based on trip origins only. Heterogeneous demand, for example, trips with longer travel distance are more sensitive to spatial prices, can be incorporated into our proposed modeling framework without fundamental changes on  modeling and computational strategies.

In the remaining of this section, we present the mathematical models for two cases: ignoring and considering matching time.  Ignoring matching time, which is significantly easier to solve (see in Section \ref{sec:solu_meth}),  is appropriate especially when congestion is severe, and drivers and riders are balanced in one region (therefore waiting time is small compared to relocation/travel time). In addition, some riders may not be sensitive to waiting time as they can request rides earlier than their scheduled departure time. We note that ignored matching time is a special case of considering matching time case.

\subsection{Mathematical Modeling: Ignoring Matching Time}

For long-term transportation planning problem with congestion, the relocation time can significantly exceed the matching time. In this section, we ignore the impacts of matching time on the behaviors of drivers and riders. This assumption will be relaxed in Section \ref{sec:modeling_matching}.

\subsubsection{Traffic Modeling}
Denote a transportation network by a directed graph $\mathcal{G} = (\mathcal{N}, \mathcal{A})$ , where $\mathcal{N}$  is the set of nodes (indexed by $n$) and  $\mathcal{A}$ is the set of links (indexed by $a$).  The service area we consider is a metropolitan area where ride-sourcing demand and supply are aggregated in predefined zones (e.g., census tracts or 1 mile by 1 mile blocks), represented by nodes.  A link may represent a road section that connects two nodes. Given driver node set $\mathcal{R}$ ($\subset \mathcal{N}$) and rider node set $\mathcal{S}$ ($\subset \mathcal{N}$), drivers will relocate from $r$ ($\in \mathcal{R}$) to $s$ ($\in \mathcal{S}$) to pick up riders. Note that the relocation of drivers could be due to accepted matchings or voluntary relocations. Also note that if a driver decides to wait at his/her current location, or has accepted trip in the same area, $r = s$.  We assume that driver relocation decisions following multinomial logistic models, with explanatory variables of locational attractiveness $\beta_{0,s}$, relocation time $t_{rs}$, and locational prices $\rho_s$. The deterministic components of drivers' utility function are given in (\ref{eq:utility}).

\begin{equation}
\label{eq:utility}
U_{rs} = \beta_{0,s} -\beta_1 t_{rs} + \beta_2 \rho_{s}
\end{equation}
where:
\begin{description}[leftmargin=!,labelwidth=\widthof{12345}]
	\itemsep-0.7em
	\item[$U_{rs}$]: deterministic component of utility measure for a driver going from $r$ to $s$;
	\item[$\beta$] : utility function parameters (model input);
	\item[$t_{rs}$] : equilibrium travel time from $r$ to $s$;
	\item[$\rho_{s}$] : locational price at $s$.
\end{description}

While drivers have flexibility to relocate themselves to other locations, we assume riders are not able to change their travel origins. At each location $s$ ($\in \mathcal{S}$), we  assume a linear ride-sourcing demand function, as defined in (\ref{eq:demand}). One can adopt more sophisticated demand models, such as binary logit model in Section \ref{sec:modeling_matching}, to describe the ride-sourcing demand as a (decreasing) function of prices, which will lead to a similar single-level convex reformulation as illustrated in Section \ref{sec:solu_approach_ignore}.

\begin{equation}
\label{eq:demand}
d_{s} = D_s - b_s\rho_{s}
\end{equation}
where:
\begin{description}[leftmargin=!,labelwidth=\widthof{12345}]
	\itemsep-0.7em
	\item[$d_{s}$]: number of riders requested service at location $s$;
	\item[$D_s, b_s$] : coefficients of demand function (model input).
\end{description}

We assume that the total vehicle travel demand, including ride-sourcing travel and passenger vehicle travel, at location $s$ is given and denoted as $\bar{D}_s$. After been picked up by drivers, ride-sourcing riders, as well as other passenger vehicles, will travel at routes that minimize their own travel time. Since $t_{rs}$ is endogenously determined by traffic equilibrium, we extend combined distribution and assignment (CDA) model \citep{wilson1969use} to describe the interactions between drivers' relocation and the routing of all ride-sourcing vehicles and conventional passenger vehicles. The model is described in  (\ref{model:lower}).

\begin{subequations}
\begin{align}
& & & \underset{\bm{\hat{v}},\bm{\check{v}}, \bm{q} \in \reals_+}{\text{minimize}}
& & \sum_{a \in \mathcal{A}} \int_{0}^{v_a} t_a(v_a) \mathrm{d}u + \frac{1}{\beta_1} \sum_{r \in \mathcal{R}}\sum_{s \in \mathcal{S}} q_{rs}\left(\ln q_{rs} - 1 - \beta_2\rho_s - \beta_{0,s}\right)\label{obj:lower} \\
& & & \text{subject to} \nonumber & & \\
& & & & & \bm{v} = \sum_{r \in \mathcal{R}, s \in \mathcal{S}}\bm{\hat{v}}_{rs}+ \sum_{s \in \mathcal{S}, k \in \mathcal{K}}\bm{\check{v}}_{sk} , \; \label{cons:v}\\
& & & (\hat{\bm{\lambda}}_{rs}) & & A\bm{\hat{v}}_{rs} = q_{rs}E_{rs} , \; \forall r, s\label{cons:v_q}\\
& & & (\check{\bm{\lambda}}_{sk}) & & A\bm{\check{v}}_{sk} = \bar{d}_{sk}E_{sk} , \; \forall s, k\label{cons:v_d}\\
& & & ({\gamma}_{r})& &  \sum_{s \in \mathcal{S}}{q_{rs}} = Q_r, \; \forall r\label{cons:q_Q}\\
& & & ({\eta}_{sk})& &  \bar{d}_{sk} = \delta_{sk} \bar{D}_s,\; \forall s, k\label{cons:d_D}
\end{align}
\label{model:lower}
\end{subequations}

where:
\begin{description}[leftmargin=!,labelwidth=\widthof{12345}]
\itemsep-0.7em
\item[$\bm{\hat{v}}_{rs}, \bm{\check{v}}_{sk}$] : link flow vector (each row corresponds to a link, $a$) grouped by OD for drivers and passenger vehicles, respectively;
\item[$\bm{q}$] : drivers' relocation flow vector (each row corresponds to an OD, $rs$);
\item[$v_a$] : aggregate traffic flow on link $a$;
\item[$t_a(\cdot)$] : travel time function of link $a$;
\item[$A$] : node-link incidence matrix of network, with $1$ at starting node and $-1$ at ending node;
\item[$E_{rs}$] : O-D incidence vector of O-D pair $rs$ with $1$ at origin $r$, $-1$ at destination $s$. If $r=s$, $E_{rs} = \bm{0}$;
\item[$\bar{d}_{sk}$] : passenger vehicle traffic flow from $s$ to $k$;
\item[$\delta_{sk}$] : ratio of traffic going from $s$ to $k$ to total travel originating from $s$ (model input);
\item[$Q_{r}$] : drivers initial availability at $r$ (model input);
\item[$\bar{D}_{s}$] : number of vehicles departing from $s$, including conventional passenger vehicles and ride-sourcing vehicles (model input);
\item[$\check{\lambda}, \hat{\lambda}, \gamma, \eta$] : dual variables of the corresponding constraints.
\end{description}

Constraint (\ref{cons:v}) calculates the aggregate link flow $v_a$ from the link flow associated with OD pairs $rs$ and $sk$. Constraints (\ref{cons:v_q}, \ref{cons:v_d}) are link-based formulations of flow conservation at each node for each OD pair. Constraint (\ref{cons:q_Q}) assumes the total drivers availability $Q_r$ at each location $r$ is inelastic, even though the relocation demand of drivers to each location $s$ is elastic and depends on the factors described in (\ref{eq:utility}). Constraint (\ref{cons:d_D}) calculates the distribution of riders and other conventional passenger vehicles OD demand.

In the objective function (\ref{obj:lower}), the first term corresponds to the total user cost as modeled in a conventional static traffic equilibrium model \citep{beckmann1956studies}, the second term involving $q^{rs}\ln q^{rs}$ corresponds to the entropy of trip distribution, and the remaining terms correspond to the utility measure of the drivers.  This objective function does not have a physical interpretation, as pointed out by \cite{Sheffi_85}, but it guarantees the first Wardrop principle \citep{Wardrop_52} and the multinomial logit location choice assumption being satisfied, as formally stated in {\bf Lemma \ref{lem:CDA}}.

\begin{lemma}{(combined distribution and assignment for ride-sourcing system)}\label{lem:CDA}
The optimal solutions $(\bm{\hat{v}^\ast},\bm{\check{v}^{\ast}}, \bm{q^\ast} )$ of  problem (\ref{model:lower}) are the equilibrium solutions for Wardrop user equilibrium and the relocation choice of drivers with multinomial logit model (\ref{eq:utility}) given spatial prices $\bm{\rho}$.
\end{lemma}

\state Proof. See \ref{app:pfs}.
\eop

\subsubsection{TNC Behaviors}

The pricing decisions of a TNC will influence the equilibrium solutions of (\ref{model:lower}), which forms a mathematical programming with equilibrium constraints (MPEC) problem. The objective of a TNC could be balancing supply and demand, maximizing matches, profits, market shares, services quality, minimizing total relocation distance, etc. In this paper, we assume that a TNC would like to minimize the imbalance between supply and demand \footnote{Balancing supply and demand is the goal of dyanmaic pricing claimed by all  TNC companies. See, for example, https://www.ridester.com/training/lessons/surge-primetime-boost-primezones/ (visited on Sep. 26, 2019).}, which has the advantage to improve driver/rider satisfactory and ultimately leads to a long-term sustainable development. Comparison between different objectives (minimizing imbalance versus maximizing short-term profits) will be presented in Section \ref{sec:nume}. The TNC decision making can be modeled as the upper-level problem, as formulated in (\ref{model:upper}).

\begin{subequations}
\begin{align}
& \underset{\boldsymbol{\rho} \in \reals^{S}}{\text{minimize}}
& &\sum_{s \in \mathcal{S}} m_s \label{obj:upper}\\
& \text{subject to}  & & \nonumber \\
& && m_s = |\sum_{r \in \mathcal{R}} q_{rs}- ({D}_s - b_s\rho_s)|, \ \forall s \label{cons:matches}\\
& && (\ref{model:lower})
\end{align}
\label{model:upper}
\end{subequations}
where:
\begin{description}[leftmargin=!,labelwidth=\widthof{12345}]
\itemsep-0.7em
\item[$m^{s}$] : demand-supply imbalance at $s$.
\end{description}

Obejective (\ref{obj:upper}) minimizes the total demand-supply imbalance over the study area. Constraint (\ref{cons:matches}) calculates the imbalance as the difference between the number of riders requesting services ${D}_s - b_s \rho_s$ and the number of drivers arriving at this location $\sum_{r \in \mathcal{R}}q_{rs}$. While constraint (\ref{cons:matches}) can be reformulated as linear constraints, the bi-level structure still makes the whole problem challenging to solve to global optimal \citep{yang1998models, gao2005solution, sinha2017review}. In Section \ref{sec:solu_meth}, we propose an equivalent single-level convex reformulation of (\ref{model:upper}), which can be efficiently solved by commercial nonlinear solver (e.g. IPOPT \citep{wachter2009short}) or by classic traffic assignment algorithms (e.g. Frank-Wolfe algorithm \citep{Sheffi_85} or Evans' procedure \citep{evans1976derivation}). To investigate the transportation impacts, the spatial pricing models presented in this paper mainly focus on peak hours, so that we do not explicitly address the unmatched, if any, riders and drivers in the following time steps. The unserved customers could keep requesting ride-sourcing services, or switch to other transportation modes, such as driving. The idle ride-sourcing vehicles will decide whether to stay, relocate, or leave the platform. Their decisions will determined the drivers initial availability and riders demand function for the next time step.

\subsection{Mathematical Modeling: Considering Matching Time}\label{sec:modeling_matching}

In this section, we explicitly model the impacts of matching time. Similar to \cite{zha2016economic}, we assume the matching rate $m$ has constant elasticity with respect to vacant drivers $N_D$ and waiting riders $N_R$, which leads to a Cobb-Douglas matching function $m = \alpha_0(N_D)^{\alpha_1}(N_R)^{\alpha_2}$. In contrast to \citep{zha2016economic}, we do not assume a stationary state, i.e. we assume driver arrival rate, rider requesting rate, and matching rate are close but may not be equal during our studied periods. This relaxation could be helpful as we can see in Section \ref{sec:nume} that dynamic pricing does not guarantee supply-demand balance even in theory.

Denote the locational \footnote{We omit location index for simplicity.} average and total waiting time for drivers (D) and riders (R) as $t_D$, $T_D$, $t_R$, and $T_R$, respectively.  $\forall i \in \{D, R\}$, the average waiting time for $i$ can be calculated in (\ref{eq:waiting}), which is explained graphically in \ref{app:explain}.
\begin{subequations}
\begin{align}
& \Dot{N}_i(t) = f_i - m(t) = f_i - \alpha_0N_D^{\alpha_1}(t)N_R^{\alpha_2}(t), \label{eq:vacant}\\
& T_i = \int_{0}^{T}N_i(t) d{t}, \ \forall i \in \{D, R\} \label{eq:total_time}\\
& t_i = \frac{T_i}{f_iT} = \frac{\int_{0}^{T}N_i(t) d{t}}{f_iT},  \label{eq:average_time}
\end{align}
\label{eq:waiting}
\end{subequations}
where $f_{D}$ ($f_{R}$) is the ride-sourcing supply (demand) flow rate, and $T$ is the study period (e.g., peak hour). (\ref{eq:vacant}) is the dynamics of vacant drivers and waiting riders; (\ref{eq:total_time}) and  (\ref{eq:average_time}) calculate the total and average waiting time for drivers and riders over $T$. While solving (\ref{eq:waiting}) analytically is challenging, $t_i$ ($\forall i \in \{D, R\}$) can be solved numerically given $f_D, f_R$ and boundary conditions $N_D(0), N_R(0)$. We then apply linear regression techniques to estimate the relationship between $t_i$ and $f_i$, $\forall i \in \{D, R\}$, with a function form shown in (\ref{eq:waiting_time_flow}). When $\alpha_0 = 0.1, \alpha_1 = \alpha_2 = 0.6$, we have $a_0 = 6.29, a_1 = 2.24, a_2 = -2.40$ as least square estimators. $|a_2| > |a_1|$ implies increasing return of scale for matching rate. The regression summary output (Figure \ref{fig:regression_output}) is presented in \ref{app:explain}.
\begin{equation}
t_{i} = a_0 f_{i}^{a_1}f_{-i}^{a_2}\quad \forall i \in \{D, R\}\label{eq:waiting_time_flow}
\end{equation}

\begin{figure*}[htbp]
	\centering
	\makebox[1.0\linewidth][c]{
		\begin{subfigure}[t]{.25\linewidth}
			\centering
			\caption{Original Network}
		\includegraphics[width=1\linewidth]{./Figures/three_node.pdf}
			\label{fig:three_node}
		\end{subfigure}
		\begin{subfigure}[t]{.75\linewidth}
			\centering
			\caption{Augmented Network}
			\includegraphics[width=1\linewidth]{./Figures/seven_node.pdf}
			\label{fig:seven_node}
	\end{subfigure}}
	\vspace{-2em}
	\caption{Illustration of Network Augmentation}
	\label{fig:aug_graph}
\end{figure*}

To incorporate matching time in a unified CDA framework, we define an augmented transportation network, $\bar{\mathcal{G}} = (\bar{\mathcal{N}}, \bar{\mathcal{A}})$. The augmenting procedures from  ${\mathcal{G}}$ to $\bar{\mathcal{G}}$ is illustrated in Figure \ref{fig:aug_graph} using a three-node transportation network, which has one driver node (node 1) and two rider nodes (node 2 and 3). For each rider node $s$ in Figure \ref{fig:three_node}, we created $s$, $s'$, and $s''$, representing nodes for markets, connectors, riders, respectively, with directed links connecting between them as shown in Figure \ref{fig:seven_node}. In augmented network $\bar{\mathcal{G}}$, link flow $f_{s's}$, $f_{s''s}$ and $f_{s''s'}$ represent the flow of driver supply, rider demand, and travelers choosing to drive at node $s$, while the link cost $t_{s's}$ and $t_{s''s}$ are the waiting time for drivers ($t_{D,s}$) and riders ($t_{R,s}$), respectively. If travelers choose to drive, there is no waiting time, so that link cost $t_{s''s'} = 0$.

With an augmented network $\bar{\mathcal{G}}$, the utility function of drivers is identical with (\ref{eq:utility}). Note that $t_{rs}$ in (\ref{eq:utility}) will include not only the travel time from $r$ to $s'$, $t_{rs'}$, but also the matching time at $s$, $t_{s's}$. The drivers relocation and routing behaviors, therefore, can be modeled as (\ref{model:lower}) (replacing $\mathcal{G}$ with $\bar{\mathcal{G}})$, given riders demand $\bm{f}_{R}$ and spatial pricing $\bm{\rho}$.

For travelers at location $s$, the ride requesting demand function is not only depends on the prices $\rho_s$, but also depends on the waiting time, $t_{s''s}$. We assume that the choice of ride-sourcing over driving follows a binary logit model, with ride-sourcing utility function as (\ref{eq:utility_riders}),

\begin{equation}
\label{eq:utility_riders}
U_{s''s} = \beta_{0,s}' -\beta_1' t_{s''s} - \beta_2' \rho_{s}
\end{equation}
where $\beta_{0,s}', \beta_{1}', \beta_{2}'$ are the utility coefficients for ride-sourcing attractiveness, waiting time, and ride-sourcing prices. We assume driving and ride-sourcing will have the same travel time, therefore, travel time will be canceled out and does not need to be included in (\ref{eq:utility_riders}). Since the rider demand couples with waiting time (see (\ref{eq:waiting_time_flow}) and (\ref{eq:utility_riders})), the rider behaviors at each location $s$ can be formulated as a CDA model (\ref{model:lower_rider}) as well, where the first term corresponds to the conventional Wardrop user equilibrium, and the second term reflects the binomial logit choice between ride-sourcing and driving.

\begin{equation}
\underset{{f}_{R,s} \in \reals_+}{\text{minimize}}\quad \int_{0}^{f_{R,s}} t_{R,s}(f_{D,s},u) \mathrm{d}u + \frac{1}{\beta_1'} \left[f_{R,s}\left(\ln f_{R,s} - 1 + \beta_2'\rho_s - \beta_{0,s}'\right) + (D_s - f_{R,s})\left(\ln (D_s - f_{R,s}) - 1  \right)\right]
\label{model:lower_rider}
\end{equation}

Similar to formulation (\ref{model:upper}) for ignoring matching time case, the TNC decision making considering matching time can be modeled as bilevel problem, as shown in (\ref{model:upper_matching}), where objective (\ref{obj:upper}) minimizes total demand-supply imbalance (calculated by (\ref{cons:matches})), subject to drivers, riders, and all other travelers user equilibrium ((\ref{model:lower}, \text{replacing $\mathcal{G}$ with $\bar{\mathcal{G}}$}) and  (\ref{model:lower_rider})).

\begin{subequations}
\begin{align}
& \underset{\boldsymbol{\rho} \in \reals^{S}}{\text{minimize}}
& &(\ref{obj:upper}) \\
& \text{subject to}  & & \nonumber \\
& && (\ref{cons:matches}) ,  (\ref{model:lower}, \text{replacing $\mathcal{G}$ with $\bar{\mathcal{G}}$}) ,  (\ref{model:lower_rider})
\end{align}
\label{model:upper_matching}
\end{subequations}

\section{Solution Approach}\label{sec:solu_meth}

\subsection{Solution Approach: Ignoring Matching Time} \label{sec:solu_approach_ignore}
We start by showing that when problem (\ref{model:upper}) is solved to optimal, the ride-sourcing market will be balanced at each location. In addition, optimal solutions $\bm{\rho}^*$ is unique. This is more formally stated in Lemma \ref{lem:balance_matches}.

\begin{lemma}{(balancing ride supply and demand)} \label{lem:balance_matches}
$\bm{\rho}^*$ optimizes problem (\ref{model:upper}) if and only if ride supply and demand are balanced at each location given $\bm{\rho}^*$. In addition, $\bm{\rho}^*$ is unique.
\end{lemma}

\state Proof. See \ref{app:pfs}.
\eop

Lemma \ref{lem:balance_matches} says that problem (\ref{model:upper}) is equivalent to the problem of finding the unique $\bm{\rho}^{\ast}$ that balance supply and demand at each location. Notice that $\bm{\rho}$ can be negative under extreme scenarios, when too many drivers exist in the system and TNC may provide incentives for riders to use ride-sourcing services. However, this will not happen in reality given reasonable driver supply $Q_r$, since drivers will dynamically respond to extreme low prices\citep{bimpikis2019spatial}. Leveraging Lemma \ref{lem:balance_matches}, the optimal spatial prices can be obtained by solving a single-level convex optimization problem, which will be illustrated in the remaining of this section.

Problem (\ref{model:upper}) has three types of agents: drivers, riders, and TNC. Because of Lemma \ref{lem:balance_matches}, the decision making of TNC can be reformulated as finding $\bm{\rho}^*$ such that

\begin{equation}
\label{cons:market_clearing}
    \sum_{r \in \mathcal{R}} q_{rs}^{\ast}(\bm{\rho}^*) = D_s - b_s\rho_{s}^{\ast}, \forall s \in \mathcal{S}
\end{equation}
where $q_{rs}^{\ast}(\bm{\rho}^*)$ is the optimal solutions of (\ref{model:lower}) given $\bm{\rho}^*$. This problem falls within the framework of multi-agent optimization problem with equilibrium constraints (MOPEC) \citep{ferris2013mopec}, where drivers make relocation decisions; riders decide whether to request ride-sourcing services; all travelers make route choices decisions; and the system is subject to equilibrium conditions (\ref{cons:market_clearing}). MOPEC has been applied in transportation, energy, economics domains, such as charging infrastructure planning \citep{Guo_et_al_16}, hydro-thermal electricity systems optimization \citep{philpott2016equilibrium}, renewable energy supply chain planning \citep{guo2017stochastic}, and computational Walrasian equilibrium \citep{deride2019solving}.

Define two types of dummy agents in our problem, $Driver$ and $Rider$. Given $\bm{\rho}$, $Driver$ solves problem (\ref{model:lower}), which determines the drivers relocation decision from $r$ to $s$, $q_{rs}(\bm{\rho}), \forall r, s$; and $Rider$ solves problem (\ref{model:demand}), which determines the riders demand $d_s(\bm{\rho})$ at each location $s$. Note that problem (\ref{model:demand}) is a constructed unconstrained quadratic programming problem, which has a closed-form solution $d_s^{\ast}(\bm{\rho}) = D_s - b_s \rho_s, \forall s \in \mathcal{S}$, identical to the demand function (\ref{eq:demand}) we assumed.

\begin{equation}
\label{model:demand}
\underset{\bm{d} \in \reals^{S}}{\text{maximize}} \ \ \sum_{s \in \mathcal{S}} D_s d_s - b_s\rho_s d_s - \frac{1}{2}(d_s)^2
\end{equation}

The equilibrium constraints (\ref{cons:market_clearing}) can be reformulated as (\ref{model:equilibrium_constraints}).

\begin{equation}
\label{model:equilibrium_constraints}
\sum_{r \in \mathcal{R}} q_{rs}^{\ast}(\bm{\rho}) = d_s^{\ast}(\bm{\rho}), \forall s \in \mathcal{S}
\end{equation}

Notice that both the objective functions of (\ref{model:lower}) and (\ref{model:demand}) consist of terms regarding prices times quantities, i.e., $\sum_{r \in \mathcal{R}}\rho_sq_{rs}$ and $\rho_sd_s$. In addition, notice that the equilibrium constraints (\ref{model:equilibrium_constraints}) are quantity balance of $\sum_{r \in \mathcal{R}}q_{rs}$ and $d_s$. Inspired by Lagrange multiplier method, we construct a single-level convex optimization problem (\ref{model:combine}), which will yield the same spatial pricing decisions as bilevel formulation, as stated in Theorem \ref{thm:combine}.

\begin{theorem}{(single-level convex reformulation)}\label{thm:combine}
$\bm{\rho}$ solves bi-level problem (\ref{model:upper}) if and only if $\bm{\rho}$ solve single-level problem (\ref{model:combine}).
\end{theorem}

\state Proof. See \ref{app:pfs}.

\begin{subequations}
\begin{align}
& & & \underset{\bm{\hat{v}},\bm{\check{v}}, \bm{q}, \bm{d} \in \reals_+}{\text{minimize}}
& & \frac{\beta_1}{\beta_2}\sum_{a \in \mathcal{A}} \int_{0}^{v_a} t_a(v_a) \mathrm{d}u + \frac{1}{\beta_2} \sum_{r \in \mathcal{R}}\sum_{s \in \mathcal{S}} q_{rs}\left(\ln q_{rs} - 1 - \beta_{0,s}\right) + \sum_{s \in \mathcal{S}}\frac{1}{b_s}(\frac{d_s^2}{2} - D_sd_s)\label{obj:combine} \\
& & & \text{subject to} \nonumber & & \\
& & & & & (\ref{cons:v} \sim \ref{cons:d_D}) \nonumber\\
& & & ({\rho}_{s})& &  \sum_{r \in \mathcal{R}} q_{rs} = d_s,\; \forall s\label{cons:q_d}
\end{align}
\label{model:combine}
\end{subequations}

The objective function (\ref{obj:combine}) is a combination of scaled objective functions (\ref{obj:lower}) and (\ref{model:demand}) without $\sum_{r \in \mathcal{R}}\rho_sq_{rs}$ and $\rho_sd_s$ terms. The purpose of scaling (\ref{obj:lower}) and (\ref{model:demand}) is to convert the units of both objective functions into \$ so that they are addable. In addition, the optimal dual variables $\rho_s^{*}$ of constraints (\ref{cons:q_d}) will unit in \$ and balance supply and demand at each location. Therefore, $\bm{\rho}^{*}$ can be interpreted as spatial prices to solve problem (\ref{model:upper}) based on Lemma \ref{lem:balance_matches}.

Problem (\ref{model:combine}) is a non-linear convex problem, with convex objective function and linear constraints. So it can be solved to global optimal by commercial nonlinear solver, such as IPOPT, relatively efficiently. For extreme large-scale problems, this reformulation opens up opportunities to apply classic and efficient transportation network solution algorithm, such as Frank-Wolfe algorithm \citep{Sheffi_85} and Evans' procedure \citep{evans1976derivation}. In this paper, we focus on small/medium transportation networks to draw policy insights, and leave the development of advanced algorithms for large network in the future.

\subsection{Solution Approach: Considering Matching Time}

Directly solving TNC upper-level problem (\ref{model:upper_matching}) may be challenging due to highly non-convexity. We restate (\ref{model:upper_matching}) as a problem of finding a maxinf-point for an appropriate bivariate function (bi-function) $W(\bm{\rho},\bm{\phi})$. This conversion is inspired by a recent theoretical development on variational convergence of bifunction by \cite{jw_09}, which offers the flexibility of constructing a bifunction and allows one to choose a sequence of bifunctions with desired properties (including convexity and continuity) to approximate the original bifunction.  A similar approach has been successfully implemented in \citep{Guo_et_al_16, deride2019solving}. In this paper, we highlight the key steps of the algorithm design.

We introduce the \emph{Walrasian}
function associated with this equilibrium problem, defined as

\[W(\bm{\rho},\bm{\varphi})=-\sum_{s\in \mathcal{S}} \varphi_s{\rm ES}_s(\bm{\rho}),\quad {\rm on }\, \reals^S\times\Delta_S,\]

\noindent where $\Delta_S$ corresponds to the $S$-dimensional unit simplex. $\rm{ES_s}$ is the square of demand-supply imbalance, defined in (\ref{eq:excess_supply}).

\begin{equation}
{\rm ES}_s(\bm{\rho}) = \left[\sum_{r \in \mathcal{R}}q_{rs}^{\ast}(\bm{\rho}) - f_{R,s}^{\ast}(\bm{\rho})\right ]^2, \; \forall s \in \mathcal{S}
\label{eq:excess_supply}
\end{equation}
where $q_{rs}^{\ast}$ and $f_{R,s}^{\ast}$ are the optimal solutions (as a function of $\bm{\rho}$) of problem (\ref{model:lower}, replacing $\mathcal{G}$ with $\bar{\mathcal{G}}$) and (\ref{model:lower_rider}), respectively.

The relationship between maxinf point of $W(\bm{\rho},\bm{\varphi})$ and the demand-supply balancing (equilibrium) prices is stated in Lemma \ref{lem:mieq}.

\begin{lemma}{(equilibrium prices and maxinf-points)}\label{lem:mieq}
For $\bm{\rho} \in\reals^S$, $\bm{\rho}$ is a maxinf-point of the Walrasian function $W$ such that $W(\bm{\rho}, \cdot) \geq 0$,
on $\Delta_S$ if and only if $\bm{\rho}$ is an equilibrium point.
\end{lemma}

\state Proof. See \ref{app:pfs}. \eop

Since $\inf_{\bm{\varphi}} W(\bm{\rho},\bm{\varphi})$ is lack of concavity in $\bm{\rho}$, we apply an \emph{augmented Lagrangian}
for this non-concave formulation. Given sequences of nonegative, nondecreasing scalars $\{r^\nu\},\,\{M^\nu\}$, one can define the sequence of \emph{augmented Walrasian}
functions for this problem as
\begin{equation}
    W^\nu(\bm{\rho},\bm{\varphi})=\inf_{\bm{z}}\left\{\left.W(\bm{\rho},\bm{z})+\frac{1}{2r^\nu}|\bm{z}-\bm{\varphi}|^2\right|\bm{z}\in\Delta_S\right\},{\rm on }\, [\bm{\rho}^{\nu -1}-M^\nu,\bm{\rho}^{\nu-1}+M^\nu]\times\Delta_S
\end{equation}

The idea of this procedure is to approximate the problem of finding maxinf-points of the original Walrasian function $W$, by computation of approximate maxinf-points $\bm{\rho}_\varepsilon$ (see Definition \ref{def:approx_maxinf}) given by a sequence
of augmented Walrasians $W^\nu$, which are easier to solve. The convergence theorem of the proposed approximation scheme is stated in Theorem \ref{thm:algo_lopconv}.

\begin{defn}{(approximating equilibrium point)}
$\bm{\rho}_\varepsilon$ is an
$\varepsilon$-approximating equilibrium point, denoted as $\varepsilon-\nargmaxinf W$, for $\varepsilon\geq 0$, if the following inequality holds:
$\left|\ninf W(\bm{\rho}_\varepsilon,\cdot)- \nsupinf W\right|\leq \varepsilon.$
\label{def:approx_maxinf}
\end{defn}

\begin{theorem}{(convergence of approximating maxinf-points)}\label{thm:algo_lopconv}

Suppose that $\nsupinf W$ is finite. Consider non-negative sequences $\{r^\nu\}$, $\{M^\nu\}$, and $\{\varepsilon^\nu\}$
such that $r^\nu \upto \infty$, $M^\nu\upto \infty$, $\varepsilon^\nu\downto 0$. Let $\{W^\nu\}$
be a family of augmented Walrasian functions associated with each parameters $r^\nu$ and $M^\nu$.

Let $\bm{\rho}^\nu\in\varepsilon^\nu-\nargmaxinf W^\nu$,
and $\bm{\rho}^*$ be any cluster point of $\{\bm{\rho}^\nu\}$. Then $\bm{\rho}^*\in\nargmaxinf W$.
\end{theorem}

\state Proof. See \citep{Guo_et_al_16}. \eop

Following Theorem \ref{thm:algo_lopconv}, we propose the computational algorithm, as summarized in Algorithm \ref{alg:iter}, to achieve a sequence of approximating maxinf-points.

\begin{algorithm}[H]

	\KwResult{$\boldsymbol{\rho}^{\nu}$}
	initialization: $\nu = 0$, $\varepsilon^0$, $M^0$, $r^0$, ${\rm gap}^0$, $\boldsymbol{\rho}^0$, $\epsilon$, $0<c_1<1$, $c_2>1$\;

	\While{${\rm gap}^{\nu} \geq \epsilon$}{

	Phase I: solve the minimization problem $\bm{\varphi}^{\nu+1}\in\nargmin W^{\nu+1}(\bm{\rho}^\nu,\cdot)$\;

    Phase II: solve the maximization problem $\bm{\rho}^{\nu+1}\in\nargmax W^{\nu+1}(\cdot,\bm{\varphi}^{\nu+1})$\;

    evaluate: ${\rm ES}_s(\bm{\rho}^{\nu+1}), s \in \mathcal{S}$ \;

    let: $gap^{\nu+1} = \max\{{\rm ES}_s(\bm{\rho}^{\nu+1}), s \in \mathcal{S}\}$\;

	let: $\varepsilon^{\nu+1} = c_1\varepsilon^{\nu}$, $M^{\nu+1} = c_2M^{\nu}$, $r^{\nu+1} = c_2 r^{\nu}$\;

	let: $\nu := \nu + 1$
	}
	\caption{Approximating Maxinf-Point Algorithm}
	\label{alg:iter}
\end{algorithm}

Phase I consists of the minimization of a quadratic objective function over the $S$-dimensional simplex. This can be solved using Cplex/Gurobi solver. Phase II is done without considering first order information (due to a lack of concavity) and relying on BOBYQA algorithm \citep{Pow09:bobyqa}, which performs a sequentially local quadratic fit of the objective functions, over box constraints, and solves it using a trust-region method. As $r^\nu\upto \infty$, and $M^\nu\upto\infty$, and $\varepsilon^\nu\downto 0$, in virtue of Theorem \ref{thm:algo_lopconv}, $\bm{\rho}^\nu\to\bm{\rho}^*$, a maxinf-point of $W$.

\noindent{\bf Remarks}:

1. The network augmenting procedures proposed in Section \ref{sec:modeling_matching} result in a transportation network with non-separable link-cost function (i.e., $t_{D}$ and $t_R$), and the Jacobian of link-cost function is asymmetric, for which there is no known mathematical program whose solutions are the equilibrium flow pattern \citep{Sheffi_85}. But, the traffic equilibrium solutions can be achieved by diagonalization method \citep{Sheffi_85}.  We note that since the Jocobian of the link-cost functions is not positive definite when $|a_1|\; \leq|a_2|$ and $f_{D,s} \approx f_{R,s}$, the convergence of traffic equilibrium is not guaranteed in theory, although the algorithm may still convergence when this condition is violated \citep{fisk1982solution}. To make our algorithm robust to non-convergence of traffic equilibrium, the algorithm we develop here does not require convergence for every iteration.

2. Notice that problem (\ref{model:upper_matching}) has at least $|\mathcal{S}|$ trivial equilibrium solutions, where only one location $s$ attracts all the drivers $\sum_{r \in \mathcal{R}} Q_r$. This is because when driver supply approaches 0 and price is finite at one location, rider demand will also approach 0 due to infinite waiting time, and vice versa. The insight from this is that ride-sourcing market may need a critical mass of drivers and riders to sustain. In this paper, we only focus on non-trivial equilibrium.

\section{Numerical Examples} \label{sec:nume}
In this section, we test our models and solution approaches on a three-node system (Figure \ref{fig:three_nodes}) and Sioux Falls network (Figure \ref{fig:siou_fall}). We implement our model on Pyomo 5.6.6 \citep{hart2017pyomo}. We solve the problems using IPOPT 3.12.13 \citep{wachter2009short} for ignoring matching time case, and Cplex 12.8 \& BOBYQA (in NLopt 2.4.2) for considering matching time case, both with 0.1\% optimality gap. All the numerical experiments presented in this section were run on a 3.5 GHz Intel Core i5 processor with 8 GB of RAM memory, under Mac OS X operating system.

\subsection{Three-node Network}
The three-node test instance (Figure \ref{fig:three_nodes}) has one driver node (node 1) and two demand nodes (node 2 and 3). 50 drivers decide where to pick up riders at node 1. $\beta_0 = 0, \beta_1 = 1, \beta_2 = 0.6$. The link travel time has a form of $t_a = t_a^0[1+0.15*(v_a/c_a)^2]$, where $t_a^0$ is the free flow travel time and $c_a$ is the link capacity parameter. The value of $t_a^0$ and $c_a$ for each link are shown in Figure \ref{fig:three_nodes}. Notice that this test instance is symmetric except that links between node 1 and 3 have lower capacity. Through out Section \ref{sec:nume}, background traffic is not considered.

\begin{figure}[htbp]
\begin{center}
    \includegraphics[width=0.5\textwidth]{./Figures/three_nodes.pdf}
\caption{Three Nodes Test Network}
\label{fig:three_nodes}
\end{center}
\end{figure}

\subsubsection{Ignoring Matching Time}
We assume both node 2 and 3 have a demand function of $d_s = 300 - 5\rho_s$. Solving this problem using our single-level reformuation (\ref{model:combine}), we have $\rho_2 = 53.5, \rho_3 = 56.5$.  Notice that with these locational prices, the demand market at both node 2 and 3 are balanced. The difference between $\rho_2$ and $\rho_3$ is because of the link congestion between node 1 and 3. In other words, node 3 is more congested to travel to due to limited link capacity, so that to attract more drivers to pick up riders at node 3, TNC needs to offer a higher locational price. If TNC doesn't consider transportation congestion, the optimal locational prices are $\rho_2' = \rho_3' = 55.0$, which will lead to unbalance of supply and demand on both demand nodes in reality. These optimal solutions are validated by applying global solver SCIP \citep{achterberg2009scip} directly on mixed-integer nonlinear programming (MINLP) reformulation of bi-level problem (\ref{model:upper}). Reformulating bi-level problem into MINLP is standard, so we omit the detail procedures for conciseness. For three-node example, our reformulation (\ref{model:combine}) can be solved by IPOPT in 0.1 seconds, while MINLP formulation takes SCIP 5.6 seconds to solve. Although both SCIP and IPOPT solve the problem for global optimal, MINLP formulation is sensitive to the selection of big-M parameters, which is a challenging issue for mixed integer programming with switching constraints \citep{guo2016contingency}.

Because TNC aims to balance supply and demand, transportation congestion can be worse under spatial pricing. We compare between two scenarios, surge pricing and uniform pricing. If we change from uniform pricing to surge pricing, the total travel time increases slightly from 1333 to 1336. The increase of total travel time is because TNC gives incentive (surge pricing) to drivers traveling through congested area in order to balance demand. This result matches the empirical findings in \citep{nie2017can} that ride-sourcing may increase transportation congestion compared to taxi services. Regulations will be needed to prevent pricing selfishly by TNCs to improve overall transportation mobility, especially in congested area.

Next, we compare the impacts of TNC's objectives between maximizing profits and minimizing imbalance. The problem of maximizing profits is shown in (\ref{model:upper2}).

\begin{subequations}
\begin{align}
& \underset{\boldsymbol{\rho} \in \reals^{S}}{\text{maximize}}
& &\sum_{s \in \mathcal{S}} \rho_s n_s \label{obj:upper2}\\
& \text{subject to}  & & \nonumber \\
& && n_s = \min(\sum_{r \in \mathcal{R}} q^{rs}, {D}^s - b^s\rho_s), \ \forall s \label{cons:matches2}\\
& && (\ref{model:lower})
\end{align}
\label{model:upper2}
\end{subequations}
where:
\begin{description}[leftmargin=!,labelwidth=\widthof{12345}]
\itemsep-0.7em
\item[$n_{s}$] : ride-sourcing matches at $s$.
\end{description}

(\ref{obj:upper2}) maximizes total revenues. Since the majority of TNC operating costs go to sales, marketing, administrative, and R\&D \footnote{https://news.crunchbase.com/news/understanding-uber-loses-money/}, we assume that operational costs for TNC is independent of spatial pricing and drivers/riders flow, so the optimal pricing maximizes total revenues will also maximize total profits in the service territory. But we note that operating costs can be easily incorporated in (\ref{obj:upper2}) if operating costs data is available. (\ref{cons:matches2}) calculates the matches at each location $s$. For problem (\ref{model:upper2}), we are not able to directly make the single-level reformulation as in (\ref{model:combine}). So we solve the bilevel problem (\ref{model:upper2}) as MINLP using SCIP solver. The numerical results are shown in Figure \ref{fig:obj_supply} and Figure \ref{fig:obj_demand} , in which we conduct sensitivity analyses of the total number of drivers and interception of demand function on equilibrium prices with different TNC's objectives. When TNC aims to minimize imbalance for each location, the optimal prices are almost linearly decreasing (increasing) with increasing of supply (demand) for this toy test instance. The trend of optimal prices are slightly more complex when TNC aims to maximize profits. When supply is relatively high or demand is relatively low, TNC's profits are not restricted by drivers availability, so that TNC will set prices converge to monopoly prices, which are $D^s/2b^s, \forall s$. This means that when TNCs aim to maximize profits, the supply and demand may not necessarily balanced at each location. This finding is consistent with the results in \citep{bimpikis2019spatial} where endogenously determined spatial prices aiming to maximize profits may not always balance supply and demand. Notice that when demand is comparable to supply, prices minimizing imbalance of ride requests are identical with prices maximizing TNC profits, which indicates that maximizing balance of supply and demand leads to maximum profits for TNC.

\begin{figure*}[htbp]
	\centering
	\makebox[1.0\linewidth][c]{
		\begin{subfigure}[t]{.5\linewidth}
			\centering
			\caption{Sensitivity on Supply}
			\includegraphics[width=1\linewidth]{./Figures/obj_supply.pdf}
			\label{fig:obj_supply}
		\end{subfigure}
		\begin{subfigure}[t]{.5\linewidth}
			\centering
			\caption{Sensitivity on Demand}
			\includegraphics[width=1\linewidth]{./Figures/obj_demand.pdf}
			\label{fig:obj_demand}
	\end{subfigure}}
	\vspace{-2em}
	\caption{Impacts of Supply and Demand on Optimal Surge Pricing}
	\label{fig:senstivity_price}
\end{figure*}

\subsubsection{Considering Matching Time}
When matching time cannot be ignored for both drivers' and riders' decision making, we can solve problem (\ref{model:upper_matching}) using Algorithm \ref{alg:iter}. We assume $D_s = 300, \; \forall s$. The riders' utility coefficients $\beta_0' = 0, \beta_1' =1, \beta_2' = 0.6$.

With different initial locational prices, the convergence pattern of prices and ES are shown in Figure \ref{fig:three_node_conv}. The average computation time is 27.8s, and all of the experiments converged efficiently to the same equilibrium solutions, $\rho_2^* = 37.4, \rho_3^* = 38.0, f_{D,2}^*=f_{R,2}^* = 33.1, f_{D,3}^* = f_{R,3}^* = 16.9$. Notice that TNC offers a slightly higher price at location 3, which is more congested to travel to. This observation is consistent with the observation in ignoring matching time case.

\begin{figure*}[htbp]
	\centering
		\begin{subfigure}[t]{.49\linewidth}
			\centering
			\caption{$\bm{\rho}^{0} \in [10, 20]$}
			\includegraphics[width=1\linewidth]{./Figures/rho10_20.pdf}
			\label{fig:rho_1020}
		\end{subfigure}
		\begin{subfigure}[t]{.49\linewidth}
			\centering
			\caption{$\bm{\rho}^{0} \in [20, 30]$}
			\includegraphics[width=1\linewidth]{./Figures/rho20_30.pdf}
			\label{fig:rho_2030}
	    \end{subfigure}
	    \begin{subfigure}[t]{.49\linewidth}
			\centering
			\caption{$\bm{\rho}^{0} \in [30, 40]$}
			\includegraphics[width=1\linewidth]{./Figures/rho30_40.pdf}
			\label{fig:rho_3040}
		\end{subfigure}
		\begin{subfigure}[t]{.49\linewidth}
			\centering
			\caption{$\bm{\rho}^{0} \in [40, 50]$}
			\includegraphics[width=1\linewidth]{./Figures/rho40_50.pdf}
			\label{fig:rho_4050}
	\end{subfigure}
	\vspace{-2em}
	\caption{Convergence Patterns with Different Starting Points $\bm{\rho}^{0}$}
	\label{fig:three_node_conv}
\end{figure*}

We note that ignoring matching time is a special case of considering matching time when $a_0 = 0$ in (\ref{eq:waiting_time_flow}). We compare the equilibrium solutions between ignoring and considering matching time cases, with the results of equilibrium spatial pricing, driver supply and rider demand shown in Figure \ref{fig:ignore_consider_three_node}. We can see that, compared to equilibrium prices, driver and rider flows are less sensitive to whether matching time is considered or not. The reason is that different locations, when supply and demand are balanced, have similar waiting time. For drivers, their relocation choices only depend on the utility difference between locations, which will not change if similar waiting time is ignored. Therefore, driver supply remain unchanged (see Figure \ref{fig:Driver_change}). Given similar amount of driver supply, TNC will need to raise up locational prices (see Figure \ref{fig:Price_change}) to compensate the ignored waiting time, so that rider demand still balance driver supply (see Figure \ref{fig:Rider_change}).

\begin{figure*}[htbp]
	\centering
	\makebox[1.0\linewidth][c]{
		\begin{subfigure}[t]{.333\linewidth}
			\centering
			\caption{Drivers Supply}
			\includegraphics[width=1\linewidth]{./Figures/Driver.pdf}
			\label{fig:Driver_change}
		\end{subfigure}
		\begin{subfigure}[t]{.333\linewidth}
			\centering
			\caption{Riders Demand}
			\includegraphics[width=1\linewidth]{./Figures/Rider.pdf}
			\label{fig:Rider_change}
		\end{subfigure}
		\begin{subfigure}[t]{.333\linewidth}
			\centering
			\caption{Equilbirium Prices $\bm{\rho}$}
			\includegraphics[width=1\linewidth]{./Figures/Price.pdf}
			\label{fig:Price_change}
	\end{subfigure}}
	\begin{subfigure}[t]{.533\linewidth}
			\centering
			\vspace{-0.5cm}
			\includegraphics[width=1\linewidth]{./Figures/legend_compare.pdf}
			\label{fig:legend_compare}
	\end{subfigure}
	\vspace{-2em}
	\caption{Equilibrium Solutions For Ignoring and Considering Matching Time Cases}
	\label{fig:ignore_consider_three_node}
\end{figure*}

\subsection{Sioux Falls Network}

We implement our model using a medium-size test system, Sioux Falls network\footnote{Sioux Falls network consists of 24 nodes and 76 directed links. The number on each node/link in Figure \ref{fig:siou_fall} is the node/link index. Figure \ref{fig:siou_fall}  is edited base on a map provided by Hai Yang and Meng Qiang, Hong Kong University of Science and Technology.}, as shown in Figure \ref{fig:siou_fall}. In Figure \ref{fig:siou_fall}, the red and blue nodes (12 of each) represent the  original locations of drivers and riders, respectively. Drivers supply at each red node is 50, while the demand function at each blue node is $d_s = 300 - 5\rho_s$. We adopt a $4^{th}$-order Bureau of Public Roads (BPR) function for link cost: $t_a = t_a^0[1+0.15*(v_a/c_a)^4]$. Coefficients of utility function for base case (\ref{eq:utility}) are $\beta_0 = 0, \beta_1 = 1, \beta_2 =0.6$.

\begin{figure}[htbp]
\begin{center}
    \includegraphics[width=0.5\textwidth]{./Figures/Sioux_Falls.pdf}
\caption{Sioux Falls Test Network}
\label{fig:siou_fall}
\end{center}
\end{figure}

\subsubsection{Ignoring Matching Time}
The optimal locational pricing decisions and total equilibrium travel time are shown in Figure \ref{fig:senstivity_b2}. With price sensitivity coefficient $\beta_2$ increase from 0.1 to 10, the price variances decrease (see Figure \ref{fig:price_sioux_fall}). This is because when drivers are more sensitive to prices, TNC needs smaller price difference to attract drivers to the desired locations. At the same time, drivers are more willing to travel longer distance in order to reach a location with higher price. This will lead to higher system total travel time, as shown in Figure \ref{fig:time_sioux_fall}.

SCIP is not able to solve the MINLP reformulation of problem (\ref{model:upper}) for Sioux Falls network, while IPOPT can efficiently solve (\ref{model:combine}) in 11.3, 6.1, and 4.9 seconds for $b_2$ = 0.1, 1, and 10, respectively.

\begin{figure*}[htbp]
	\centering
	\makebox[1.0\linewidth][c]{
		\begin{subfigure}[t]{.5\linewidth}
			\centering
			\caption{Locational Prices}
			\includegraphics[width=1\linewidth]{./Figures/price_sioux_falls.pdf}
			\label{fig:price_sioux_fall}
		\end{subfigure}
		\begin{subfigure}[t]{.5\linewidth}
			\centering
			\caption{Total Travel Time}
			\includegraphics[width=1\linewidth]{./Figures/time_sioux_fall.pdf}
			\label{fig:time_sioux_fall}
	\end{subfigure}}
	\vspace{-2em}
	\caption{Impacts of Supply and Demand on Optimal Surge Pricing}
	\label{fig:senstivity_b2}
\end{figure*}

\subsubsection{Considering Matching Time}

Considering matching time, the problem can be solved by Algorithm \ref{alg:iter} in 6.4 hours, which is significantly longer than the computation time for ignoring matching time case. This is because of the lack of convexity for both upper and lower problems in (\ref{model:upper_matching}). But the algorithm converge reliably in 12 iterations, with convergence patterns of ES and $\bm{\rho}$ shown in Figure \ref{fig:siou_fall_matching_conv}.
\begin{figure*}[htbp]
	\centering
	\makebox[1.0\linewidth][c]{
		\begin{subfigure}[t]{.5\linewidth}
			\centering
			\caption{Convergence of ES}
			\includegraphics[width=1\linewidth]{./Figures/sioux_fall_matching_es.pdf}
			\label{fig:sioux_fall_matching_es}
		\end{subfigure}
		\begin{subfigure}[t]{.5\linewidth}
			\centering
			\caption{Convergence of $\bm{\rho}$}
			\includegraphics[width=1\linewidth]{./Figures/sioux_fall_matching_prices.pdf}
			\label{fig:sioux_fall_matching_prices}
	\end{subfigure}}
	\begin{subfigure}[t]{0.8\linewidth}
			\centering
			\vspace{-0.5cm}
			\includegraphics[width=1\linewidth]{./Figures/legend_converge.pdf}
			\label{fig:legend_compare}
	\end{subfigure}
	\vspace{-2em}
	\caption{Convergence of ES and $\bm{\rho}$ Considering Matching Time}
	\label{fig:siou_fall_matching_conv}
\end{figure*}

Comparing between the impact of spatial pricing on transportation congestion, the total travel cost is 3805.5 when spatial pricing is adopted. When TNC adopts uniform pricing, the total travel cost is 3770.4. This observation is again consistent with the results in ignoring matching time case.

\section{Discussion}

In this paper, we have presented a new modeling framework and effective computational techniques for ride-sourcing spatial pricing problems, considering leader-follower structure of TNCs, riders, and drivers. In the lower level, interactions between drivers’ relocation, riders' mode choice, all travelers' routing behaviors, and network congestion are explicitly modeled. In the upper level, a monopoly TNC optimally determines spatial prices to achieve its own objectives. When matching time can be ignored, we show that the problem is equivalent to a convex optimization problem, which can be efficiently solved to global optimal by commercial nonlinear solver, such as IPOPT. Existence and uniqueness of optimal solutions are proved. When matching time cannot be ignored, we show that the lower-level drivers' and riders' two-sided interaction can be reformulated in a unified CDA framework with non-separable link-cost function through network augmentation. The problem can be solved reliably by approximating maxinf-points algorithm.

In addition to showing the effectiveness of our solution approaches, we demonstrated that (1) transportation congestion affects spatial pricing strategies, and spatial pricing strategies may aggravate transportation congestion compared to uniform pricing; (2) the spatial pricing strategies minimizing supply-demand imbalance also maximize TNC profits when maximum demand and supply are comparable; (3) drivers' preference will significantly impact spatial prices and transportation congestion; and (4) the impacts of waiting time may be small for the distribution of drivers and riders, but may be large for the scale of spatial pricing.

This research can be extended in several directions. From a methodological viewpoint, our model mainly focuses on spatial aspects. Coupling temporal and spatial dimensions are critical to fully understand the impacts of dynamic pricing on transportation systems. In addition, several assumptions in this study can be relaxed. For example, the assumption on monopoly competition and inelastic total driver supply could be relaxed to generalize our findings. After gaining a clear understanding about the impacts of saptial pricing on transportation systems, strategies to mitigate the negative impacts from regulators perspective is urgently needed. Extending our model to a stochastic environment is another immediate next step considering the high level of uncertainties involved in ride-sourcing market, including congestion, rider demand, driver supply, etc. Although our model can be efficiently solved for small and medium transportation networks, algorithm development is needed for extreme large cases. Classic traffic assignment algorithm could be leveraged to solve the lower-level problem more efficiently. Solving a stochastic version of our model might also present further numerical challenges, for which decomposition methods (such as scenario decomposition and Benders decomposition) developed for stochastic programs may be integrated with the reformulation techniques in this study. From a pratical perspective, given the challenges of obtaining ride-sourcing data, agent-based simulation techniques can be leveraged to simulate the ride-sourcing environment and generate simulated data for implementation, validation and numerical insights.

\section*{References}
\bibliography{ref.bib}
\pagebreak
\appendix

\input{./Appendics/app_pfs}
\pagebreak
\setcounter{table}{0}
\input{./Appendics/app_explain}

\end{document}

config: arxiv


TITLE: What exactly are the atoms in a discrete distribution?
QUESTION [1 upvotes]: If I build a word count on a corpus of text, are the atoms of this distribution the unique words themselves?
I ask because the definitions I read of atoms in a probability distribution (such as here) are too abstract.
It's the excellent answer to this StackExchange question that prompts me to ask. It gives an equation "where |x| is the number of atoms in the discrete distribution". Interpreting atoms as the set of words in the corpus is certainly consistent with the context but I can't find anywhere that says this definitively.
Similarly, my interpretation that atoms as the possible outcomes for any probability distribution is supported by this StackExchange question but I am still not sure.
Can anybody please assure me?

REPLY [1 votes]: The atoms of a measure space are, in some sense, the smallest non-null sets in the space.  Any set contained within an atom has zero measure, and a set is not an atom if it contains a measurable set that has non-zero measure.
For counting the words in the corpus you are also correct that distinct words are atoms: though words may contain other words (for example, the appears inside other) they do not contain distinct words (surrounded by non-word characters) for the purposes of word-count$[1]$.  In such a corpus, words are atoms, and then phrases or sentences are built out of atoms; paragraphs out of phrases and sentences, etc.
You don't say, but I suspect, that you're planning on using a Bayesian classifier, in which case words are definitely the right atom to select.
$[1]$ Language is tricky: a hyphenated word can certainly be claimed to contain at least two distinct words, and some languages use symbols as "letters" (e.g. representing a glottal stop as an apostrophe) that might be thought to be non-word characters in other languages.  But for word-count, you can almost certainly treat a distinct word as: being at the start of a line and followed by a punctuation mark or whitespace, being both preceded and succeeded by punctuation marks and/or whitespace, or being at the end of a line and preceded by punctuation or whitespace.  You will have to decide if you want to special-case the hyphen as the above rules will treat the hyphenated word as two (or more).  You might also want to note English has a couple of special case words as well, like stun's'l and fo'c'sle that will get turned into three words.


TITLE: Geometrical interpretation of a Schrödinger operator
QUESTION [2 upvotes]: Consider a $2 \times 2$ Hermitian (or symmetric) matrix-valued function
$$g(x) = \{ g_{jk}(x)\}_{j,k=1,2}, \quad x \in \mathbb{R}^{2},$$
such that $0 < m_{-}I \leq g(x) \leq m_{+}I$, for some $m_{-}, m_{+} > 0$. Set $A = (A_{1}, A_{2}) := (-bx_{2}/2, bx_{1}/2)$, $b > 0$ and define the operator
$$H = \sum_{j,k=1,2} (-i\partial/\partial x_{j} - A_{j}) g_{jk} (-i\partial/\partial x_{k} - A_{k}),$$
selfadjoint in $L^{2}(\mathbb{R}^{2})$ and essentially selfadjoint in $C_{0}^{\infty}(\mathbb{R}^{2})$.
If $g(x) = I$ for all $x \in \mathbb{R}^{2}$, this operator is called the Landau Hamiltonian and has the quantum mechanical interpretation of a spinless, charged particle under a constant magnetic field $b > 0$. I would like to understand further physical interpretations for the operator $H$ (in its general form).
Also, I understand that this operator can be given an interpretation in geometrical terms. Could you please explicit these interpretations and give some references to better understand them?

REPLY [2 votes]: I'm afraid I don't know any references off the top of my head, but let me at least give you a differential-geometric translation of sorts.

If $g$ is real-valued, then it defines a Riemannian metric on $\mathbb{R}^2$.
The vector field $A$ is a vector potential for the constant magnetic field $b$, in the sense that $\operatorname{curl}(A) \cdot \hat{\mathbf{k}} = b$. Even better, the magnetic potential $A$ can be interpreted as the connection $1$-form
$$
 A := -\frac{1}{2}bx^2\mathrm{d}x^1 + \frac{1}{2}bx^1\mathrm{d}x^2
$$
of the unitary connection $\nabla = d - iA$ on the (trivial) line bundle $\mathbb{R}^2 \times \mathbb{C}$ defined by
$$
 \nabla_{\frac{\partial}{\partial x^1}} = \frac{\partial}{\partial x^1} + i \frac{1}{2}bx^2, \quad \nabla_{\frac{\partial}{\partial x^2}} = \frac{\partial}{\partial x^2} - i \frac{1}{2}bx^1,
$$
with curvature (viz, magnetic field strength)
$$
 B := \mathrm{d}A + A \wedge A = \mathrm{d}A = b \,\mathrm{d}x^1 \wedge \mathrm{d}x^2;
$$
observe that sections of the line bundle $\mathbb{R}^2 \times \mathbb{C}$ are just complex-valued functions on $\mathbb{R}^2$. Parallel transport along this connection, then, is none other than magnetic translation.
Given a complete Riemannian manifold $(X,g)$, a Hermitian vector bundle $E \to X$, and a unitary connection $\nabla$ on $E$, you get a canonical essentially self-adjoint second order elliptic differential operator called the Bochner Laplacian $\nabla^\ast \nabla$, which satisfies, as one would expect,
$$
 \nabla^\ast \nabla = \sum_{j,k} g^{jk}(x)\nabla_{\frac{\partial}{\partial x^j}}\nabla_{\frac{\partial}{\partial x^k}} + \text{lower order terms}.
$$
If I'm not too mistaken, your magnetic Schroedinger operator $H$ should basically be the Bochner Laplacian for the connection $\nabla = d - iA$ on the trivial line bundle $\mathbb{R}^2 \times \mathbb{C}$ over $(\mathbb{R}^2,g)$.

I might have some signs and constants out of place here or there, but I think this should give at least the moral translation into differential-geometric terms. Lurking in the background is Weyl's famous characterisation of electromagnetism as a  $U(1)$ gauge theory, i.e., in terms of a unitary connection (viz, electromagnetic potential) on a line bundle over spacetime, whose curvature therefore gives the electromagnetic field strength.

REPLY [1 votes]: your $\mathbf{g}$ is the position-dependent inverse effective mass tensor; if you calculate the classical equations of motion
$$
{{\ddot{x}_1}\choose{\ddot{x}_2}}=2b\,\mathbf{g}(\mathbf{x})\cdot{{-\dot{x}_2}\choose{\dot{x}_1}}
$$
then the semiclassical quantization condition is that the area inside a closed orbit must equal $(2\pi/b)(n-1/2)$, $n=1,2,3,\ldots$.
For a discussion in a three-dimensional setting, but without the position dependence of $\mathbf{g}$, see these lecture notes.
For a physical application to a semiconductor with position dependent effective mass, see Landau levels and cyclotron resonance in graded mixed semiconductors.


TITLE: Algebra - Prove that these 2 statements are equivalent.
QUESTION [0 upvotes]: I have got the following task:
Prove, that these 2 statements are equivalent

A $G$ group is finite.
A $G$ group has finite amount of subgroups.

The trivial side is easy: If $G$ has infinite amount of subgroups, then $G$ can't be finite(The number of subgroups is at most $2^k$, where $k$ is the number of the elements in $G$. If $k$ is finite, $2^k$ will be finite too.
However, the other side doesn't seem so easy. I must prove, that if I have a $G$ group with infinite amount of elements, then the number of subgroups must be infinite aswell.
Any ideas, how should I start proving this? Any help appreciated. :)

REPLY [2 votes]: HINT: Let $G$ be an infinite group. Each $g$ in $G$ generates a subgroup $\langle g\rangle=\{g^n:n\in\Bbb Z\}$. There are two cases.

All of the groups $\langle g\rangle$ are finite.
There is at least one $g\in G$ such that $\langle g\rangle$ is infinite.

The first should be easy. For the second, show that $\langle g\rangle$ is isomorphic to a very familiar group that has infinitely many subgroups.


TITLE: What are ADU (analog-to-digital units)?
QUESTION [11 upvotes]: Can someone explain simply what are ADU's? I was reading this post here: http://www.qsimaging.com/blog/understanding-gain-on-a-ccd-camera/
However, I still don't quite understand this statement:

"Gain on a CCD camera represents the conversion factor from electrons (e-) into digital counts, or Analog-Digital Units (ADUs).  Gain is expressed as the number of electrons that get converted into a digital number, or electrons per ADU (e-/ADU)."

It seems ADU is a "digital number" but what is that? The units of ADU is "counts", but what are those counts? They are not electrons, it seems, then what are they? Time? I'm sorry if this is silly, but I just can't comprehend what ADU's physically are. It really stumped me from understanding the rest of the article.

REPLY [11 votes]: There are several concepts and issues going on here that are getting mixed together.
First the ADC;
An ADC (Analog To Digital Convertor) takes signal values in a certain range and converts then to a digital number.  Let's run some numbers:
A N bit ADC will be able to represent 2^N states.  So a 4 bit ADC can represent 16 distinct states, 8 bits => 256 States and a 12 bit convertor will give you 4096 states.  By itself that tells you nothing, you need to know that going from a digital representation of say 533 -> 534 means that the input signal changed by certain amount.  To keep the example simple I'm going to say that I have an input range from 0 Volts to 4.095 Volts on a 12 bit convertor, that means that when I have a digital number of 0 then I must have had 0 on the input.  Let's also assume everything is ideal for now. With my sneaky choice of input range you can see that for every change in the ADC output digital number by one count then the input must have changed by 1 mV.
Why did I pick 4.095? Well a 12 bit convertor will have 4096 digital values that range from 0 to 4095 (2^N-1 when all the bits are set to "1").  So 4.095 Volts/4095 = 1 mv/count.  That means that if you have a 3.567 Volt value on the output and it changes to 3.568 Volts ( 1 mV change on the input) then the digital number on the output should change from 3567 to 3568 digital number on the output from 110111101111 to = 110111110000 in raw binary.
Each of these binary steps are called an ADU (Analog Digital Unit) or Binary Number or Digital Count etc. etc. to keep it separate from the number of bits that the ADC has.  This is to ensure that the relationship is in a linear range.  If you start using "bits" then it is in a logarithmic range (2^N). The main reason these other names/units are used is that LSB's used to be used.  What is a LSB? - it stands for Least Significant Bit, i.e. the zeroth bit in the digital number, which changes precisely in step with the ADU but using LSB (and the implied 'bit") is confusing.  Imagine saying, " the ADC changed by 30 LSB's therefore the light flux must have changed by 3000 photons ".  30 LSB's really doesn't make sense, it is a mixing of terminology, so people are moving away from that.  But that has meant that many different terms being used instead confusing again...
So you have a conversion from voltage into a digital number.
But you are collecting photons, where does voltage come from?
Next the Voltage conversion;
All image sensors at some point in the signal chain will convert the collected signal charge into voltage to interact with the outside world.  This is always done using a capacitance and a buffer amplifier.  This capacitor and the gain of the amplifier set the conversion from electrons into voltage as A/C_sense which is derived from the Q= CV equation.  With C_sense = the sense node capacitance and A = gain of the buffer amplifier.
Next the photon conversion
When a Photon comes rattling into a pixel it has to make it into the photosensitive substrate, this interface is controlled by the fresnel equations and dictates how much light goes into the substrate based upon the indices of refraction and the various materials and AR coatings present (AR = Anti-reflection).  This is known as the external QE (Quantum efficiency). Once in the substrate the photons are absorbed through it's depth and generate electron/hole pairs through the photo electron effect. Electric fields sweep the carriers into storage structures.  The absorption depth and the depth of influence of the electric fields (these two depths may not be co-incident) are what determines the Internal QE.  NOt every converted photon's carriers get collected.
These collected carriers (either electrons or holes) are brought to the sense node and converted into voltages.  Where this conversion happens (carrier to voltage) is determined by the type of sensor, a CCD or CMOS image sensor.
The total conversion process;
(Photon flux) * (Integration period) * QE_external *QE_Internal * A/C_sense * ADC_conversion
Will give you units of Photons/ADU.


TITLE: Dirichlet approximation theorem: How "sporadic" are the good denominators?
QUESTION [2 upvotes]: For an irrational number $\alpha \in \Bbb{R} \setminus \Bbb{Q}$, the Dirichlet approximation theorem states that there are infinitely many irreducible fractions $\frac{p}{q}$ such that $|\alpha - \frac{p}{q}| < \frac{1}{q^2}$.
I would like to know if anything is known about how "sporadic" these "good denominators" $q$ are. Specifically, I would like to know whether the following holds:

Are there $B,C > 1$ such that for every $n \in \Bbb{N}$, there is $q \in \Bbb{N} \cap [B^n, B^{n+1}]$ and $p \in \Bbb{Z}$ such that $\frac{p}{q}$ is irreducible and $|\alpha - \frac{p}{q}| \leq \frac{C}{q^2}$?

In the above question, $B,C$ are allowed to depend on $\alpha$ if need be. I would also be willing to relax the desired estimate to $|\alpha - \frac{p}{q}| \leq \frac{C}{q^{2-\epsilon}}$ for arbitrary $\epsilon \in (0,2)$ and $C,B$ depending on $\alpha$ and $\epsilon$.
Motivation:
The idea here is that for any given $K \geq 1$, I want to be able to choose $q \sim K$ satisfying the estimate $|\alpha - \frac{p}{q}| < \frac{C}{q^2} \sim K^{-2}$. My ultimate goal is to prove a kind of "quantitative equidistribution theorem", i.e., I want to estimate $\sup_{f \in \mathcal{F}} \big|\frac{1}{N} \sum_{\ell=1}^N f(\alpha \ell) - \int_0^1 f(x) \, dx \big| \lesssim N^{-\beta}$ for a certain class of periodic functions $\mathcal{F}$, and the above estimate would be a big help for doing so.
Disclaimer: I have next to no knowledge about number theory, so it might be that my question is somewhat stupid. In any case I am looking forward to learning something.

REPLY [4 votes]: Technical remark to start: the interval $[X,B^2 X]$ contains two powers of $B$, so one can replace the assumption that the integer $q \in [B^m,B^{m+1}]$ by the weaker condition that for any $X$ there is a $q \in [X,B^2 X]$ satisfying the conditions.
Let's start with the bad news; certainly some $\alpha$ do not have any such approximation, note even the weaker bound:
$$\left| \alpha - \frac{p}{q} \right| < \frac{1}{q^{1 + \epsilon}}$$
for any fixed $\epsilon > 0$. To see this, let
$$\alpha = \sum_{m=1}^{\infty} \frac{1}{10^{m!}}$$
This is Liouville number (transcendental) which has extremely good rational
approximations. For example, we can let
$$\frac{p_n}{q_n} = \sum_{m=1}^{n} \frac{1}{10^{m!}}$$
and then
$$\left| \alpha - \frac{p_n}{q_n} \right| \le \frac{2}{q^{n+1}_n} = \frac{2}{q_{n+1}}.$$
The key point, however, is that very good approximations tend to repell other good approximations. The triangle inequality says that
$$\left| \frac{p}{q} - \frac{p_n}{q_n} \right|
\le \left| \alpha - \frac{p}{q} \right| +
\left| \alpha - \frac{p_n}{q_n} \right| \le \frac{1}{q^{1 + \epsilon}}
+ \frac{2}{q_{n+1}}.$$
Now choose $X$ such that:
$$3 \cdot 10^{n!/\epsilon} < X < B^2 X < 10^{(n+1)!/(1 + \epsilon)},$$
As long as $\epsilon > 0$, this is possible to do for $n$ large enough.
Now if $q \in  [X,B^2 X]$ then $q^{1 + \epsilon} < q_{n+1}$, so the error term
above is at must $3/q^{1 + \epsilon}$. But then we have:
$$\frac{3}{q^{1 + \epsilon}} \ge \left| \frac{p}{q} - \frac{p_n}{q_n} \right|
\ge \frac{1}{q_n q},$$
the last inequality following from using a common denominator and assuming $p/q \ne p_n/q_n$.
But this gives:
$$q^{\epsilon} < 3q_n,$$
which is a contradition. The same argument more or less should even work with inequalities of the form
$$\left| \alpha - \frac{p}{q} \right| \le \frac{1}{q f(q)}$$
for any monotonically increasing function $f(q) \rightarrow \infty$, after replacing $\alpha$ by
another Liouville number with even more drastic convergents.
Now the second bad news. Suppose instead of $p/q$ such that:
$$\left| \alpha - \frac{p}{q} \right| < \frac{1}{q^2},$$
for all $\alpha$, you only ask about it for almost all $\alpha$. Here I am particular in making the RHS of the form $1/q^2$. Even this is too much to ask.
It turns out that the inequality above implies that $p/q$ is a  convergent to $\alpha$. But the denominators $q_n$ of the convergent turn out to grow exponentially, and given the continued fraction $\alpha = [a_0,a_1,a_2,a_3, \ldots]$ there's a formula:
$$q_n = a_{n} q_{n-1} + q_{n-2} \in [a_n q_{n-1},(a_n + 1) q_{n-1}].$$
Hence requiring that there is a $q \in [B^m,B^{m+1}]$ is would imply that the integers $a_i$ bounded. But it turns out that almost all real numbers have unbounded $a_i$ (by the Gauss-Kuzmin Theorem).
The continued fraction at least tells you roughly what to expect -- by Khinchin's theorem the geometric mean of the $a_n$ converge (almost always) to a fixed constant $K$, which implies that (a.a.) the $q_n$ also grow at most exponentially, which implies that you can  find a $B$ such that the desired approximation holds for $q \in [B^n,B^{n+1}]$ for "many" $n$. You could also consider the relaxed inequality with $1/q^{2 - \epsilon}$ and then think about what happens for almost all $\alpha$, although I haven't thought much about that.


TITLE: Advent of our solar system
QUESTION [0 upvotes]: When the solar system was born why did Sun not consume all the planets by its immense gravity, as the planets were all gases, so it would have been very easy?

REPLY [4 votes]: The answer is basically, angular momentum.
The collapsing proto-solar nebula has some angular momentum. Whilst dissipative processes can allow the nebula to collapse along the axis of rotation, there is still the problem of how to shed angular momentum in order to allow gas/dust to orbit closer to the rotation axis. This is just a basic application of Newtonian mechanics. Objects in orbits further out have more angular momentum. To move them inwards requires that they lose angular momentum.
This process is possible, there are various poorly understood mechanisms that can apply torques and move angular momentum outwards in the proto-solar accretion disk (e.g. the magneto-rotational instability, which increases the disk viscosity).
However, it seems (both from empirical measurements of circumstellar material in clusters of known age, and the presence of planets around most stars) that the timescales for the accretion of the disk due to its viscosity and the timescales of other mechanisms that can either allow the disk material to accrete or disperse are longer (of order 10 Myr) than the the timescales on which planets can form.
Once the planets are formed there is no reason at all that their orbits should shrink, since once the gas/dust of the disk is removed/accreted, there are no effective processes to remove their angular momentum.


TITLE: Proving a limit of a sequence equals a fixed point
QUESTION [0 upvotes]: The iteration  $x_{k + 1} = \frac{1}{2}(x_{k}^{2} + c)$
  where $0 < c < 1$ has two fixed points $\zeta_{1}$, $\zeta_{2}$, where
  $0 < \zeta_{1} < 1 < \zeta_{2}$. Show that
$$x_{k + 1} - \zeta_{1} = \frac{1}{2}(x_{k} + \zeta_{1})(x_{k} -
 \zeta_{1}) $$
and show $\lim_{k\to\infty} x_{k} = \zeta_1$ whenever $0 \leq x_{0} <
 \zeta_{2}$

I've done the first part, but I can't prove the limit. I have no idea how to show the limit. To do the first part, I just subtracted the iteration equation with the fixed point equation and used difference of squares.
Does anyone have any ideas?

REPLY [0 votes]: Let $f(x)=(x^2+c)/2$. Then $x<f(x)<\zeta_1$ if $x\in[0,\zeta_1)$ and $\zeta_1<f(x)<x$ if $x\in(\zeta_1,\zeta_2)$.
If $x_0=\zeta_1$, the $x_n=\zeta_1$ for all $n$.
Take now $x_0\in[0,\zeta_1)$. Then, using the first of the above inequalities, it is easy to see that the sequence of iterates $\{x_n\}$ is increasing and bounded by $\zeta_1$. Therefore it converges, and the limit is precisely \zeta_1$.
Similarly, if $x\in(\zeta_1,\zeta_2)$, then $\{x_n\}$ is decreasing, bounded below by $\zeta_1$ and converges to $\zeta_1$.


TITLE: BMO1, Q6 Number Theory
QUESTION [1 upvotes]: Consecutive positive integers $m$, $m+1$, $m+2$ and $m+3$ are divisible by consecutive odd positive integers $n$, $n+ 2$, $n+ 4$ and $n+ 6$ respectively. Determine the smallest possible $m$ in terms of $n$.
So, I already tried solving this using the fact that this is a system of linear congruences. We have:
$$m\equiv 0 \pmod{n}$$
$$m+1 \equiv 0 \pmod{n + 2}$$
$$m+2 \equiv 0 \pmod{n + 4}$$
$$m+3 \equiv 0 \pmod{n + 6}$$
My approach revolved around this:
From the first congruence, we know that
$$m=nk$$
where $k$ is an integer.
Then we take this and substitute it into the second congruence:
$$ nk+1 \equiv 0 \pmod{n + 2}$$
And then solve for $k$, introduce a new variable, and substitute it back to the original equation for $m$. Needless to say, this approach gets extremely long and ugly. My teacher told me there is a way to do this problem using the Chinese Remainder theorem, however how do we prove that $n$, $n+2$, $n+4$ and $n+6$ are pairwise relatively prime?

REPLY [0 votes]: Here are some hints.
Begin by showing that, for $n$ relatively prime to $3$, that
$$
m=\frac{n(n+2)(n+4)(n+6)+n}{2}
$$
works, and for $n$ divisible by $3$, that
$$
m=\frac{n(n+2)(n+4)(n+6)+3n}{6}
$$
works.
Then use the Chinese Remainder Theorem to argue that no smaller $m$ will do.