Research map / Bandits and online learning / Online convex optimization and games
On the Convergence of No-Regret Dynamics in Information Retrieval Games with Proportional Ranking Functions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that proportional ranking functions with concave activation induce socially concave publisher games, so no-regret dynamics converge to Nash equilibrium in average, and compares activation families empirically on publisher/user welfare and convergence rate.
Problem
Strategic content publishers in search/recommendation ecosystems learn via no-regret dynamics; it is unknown which ranking functions guarantee convergence of such dynamics to equilibrium, and how ranking choice affects welfare.
Approach
Defines proportional ranking functions (PRFs) determined by a single activation function g and proves that concavity of g is equivalent to the induced games being concave and socially concave, so any no-regret dynamics converge in average to a Nash equilibrium.
Key results
- Theorem 2: for a proportional ranking function, concavity of the activation g is equivalent to the induced games being concave and socially concave, implying no-regret dynamics converge in average to an approximate Nash equilibrium.
- Simulations show a trade-off: ranking functions closer to uniform yield higher publishers' welfare, lower users' welfare, and slower convergence.
- Softmax (non-concave) activation yields linear regret growth in simulations even though dynamics converge, so no-regret guarantee fails there.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use a concave activation function in the proportional ranking function | proportional ranking functions in publishers' games · publishers' games | no-regret dynamics convergence | Helped |
| use a less uniform ranking function | Linear, Logarithmic, and Root PRFs · simulated publishers' games | users' welfare | Helped |
| use a less uniform ranking function | Linear, Logarithmic, and Root PRFs · simulated publishers' games | publishers' welfare | Hurt |
| use a less uniform ranking function | Linear, Logarithmic, and Root PRFs · simulated publishers' games | convergence rate | Helped |
| increase the penalty factor λ (ablation) | simulated publishers' games with uniform i.i.d. instances · publishers' welfare | publishers' welfare | Mixed |
| increase the penalty factor λ (ablation) | simulated publishers' games · users' welfare | users' welfare | Hurt |
| increase the penalty factor λ (ablation) | simulated publishers' games with uniform i.i.d. instances · convergence rate | convergence rate | No clear effect |
| increase the number of publishers n (ablation) | simulated publishers' games · publishers' welfare | publishers' welfare | Mixed |
| increase the number of publishers n (ablation) | simulated publishers' games · users' welfare | users' welfare | Hurt |
| increase the number of publishers n (ablation) | simulated publishers' games · convergence rate | convergence rate | Hurt |
| increase the demand support size s (ablation) | simulated publishers' games · publishers' welfare | publishers' welfare | Helped |
| increase the demand support size s (ablation) | simulated publishers' games · users' welfare | users' welfare | Hurt |
Surprising findings
- With softmax (non-concave) activation, the dynamics converge empirically but publishers' regret grows linearly, so they are not no-regret dynamics.
Limitations
- No theoretical convergence-rate analysis; guarantees are only in the average sense, while simulations show last-iterate convergence.
- Each publisher produces a single document and a specific quadratic-style integrity cost is assumed.
- No algorithm known with sublinear regret for non-concave games, so the non-concave case is not covered.
Experimental setup
Metrics: publishers' welfare users' welfare convergence rate average regret
Baselines: softmax ranking function linear PRF root PRF logarithmic PRF
Builds on: socially concave games (Even-dar et al., 2009) concave games (Rosen, 1965) LRL-OFTRL (Farina et al., 2022) publishers' game of Madmon et al. (2023)
Closest papers by meaning
- Convergence of Learning Dynamics in Information Retrieval Games (AAAI 2019 · similarity 0.91)
- No-regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests (NeurIPS 2024 · similarity 0.88)
- On the Power of Strategic Corpus Enrichment in Content Creation Games (AAAI 2025 · similarity 0.87)
- Convergence of No-Swap-Regret Dynamics in Self-Play (NeurIPS 2024 · similarity 0.86)
- Best of Both Worlds: Regret Minimization versus Minimax Play (ICML 2025 · similarity 0.85)
- No Internal Regret with Non-convex Loss Functions (AAAI 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.