Large-Scale Allocation of Personalized Incentives Lucas Javaudin1 Andrea Araldo2 André de Palma1 1CY Cergy University lucas.javaudincyu.fr andre.de-palma.cyu.fr

2025-05-03 0 0 1.37MB 6 页 10玖币

侵权投诉

Large-Scale Allocation of Personalized Incentives

Lucas Javaudin1, Andrea Araldo2, André de Palma1

1CY Cergy University; lucas.javaudin@cyu.fr; andre.de-palma.cyu.fr

2Télécom SudParis, Institut Polytechnique de Paris; andrea.araldo@telecom-sudparis.eu

Abstract—We consider a regulator willing to drive individual

choices towards increasing social welfare by providing incentives

to a large population of individuals.

For that purpose, we formalize and solve the problem of

ﬁnding an optimal personalized-incentive policy: optimal in the

sense that it maximizes social welfare under an incentive budget

constraint, personalized in the sense that the incentives proposed

depend on the alternatives available to each individual, as well as

her preferences. We propose a polynomial time approximation

algorithm that computes a policy within few seconds and we

analytically prove that it is boundedly close to the optimum. We

then extend the problem to efﬁciently calculate the Maximum

Social Welfare Curve, which gives the maximum social welfare

achievable for a range of incentive budgets (not just one value).

This curve is a valuable practical tool for the regulator to

determine the right incentive budget to invest.

Finally, we simulate a large-scale application to mode choice

in a French department (about 200 thousands individuals) and

illustrate the effectiveness of the proposed personalized-incentive

policy in reducing CO2emissions.

I. INTRODUCTION

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 pref-

erences. On the other hand, with the increase in information

available to governments [1], economic policies can be im-

proved to consider the peculiarities of each individual. We pro-

pose 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 [2], [3], with

some exception [4]. Differently from the latter, we seek for a

method with provable performance bounds.

We deﬁne the optimal personalized-incentive policy as the

allocation of incentives that maximizes social welfare (deﬁned

as the reduction of CO2emissions in the example above),

for a given budget. We formalize the problem of ﬁnding 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

– §II), which has been used in several contexts, like Eco-

nomics [5] and Computer Science [6]. To approximate the

optimal policy in polynomial time, we adapt a greedy algo-

rithm from the Operations Research literature and we analyze

some of its analytical (e.g., suboptimality gap bound) and

economic (e.g., diminishing returns) properties (§III). 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 (§IV).

Using data from the French census at the scale of a

French department, we evaluate the CO2reduction achieved

via the transportation mode incentive policy computed with

our algorithm (§ V). The results show that our personalized

incentives achieve the same CO2reduction as ﬂat subsidies,

but with a considerably smaller amount of incentives spent.

Our code is available as open source [7].

We are aware that our framework is based on several

idealized assumptions that makes its direct applicability dif-

ﬁcult 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 ﬁndings of this paper, coupled with

the continuous evolution of techniques for collecting societal

big-data, while respecting privacy, provide important steps

along this path.

II. FRAMEWORK AND INCENTIVE POLICY

A. Model

We consider a population I ≡ {1, . . . , m}of mindi-

viduals. Each individual i∈ I chooses an alternative j

among an individual-speciﬁc choice-set Ni. For example,

we can consider individuals choosing a mode of transporta-

tion to commute to their work. In this case, the choice

set could be Ni={car,walk,bike,public transit}. The

choice set can be individual-speciﬁc so that if individ-

ual iowns a car but individual i0does not, we could

have Ni={car,walk,bike,public transit}and Ni0=

{walk,bike,public transit}.

Let yi,j >0be an incentive provided by the regulator to

individual i, when she chooses alternative j. Since yi,j changes

from an individual to another, such policy is personalized.

A policy inﬂuences the individual choice since the proposed

monetary transfers change her utilities. The utility Ui,j of

individual iwhen choosing alternative j∈ Niis given by

Ui,j =Vi,j +yi,j ,, where Vi,j ∈Ris the intrinsic utility

(in the absence of policy). Each individual ichooses an

alternative j∗

iwhich maximizes her utility j∗

i∈arg maxjUi,j .

Each alternative jof individual iis characterized by a social

indicator bi,j ∈R(e.g., the opposite of CO2emissions

induced by the commutes).

We assume the regulator has perfect information: it knows

exactly the intrinsic utilities {Vi,j }i,j and social indicators

arXiv:2210.00463v1 [econ.EM] 2 Oct 2022

{bi,j }i,j of all the alternatives, for all the individuals. We will

relax this assumption in §IV.

The alternative chosen by each individual iin the absence of

policy (i.e., where yi,j = 0,∀i, j) is called default alternative,

and denoted j0

i,arg maxj0∈arg maxjVi,j bi,j0. In order to

convince an individual ito shift from its default alternative

to any other alternative j, it is necessary and sufﬁcient for

the regulator to provide an incentive wi,j ,Vi,j0

i−Vi,j , to

compensation for the decrease of individual utility.

B. Maximum Social Welfare Problem

The regulator has to decide, for each individual i, which al-

ternative to incentivize, which can be summarized by a binary

decision variable xi,j that is equal to 1if the regulator wants

to make individual ichoose alternative j, and 0otherwise.

The incentive can be thus written as yi,j =xi,j ·wi,j . The

Maximum Social Welfare problem is

max

{xi,j }i,j X

i∈I X

j∈Ni

bi,j xi,j (1)

s.t. X

i∈I X

j∈Ni

wi,j xi,j ≤Q(2)

j∈Ni

xi,j = 1, i ∈ I (3)

xi,j ∈ {0,1}, i ∈ I, j ∈ Ni(4)

The objective function (1) aims to maximize the social welfare,

i.e., the sum of all social indicators, constraint (2) indicates

that the regulator cannot spend more than Q. Moreover, only

one alternative per individual is incentivized (3).

For any budget Q, we indicate with B∗(Q)the maximum

of the social welfare, solution of problem (1).

C. Maximum Social Welfare Curve Problem

Suppose now that the regulator is endowed with a maximum

budget Qand that he can spend any budget in the interval

Y∈[0, Q]. To decide the exact amount of budget that is

convenient to spend, it is useful to obtain the Maximum Social

Welfare Curve C∗

Q, representing the maximum social welfare

reachable, B∗(Y), for any budget Y∈[0, Q], i.e. C∗

{(Y, B∗(Y)) |Y∈[0, Q]}, which is clearly monotone non-

decreasing (the larger the budget spent, the larger the social

welfare reached). Observe that, although a maximum budget

Qis 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 ﬁnd the minimum budget needed

to reach a certain social-welfare target (see the example of

Fig. 3).

III. APPROXIMATION ALGORITHM

The MCKP problem, and thus the Maximum Social Welfare

problem (1), is NP-hard [8] . 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.

A. Preliminary Steps

Before presenting the proposed algorithm, we need to

“clean” the input of the problem, removing some irrelevant

alternatives from the set Niof the alternatives of any individ-

ual i[8, Section 11.2.1]. 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 Ri⊆ Ni. Figure 1 gives the

intuition behind the process of constructing the set Ri, which

is called concavization [9, Fig.1,2]. In the ﬁgure, alternative

3is irrelevant since 2provides a larger social indicator, while

requiring less incentive. Alternative 7is 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 signiﬁcant social indicator improvement with

respect to 6.

Fig. 1: Alternative set Niof individual iand the subset Riof

LP-extremes.

We follow the Operations Research literature in the slight

abuse of notation of denoting with wi,j the incentive to be

provided to the j-th alternative in Ri. With no loss of gener-

ality, we can assume the ordering wi,1< wi,2<··· < wi,|Ri|.

Obviously, the default alternative is the ﬁrst alternative in the

set Riand wi,1= 0.

Deﬁnition III-A.1 (Efﬁciency and incremental efﬁciency).We

deﬁne the efﬁciency of an alternative jof individual ias ei,j ,

bi,j −bi,j0

wi,j , i.e., the gain in social indicator that we can gain

via a unit of incentive allocated to that alternative.

We also deﬁne the incremental social indicator ˜

bi,j and the

incremental incentive ˜wi,j required for each alternative j∈

Rias

bi,j ,bi,j −bi,j−1

˜wi,j ,wi,j −wi,j−1

, j = 2,...,|Ri|.(5)

The incremental efﬁciency is then deﬁned as ˜ei,j ,˜

bi,j /˜wi,j .

The incremental efﬁciency ˜ei,j can be interpreted as the

increase in social welfare for each monetary unit spent, when

individual ishifts from alternative j−1to alternative j.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Large-ScaleAllocationofPersonalizedIncentivesLucasJavaudin1,AndreaAraldo2,AndrédePalma11CYCergyUniversity;lucas.javaudin@cyu.fr;andre.de-palma.cyu.fr2TélécomSudParis,InstitutPolytechniquedeParis;andrea.araldo@telecom-sudparis.euAbstractWeconsideraregulatorwillingtodriveindividualchoicestowardsincre...

展开>> 收起<<

Large-Scale Allocation of Personalized Incentives Lucas Javaudin1 Andrea Araldo2 André de Palma1 1CY Cergy University lucas.javaudincyu.fr andre.de-palma.cyu.fr.pdf

共6页,预览2页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Large-Scale Allocation of Personalized Incentives Lucas Javaudin1 Andrea Araldo2 André de Palma1 1CY Cergy University lucas.javaudincyu.fr andre.de-palma.cyu.fr

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: