Summary
The paper defines and studies a new Stackelberg games setup. Rather than making some standard assumptions --- e.g. that the principal and/or the agent exhibit specific types of play (e.g. agent playing no regret), or assuming access to the agent’s best response oracle, etc. --- this paper only assumes that the agent will be playing by best-responding to (appropriately) calibrated forecasts of the principal play. In this Calibrated Stackelberg Games setup, the authors show that: (1) The principal, by only knowing that the agent will be playing in a calibrated way, can achieve exactly (no more and no less than) the Stackelberg value of the game over a repeated interaction, by following an explore-then-commit style algorithm; (2) The agent has an efficient algorithm for producing said calibrated forecasts (in fact, strengthened by the notion of adaptivity --- meaning that calibration should hold over all subintervals of the time axis). These results are further complemented by e.g. considering both finite and continuous action spaces, as well as an adaptive calibration algorithm.
Strengths
As intended by the authors, they are able to demonstrate that Calibrated Stackelberg games indeed show potential towards relaxing/moving away from various restrictive assumptions (on what the principal and the agent observe and how they play) in the literature. An important moral takeaway is that the same old Stackelberg value --- which one might have expected might in fact require the principal and the agent to (more or less) explicitly observe each other’s play --- can be achieved over time by only asking the agent to use calibrated forecasts of the principal’s play (which is a fairly mild requirement), and the principal to know and use the fact that the agent exhibits calibration.
In fact, this conclusion is carefully shown to hold (existentially and algorithmically) both for finite and continuous action spaces --- which, while to be morally expected from standard minimax reasoning, still takes work to rigorously establish and shows thoroughness on the authors’ part.
In terms of the techniques employed, the exploration process for achieving this value on the principal’s side is, in fact, not very straightforward to design both for finite and continuous action spaces; so, there is a healthy dose of sophistication involved. The adaptive calibration algorithm, on the other hand, quite straightforwardly follows from existing techniques at the intersection of no-regret dynamics and online multiobjective settings.
Weaknesses
I did not spot any technical weaknesses, and the contribution of this paper to both the Stackelberg games and the calibration literatures is solid. So overall, the paper does not have any significant weaknesses. However,
I would, however, like to point out that the principal needing, in certain parts of this new framework, to know the calibration rate of the agent is not to be taken lightly given that an important motivation of this paper is to relax, as much as possible, the prevalent specificity, in existing literature, of the requirements on what the principal and the agent should know. I would appreciate it if the authors could provide further elaboration of this, beyond the brief mention in the conclusion.
Secondly, while having *adaptive* calibration guarantees is nice, compared to regular marginal ones, I’m not clear on how or whether this adaptivity interacts with the proposed theory of CSG or is more or less orthogonal? In other words --- okay, using the standard sleeping experts technique for establishing adaptive online guarantees, it is possible to make the agent calibrated on every [s, t] rather than just on [1, T]; but does that really matter for e.g. being able to achieve the value V* in the process of play, or any other desirable Stackelberg properties? Since the main point of the paper is to propose a theory of calibrated Stackelberg games, it is important to be clear on whether this is an essential element of such a theory or was just added to the paper for good measure. If this is in fact an essential element, I’d like to ask the authors to clarify this.
I also did find the presentation suboptimal --- the paper reads quite densely; especially, in my experience, when it comes to the proof sketch after Theorem 3.2 in Section 3. I invite the authors to revamp that part of the presentation for the rebuttal phase. Some specific things that I’d appreciate would be (1) alleviating the notational/explanatory tedium related to condition (P1) --- I am still not clear on how strong or weak it is, and where exactly things must break if it wasn’t required; (2) adding a high-level description (preferably involving more prose) of how the agent’s calibration figures into what the algorithm for the principal does.
Questions
For the substantive questions, please see my questions above on: (1) the principal needing to know the calibration rate; (2) the requirement of adaptivity of calibration; (3) some elements of Section 3 such as property (P1) etc.
Here, I’ll quickly list a sampling of a few typos and notational issues:
Line 300: bound*ed*
Line 285: Where is the notation L_g defined?
Line 276: Brackets around sigma in the subscript for g
Line 222: Probably meant to say that (h hat, y) is an equilibrium rather than just h hat
Line 201: Where is h bar_T defined?
Line 174: The fundamental constructs from Definition 2.2 are reviewed, not from Eq 1
Line 102: converged *to a* Stackelberg equilibrium
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.