Finite-Time Convergence Rates in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Authors: Eric Frankel, Kshitij Kulkarni, Dmitriy Drusvyatskiy, Sewoong Oh, Lillian J. Ratliff
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 5. Empirical Vignettes In this section, we present some empirical results targeting some of the technical assumptions. These results elucidate the effect of the decision-maker s algorithm design space on the shape of the agent game and convergence behavior. A broader set of experiments is contained in Appendix D. D. Numerical Experiments Code is available at https://github.com/Sewoong Lab/stoch-stackelberg. In this section, we present numerical examples that are aimed at exploring the limits of the theory, and numerical examples that explore applying the theory to semi-synthetic real-world simulations. In particular, we use real-world data to create semi-synthetic experiments for price setting in ride-share markets. |
| Researcher Affiliation | Academia | 1University of Washington, Seattle 2University of California, Berkeley. Correspondence to: Eric Frankel <EMAIL>. |
| Pseudocode | Yes | Algorithm 1 Epoch-Based Drift-to-Noise Control Algorithm 2 Geometric Decay Schedule Algorithm 3 Projected Stochastic Gradient Play Algorithm 4 Epoch-Based Algorithm Framework for Stochastic Stackelberg Games |
| Open Source Code | Yes | D. Numerical Experiments Code is available at https://github.com/Sewoong Lab/stoch-stackelberg. |
| Open Datasets | Yes | D.3. Quadratic Ride-Sharing Game: Semi-Synthetic Simulations We consider an example from ride-sharing markets. Demand signals may be used to create more efficient ride share markets without reducing individual revenue streams by enabling information-limited firms to recover latent demand. Using an analogous set up as in Narang et al. (2022), we explore semi-synthetic competition between two ride-share platforms seeking to maximize their revenue given that the demand they experience is influenced by their own prices as well as their competitors. The data we use is from a prior Kaggle competition.4 4Data is publicly available: https://www.kaggle.com/datasets/brllrb/uber-and-lyft-dataset-boston-ma |
| Dataset Splits | No | The data we use is from a prior Kaggle competition.4... It uses "semi-synthetic simulations" but doesn't specify how the Kaggle data was split into train/test/validation for their specific experiments. It's more about "game formulation" using data characteristics. The "simulations" use "random quadratic game instance" and "synthetic Kelly auction". |
| Hardware Specification | No | No specific hardware details are mentioned in the paper. |
| Software Dependencies | No | No specific software versions or dependencies are mentioned in the paper. |
| Experiment Setup | Yes | 5. Empirical Vignettes In this section, we present some empirical results targeting some of the technical assumptions. These results elucidate the effect of the decision-maker s algorithm design space on the shape of the agent game and convergence behavior. A broader set of experiments is contained in Appendix D. D.1. Effect of Choosing τ without a priori Knowledge of Agent Game Parameters ...we explore the choice of τ on the tracking error of the agents equilibrium relative to the appropriate equilibrium... ...the decision-maker is deploying actions to with the objective of tracking a desired equilibrium. The decision-maker may not know the agent game-related hyperparameters a priori and thus may not be able to set τ optimally as noted. D.3.1. Estimation of Price Elasticities ...if a decision-maker aims to estimate each of the Ai s i.e., the price elasticities of players then they can run online least squares where in each round t they first query the environment and observe zt,i = ξt,i + Aixt where Ai = Ai,i Ai, i . Then, they perturb the prices with actions ui for each player, and observe qt,i = Ai(xt + ut,i) + ξ t,i. With these two queries, the decision maker updates their estimate of the price elasticities as follows: ˆAt+1,i = ˆAt,i + νt(qt,i zt,i ˆAt,iut,i)u t,i, where νt is the step size. Theorem 4.4 ... using step-size η α 4L2 ℓ(1+L2eq)... epoch length τ O 1 (1 ρ2) log 2 R2 ϵτ + c2σ2 a ρ2. |