Contacts:
Devansh Jalota
Devansh is a PhD student in Computational and Mathematical Engineering at Stanford University. Prior to joining Stanford, he received his BS in Civil and Environmental Engineering and BA in Applied Mathematics with highest distinction from University of California Berkeley. During his time at Berkeley, Devansh developed practically efficient tools to approach a suede of problems in the water, transportation and energy spaces, including the implementation of water purification systems in slum communities in Mumbai.Devansh’s current research interests span algorithmic game theory, market design and optimization. His current work is focused on the development of incentive schemes and market mechanisms for society to enable a smooth uptake of socially aware traffic routing strategies.
Awards:
- Departmental Citation in Civil and Environmental Engineering at UC Berkeley
ASL Publications
-
D. Jalota, D. Paccagnan, M. Schiffer, and M. Pavone, “On Online Traffic Routing: Deterministic Limits and Data-driven Enhancements,” INFORMS Journal on Computing, 2023. (In Press)
Abstract: Over the past decade, GPS enabled traffic applications, such as Google Maps andWaze, have become ubiquitous and have had a significant influence on billions of daily commuters? travel patterns. A consequence of the online route suggestions of such applications, e.g., via greedy routing, has often been an increase in traffic congestion since the induced travel patterns may be far from the system optimum routing pattern. Spurred by the widespread impact of navigational applications on travel patterns, this work studies online traffic routing in the context of capacity-constrained parallel road networks and analyzes this problem from two perspectives. First, we perform a worst-case analysis to identify the limits of deterministic online routing and show that the ratio between the online solution of any deterministic algorithm and the optimal offline solution is unbounded, even in simplistic settings. This result motivates us to move beyond worst-case analysis. Here, we consider algorithms that exploit knowledge of past problem instances and show how to design a data-driven algorithm whose performance can be quantified and formally generalized to unseen future instances. Finally, we present numerical experiments based on two application cases for the San Francisco Bay Area and evaluate the performance of our approach. Our results show that the data-driven algorithm often outperforms commonly used greedy online routing algorithms, in particular, in scenarios where the user types are heterogeneous and the network is congested.
@article{JalotaPaccagnanEtAl2023, author = {Jalota, D. and Paccagnan, D. and Schiffer, M. and Pavone, M.}, title = {On Online Traffic Routing: Deterministic Limits and Data-driven Enhancements}, journal = {{INFORMS Journal on Computing}}, year = {2023}, note = {In Press}, booktitle = {{INFORMS Journal on Computing}}, keywords = {press}, owner = {devanshjalota}, timestamp = {2023-01-01}, url = {https://arxiv.org/abs/2109.08706} } -
D. Jalota, O. M., and M. Pavone, “Matching with Transfers under Distributional Constraints,” Theoretical Economics, 2023. (Submitted)
Abstract:
@article{JalotaOstrovskyEtAl2023, author = {Jalota, D. and M., Ostrovsky and Pavone, M.}, title = {Matching with Transfers under Distributional Constraints}, journal = {Theoretical Economics}, year = {2023}, note = {Submitted}, keywords = {sub}, owner = {devanshjalota}, timestamp = {2023-01-19}, url = {https://arxiv.org/abs/2202.05232} } -
D. Jalota, J. Lazarus, A. Bayen, and M. Pavone, “Credit-Based Congestion Pricing: Equilibrium Properties and Optimal Scheme Design,” in Proc. Int. Conf. on Autonomous Agents and Multiagent Systems, 2023. (Submitted)
Abstract: Credit-based congestion pricing (CBCP) has emerged as a mechanism to alleviate the social inequity concerns of road congestion pricing - a promising strategy for traffic congestion mitigation - by providing low-income users with travel credits to offset some of their toll payments. While CBCP offers immense potential for addressing inequity issues that hamper the practical viability of congestion pricing, the deployment of CBCP in practice is nascent, and the potential efficacy and optimal design of CBCP schemes have yet to be formalized. In this work, we study the design of CBCP schemes to achieve particular societal objectives and investigate their influence on traffic patterns when routing heterogeneous users with different values of time (VoTs) in a multi-lane highway with an express lane. We introduce a new non-atomic congestion game model of a mixed-economy, wherein eligible users receive travel credits while the remaining ineligible users pay out-of-pocket to use the express lane. In this setting, we investigate the effect of CBCP schemes on traffic patterns by characterizing the properties (i.e., existence, comparative statics) of the corresponding Nash equilibria and, in the setting when eligible users have time-invariant VoTs, develop a convex program to compute these equilibria. We further present a bi-level optimization framework to design optimal CBCP schemes to achieve a central planner’s societal objectives. Finally, we conduct numerical experiments based on a case study of the San Mateo 101 Express Lanes Project, one of the first North American CBCP pilots. Our results demonstrate the potential of CBCP to enable low-income travelers to avail of the travel time savings provided by congestion pricing on express lanes while having comparatively low impacts on the travel costs of other road users.
@inproceedings{JalotaEtAl2023, author = {Jalota, D. and Lazarus, J. and Bayen, A. and Pavone, M.}, title = {Credit-Based Congestion Pricing: Equilibrium Properties and Optimal Scheme Design}, booktitle = {{Proc. Int. Conf. on Autonomous Agents and Multiagent Systems}}, year = {2023}, note = {Submitted}, keywords = {sub}, owner = {devanshjalota}, timestamp = {2022-11-21} } -
D. Jalota, K. Gopalakrishnan, N. Azizan, R. Johari, and M. Pavone, “Online Learning for Traffic Routing under Unknown Preferences,” in Int. Conf. on Artificial Intelligence and Statistics, 2023. (In Press)
Abstract: In transportation networks, users typically choose routes in a decentralized and self-interested manner to minimize their individual travel costs, which, in practice, often results in inefficient overall outcomes for society. As a result, there has been a growing interest in designing road tolling schemes to cope with these efficiency losses and steer users toward a system-efficient traffic pattern. However, the efficacy of road tolling schemes often relies on having access to complete information on users’ trip attributes, such as their origin-destination (O-D) travel information and their values of time, which may not be available in practice. Motivated by this practical consideration, we propose an online learning approach to set tolls in a traffic network to drive heterogeneous users with different values of time toward a system-efficient traffic pattern. In particular, we develop a simple yet effective algorithm that adjusts tolls at each time period solely based on the observed aggregate flows on the roads of the network without relying on any additional trip attributes of users, thereby preserving user privacy. In the setting where the O-D pairs and values of time of users are drawn i.i.d. at each period, we show that our approach obtains an expected regret and road capacity violation of O(\sqrtT), where T is the number of periods over which tolls are updated. Our regret guarantee is relative to an offline oracle that has complete information on users’ trip attributes. We further establish a Ω(\sqrtT) lower bound on the regret of any algorithm, which establishes that our algorithm is optimal up to constants. Finally, we demonstrate the superior performance of our approach relative to several benchmarks on a real-world transportation network, thereby highlighting its practical applicability.
@inproceedings{JalotaEtAl2022, author = {Jalota, D. and Gopalakrishnan, K. and Azizan, N. and Johari, R. and Pavone, M.}, title = {Online Learning for Traffic Routing under Unknown Preferences}, booktitle = {{Int. Conf. on Artificial Intelligence and Statistics}}, year = {2023}, note = {In Press}, keywords = {press}, owner = {devanshjalota}, timestamp = {2022-05-03}, url = {https://arxiv.org/abs/2203.17150} } -
D. Jalota, K. Solovey, M. Tsao, S. Zoepf, and M. Pavone, “Balancing Fairness and Efficiency in Traffic Routing via Interpolated Traffic Assignment,” in Proc. Int. Conf. on Autonomous Agents and Multiagent Systems, 2022.
Abstract: System optimum (SO) routing, wherein the total travel time of all users is minimized, is a holy grail for transportation authorities. However, SO routing may discriminate against users who incur much larger travel times than others to achieve high system efficiency, i.e., low total travel times. To address the inherent unfairness of SO routing, we study the β-fair SO problem whose goal is to minimize the total travel time while guaranteeing a β≥1 level of unfairness, which specifies the maximal ratio between the travel times of different users with shared origins and destinations. To obtain feasible solutions to the β-fair SO problem while achieving high system efficiency, we develop a new convex program, the Interpolated Traffic Assignment Problem (I-TAP), which interpolates between a fair and an efficient traffic-assignment objective. We then leverage the structure of I-TAP to develop two pricing mechanisms to collectively enforce the I-TAP solution in the presence of selfish homogeneous and heterogeneous users, respectively, that independently choose routes to minimize their own travel costs. We mention that this is the first study of pricing in the context of fair routing. Finally, we use origin-destination demand data for a range of transportation networks to numerically evaluate the performance of I-TAP as compared to a state-of-the-art algorithm. The numerical results indicate that our approach is faster by several orders of magnitude, while achieving higher system efficiency for most levels of unfairness.
@inproceedings{JalotaSoloveyEtAl2022, author = {Jalota, D. and Solovey, K. and Tsao, M. and Zoepf, S. and Pavone, M.}, title = {Balancing Fairness and Efficiency in Traffic Routing via Interpolated Traffic Assignment}, booktitle = {{Proc. Int. Conf. on Autonomous Agents and Multiagent Systems}}, year = {2022}, owner = {devanshjalota}, timestamp = {2022-03-01} } -
D. Jalota, K. Solovey, K. Gopalakrishnan, S. Zoepf, H. Balakrishnan, and M. Pavone, “When Efficiency meets Equity in Congestion Pricing and Revenue Refunding Schemes,” in ACM Conf. on Equity and Access in Algorithms, Mechanisms, and Optimization, Online, 2021.
Abstract: Congestion pricing has long been hailed as a means to mitigate traffic congestion; however, its practical adoption has been limited due to the resulting social inequity issue, e.g., low-income users are priced out off certain roads. This issue has spurred interest in the design of equitable mechanisms that aim to refund the collected toll revenues as lump-sum transfers to users. Although revenue refunding has been extensively studied for over three decades, there has been no thorough characterization of how such schemes can be designed to simultaneously achieve system efficiency and equity objectives. In this work, we bridge this gap through the study of congestion pricing and revenue refunding (CPRR) schemes in non-atomic congestion games. We first develop CPRR schemes, which in comparison to the untolled case, simultaneously (i) increase system efficiency and (ii) decrease wealth inequality, while being (iii) user-favorable: irrespective of their initial wealth or values-of-time (which may differ across users) users would experience a lower travel cost after the implementation of the proposed scheme. We then characterize the set of optimal user-favorable CPRR schemes that simultaneously maximize system efficiency and minimize wealth inequality. These results assume a well-studied behavior model of users minimizing a linear function of their travel times and tolls, without considering refunds. We also study a more complex behavior model wherein users are influenced by and react to the amount of refund that they receive. Although, in general, the two models can result in different outcomes in terms of system efficiency and wealth inequality, we establish that those outcomes coincide when the aforementioned optimal CPRR scheme is implemented. Overall, our work demonstrates that through appropriate refunding policies we can achieve system efficiency while reducing wealth inequality.
@inproceedings{JalotaEtAl2021, author = {Jalota, D. and Solovey, K. and Gopalakrishnan, K. and Zoepf, S. and Balakrishnan, H. and Pavone, M.}, title = {When Efficiency meets Equity in Congestion Pricing and Revenue Refunding Schemes}, booktitle = {{ACM Conf. on Equity and Access in Algorithms, Mechanisms, and Optimization}}, year = {2021}, address = {Online}, month = oct, owner = {devanshjalota}, timestamp = {2021-06-22}, url = {https://dl.acm.org/doi/10.1145/3465416.3483296} } -
D. Jalota, M. Pavone, Q. Qi, and Y. Ye, “Fisher Markets with Linear Constraints: Equilibrium Properties and Efficient Distributed Algorithms,” Games and Economic Behavior, 2021. (Submitted)
Abstract:
@article{JalotaPavoneEtAl2021, author = {Jalota, D. and Pavone, M. and Qi, Q. and Ye, Y.}, title = {Fisher Markets with Linear Constraints: Equilibrium Properties and Efficient Distributed Algorithms}, journal = {{Games and Economic Behavior}}, year = {2021}, note = {Submitted}, keywords = {sub}, owner = {devanshjalota}, timestamp = {2021-06-22}, url = {https://arxiv.org/abs/2106.10412} } -
D. Jalota, M. Pavone, Q. Qi, and Y. Ye, “Markets for Efficient Public Good Allocation with Social Distancing,” in The Conference on Web and Internet Economics (WINE), Beijing, China, 2020.
Abstract: Public goods are often either over-consumed in the absence of regulatory mechanisms, or remain completely unused, as in the Covid-19 pandemic, where social distance constraints are enforced to limit the number of people who can share public spaces. In this work, we plug this gap through market based mechanisms designed to efficiently allocate capacity constrained public goods. To design these mechanisms, we leverage the theory of Fisher markets, wherein each agent in the economy is endowed with an artificial currency budget that they can spend to avail public goods. While Fisher markets provide a strong methodological backbone to model resource allocation problems, their applicability is limited to settings involving two types of constraints - budgets of individual buyers and capacities of goods. Thus, we introduce a modified Fisher market, where each individual may have additional physical constraints, characterize its solution properties and establish the existence of a market equilibrium. Furthermore, to account for additional constraints we introduce a social convex optimization problem where we perturb the budgets of agents such that the KKT conditions of the perturbed social problem establishes equilibrium prices. Finally, to compute the budget perturbations we present a fixed point scheme and illustrate convergence guarantees through numerical experiments. Thus, our mechanism, both theoretically and computationally, overcomes a fundamental limitation of classical Fisher markets, which only consider capacity and budget constraints.
@inproceedings{JalotaEtAl2020, author = {Jalota, D. and Pavone, M. and Qi, Q. and Ye, Y.}, title = {Markets for Efficient Public Good Allocation with Social Distancing}, booktitle = {The Conference on Web and Internet Economics (WINE)}, year = {2020}, url = {https://arxiv.org/abs/2005.10765}, address = {Beijing, China}, month = dec, owner = {devanshjalota}, timestamp = {2020-10-10} }