Kshitij Kulkarni and S. Shankar Sastry

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2022-217

August 18, 2022

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-217.pdf

Tolls and incentives are tools that can be used by societal-scale system designers to steer selfish players to social optimality in a variety of settings. Some representative examples include traffic routing and competition between firms. These tools have been studied heavily in static settings, but in many situations, players are learning or updating their strategies in response to changing system conditions. We ask two questions: 1) In setting tolls on traffic networks, how can a traffic authority design tolls that induce socially optimal traffic loads with dynamically arriving travelers who make selfish routing decisions? 2) In the more general setting of atomic and nonatomic games, how can a planner adaptively incentivize selfish agents who are learning in a strategic environment to induce a socially optimal outcome in the long run?

To answer both questions, we propose toll and incentive updates that account for the externality created by the players as measured by the planner's objective function over time. These dynamics, when coupled to the strategy update dynamics of the selfish players, run at a slower timescale. In the case of traffic routing, we consider load updates in which inflows and outflows into the network are stochastically realized, and such that the travelers are myopic. We show that the toll and load updates converge to a neighborhood of the socially optimal loads. In the general case of atomic and nonatomic games, we provide sufficient conditions for the incentive and strategy updates to converge asymptotically to social optimality, and provide applications that satisfy these conditions, including Cournot competition and quadratic aggregative games. This thesis is the compilation of the two works [28] and [27].

Advisors: S. Shankar Sastry

---

BibTeX citation:

@mastersthesis{Kulkarni:EECS-2022-217,
    Author= {Kulkarni, Kshitij and Sastry, S. Shankar},
    Title= {Social Optimality via Dynamic Tolling and Adaptive Incentive Design},
    School= {EECS Department, University of California, Berkeley},
    Year= {2022},
    Month= {Aug},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-217.html},
    Number= {UCB/EECS-2022-217},
    Abstract= {Tolls and incentives are tools that can be used by societal-scale system designers to steer selfish players to social optimality in a variety of settings. Some representative examples include traffic routing and competition between firms. These tools have been studied heavily in static settings, but in many situations, players are learning or updating their strategies in response to changing system conditions. We ask two questions: 1) In setting tolls on traffic networks, how can a traffic authority design tolls that induce socially optimal traffic loads with dynamically arriving travelers who make selfish routing decisions? 2) In the more general setting of atomic and nonatomic games, how can a planner adaptively incentivize selfish agents who are learning in a strategic environment to induce a socially optimal outcome in the long run? 

To answer both questions, we propose toll and incentive updates that account for the externality created by the players as measured by the planner's objective function over time. These dynamics, when coupled to the strategy update dynamics of the selfish players, run at a slower timescale. In the case of traffic routing, we consider load updates in which inflows and outflows into the network are stochastically realized, and such that the travelers are myopic. We show that the toll and load updates converge to a neighborhood of the socially optimal loads. In the general case of atomic and nonatomic games, we provide sufficient conditions for the incentive and strategy updates to converge asymptotically to social optimality, and provide applications that satisfy these conditions, including Cournot competition and quadratic aggregative games. This thesis is the compilation of the two works [28] and [27].},
}

EndNote citation:

%0 Thesis
%A Kulkarni, Kshitij 
%A Sastry, S. Shankar 
%T Social Optimality via Dynamic Tolling and Adaptive Incentive Design
%I EECS Department, University of California, Berkeley
%D 2022
%8 August 18
%@ UCB/EECS-2022-217
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-217.html
%F Kulkarni:EECS-2022-217