## 3 Discount-Guaranteed Ridesharing Problem
\begin{table}
\begin{tabular}{c c} \hline \hline
**Variable** & \multicolumn{1}{c}{**Meaning**} \\ \hline \(P\) & Total no. of passengers. \\ \(D\) & Total no. of drivers. \\ \(p\) & The index of a passenger and the corresponding passenger agent, where \(p\in\{1,2,3,\ldots,P\}\). \\ \(d\) & The index of a driver and the corresponding driver agent, where \(d\in\{1,2,3,\ldots,D\}\). \\ \(k\) & The index of a location, \(k\in\{1,2,\ldots,K\}\). \\ \(I_{d}\) & Total no. of bids submitted by driver agent \(d\in\{1,2,\ldots,D\}\). \\ \(j\) & The index of the \(j-\) th bid placed by a driver agent with \(j\in\{1,2,\ldots,I_{d}\}\). \\  & \(DB_{ij}\) & \(=\{q_{ij1},q_{ij2},q_{ij3},\ldots,q_{ijp},q_{ijp},q_{ijp}\}\): the \(j\)-th bid of driver agent \(d\), where \\ \(DB_{ij}\) & \(q_{ij}\) is the available seats to serve passenger \(p\), \\  & \(q_{ij}\) is the original cost when the driver lasts alone, and \\  & \(c_{ij}\) is the travel cost of the bid. \\ \(q_{ijp}^{1}\) & The number of seats for picking up passengers at the pick – up location of passenger \(p\), \(q_{ijp}^{1}=q_{ijp}\). \\ \(q_{ijp}^{2}\) & The number of seats released after dropping the passengers at the drop – off location of passenger \(p\), \(q_{ijp}^{2}=q_{ijp}\). \\ \(PB_{p}\) & \(PB_{p}\) & \(=\{S_{p1},S_{p2},S_{p3},\ldots,S_{pK,fjp}\}\): the bid of passenger agent \(p\), where \\  & \(S_{pk}\) is the number of seats requested by passenger \(p\) for location \(k\) and \\  & \(f_{p}\) is the cost of passenger \(p\) without ridesharing. \\ \(s_{pk}^{1}\) & No. of seats requested by passenger \(p\) at the pick – up location of passenger \(p\), \(s_{pk}^{1}=\{\begin{array}{l}s_{p}\text{ \emph{if} }k=p\\ 0\text{ \emph{otherwise}}\end{array}\right.\) \\ \(s_{pk}^{2}\) & No. of seats requested by passenger \(p\) at the drop – off location of passenger \(p\), \(s_{pk}^{2}=\{\begin{array}{l}s_{p}\text{ \emph{if} }k=p\\ 0\text{ \emph{otherwise}}\end{array}\right.\) \\ \(x_{dj}\) & A decision variable: \(x_{dj}=1\) if the \(j\)-th bid of driver \(d\) is a winning bid and \(x_{dj}=0\) otherwise. \\ \(y_{p}\) & A binary decision variable: \(y_{p}=1\) if the bid of passenger \(p\) is a winning bid and \(y_{p}=0\) otherwise. \\ \(r_{D}\) & Minimal expected cost savings discount for drivers. \\ \(r_{p}\) & Minimal expected cost savings discount for passengers. \\ \(H(x,y)\) & The total cost savings objective function, \\ \(H(x,y)=\left(\sum\limits_{t=1}^{P}y_{p}\left(f_{p}\right)\right)+\left(\sum \limits_{t=1}^{D}\sum\limits_{j=1}^{D}x_{dj}q_{ij}\right)-\left(\sum\limits_{t= 1}^{D}\sum\limits_{j=1}^{L}x_{dj}c_{dj}\right).\) \\ \(\Gamma_{dj}\) & The set of passengers on the ride corresponding to the \(j\)-th bid submitted by driver \(d\). \\ \(H_{dj}(x,y)\) & The cost savings of the \(j\)-th bid submitted by driver \(d\) \\ \(H_{dj}(x,y)=\left[\left(\sum\limits_{p\in I_{dj}}y_{p}f_{p}\right)+x_{dj}o_{dj}- \left(x_{dj}c_{dj}\right)\right].\) \\ \(cf_{pij}\) & Travel cost for passenger \(p\) on the ride corresponding to the \(j-\) th bid submitted by driver \(d\), where \(p\in\Gamma_{dj}\). \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Notations of symbols, variables, and parameters. As a ridesharing system typically consists of three entities, namely drivers, passengers, and a service provider, it can be modeled as a multi-agent system (MAS) [8; 9]. In a MAS, an agent is a cooperative, autonomous, and intelligent entity working to achieve certain goals. In this paper, we adopted the MAS concept to model a ridesharing system. The ridesharing MAS includes driver agents, passenger agents, and the service provider agent. Driver agents and passenger agents submit bids to the system, and the service provider agent must determine the winning bids by matching driver agents and passenger agents based on the bids submitted. The operation of the ridesharing MAS is very similar to an auction [10].