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, M. Tsao, and M. Pavone, “Catch Me If You Can: Combatting Fraud in Artificial Currency Based Government Benefits Programs,” in ACM Conf. on Economics and Computation, New Haven, United States, 2024. (Submitted)
Abstract: Artificial currencies have grown in popularity in many real-world resource allocation settings. In particular, they have gained traction in government benefits programs, e.g., food assistance or transit benefits programs, that provide support to eligible users in the population, e.g., through subsidized food or public transit. However, such programs are prone to two common fraud mechanisms: (i) misreporting fraud, wherein users can misreport their private attributes to gain access to more artificial currency (credits) than they are entitled to, and (ii) black market fraud, wherein users may seek to sell some of their credits in exchange for real money. In this work, we develop mechanisms to address these two sources of fraud in artificial currency based government benefits programs. To address misreporting fraud, we propose an audit mechanism that induces a two-stage game between an administrator and users, wherein the administrator running the benefits program can audit users at some cost and levy fines against them for misreporting their information. For this audit game, we first investigate the conditions on the administrator’s budget to establish the existence of equilibria and present a linear programming approach to compute these equilibria under both the signaling game and Bayesian persuasion formulations. We then show that the decrease in misreporting fraud corresponding to our audit mechanism far outweighs the spending of the administrator to run it by establishing that its total costs are lower than that of the status quo with no audits. To highlight the practical viability of our audit mechanism in mitigating misreporting fraud, we present a case study on Washington D.C.’s federal transit benefits program where the proposed audit mechanism even demonstrates several orders of magnitude improvement in total cost compared to a no-audit strategy for some parameter ranges.
@inproceedings{JalotaTsaoEtAl2023, author = {Jalota, D. and Tsao, M. and Pavone, M.}, title = {Catch Me If You Can: Combatting Fraud in Artificial Currency Based Government Benefits Programs}, booktitle = {{ACM Conf. on Economics and Computation}}, year = {2024}, address = {New Haven, United States}, month = jul, url = {https://arxiv.org/abs/2402.16162}, keywords = {sub}, owner = {devanshjalota}, timestamp = {2023-07-02} } -
D. Jalota, M. Ostrovsky, and M. Pavone, “When Simple is Near-Optimal in Security Games,” in ACM Conf. on Economics and Computation, New Haven, United States, 2024. (Submitted)
Abstract: Fraudulent or illegal activities are ubiquitous across applications and involve users bypassing the rule of law, often with the strategic aim of obtaining some benefit that would otherwise be unattainable within the bounds of lawful conduct. However, user fraud is detrimental, as it may compromise safety or impose disproportionate negative externalities on particular population groups. To mitigate the potential harms of user fraud, we study the problem of policing such fraud as a security game between an administrator and users. In this game, an administrator deploys R security resources (e.g., police officers) across L locations and levies fines against users engaging in fraud at those locations. For this security game, we study both welfare and revenue maximization administrator objectives. In both settings, we show that computing the optimal administrator strategy is NP-hard and develop natural greedy algorithm variants for the respective settings that achieve at least half the welfare or revenue as the welfare-maximizing or revenue-maximizing solutions, respectively. We also establish a resource augmentation guarantee that our proposed greedy algorithms with one extra resource, i.e., R+1 resources, achieve at least the same welfare (revenue) as the welfare-maximizing (revenue-maximizing) outcome with R resources. Finally, since the welfare and revenue-maximizing solutions can differ significantly, we present a framework inspired by contract theory, wherein a revenue-maximizing administrator is compensated through contracts for the welfare it contributes. Beyond extending our theoretical results in the welfare and revenue maximization settings to studying equilibrium strategies in the contract game, we also present numerical experiments highlighting the efficacy of contracts in bridging the gap between the revenue and welfare-maximizing administrator outcomes.
@inproceedings{JalotaEtAl2024, author = {Jalota, D. and Ostrovsky, M. and Pavone, M.}, title = {When Simple is Near-Optimal in Security Games}, booktitle = {{ACM Conf. on Economics and Computation}}, year = {2024}, address = {New Haven, United States}, month = jul, keywords = {sub}, url = {https://arxiv.org/abs/2402.11209}, owner = {devanshjalota}, timestamp = {2024-03-01} } -
D. Berriaud, E. Elokda, D. Jalota, E. Frazzoli, M. Pavone, and F. Dorfler, “To Spend or to Gain: Online Learning in Repeated Karma Auctions,” in ACM Conf. on Economics and Computation, New Haven, United States, 2024. (Submitted)
Abstract: Recent years have seen a surge of artificial currency-based mechanisms in contexts where monetary instruments are deemed unfair or inappropriate, e.g., for traffic congestion management or allocation of food donations. Yet the applicability of these mechanisms remains limited, since it is challenging for users to learn how to bid an artificial currency that has no value outside the mechanism. Indeed, users must learn the value of the currency as well as how to optimally spend it in a coupled manner. In this paper, we study learning to bid in two prominent classes of artificial currency auctions: those in which currency is issued at the beginning of a finite period only to be spent over the period; and those where in addition to the initial endowment currency is transferred among users by redistributing payments in each time step. In the latter class the currency has been referred to as karma, since users do not only spend karma to acquire public resources but also gain karma for yielding them. In both classes, we propose a simple learning strategy, called adaptive karma pacing strategy, and show that a) it is asymptotically optimal for a single agent bidding against a stationary competition; b) it leads to convergent learning dynamics when all agents adopt it; and c) it constitutes an approximate Nash equilibrium as the number of agents grows. This requires a novel analysis in comparison to adaptive pacing strategies in monetary auctions, since we depart from the classical assumption that the currency has known value outside the auctions. The analysis is further complicated by the possibility to both spend and gain currency in auctions with redistribution.
@inproceedings{BerriaudElokdaEtAl2024, author = {Berriaud, D. and Elokda, E. and Jalota, D. and Frazzoli, E. and Pavone, M. and Dorfler, F.}, title = {To Spend or to Gain: Online Learning in Repeated Karma Auctions}, booktitle = {{ACM Conf. on Economics and Computation}}, year = {2024}, address = {New Haven, United States}, month = jul, keywords = {sub}, owner = {devanshjalota}, timestamp = {2024-03-01} } -
C. Chiu, D. Jalota, and M. Pavone, “Credit vs. Discount-Based Congestion Pricing: A Comparison Study,” in Proc. IEEE Conf. on Decision and Control, 2024. (Submitted)
Abstract: Tolling, or congestion pricing, offers a promising traffic management policy for regulating congestion, but has also attracted criticism for placing outsized financial burdens on low-income users. Credit-based congestion pricing (CBCP) and discount-based congestion pricing (DBCP) policies, which respectively provide travel credits and toll discounts to low-income users on tolled roads, have emerged as promising mechanisms for reducing traffic congestion without worsening societal inequities. However, the optimal design of CBCP and DBCP policies, as well as their relative advantages and disadvantages, remain poorly understood. To address this, we study the effects of implementing CBCP and DBCP policies to route users on a network of multi-lane highways with tolled express lanes. We formulate a non-atomic routing game framework in which a subset of eligible users is granted toll relief in the form of a fixed budget or toll discount, while the remaining ineligible users must pay out-of-pocket. We prove the existence of Nash equilibrium traffic flow patterns corresponding to any given CBCP or DBCP policy. Under the additional assumption that eligible users have time-invariant VoTs, we provide a convex program to efficiently compute these equilibria. For networks consisting of a single edge, we identify conditions under which CBCP policies outperform DBCP policies (and vice versa), in the sense of improving eligible users’ access to the express lane. Finally, we present empirical results from a CBCP pilot study of the San Mateo 101 Express Lane Project in California. Our empirical results corroborate our theoretical analysis of the impact of deploying credit-based and discount-based policies, and lend insights into the sensitivity of their impact with respect to the travel demand and users’ VoTs.
@inproceedings{ChiuJalotaEtAl2024, author = {Chiu, C. and Jalota, D. and Pavone, M.}, title = {Credit vs. Discount-Based Congestion Pricing: A Comparison Study}, booktitle = {{Proc. IEEE Conf. on Decision and Control}}, year = {2024}, keywords = {sub}, owner = {devanshjalota}, url = {https://arxiv.org/abs/2403.13923}, timestamp = {2024-03-25} } -
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 IEEE Transactions on Control of Network Systems, 2023. (In Press)
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{JalotaSoloveyGopalakrishnanEtAl2023, 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 = {{IEEE Transactions on Control of Network Systems}}, note = {In press}, year = {2023}, month = oct, keywords = {press}, owner = {devanshjalota}, timestamp = {2021-06-22}, url = {https://ieeexplore.ieee.org/document/10319707} } -
D. Jalota, K. Solovey, M. Tsao, S. Zoepf, and M. Pavone, “Balancing Fairness and Efficiency in Traffic Routing via Interpolated Traffic Assignment,” Autonomous Agents and Multi-Agent Systems, vol. 37, no. 32, pp. 1–40, 2023.
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.
@article{JalotaSoloveyEtAl2023, 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}, journal = {{Autonomous Agents and Multi-Agent Systems}}, volume = {37}, number = {32}, pages = {1--40}, year = {2023}, keywords = {pub}, asl_url = {https://link.springer.com/article/10.1007/s10458-023-09616-7}, owner = {devanshjalota}, timestamp = {2024-02-29} } -
D. Jalota, M. Pavone, Q. Qi, and Y. Ye, “Fisher Markets with Linear Constraints: Equilibrium Properties and Efficient Distributed Algorithms,” Games and Economic Behavior, vol. 141, pp. 223–260, 2023.
Abstract:
@article{JalotaPavoneEtAl2023, 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}}, volume = {141}, number = {}, pages = {223--260}, year = {2023}, keywords = {pub}, owner = {devanshjalota}, timestamp = {2024-02-29}, url = {https://arxiv.org/abs/2106.10412} } -
D. Jalota, D. Paccagnan, M. Schiffer, and M. Pavone, “Online Routing Over Parallel Networks: Deterministic Limits and Data-driven Enhancements,” INFORMS Journal on Computing, vol. 35, no. 3, pp. 560–577, 2023.
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 = {Online Routing Over Parallel Networks: Deterministic Limits and Data-driven Enhancements}, journal = {{INFORMS Journal on Computing}}, volume = {35}, number = {3}, pages = {560--577}, year = {2023}, booktitle = {{INFORMS Journal on Computing}}, keywords = {pub}, owner = {devanshjalota}, timestamp = {2023-01-01}, url = {https://arxiv.org/abs/2109.08706} } -
D. Jalota, M. Ostrovsky, and M. Pavone, “Matching with Transfers under Distributional Constraints,” Games and Economic Behavior, 2023. (Submitted)
Abstract:
@article{JalotaOstrovskyEtAl2023, author = {Jalota, D. and Ostrovsky, M. and Pavone, M.}, title = {Matching with Transfers under Distributional Constraints}, journal = {{Games and Economic Behavior}}, 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. IEEE Conf. on Decision and Control, 2023.
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. IEEE Conf. on Decision and Control}}, year = {2023}, keywords = {pub}, owner = {devanshjalota}, timestamp = {2023-04-01} } -
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.
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}, keywords = {pub}, 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, “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} }