Steering No-Regret Learners to Optimal Equilibria

We thank the reviewer for the helpful feedback.

Bounded regret (page 1)

We mean that the regret should be bounded by a sublinear function of $T$, as is the usual assumption. We've changed it to "sublinear regret".

Algorithm 5.1: Do the sandboxing payments have the same property in the normal form case where having those payments ensures that d_i is a dominant strategy?

Yes--the ability to set these sandboxing payments is precisely what distinguishes the full-feedback case from the bandit case. As we discuss, in the bandit case, it is impossible in general to make $d_i$ dominant.

We thank the reviewer for the helpful feedback. Below we address the reviewer's questions and concerns.

Assumption that agents willingly accept being directed

We're a bit confused what the reviewer means by this. The players do not need to willingly accept anything: the only assumption we make about their behavior is that they are no-regret. In the non-pure-equilibrium setting, the players are free to ignore or disobey the recommendations of the mediator if they wish.

Should compensation be provided once they reach this equilibrium?

In our model, if the players are playing the equilibrium, they will continue to receive a small (and vanishing with time) amount of payment, just to ensure that they continue to play the equilibrium. Intuitively, this payment exists to address the case where the equilibrium is not strict.

Moreover, an alternative approach could be to simplify the model into a single step, instructing agents to directly adopt the ideal equilibrium. [...] Specifically, regarding the assumption that followers will consistently play a no-regret strategy in response to the leader's queries, especially when they are aware of the steering process towards equilibrium. [...] It is crucial for the paper to elaborate on the validity of this behavior model

The alternative model proposed by the reviewer, in which the agents would directly switch to the equilibrium upon being instructed to do so, is far stronger (and harder to justify) than the one we work with. As the reviewer also mentions, working in that model would essentially render the problem trivial, because steering to an equilibrium would then amount to nothing but telling the players what to play.

We agree that, if the players were aware of the steering process and could collude against our mediator, they could manage to "break" the algorithm by, for example, extracting high payments from the mediator. However, this would result in a "prisoner's-dilemma-like" situation where at least one player would end up having high regret.

Many "intuitive" algorithms that could be adopted by learning agents in practice, such as (projected) gradient descent, multiplicative weights, or regret matching, are no-regret dynamics. Further, a player who incurs high regret has in some sense "failed to learn", because, in hindsight, it would have done better by acting in some other way. For these reasons, we believe that the assumption of no regret is a fairly weak and reasonable assumption in our eyes (and indeed that is the reason we work with it).

We have included this discussion in the revised version.

From a technical perspective, I found it challenging to understand how the algorithms can be effectively applied to mixed-strategy equilibria through a mediator-augmented game. Specifically, when dealing with pure strategies, solving equation (2) seems feasible. However, when considering mixed strategies, X_i transforms into an infinite set, and solving equation (2) would necessitate the optimization of a non-convex problem.

Considering the infinite game in which each player selects a mixed strategy is just one way to address the issue of mixed strategies. Indeed, Monderer and Tennenholtz (2004) discuss this approach in Section 3 of their paper. It is not the way that our paper takes. Instead, our paper addresses the mixed equilibrium case by empowering the mediator to give action recommendations to the player. This augmented game is still finite (as long as the underlying game is finite, of course): the mediator has finitely many action recommendations to select from, and the player, upon seeing an action recommendation, picks among its finitely many choices of action. This augmented game is also extensive form---as such, the players' strategy spaces are still polytopes, and the optimization remains convex and efficient.

We continue our response below.

We thank the reviewer for the valuable feedback. Below we address the reviewer's concerns.

For the case of non-pure Nash equilibria, if I am not mistaken, the paper does not solve the problem that is advertised in the title/abstract/intro

For mixed equilibria, we do not believe that allowing the mediator to also give recommendations to players is too strong or far-fetched an assumption, especially given that the mediator is already interacting with the players to provide payments. Indeed, for normal-form games, Monderer and Tennenholtz (2004, Section 6) use the same principle to address mixed equilibria in their paper.

Further, for mixed equilibria, without advice, there is no hope of performing steering. This is best illustrated by example. Consider the normal-form two-player coordination game where the payoff for both players is the identity, and suppose that the mediator wishes to steer the players toward the mixed (uniform) equilibrium. Since the target equilibrium is fully mixed, every action profile (terminal history) is reached with positive probability in equilibrium; therefore, the mediator cannot give positive limiting payments to any action profile because such payments would actually appear in equilibrium. We have made this formal in Appendix D of the new version.

The above shows that without advice, steering to a mixed-Nash equilibrium is in general impossible, already in normal-form games. In extensive-form games challenges related to steering only become more acute. All in all, the discussion above shows that the definition of steering that the reviewer suggests is impossible to achieve.

The current paper mentions in passing in the introduction some of these papers by Balcan et al (see also [1] for a more recent paper) but they fail to mention that these settings work with a more realistic broadcasting device, which only reaches a small random fraction of all agents (e.g. 1%)

There are many crucial differences between our paper and the paper of Balcan et al. [1]. Namely, 1) their results apply only to a limited class of games, while our results apply to general extensive-form games; 2) using the broadcasting device of Balcan et al., which reaches only a small random fraction of all agents, does not suffice to yield optimal equilibria, but rather only yields an approximation of the optimal welfare; and 3) our results apply under a weaker behavioral assumption, namely the no-regret property.

To elaborate more on point 3) above, in Section 3 of the paper of Balcan et al. it is assumed that the dynamics consist of two phases. In the first phase a subset of the players are assumed to follow the advertising strategy, while the rest of the players are assumed to be best responding. These assumptions are quite brittle compared to our behavioral assumption of assuming the no-regret property. Similar limitations apply to the learning protocol described in Section 4 of the paper of Balcan et al.

We have included a discussion on those points (and a comparison to [1]) in the related work section of the revised version.

Why should we care enough for totally non-meaningful no-regret behaviors that do not capture any realistic algorithm either from an optimization or a behavioral point of view to be willing to accept paying an infinite amount of money when finite amount should suffice for all reasonable dynamics?

So here is how to informally stabilize all of them with a finite amount of money. Pad the target strategies with enough money at an initial phase of the algorithm. With a finite excess payoff any reasonable aggregate payoff based dynamics (not even no-regret) after some finite amount of investment will be in the attractor. This is a stronger convergence result since it is actually even guarantees last-iterate convergence (and it does so with a finite amount of money).

First of all, we do not believe that there is a definite answer as to what constitutes "reasonable dynamics." For example, the papers cited by the reviewer do not (to the best of our understanding) capture regret matching, one of the most fundamental and natural learning dynamics. Making stronger assumptions regarding the class of update rules followed by the players would limit the scope of our results, and so instead we chose to treat the problem under the much broader condition of incuring sublinear regret. As we point out in the last paragraph of our related work section, there is a recent literature in mechanism design that operates under this exact assumption.

We continue our response below.

We thank the reviewer for the helpful feedback. Below we address the reviewer's questions and concerns.

The definition of the steering problem in terms of pure Nash equilibria is also odd, since pure Nash equilibria are not guaranteed to exist.

The steering problem is defined pure strategy Nash equilibria, when are pure strategy Nash equilibria guaranteed to exist in extensive form and normal-form games? How much of the theory provided by the authors apply to mixed Nash equilibria?

As we formalize in Section 6, our results directly apply to mixed-strategy Nash equilibria as well as correlated and communication equilibria. While pure-stratgy Nash equilibria are not guaranteed to exist in general, as the reivewer correctly points out, our results apply to any extensive-form game through the notion of a mediator-augmented game (Definition 6.1).

The experiments seem also unrelated to the theoretical results (Pure Nash vs. Correlated).

There seems to be a misunderstanding here. As we explained above, our results also directly apply to correlated equilibria (see Section 6 of the paper). As a result, our experiments are directly under the umbrella of our theoretical results.

A central notion to the paper such as optimal equilibrium is not well-defined—is it one that is Pareto-optimal or that maximizes some notion of welfare?

By optimal we mean an equilibrium that, among the set of all equilibria, maximizes the objective of the mediator, as we already introduce in Definition 6.1 of the paper. This objective could be, for example, the social welfare or the revenue of a mechanism, but our results apply for any mediator objective function. Note that Sections 4 and 5 concern steering to a pure Nash equilibrium (without any underlying notion of optimality), which is why our notion of optimality is formally introduced later in Section 6 where we apply our earlier results to steer to optimal equilibria.

What is the meaning of the directness gap?

The directness gap quantifies how close players' strategies are from the direct (i.e., obedient) strategies---as prescribed by the target equilibrium.

Page 2: full feedback is not defined

The full feedback setting is introduced in the beginning of Section 5, and it means that the mediator can observe the players' strategies. We have added a reference to Section 5 in the revised version to help the reader.

Are the time iterations, the time iterations of some online learning algorithm or is this the steps of an episode? I think as is standard in the literature, the author are considering repeated-play settings...

We are indeed operating in the standard setting from the repeated games literature, as we specify in Definition 3.1.

The revelation principle is applicable beyond mechanism design as well. Here are some examples, starting with the usual mechanism design version.

• For mechanism design, the revelation principle states that, WLOG, messages are information reports and all players are honest in equilibrium. The direct strategy $\boldsymbol d_i$ for each player is the strategy that always sends honest information.
• For correlated equilibrium (and other versions thereof, e.g., EFCE), the revelation principle states that, WLOG, the signals sent to the players are action recommendations and players in equilibrium should always play the recommended actions. The strategy $\boldsymbol d_i$ for each player $i$ in this case is the strategy that always plays the recommended actions.
• Similarly, for communication equilibrium, the revelation principle states that players should both send honest information and play action recommendations in equilibrium.

These notions of revelation principle are ubiquitous when dealing with their respective equilibrium concepts, even if often they are not referred to as revelation principles (e.g., the correlated equilibrium revelation principle is often simply taken as part of the definition of correlated equilibrium). We refer the interested reader to any of the cited papers, especially to Appendix A of the cited paper Zhang et al (2023) which Section 6 uses, for more detail about augmented games and the revelation principle. We also commit to adding more detail about the revelation principle, including the above clarifications, in the final version.

Section 6 does define a notion of equilibrium and notion of steering formally, via Definitions 6.1 and 6.2. It is the revelation principle that allows the construction of the augmented game (which only includes honest messages and action recommendations) and the definition of direct strategies to be without loss of generality (i.e., without excluding any equilibria).

Please let us know what else, if anything, you believe can be improved in the presentation. Due to the lack of time remaining in the discussion period, we may not be able to revise during the discussion period, but we promise to take them into consideration in the final version.