- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies acquisition games and no-regret learning — an agent must acquire a prescribed quantity of a common resource within a fixed time. The state is endogenous — the market price is determined by past actions. The authors provide a proof of existence of a pure Nash Equilibrium, in addition to convergence guarantees of their learning algorithm. The major contribution is a model-free bandit algorithm demonstrating that it achieves sublinear regret and coarse correlated equilibrium.
Critical strengths
Overall I liked the paper. This paper is well written, well structured, and well motivated, with good, clear exposition.
The authors examine a relevant economic problem, and the guarantees it provides are non-trivial and useful.
The paper is well positioned against previous literature, making non-incremental contributions.
Critical weaknesses
To be honest, I didn't really identify any major weaknesses here. Perhaps one question is why the authors chose convergence to CCE and not something stronger, e.g., CE, MNE, etc., or something like Bayes NE.
Furthermore, some more ablation studies could be conducted here to demonstrate more robustness.
Questions for authors
I would like to know whether this work could extend to other games, like inventory procurement games, Bertrand/Cournot oligopolies, and Newsvendor settings, and if the authors have any insight on the key relationships.
Suppose there is collusion among the players in the system — how would this affect the algorithm if multiple agents collude to avoid the equilibrium solution and attempt a different learning algorithm as a subset?
Soft quota: what if the quota specification is a soft requirement — agents aim to hit the quota but receive a gradual penalty if they don't meet it — how would the results likely change?
2 comments
I thank the authors for their qualifications - the work is clearer.
I encourage the author(s) to add further remarks to the paper regarding:
-
" A competitive multi-firm, multi-period newsvendor variant fits our framework if firms allocate fixed requirements over time and their orders affect a common transient price, under the conditions above."
-
"The colluded game is thus an acquisition game with fewer agents."
-
"... soft quotas" etc.
Perhaps, some additional content in the Appendix to highlight the relation/reduction to soft quotas, multi-period Newsvendor, and collusion would help improve the paper.
My score remains the same - impression positive.
Response to Reviewer 4Sfg: Possible extensions to other games, robustness, agent collusion and soft quota
We thank the reviewer for their careful reading and insightful questions.
Convergence to CCE. Where the structure of the game allows it, we obtain stronger notions. Across episodes, we prove O(1/K) mean-square last-iterate convergence to the unique Nash equilibrium (Theorem 3.1) and, with private random quotas, to the unique Bayesian Nash equilibrium (Theorem 3.2).
CCE appears only in within-episode learning. The quota-constrained acquisition game of Sections 2–4 and the canonical policy game of Section 5 have different information and strategy structures. The latter is a finite game over scheduling policies, where the strong monotonicity behind Nash convergence is lost. PB-Exp3 bounds the regret against every fixed policy in the library, and such no-regret dynamics lead to CCE (Theorem 5.2). We stress that the CCE result is not a weaker replacement for Nash convergence. It concerns a different game defined on the same price dynamics.
Convergence to CE requires bounding swap regret. Since our coupling argument does not depend on how policies are selected, a bandit swap-regret algorithm (Blum & Mansour, 2007) would give convergence to a CE of the policy game. Last-iterate convergence to (mixed) Nash equilibrium would require additional structure on the policy game.
Robustness. Our work is mainly theoretical. We analyze price and state noise (Appendices E.5 and G.7), misspecified impact parameters (Appendix E.5) and estimation of γ (Appendix E.5.1). Experiments test Bayesian learning with price or state noise (Figure 1(a)); price-oblivious and price-responsive libraries against, respectively, demand with one-period memory and time-varying demand (H.3); fixed-policy sensitivity for γ∈{0.3,0.6,0.9,1} (Figure 7); CCE with reset/inherited impact and growing blocks (H.4); tight/wide PB-Exp3 loss intervals (H.3); and omission of the forward term or permanent-impact belief in the correction and step size (Appendix I).
Extensions to other classes of games. For single-period versions of the games mentioned by the reviewer, if losses are convex, the pseudo-gradient is strongly monotone and gradient feedback is available, standard methods for monotone games guarantee convergence to equilibrium (e.g., Mertikopoulos & Zhou, 2019).
We understand that the question concerns their dynamic extensions, in which each player allocates a fixed quota over time and aggregate decisions affect a common state. The standard Cournot, Bertrand and (single-agent) newsvendor models have no intertemporal quota constraints. Inventory-procurement models may have requirements, but rarely an exact requirement constraint over a fixed time horizon. Our repeated-episode argument applies to their dynamic quota-constrained extensions under the same convexity, monotonicity and gradient-observability conditions. This includes multi-period procurement and Cournot-type models with aggregate prices and a transient state. The within-episode technique is model-free and instead requires bounded costs, finite-memory competing responses, and a horizon-independent bound on the difference between realized and counterfactual policy costs.
Classical Bertrand competition may exhibit discontinuous demand and is not covered by our approach. A competitive multi-firm, multi-period newsvendor variant fits our framework if firms allocate fixed requirements over time and their orders affect a common transient price, under the conditions above.
Agent collusion. Across episodes, the O(logK) regret bound holds against arbitrary, even adversarial, competing schedules, and remains valid under agent collusion. Within an episode, the policy-regret bound holds whenever the competitors' demand depends only on the agent's current and last m actions and their response rule is fixed before the episode.
Regarding convergence to equilibrium, a self-interested coalition S that minimizes its members' total cost acts as a single agent with accumulated quota. The colluded game is thus an acquisition game with fewer agents. If the coalition, like the other agents, runs Algorithm 1 on its aggregate schedule, learning converges to the equilibrium of the new game (which generally differs from that of the original game).
Soft quotas. Hard quotas are among the most challenging aspects of our work. A convex shortfall penalty preserves strong monotonicity. Hence existence, uniqueness and our repeated-episode guarantees carry over, with the gradient of (5) plus the agent's own penalty derivative. Then, the total volume acquired within an episode becomes a strategic choice, which adds a Cournot-type externality in volumes to the timing externality we study. Within an episode, exploiting the softness would need a separate coupling argument. The Ω(T) lower bound depends on exact completion. With soft quota, it requires a sufficiently steep penalty and a separate argument.
The revised version includes these remarks.