Online Constraint Satisfaction via Tolls in MDP Congestion Games

Sarah H. Q. Li, Yue Yu, Daniel J. Calderone, Lillian J. Ratliff, Behçet AçikmesearXiv 2019 · arXiv · OpenReview

TL;DR

This paper introduces a novel algorithm for setting tolls in transportation networks to enforce system-wide constraints (like reducing congestion) even when the exact costs of player behavior are unknown. By leveraging an "inexact oracle" that estimates player responses to tolls, the algorithm iteratively adjusts tolls to satisfy constraints on average, minimizing the impact on individual drivers.

What Problem Does This Paper Address?

Imagine a city trying to reduce traffic congestion during rush hour. A common approach is to implement tolls. However, setting the right toll is tricky. It requires understanding how drivers will react to different toll levels, which in turn depends on their individual costs (fuel, time, etc.). In complex systems like urban transportation, these costs are often unknown or hard to model precisely. This paper tackles the challenge of finding the optimal toll to enforce system-level constraints (e.g., limiting the number of cars in a certain area) when the underlying player behavior (driver cost functions) is not perfectly known. They frame this as an "MDP congestion game" where players (drivers) make decisions over time, and the system operator (city or ride-sharing company) wants to influence their collective behavior through tolls.

Methods

The core of the paper is a new algorithm for iteratively determining the minimum toll required to satisfy constraints. Here's a breakdown:

  • MDP Congestion Game Framework: They model the system as a Markov Decision Process (MDP) congestion game. This means players (drivers) make sequential decisions, and their costs depend on the aggregate behavior of all players (how many drivers choose a particular route or zone).
  • Unknown Congestion Costs: A key assumption is that the system operator doesn't know the exact cost functions of the drivers. This is a realistic scenario for many real-world applications.
  • Inexact Oracle: Instead of knowing the exact driver response, they assume an "inexact oracle." This oracle can take a toll value and return an approximate optimal population distribution (e.g., how drivers would distribute themselves) for that toll. This is motivated by model-free learning algorithms that can estimate equilibrium behavior.
  • Gradient Descent on Tolls: The algorithm uses a gradient descent approach, but instead of directly optimizing the system's objective, it optimizes the toll value. The "gradient" it uses is derived from the inexact oracle's output, effectively giving an estimate of how changing the toll affects the constraint violation.
  • Myopic Update: The algorithm is "myopic" in that it makes decisions based on the current state and estimated responses, iteratively refining the toll.
  • Constraint Satisfaction on Average: The algorithm aims to ensure that the constraints are met on average over time, acknowledging that perfect satisfaction at every single moment might be too strict or impossible with unknown costs.

Datasets

  • NYC Taxi and Limousine Commission (TLC) Data: The authors use real-world data from the NYC TLC, specifically six hundred thousand trip records from yellow taxis in January 2019. This data is used to model driver behavior, trip times, and demand for a ride-sharing congestion game.
  • Uber's NYC Pay Rate: Information on Uber's pay structure is also incorporated to model driver incentives.

Key Insights and Ideas

  • Tolls as a Lever for Unknown Costs: The paper demonstrates that tolls can be an effective mechanism for controlling system behavior even when the precise cost functions of individual agents are unknown. The key is to use an oracle that can estimate their response.
  • The Power of "Good Enough" Information: The concept of an "inexact oracle" is crucial. It shows that perfect knowledge isn't always necessary; a reasonably accurate estimate of player behavior is sufficient for the gradient descent approach to converge.
  • Balancing System Goals and Individual Earnings: The application to ride-sharing drivers highlights a critical trade-off. The algorithm aims to reduce congestion (a system-level goal) while also analyzing its impact on driver earnings. The findings suggest that well-designed tolls might not significantly harm earnings and could even improve them by reducing overall congestion.
  • Average Constraint Satisfaction is Achievable: The algorithm's focus on average constraint satisfaction is a practical approach for dynamic systems where perfect real-time control is difficult.

Key Results

  • Algorithm 1: The proposed iterative toll synthesis algorithm is presented and analyzed.
  • Convergence Guarantees: Theoretical results are provided for the convergence of the average toll value and the average population distribution towards optimal values, as well as the average constraint violation towards zero. The convergence rates are shown to be sublinear, influenced by the accuracy of the inexact oracle.
  • NYC Ride-Share Simulation: A simulation using NYC TLC data for ride-share drivers in Manhattan demonstrates the algorithm's effectiveness.
  • The algorithm successfully reduced the average constraint violation (e.g., number of drivers in congested zones) from over 200 to less than 10 drivers per time step per state.
  • The average toll value converged to a reasonable level (around $1 per time step per state).
  • Empirical results showed that tolling did not significantly impact driver earnings, and in some cases, social cost (which can be related to driver earnings) even decreased.
  • Impact of Oracle Accuracy: The study shows that higher accuracy from the inexact oracle leads to lower toll values and reduced constraint violation.

Limitations and Future Work

  • Sublinear Convergence: The convergence of the toll value and population distribution is sublinear, meaning it can take many iterations to reach a very precise solution.
  • Constant Error Oracle: The analysis often assumes a constant error for the inexact oracle. The impact of varying error levels could be further explored.
  • General Convex Constraints: The current work focuses on affine constraints. The authors suggest extending the toll synthesis method to handle more general convex constraints.
  • Model-Free Learning Integration: While motivated by model-free learning, the paper primarily uses an assumed oracle. Further work could integrate actual model-free learning algorithms to generate the inexact oracle outputs in a truly end-to-end fashion.

Summary updated

Abstract

Under the Markov decision process (MDP) congestion game framework, we study the problem of enforcing population distribution constraints on a population of players with stochastic dynamics and coupled congestion costs. Existing research demonstrates that the constraints on the players' population distribution can be satisfied by enforcing tolls. However, computing the minimum toll value for constraint satisfaction requires accurate modeling of the player's congestion costs. Motivated by settings where an accurate congestion cost model is unavailable (e.g. transportation networks), we consider an MDP congestion game with unknown congestion costs. We assume that a constraint-enforcing authority can repeatedly enforce tolls on a population of players who converges to an $\epsilon$-optimal population distribution for any given toll. We then construct a myopic update algorithm to compute the minimum toll value while ensuring that the constraints are satisfied on average. We analyze how the players' sub-optimal responses to tolls impact the rates of convergence towards the minimum toll value and constraint satisfaction. Finally, we construct a congestion game model for Uber drivers in Manhattan, New York City (NYC) using data from the Taxi and Limousine Commission (TLC) to illustrate how to efficiently reduce congestion while minimizing the impact on driver earnings.
BibTeX
@misc{li2019online,
  author = {Sarah H. Q. Li and Yue Yu and Daniel J. Calderone and Lillian J. Ratliff and Behçet Açikmese},
  title = {{Online Constraint Satisfaction via Tolls in MDP Congestion Games}},
  year = {2019},
  eprint = {1907.08912},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1907.08912},
}

Loading related content...

Figure