Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
36,223 characters · 14 sections · 18 citation commands
Large-Scale Allocation of Personalized Incentives
\thispagestyle{plain} \pagestyle{plain}
Taxes and subsidies in transportation are often perceived by the population as unfair, since they neglect the alternatives actually available to each individual and the individual preferences. On the other hand, with the increase in information available to governments clarke2014governments, economic policies can be improved to consider the peculiarities of each individual. We propose a policy of personalized incentives in a framework where individuals choose between multiple alternatives options. A regulator has a limited budget that he can use to propose monetary incentives, with the goal to induce individuals to change their choice toward socially-better ones. Most incentive policies in the literature are not personalized Sun2020,HaiYang2020, with some exception Araldo2019. Differently from the latter, we seek for a method with provable performance bounds.
We define the optimal personalized-incentive policy as the allocation of incentives that maximizes social welfare (defined as the reduction of CO\textsubscript{2} emissions in the example above), for a given budget. We formalize the problem of finding a personalized-incentive policy maximizing social welfare under the regulator's budget constraint and show that it reduces to the well-known Multiple-Choice Knapsack Problem (MCKP -- \S(ref)), which has been used in several contexts, like Economics Colorni2017 and Computer Science AraldoSAC2020. To approximate the optimal policy in polynomial time, we adapt a greedy algorithm from the Operations Research literature and we analyze some of its analytical (e.g., suboptimality gap bound) and economic (e.g., diminishing returns) properties (\S(ref)). While in most of the paper we assume that the regulator knows exactly the preferences of each individual, we also study the case of imperfect information (\S(ref)).
Using data from the French census at the scale of a French department, we evaluate the CO\textsubscript{2} reduction achieved via the transportation mode incentive policy computed with our algorithm (\S (ref)). The results show that our personalized incentives achieve the same CO\textsubscript{2} reduction as flat subsidies, but with a considerably smaller amount of incentives spent. Our code is available as open source JavaudinCode2022.
We are aware that our framework is based on several idealized assumptions that makes its direct applicability difficult in practical situations, in particular for what concerns the assumption of being able to collect precise information about individual preferences. In this sense, the path toward personalized-incentives is still a long way to go. However, we argue that the theoretical findings of this paper, coupled with the continuous evolution of techniques for collecting societal big-data, while respecting privacy, provide important steps along this path.
We consider a population $\mathcal{I} \equiv \{1, \dots, m\}$ of $m$ individuals. Each individual $i\in\mathcal{I}$ chooses an alternative $j$ among an individual-specific choice-set $\mathcal{N} _{i}$. For example, we can consider individuals choosing a mode of transportation to commute to their work. In this case, the choice set could be $\mathcal{N} _{i}=\{\text{car}, \text{walk}, \text{bike}, \text{public transit}\}$. The choice set can be individual-specific so that if individual $i$ owns a car but individual $i'$ does not, we could have $\mathcal{N} _{i}=\{\text{car}, \text{walk}, \text{bike}, \text{public transit}\}$ and $\mathcal{N} _{i'}=\{\text{walk}, \text{bike}, \text{public transit}\}$.
Let $y_{i,j}>0$ be an incentive provided by the regulator to individual $i$, when she chooses alternative $j$. Since $y_{i,j}$ changes from an individual to another, such policy is personalized.
A policy influences the individual choice since the proposed monetary transfers change her utilities. The utility $U_{i,j}$ of individual $i$ when choosing alternative $j\in\mathcal{N} _{i}$ is given by $ U_{i,j} = V_{i,j} + y_{i,j}, $, where $V_{i,j}\in\mathbb{R}$ is the intrinsic utility (in the absence of policy). Each individual $i$ chooses an alternative $j^{*}_{i}$ which maximizes her utility $ j^{*}_{i} \in \operatorname*{arg\,max}_{j} U_{i,j}. $ Each alternative $j$ of individual $i$ is characterized by a social indicator $b_{i,j}\in\mathbb{R}$ (e.g., the opposite of CO\textsubscript{2} emissions induced by the commutes).
We assume the regulator has perfect information: it knows exactly the intrinsic utilities $\{V_{i,j}\}_{i,j}$ and social indicators $\{b_{i,j}\}_{i,j}$ of all the alternatives, for all the individuals. We will relax this assumption in \S(ref).
The alternative chosen by each individual $i$ in the absence of policy (i.e., where $y_{i,j}=0$, $\foralli, j$) is called default alternative, and denoted $j^0_{i} \triangleq \operatorname*{arg\,max}_{{j'}\in\operatorname*{arg\,max}_jV_{i,j}} b_{i,{j'}}$. In order to convince an individual $i$ to shift from its default alternative to any other alternative $j$, it is necessary and sufficient for the regulator to provide an incentive $w_{i,j} \triangleq V_{i,j^0_{i}} - V_{i,j}$, to compensation for the decrease of individual utility.
The regulator has to decide, for each individual $i$, which alternative to incentivize, which can be summarized by a binary decision variable $x_{i,j}$ that is equal to $1$ if the regulator wants to make individual $i$ choose alternative $j$, and $0$ otherwise. The incentive can be thus written as $y_{i,j}=x_{i,j}\cdot w_{i,j}$. The Maximum Social Welfare problem is
The objective function (ref) aims to maximize the social welfare, i.e., the sum of all social indicators, constraint (ref) indicates that the regulator cannot spend more than $Q$. Moreover, only one alternative per individual is incentivized (ref).
For any budget $Q$, we indicate with $B^*(Q)$ the maximum of the social welfare, solution of problem (ref).
Suppose now that the regulator is endowed with a maximum budget $Q$ and that he can spend any budget in the interval $Y\in[0,Q]$. To decide the exact amount of budget that is convenient to spend, it is useful to obtain the Maximum Social Welfare Curve $\mathcal{C}^*_Q$, representing the maximum social welfare reachable, $B^*(Y)$, for any budget $Y\in[0, Q]$, i.e. $ \mathcal{C}^*_Q = \left\{ \big(Y, B^*(Y) \big) \:\middle|\: Y \in [0, Q] \right\} \label{eq:max-soc-ut-curve} $, which is clearly monotone non-decreasing (the larger the budget spent, the larger the social welfare reached). Observe that, although a maximum budget $Q$ is available, the regulator may not want to indiscriminately spend it all, but may choose the actual budget to invest in incentives, based on several criteria. For instance, the regulator may use the above curve to find the minimum budget needed to reach a certain social-welfare target (see the example of Fig. (ref)).
The MCKP problem, and thus the Maximum Social Welfare problem (ref), is NP-hard Kellerer2004 . We provide in this section a polynomial time algorithm based on greedy algorithms from the Operations Research literature, which gives us solutions boundedly close to the optimum.
Before presenting the proposed algorithm, we need to “clean” the input of the problem, removing some irrelevant alternatives from the set $\mathcal{N} _{i}$ of the alternatives of any individual $i$ Kellerer2004. In broad terms, irrelevant alternatives are the ones that do not provide enough social indicator compared to the incentive amount needed to induce them. The alternatives remaining after the cleaning are usually called LP-extremes and we denote them with $\mathcal{R}_{i}\subseteq\mathcal{N} _{i}$. Figure (ref) gives the intuition behind the process of constructing the set $\mathcal{R}_{i}$, which is called concavization Zoltners1979. In the figure, alternative $3$ is irrelevant since $2$ provides a larger social indicator, while requiring less incentive. Alternative $7$ is irrelevant since it requires to spend more incentive than $6$, for a negligible gain in the social indicator. It is much more convenient to make a slightly bigger investment to induce alternative $9$, which provides a significant social indicator improvement with respect to $6$.
We follow the Operations Research literature in the slight abuse of notation of denoting with $w_{i,j}$ the incentive to be provided to the $j$-th alternative in $\mathcal{R}_{i}$. With no loss of generality, we can assume the ordering $ \label{eq:ordering} w_{i,1} < w_{i,2} < \dots < w_{i,|\mathcal{R}_{i}|} $. Obviously, the default alternative is the first alternative in the set $\mathcal{R}_{i}$ and $w_{i,1}=0$.
The incremental efficiency $\tilde{e}_{i,j}$ can be interpreted as the increase in social welfare for each monetary unit spent, when individual $i$ shifts from alternative $j-1$ to alternative $j$.
Very efficient algorithms Kellerer2004 are known to solve problem (ref), i.e., to approximate the maximum social welfare for a fixed single value of budget $Q$. However, to apply them to the Maximum Social Welfare Curve problem, in which we want to find the maximum social welfare for a range of budget values $Y\in[0,Q]$, instead of just one, we would have to run those algorithms from scratch for every single value of budget. For this reason, we build our solutions upon a simpler greedy algorithm Kellerer2004, which is less efficient to solve the Maximum Social Welfare problem (although still polynomial in time complexity), but easily extendable to also solve the Maximum Social Welfare Curve problem. The other advantage deriving from such choice is that this greedy algorithm has interesting properties that increase its practical application.
The pseudocode of the algorithm is in Algorithm (ref). The notation $[i,j]$ stands for “$j$-th alternative of individual $i$”. First, the algorithm finds all the LP-extremes alternatives and sort them by order of decreasing incremental efficiency. Then, at each iteration, the next pair $[i',j']$ with the highest incremental efficiency is picked (line (ref)). The alternative induced to $i'$ is set to $j'$ (line (ref)) and the budget is reduced by the amount of the incremental weight (ref). An additional piece of the approximation of the social welfare curve is computed (ref). The algorithm stops when the maximum budget $Q$ is depleted.
Observe that the curve $\mathcal{C}_Q$ given as output by the algorithm is an approximation of the solution $\mathcal{C}^*_Q$ of the Maximum Social Welfare Curve Problem (Section (ref)). Moreover, given any maximum budget $Q$, the algorithm returns an approximation $B(Q)$ to the solution $B^*(Q)$ of the Maximum Social Welfare Problem (ref). Note that, in order to achieve $B(Q)$, the policy issued by the algorithm does not spend the entire maximum budget $Q$, but only $\tilde{Q}\leQ$.
The algorithm also gives as output the incremental efficiency of the “split item”, denoted with $\tilde{e}_{s,t}$, useful to compute the optimality gap of the algorithm (Theorem (ref) below). The name split item, which we borrow from Kellerer2004, reminds that, when we allocate budget $Q$, we add to the solution all the LP-extreme alternatives, in decreasing order of incremental efficiency, up to the “split alternative” $[s,t]$, as $[s,t]$ actually splits the set $\mathcal{R}$ of all LP-extremes in two subsets: the first containing the alternatives to include in our solution, while we do not include the LP-extremes from the second subset.
The following statements guarantee that the result from the algorithm is boundedly close to the optimum. We omit the proofs for lack of space, which can be obtained by adapting Kellerer2004.
Fig. (ref) illustrates the property above in a small example.
Note that, since the alternatives of each individual are independent of the others, the sets $\mathcal{R}_{i}$ can be computed in parallel, thus reducing even further the computation time.
Despite our algorithm being computationally efficient, there might be cases in which it is desirable to stop it prematurely, without waiting for it to completely terminate. This can be the case when a personalized-incentive policy must be computed on-the-fly, within tight time-constraints. The following properties ensure that our algorithm is suitable to this situation, which eases its practical adoption.
The assumption that the regulator knows perfectly the utility of the individuals may seem restrictive. In this section, we show that the algorithm is still relevant when the utility is imperfectly known. From discrete-choice theory Anderson1992, we assume that intrinsic utility of alternative $j$ of individual $i$ is $V_{i,j} = \hat{V}_{i,j} + \epsilon_{i,j}$, where $\hat{V}_{i,j}$ is deterministic and $\epsilon_{i,j}$ randomly Gumbel-distributed. Their specific parameters are specified in our code JavaudinCode2022.
We assume that the regulator knows the deterministic part $\hat{V}_{i,j}$ of the utility but not the random part $\epsilon_{i,j}$.
Under this assumption, the regulator does not know the minimum incentive amount needed to induce individual $i$ to shift from her default alternative $j^0_{i}$ to another alternative $j$. A heuristic solution would be to set the incentive amount equal to the expectation of the utility difference between the two alternatives, given that $j^0_{i}$ is the default alternative chosen when there is no incentive. In this case, the incentives $\{y_{i,j}\}_{j\in\mathcal{N} _{i}}$ proposed by the regulator to individual $i$, to convince her to shift to alternative $j$, are such that $y_{i,{j'}}=0$, for any ${j'}\neqj$, and
where $\hat{y}_{i,j} = \hat{V}_{i,j^0_{i}}-\hat{V}_{i,j}$ is the difference in the deterministic part of the utility, known to the regulator.
Given an individual $i$ and an alternative $j\in\mathcal{N} _{i}$, if the regulator proposes the incentive $y_{i,j}$, as defined by (ref), then individual $i$ has a positive probability to refuse the incentive. Hence, the expenses of the regulator may be smaller than the total incentive amount proposed.
Algorithm (ref) can be used to compute a personalized-incentive policy under imperfect information, by defining new weights
At each iteration of the algorithm, the regulator proposes the incentive $w_{i',j'}$ to individual $i'$ for alternative $j'$, where $[i', j']$ is the pair of individual and alternative selected by the algorithm. The regulator observes the response of the individual to the incentive. If the individual accepts the incentive, it decreases the budget by the incentive amount. The regulator keeps proposing incentives one by one until his budget is depleted.
Note that, if an individual $i$ accepts an incentive $y_{i,j}$ for alternative $j\in\mathcal{N} _{i}$, the regulator can still propose her, later, an incentive $y_{i,{j'}}$ for another alternative ${j'}\in\mathcal{N} _{i}$. If the individual refuses the second incentive $y_{i,{j'}}$, she still receives the first incentive $y_{i,j}$.
In Section (ref), we apply the policy presented above to our case study and compare it to the case with perfect information, assuming that random terms are Gumbel-distributed. The following proposition gives the exact expression of the incentives (ref), in case of Gumbel-distributed random terms.
We consider a regulator willing to employ a limited monetary budget in order to promote eco-friendly modes of transportation in order to reduce CO\textsubscript{2} emissions.
Observed variables include city- or district-level home and work location, main mode of transportation used for commuting, and some socio-demographic variables. The modes of transportation are: car, public transit, walking, cycling and motorcycle. To estimate the utilities $V_{i,j}$ of each mode of transportation perceived by each individual, we resort to multinomial logit modeling on census data on the Rhône department (\num{222000} households) from the French statistics institute INSEE in 2015-19. To estimate the social indicators $b_{i,j}$, we use data from the French Environmental Agency ADEMEGreenHouse. Details about the datasets and the estimation procedure can be found in our repository JavaudinCode2022.
We implicitly assume that the utility and the social benefit of an individual when commuting by car or public transit does not depend on how many other individuals commute by car or by public transit. This approximation is legitimate if the number of modal shifts induced by the policy is low, so that their impact on congestion and occupation is negligible. We checked a posteriori that this latter assumption is verified in our case (less than \SI{1.60}{%} of individuals shifted mode).
We have about $2\cdot 10^5$ individuals and $10^6$ alternatives. The regulator proposes, each day, incentives to the individuals before their home-work trip. The social indicator of an alternative is the reduction in CO\textsubscript{2} emissions for the trip back and forth, with respect to the default alternative. The budget is the daily amount available to the regulator. The social welfare curve given by Alg. (ref) when daily budget is \num{3000} € is in Fig. (ref).
We then set the budget of the regulator to $Q=\num{1800}$ €. Running Algorithm (ref) with this budget required about \num{3500} iterations and took about 6 seconds (with Python, on a computer with an Intel i5-8350U 1.7GHz and 24GB of memory). The algorithm allocates practically all the budget (\num{1798.59} €), inducing modal shift of \num{1.57}% of individuals and CO\textsubscript{2} reduction by \num{18} tons per day (\SI{3.00}{%} of total CO\textsubscript{2} emissions). Thus, this policy would cost on average \num{100.61} € for each ton of CO\textsubscript{2} prevented, which is a reasonable carbon price quinet2009valeur.
Despite the small incentives, the reduction in CO\textsubscript{2} emissions is considerable. Indeed, among the individuals who received incentives, the average amount of incentives is \num{0.52} € per individual, for an average daily reduction in CO\textsubscript{2} emissions of \num{5} kilograms. Recall that alternatives providing a large reduction in CO\textsubscript{2}, while requiring small incentive, have a high efficiency. Hence, the algorithm selects first shifts achievable with a small incentive, i.e., where the individual is almost indifferent between the two alternatives, which however have a large difference in CO\textsubscript{2}. Fig.(ref) shows the distribution of the incentive amount and the CO\textsubscript{2} reduction for the incentivized individuals. For most incentives, the amount proposed to individuals is below \num{1} euro (larger incentives are rarely efficient).
Fig.(ref) compares mode share before and after the policy. Most individuals who received incentives are individuals who commuted by car and were induced to commute by public transit (\num{1.2}% of all individuals, \num{74}% of individuals who received incentives). The share of individuals commuting by car decreased by 2.4%, while public transit ridership increased by \num{4}%.
We now compute a bound of the optimality gap, i.e., the maximum additional CO\textsubscript{2} savings we would achieve if we could use a theoretical optimal policy instead of resorting to Algorithm (ref) (Theor. (ref)). Since the incremental efficiency of the split item returned by the algorithm is $\tilde{e}_{s,t}\simeq 5$ kilograms of CO\textsubscript{2} per euro and the unused budget is $Q-\tilde{Q}=1.41$ €, an optimal policy would reduce of just $5\cdot 1.41 \simeq 7$ kilograms more than Algorithm (ref), which is negligible compared to the total CO\textsubscript{2} emissions reduction of \num{18} tons provided overall.
We show in this section the performance of our allocation policy when the regulator has imperfect information about individual utilities. In this case, the allocation policy is computed as in Section (ref). Using the values of the random variables $\epsilon_{i,j}$ drawn previously, we can check whether individuals accept the incentives proposed to them. The policy stops when the daily budget of \num{1800} € is depleted.
Table (ref) compares the performance of our personalized-incentive policy under perfect and imperfect information. As expected, imperfect information decreases the efficacy of the policy. Since the regulator does not exactly know the individual utilities, it may propose insufficient incentives, which are rejected by individuals (it happens \SI{41}{%} of the times). This results in a smaller reduction of CO\textsubscript{2} (\SI{21}{%} compared with the perfect information case). Note that less individuals are involved in the incentive program (only \SI{12}{%} compared to the perfect information case) because incentive given to single individuals are on average larger, and thus the budget is depleted more quickly.
These results could be improved by learning from the responses of individual $i$ to the incentives proposed earlier in order to compute the incentives that will be proposed to her for other alternatives. For example, if the regulator observes that individual $i$ refused the incentive to shift from car to walking, he learns information on the random term of the utility for car of individual $i$.
Also, if it is not possible to propose incentives to individual $i$ for different alternatives consecutively, the regulator could propose incentives for multiple alternatives simultaneously.
These extensions cannot be carried out with Algorithm (ref). Future work could study the optimal personalized-incentive policy under imperfect information.
This paper explores a computationally efficient method for the regulator to determine the optimal incentives to be provided to each individual to alter their choices in order to maximize social welfare. Such a method requires to know the preferences of individuals, which could be possible, thanks to the wealth of data available for user nowadays, in compliance to privacy. We will more systematically study in our future work the imperfect information case, which we have here tackled empirically. Moreover, we will consider the possible congestion induced by the distribution of incentives, possibly via an iterative procedure alternating the incentive algorithm and the computation of the current level of congestion.
This work has been supported by The French ANR research project MuTAS (ANR-21-CE22-0025-01).