Free utility model for explaining the social gravity law

Before presenting our model to explain the social gravity law, we first briefly introduce the gravity model that is widely used to predict the spatial interaction flow obeying the social gravity law. The earliest gravity model Odlyzko15 , generated from an analogy with Newton’s law of universal gravitation, has the following functional form:

where $T_{ij}$ is the flow from origin $i$ to destination $j$, $m_{i}$ is the activity (usually quantified by population) of location $i$, $d_{ij}$ is the distance between $i$ and $j$, and $\alpha$ and $\beta$ are parameters. This original gravity model has a simple form and can be used to reproduce the distribution pattern of spatial interaction flow, but difficulties arise when predicting future flows. For example, the $T_{ij}$ calculated by Eq. (1) would increase by a factor of 100 if the future populations $m_{i}$ and $m_{j}$ both increase by factors of 10, which is clearly not realistic.

An improvement to overcome this shortcoming of the original gravity model is to discard the fixed parameter $\alpha$ and use the following equation to calculate the flow:

where $O_{i}$ is the outflow of location $i$, which is usually roughly proportional to the population of location $i$, i.e., $O_{i}\approx\theta m_{i}$ Simini12 . The results calculated by Eq. (2) satisfy the constraint $\sum_{j}T_{ij}=O_{i}$, so Eq. (2) is named the singly-constrained gravity model Dios11 .

The more commonly used gravity model in transportation science is the doubly-constrained gravity model Dios11 , which is constructed to satisfy two constraints, i.e., $\sum_{j}T_{ij}=O_{i}$ and $\sum_{i}T_{ij}=D_{j}$, where $D_{j}$ is the inflow of location $j$. In addition, travel cost $c_{ij}$ is used more often than distance $d_{ij}$ in trip distribution forecasting, so the doubly-constrained gravity model can be written as

where $f(c_{ij})$ is the travel cost function and $a_{i}=1/{\sum_{j}b_{j}D_{j}f(c_{ij})}$ and $b_{j}=1/{\sum_{i}a_{i}O_{i}f(c_{ij})}$ are balancing factors.

Next, we will establish the free utility model from the perspective of individual choice behavior to derive the singly- and doubly-constrained gravity models and explain the social gravity law.

Similar to some of the aforementioned studies explaining the social gravity law, we conduct our research in the context of individual destination choice behavior in the transportation system. In this system, there are $M$ origins labeled $i$ $(i=1,2,\dots,M)$ and $N$ destinations labeled $j$ $(j=1,2,\dots,N)$. $O_{i}$ is the number of trips leaving origin $i$. We initially start with the simplest system, in which there is only one origin $(M=1)$ and one trip $(O_{i}=1)$ made by a traveler who can select $N$ $(N>1)$ destinations. The utility of destination $j$ for this traveler is $u_{ij}$, which describes her satisfaction degree concerning the attractiveness of destination $j$ and the travel cost from origin $i$ to destination $j$. According to the utility maximization principle, this traveler will select the destination with the highest utility only if she is perfectly rational Fishburn82 . However, it is difficult for a bounded rational traveler to exactly perceive the utilities of all destinations in reality. In this case, her choice is probabilistic, i.e., destination $j$ is selected with probability $p_{ij}$, which depends on $u_{ij}$ Luce59 . If the traveler is completely uncertain about the utilities of all destinations, she can select destination $j$ only with probability $p_{ij}=\frac{1}{N}$, and her expected utility $\sum_{j}p_{ij}u_{ij}$ is the average of the utilities of all destinations. If she wants to obtain higher expected utility, she must acquire knowledge about the utilities of the destinations through information processing Marsili99 . A natural measure of information processing is negative information entropy $-H=\sum_{j}p_{ij}\ln p_{ij}$ Marsili99 ; Wolpert12 ; Ortega13 . Assuming that the price of unit information is $\tau$, then the information-processing cost is $-\tau H$. If $\tau\to\infty$, which means that the information-processing cost is extremely high, the traveler does not care about the expected utility and focuses only on the information-processing cost. Hence, she will make a totally random choice of destination, that is, a uniform distribution over the set of destinations. If $\tau=0$, which means that information processing has no cost, she will select only the destination with the highest utility. In general case $\tau>0$, she must trade off her expected utility and the information-processing cost Guan20 ; Tkacik16 to achieve the total utility maximization goal, i.e.,

where $\sum_{j}p_{ij}u_{ij}+\tau H$ is the objective function subjected to $\sum_{j}p_{ij}=1$. Using the Lagrange multiplier method, we can obtain the solution of Eq. (4) as follows:

where $\lambda$ is a Lagrange multiplier. According to $\frac{\partial L}{\partial p_{ij}}=0$ for all destinations, we can obtain

which means that all destinations have the same utility minus the marginal information-processing cost under the traveler’s optimal choice strategy. This situation is very similar to consumer equilibrium in microeconomics Tewari03 , in which the marginal utility of each good is equal. Thus, we name $u_{ij}-\tau(\ln p_{ij}+1)$ the marginal utility of destination $j$. The total utility of the system is the sum of the integrals of the marginal utilities of all destinations. The optimal choice strategy for the traveler is to follow the equimarginal principle Tewari03 to select destinations in order to achieve maximum total utility. Combining Eq. (6) and $\sum_{j}p_{ij}=1$, we can derive

which is the equilibrium solution of Eq. (4). In economics, the reciprocal of the parameter $\tau$ in Eq. (7) is commonly referred to as the intensity of choice parameter Brock97 , which measures how sensitive a traveler is with respect to differences in the destination utilities. The greater $1/\tau$ is, the more sensitive the traveler is to differences in the destination utilities, and vice versa. In mathematical form, Eq. (7) is the Logit model derived in terms of random utility theory DoMc75 . However, our derivation does not need to assume in advance that the destination utility perception errors follow the Gumbel distribution.

We further extend the transportation system to the case where origin $i$ has infinite homogeneous travelers (i.e., $O_{i}\gg 1$), each of whom still has only one trip. The question then becomes how these trips are distributed among various destinations. If the utility of destination $j$ is not affected by the number of trips to $j$, Eq. (7) can still be applied in this system. On this occasion, the number of trips from $i$ to $j$ is $T_{ij}=O_{i}p_{ij}$, and the system entropy $S$ is the sum of the information entropy $H$ of each trip, i.e., $S=O_{i}H$. Therefore, we can rewrite Eq. (4) as

Similarly, all homogeneous travelers follow the equimarginal principle so that all destinations have the same marginal utility for them. If the utility of destination $j$ is abstractly written as $u_{ij}=A_{j}-c_{ij}$, where $A_{j}$ is the constant attractiveness of destination $j$ reflecting the activity opportunities (including variables such as retail activity and employment density) Sheffi85 available there, and $c_{ij}$ is the constant travel cost from $i$ to $j$, we can use the Lagrange multiplier method to obtain the equilibrium solution of Eq. (8) as

which is the same as the singly-constrained gravity model derived from the Logit model DoMc75 .

However, in practice, the utility of destination $j$ is affected by the number of trips from $i$ to $j$ Fujita89 ; that is, $u_{ij}$ is a function of $T_{ij}$. For example, an increase in the trip number $T_{ij}$ from origin $i$ to destination $j$ will increase the travel cost from $i$ to $j$ and decrease the attractiveness of destination $j$ Yan19 , both of which will change the utility of destination $j$. Hence, the utility can be abstractly written as $u_{ij}(T_{ij})=A_{j}-l_{j}(T_{ij})-c_{ij}-g_{ij}(T_{ij})$, where $l_{j}(T_{ij})$ is the variable attractiveness function of destination $j$ and $g_{ij}(T_{ij})$ is the congestion function on the way from $i$ to $j$. To solve the subsequent optimization problems, we assume that $l_{j}(T_{ij})$ and $g_{ij}(T_{ij})$ are both monotonically nondecreasing differentiable functions. We already know that each traveler follows the equimarginal principle to make the optimal choice. In this context, a traveler’s choice of destination depends on how other travelers are distributed over all destinations Conlisk76 . The phenomenon of one individual’s behavior being dependent on the behavior of other individuals, known as individual interaction, is widespread in social systems. In this interactive system, the optimal choice strategy for all travelers is still to assign all destinations the same marginal utility. Since the total utility of the system is the sum of the integrals of the marginal utilities of all destinations, the utility maximization model of the interactive system can be written as

Interestingly, the objective function of Eq. (10) is mathematically consistent with the Helmholtz free energy in physics Kittel80 ; thus, we name Eq. (10) the free utility model. Analogous to the thermodynamic system, the equilibrium trip distribution maximizes the free utility function in the transportation system. In addition, the first term of the free utility function, $\sum_{j}\int_{0}^{T_{ij}}u_{ij}(x)\mathrm{d}x$, is analogous to internal energy, including potential energy in a thermodynamic system. Monderer and Shapley Monderer96 therefore named this term the potential function. The free utility model with $\tau=0$ is essentially a potential game with an infinite number of agents.

Here, to generate gravity-like behavior, the utility needs a logarithmic dependence on the number of travelers from $i$ to $j$, i.e., $u_{ij}(T_{ij})=A_{j}-c_{ij}-\gamma\ln T_{ij}$, where $\gamma\ln T_{ij}=l_{j}(T_{ij})+g_{ij}(T_{ij})$ is the simplified cost function, including the travel congestion cost and the destination variable attractiveness, and $\gamma$ is a non-negative parameter. The logarithmic form of the cost function can be explained by the Weber-Fechner law in behavioral psychology Takemura14 . This law holds that the magnitude of human perception (e.g., the traveler’s perception of travel cost) is proportional to the logarithm of the magnitude of the physical stimulus (e.g., the number of travelers $T_{ij}$). Equation (10) can be specifically written as

Using the Lagrange multiplier method, we can obtain

This result is the singly-constrained gravity model Dios11 . Parameter $\tau$ reflects the information-processing price for bounded rational travelers, and parameter $\gamma$ reflects travelers’ interaction strength. Figure 1 shows the effect of changes in parameters $\tau$ and $\gamma$ on the free utility optimal solution in a simple system with one origin and two destinations. The surface in Fig. 1 describes the optimal solution of the free utility model in this simple system. From Eq. (11), we can see that when $\gamma>0$ and $\tau=0$ (meaning no information-processing cost), the free utility model is equivalent to the degenerated destination choice game model Yan19 in terms of potential game theory, as shown in the left dashed line of Fig. 1; when $\gamma>0$ and $\tau\to\infty$ (meaning that the information-processing cost is too high), travelers can only uniformly randomly select each destination, as shown in the lower-right solid line of Fig. 1; when $\tau>0$ and $\gamma=0$ (meaning that there is no interaction among travelers), the free utility model is equivalent to the Logit model DoMc75 , as shown in the upper-right dotted line of Fig. 1; and when $\tau=0$ and $\gamma=0$, all travelers will select the destination with the highest constant utility, as shown in the intersection point of the dashed line and dotted line of Fig. 1.

Above, we considered only a simple system with a single origin. However, there is more than one origin $(M>1)$ in a real transportation system. In such a system, the utility form of destination $j$ is changed. It is affected by not only the number of trips from $i$ to $j$ but also the total number of trips attracted to destination $j$. Hence, the utility of destination $j$ for travelers at origin $i$ can be abstractly written as $u_{ij}(T_{ij},D_{j})=A_{j}-l_{j}(D_{j})-c_{ij}-g_{ij}(T_{ij})$, where $D_{j}$ is the total number of trips attracted to destination $j$, i.e., $D_{j}=\sum_{i}T_{ij}$, and used as the independent variable of the variable attractiveness function $l_{j}(D_{j})$ of destination $j$. If $D_{j}$ is as constant as $O_{i}$, that is, not only the total number of trips emanating from origin $i$ but also the number of trips attracted to any destination is fixed, then, the variable attractiveness function $l_{j}(D_{j})$ of destination $j$ is also constant and thus can be merged into the constant attractiveness $A_{j}$ of destination $j$. In other words, only the travel congestion function $g_{ij}(T_{ij})$ influences the destination choice behavior of travelers. If $g_{ij}(T_{ij})=\gamma\ln T_{ij}$, the free utility model of the system can be written as

where the two constraints $\sum_{j}T_{ij}=O_{i}$ and $\sum_{i}T_{ij}=D_{j}$ are the fixed total number of trips emanating from origin $i$ and the fixed total number of trips attracted to destination $j$, respectively. Using the Lagrange multiplier method (see Appendix), we can obtain

where $a_{i}=1/\sum_{j}b_{j}D_{j}\mathrm{e}^{-c_{ij}/(\gamma+\tau)}$ and $b_{j}=1/\sum_{i}a_{i}O_{i}\mathrm{e}^{-c_{ij}/(\gamma+\tau)}$. This is the doubly-constrained gravity model widely used in transportation science Dios11 . This free utility model can be reduced to some classical models under specific parameter combinations. When $\tau>0$ and $\gamma=0$ (meaning that there is no interaction among travelers), Eq. (13) is equivalent to the free cost model proposed by Tomlin et al. Tomlin68 , and its solution has the same form as that of Wilson’s maximum entropy model Wilson67 . When $\tau=0$ and $\gamma=0$, Eq. (13) is equivalent to the Hitchcock-Koopmans problem Hitchcock41 , which asks, for every origin $i$ and destination $j$, how many travelers must journey from $i$ to $j$ in order to minimize the total cost $\sum_{i}\sum_{j}(c_{ij}-A_{j})T_{ij}$. When $\tau\to\infty$ (meaning that the first term of the free utility function in Eq. (13) is negligible), Eq. (13) is equivalent to the equal priori probability Sasaki model Tomlin68 with the solution $T_{ij}\propto O_{i}D_{j}$.

In a real transportation system, the travel cost $c_{ij}$ often follows an approximate logarithmic relationship with distance $d_{ij}$, i.e., $c_{ij}\approx\beta\ln d_{ij}$ Yan13 . Using $\beta\ln d_{ij}$ instead of $c_{ij}$ in Eq. (14), we can obtain the social gravity law

Thus far, we have achieved the goal of explaining the root of the social gravity law. The social gravity law is a macroscopic phenomenon caused by the interaction of bounded rational individuals in destination choice. In contrast, the destination choice game model considers only individual interaction but ignores individual bounded rationality, which is almost universal in practice, while the maximum entropy model, the free cost model and the Logit model reflect the randomness of individual choice decisions but do not reflect individual interaction.

The above constraints $\sum_{j}T_{ij}=O_{i}$ and $\sum_{i}T_{ij}=D_{j}$ are essential in the classic four-step travel demand forecasting models in transportation science since the second-step model predicting trip distribution requires the input values of trip production and attraction resulting from the first-step model Dios11 . However, the total number of trips $D_{j}$ attracted to destination $j$ is impossible to fix beforehand in a real transportation system since $D_{j}=\sum_{i}T_{ij}$ is the product of the individual destination choice process. In other words, $D_{j}$ is variable. In this case, the free utility model can still describe traveler destination choice behavior. For a better understanding, we transform the destination choice problem in the transportation system with multiple origin-destination pairs into an equivalent route choice problem in a network, as shown in Fig. 2. In this network, there are $M$ origin nodes, $N$ destination nodes and one dummy node $s$. There are $M\times N$ links leading from each origin node to each destination node and $N$ links leading from each destination node to the dummy node. Each origin node has $O_{i}$ travelers whose final destination in this network is the dummy node $s$. The traveler journeying from $i$ to $s$ has $N$ alternative paths. Each path is composed of two links, $ij$ and $js$. The flow along link $ij$ is $T_{ij}$, and that along $js$ is $\sum_{i}T_{ij}$. The path utility consists of the utility $u_{ij}(T_{ij})=-c_{ij}-g_{ij}(T_{ij})$ of link $ij$ and the utility $u_{j}(\sum_{i}T_{ij})=A_{j}-l_{j}(\sum_{i}T_{ij})$ of link $js$. Hence, the free utility model for this network can be written as

where $S_{i}=-\sum_{j}T_{ij}\ln\frac{T_{ij}}{O_{i}}$. In addition, some paths may not be selected since the number of trips $O_{i}$ is finite in practice; thus, constraint $T_{ij}\geq 0$ must be added to Eq. (16). Interestingly, Eq. (16) is identical to the stochastic user equilibrium (SUE) model Fisk80 for traffic assignment in transportation science. There are many algorithms that can solve this model and calculate the traffic flow on all links in the network Sheffi85 . Although the free utility model in Eq. (16) cannot provide an explicit expression of $T_{ij}$, it can better characterize collective destination choice behavior than the doubly-constrained gravity model that specifies the number of trips $D_{j}$ attracted to destination $j$.