Imperfect Best-Response Mechanisms

Abstract

Best-response Mechanisms, introduced by Nisan et al. (2011) provide a unifying framework for studying various distributed protocols in which the participants are instructed to repeatedly best respond to each others’ strategies. Two fundamental features of these mechanisms are convergence and incentive compatibility. This work investigates convergence and incentive compatibility conditions of such mechanisms when players are not guaranteed to always best respond but they rather play an imperfect best-response strategy. That is, at every time step every player deviates from the prescribed best-response strategy according to some probability parameter. The results explain to what extent convergence and incentive compatibility depend on the assumption that players never make mistakes, and how robust such protocols are to “noise” or “mistakes”.

Appendices

Appendix A: Models for limited knowledge and bounded rationality

1.1 A.1 Mutation and mistakes models

The mutation and the mistakes models adopt the same response rule: at every time step, each selected player updates her strategy to the best response to what other players are currently doing except with probability ε. With such a probability, a mutation or mistake occurs, meaning that the selected player chooses a strategy uniformly at random. That is, suppose player i is selected at time step t and the current strategy profile is s ^t. We denote with $b_{i}(\mathbf {s}^{t})$ the best response of i to profile s ^t (if more than one best response exists and the current strategy ${x^{t}_{i}}$ of i is a best response, then we set $b_{i}(\mathbf {s}^{t}) = {x^{t}_{i}}$, otherwise we choose one of the best responses uniformly at random). Then, a strategy s _j ∈S _i will be selected by i with probability

$$p_{ij} = \left\{\begin{array}{ll} (1-\varepsilon) + \varepsilon \cdot \frac{1}{|S_{i}|}, & \text{if } s_{j} = b_{i}(\mathbf{s}^{t});\\ \varepsilon \cdot \frac{1}{|S_{i}|}, & \text{otherwise.} \end{array}\right. $$

The main difference between these models concerns the schedule: the mutation model assumes that at each time step every player is selected for update; the mistakes model assumes that at each time step only one player is selected uniformly at random for update.

1.2 A.2 Logit dynamics

Logit dynamics is another kind of imperfect best response dynamics in which the probability of deviating from best response is determined by a parameter β≥0. The logit dynamics for a game G with parameter β runs as follows. At every time step

• 1. Select one player i uniformly at random;

• 2. Update the strategy of player i according to the following probability distribution:

  $$\sigma_{i}(s_{i},\mathbf{s}_{-i}) = \frac{e^{\beta u_{i}(s_{i},\mathbf{s}_{-i})}}{Z(\mathbf{s}_{-i})}, $$

  where $Z(\mathbf {s}_{-i})={\sum }_{s_{i}^{\prime }}e^{\beta u_{i}(s_{i}^{\prime },\mathbf {s}_{-i})}$ and β≥0.

Remark 5

The parameter β is sometimes called the “inverse noise” parameter: for β=0 the player chooses the strategy uniformly at random, while for $\beta \rightarrow \infty$ the player chooses a best response (if more than one best response is available, she selects one of these uniformly at random). Thus, the probability that i plays a best response is guaranteed to be least 1/|S _i |. So, every logit dynamics is p-imperfect for some p<1. Moreover, if the payoffs between a best response and a non-best response differ by at least γ, then the dynamics is p-imperfect with p≤(m−1)/(m−1+e ^γβ).

The above dynamics defines an ergodic Markov chain [7] over the set of all strategy profiles and with transition probabilities P given by

$$P(\mathbf{s}, \mathbf{s}^{\prime}) = \frac{1}{n} \cdot \left\{\begin{array}{ll} \sigma_{i}(s_{i} ,\mathbf{s}_{-i}), & \quad \text{ if } \mathbf{s}_{-i} = \mathbf{s}^{\prime}_{-i} \text{ and } s_{i} \neq s^{\prime}_{i}; \\ {\sum}_{i=1}^{n} \sigma_{i}(s_{i} , \mathbf{s}_{-i}), & \quad \text{ if } \mathbf{s} = \mathbf{s}^{\prime}; \\ 0, & \quad \text{ otherwise.} \end{array}\right. $$

Since the Markov chain is ergodic, the chain converges to its (unique) stationary distribution π. That is, for any starting profile s and any profile $\mathbf {s}^{\prime }$,

$$\lim\limits_{t \rightarrow \infty} P^{t}(\mathbf{s},\mathbf{s}^{\prime}) = \pi(\mathbf{s}^{\prime}), $$

where $P^{t}(\mathbf {s},\mathbf {s}^{\prime })$ is the probability that the dynamics starting with profile s is in profile $\mathbf {s}^{\prime }$ after t steps. Thus, the stationary distribution represents the equilibrium reached by the logit dynamics, also called the logit equilibrium of game G [4].

The stationary distribution of logit dynamics is fully understood for the class of so-called potential games. We recall that a game is a potential game if there exists a function Φ such that, for all i, for all s _−i , and for all $s_{i},s_{i}^{\prime }$, it holds that

$${\Phi}(s_{i},\mathbf{s}_{-i}) - {\Phi}(s_{i}^{\prime},\mathbf{s}_{-i}) = u_{i}(s_{i}^{\prime},\mathbf{s}_{-i}) - u_{i}(s_{i},\mathbf{s}_{-i}). $$

Blume [7] showed that in this case, the stationary distribution of the corresponding logit dynamics is

$$\pi(\mathbf{s}) = \frac{e^{-\beta {\Phi}(\mathbf{s})}}{Z} , $$

where $Z = {\sum }_{\mathbf {s}^{\prime } \in S} e^{-\beta {\Phi }(\mathbf {s}^{\prime })}$ is the normalizing constant.

Finally, the time to converge to the logit equilibrium is the so-called mixing time of the corresponding Markov chain [4], defined as follows. For any 𝜖>0, consider

$$t_{mix}(\epsilon) := \min_{t \in \mathbb{N}}\max_{\mathbf{s}\in {\Omega}} \left\{ \left\|P^{t}(\mathbf{s},\cdot) - \pi\right\| \leq \epsilon\right\}, $$

where $\|{P^{t}(\mathbf {s},\cdot ) - \pi }\| = \frac {1}{2}{\sum }_{\mathbf {s}^{\prime \prime } \in {\Omega }} |P^{t}(\mathbf {s},\mathbf {s}^{\prime \prime }) - \pi (\mathbf {s}^{\prime \prime })|$ is the total variation distance (see Appendix A2 for more details). This quantity measures the time needed for the chain (dynamics) to get close to stationary within an additive factor of 𝜖. The mixing time of the chain is simply defined as t _{m i x} :=t _{m i x} (1/2), since it is well-known that $t_{mix}(\epsilon ) \leq t_{mix}\cdot \log _{2} (1/\epsilon )$ for any 𝜖.

Appendix B: Total variation distance

The total variation distance between distributions μ and $\hat \mu$ on an enumerable state space Ω is

$$\|{\mu - \hat \mu}\|:= \frac{1}{2}\sum\limits_{x \in {\Omega}} \mid \mu(x) - \hat \mu(x)| = \sum\limits_{\begin{subarray}{c}x \in {\Omega}\\\mu(x) > \hat \mu(x)\end{subarray}} \mu(x) - \hat \mu(x). $$

Note that the total variation distance satisfies the usual triangle inequality of distance measures, i.e.,

$$\|\mu - \hat \mu\| \leq \|{\mu - \mu^{\prime}}\| + \|{\mu^{\prime} - \hat \mu}\|, $$

for any distributions μ and $\mu ^{\prime }$. Moreover, the following monotonicity properties hold:

$$\begin{array}{@{}rcl@{}} \|\mu P - \hat{\mu P}\| & \leq& \|\mu - \hat{ \mu}\|, \end{array} $$

(8)

$$\begin{array}{@{}rcl@{}} \| \mu P - \mu {\hat P}\| & \leq& \sup\limits_{x \in {\Omega}} \|{P(x,\cdot) - \hat P(x,\cdot)}\|, \end{array} $$

(9)

$$\begin{array}{@{}rcl@{}} \|\mu P - {\hat \mu P}\| & \leq& \sup\limits_{x,y \in {\Omega}} \|{P(x,\cdot) - P(y,\cdot)}\|, \end{array} $$

(10)

where P and $\hat P$ are stochastic matrices. Indeed, as for (8) we have

$$\begin{array}{@{}rcl@{}} \|{\mu P - \hat \mu P}\| = \|(\mu - \hat \mu) P\| & =& \frac{1}{2} \sum\limits_{y \in {\Omega}} \left| \sum\limits_{x \in {\Omega}} (\mu(x) - \hat \mu(x)) P(x,y)\right|\\ & \leq& \frac{1}{2} \sum\limits_{x \in {\Omega}} \left| \mu(x) - \hat \mu(x)\right| \sum\limits_{y \in {\Omega}} P(x,y)\\ & =& \|{\mu - \hat \mu}\|. \end{array} $$

As for (9) we observe that

$$\begin{array}{@{}rcl@{}} \|{\mu P - \mu \hat P}\| = \|{\mu (P - \hat P)}\| & =& \frac{1}{2} \sum\limits_{y \in {\Omega}} \left| \sum\limits_{x \in {\Omega}} \mu(x) (P(x,y) - \hat P(x,y))\right|\\ & \leq& \sum\limits_{y \in {\Omega}} \left( \frac{1}{2} \sum\limits_{x \in {\Omega}} \mu(x)\left| P(x,y) - \hat P(x,y)\right| \right)\\ \\ & =& \sum\limits_{x \in {\Omega}} \mu(x)\left( \frac{1}{2} \sum\limits_{y \in {\Omega}} \left| P(x,y) - \hat P(x,y)\right| \right)\\ & \leq& \sup\limits_{x \in {\Omega}} \|{P(x,\cdot) - \hat P(x,\cdot)}\|. \end{array} $$

Finally, for (10) we have

$$\begin{array}{@{}rcl@{}} \|{\mu P - \hat \mu P}\| & =& \left\|{\sum\limits_{z \in {\Omega}} \mu(z) \sum\limits_{w \in {\Omega}} \hat \mu(w) \left( P(z,\cdot) - P(w, \cdot) \right)}\right\|\\ & \leq& \sum\limits_{z \in {\Omega}} \mu(z) \sum\limits_{w \in {\Omega}} \hat \mu(w) \|{P(z,\cdot) - P(w, \cdot)}\|\\ & \leq& \sup\limits_{x,y \in {\Omega}} \|{P(x,\cdot) - P(y,\cdot)}\|. \end{array} $$

Appendix C: Equilibria of logit dynamics and NBR-reducible games

In this section we specialize the approach described in Section 5.2 to the case of logit dynamics. First of all, the status “h” is immaterial in this case since the dynamics is by definition Markovian (i.e., the transition probabilities depend only on the current profile).

We next provide a sufficient condition for which the (equilibrium of) the logit dynamics of the subgame is a good approximation of the (equilibrium of) the logit dynamics of the original game. Let G be a game NBR-reducible to $\hat G$, and let π _β and $\hat \pi _{\beta }$ denote the stationary distributions of the logit dynamics with parameter β for G and $\hat G$, respectively. The following lemma says that π _β and $\hat \pi _{\beta }$ are close to each other (in total variation) if β is large enough.

Lemma 5

Let $\hat \tau _{\beta }$ be the mixing time of the restricted chain given by the logit dynamics with parameter β, and let p=p _β be the corresponding probability of selecting a NBR strategy. If $\lim _{\beta \rightarrow \infty } (p_{\beta }\hat \tau _{\beta }) = 0$ , then for every δ>0, there exists a constant β _δ such that

$$\|{\pi_{\beta} - \hat \pi_{\beta}}\| \leq \delta $$

for all β≥β _δ .

Proof

Let $\tau =\hat {t}_{mix}^{(\beta )}(\delta /8)$ be the mixing time of the restricted chain. Consider first two copies of the chain starting in profiles $\hat {\mathbf {s}}, \hat {\mathbf {s}^{\prime }} \in \hat {G}$ and bound the total variation after τ time steps:

$$\begin{array}{@{}rcl@{}} \|{P}^{\tau}(\hat{\mathbf{s}},\cdot )-{P}^{\tau}(\hat{\mathbf{s}}^{\prime}\|,\cdot) &\leq& \|{P}^{\tau}(\hat{\mathbf{s}},\cdot)-\hat{P}^{\tau}(\hat{\mathbf{s}}\|,\cdot) + \|\hat{P}^{\tau}(\hat{\mathbf{s}},\cdot)- \hat{\pi}\|\\ &&+\|\hat{\pi}- \hat{P}^{\tau}(\hat{\mathbf{s}}^{\prime},\cdot)\| + \|\hat{P}^{\tau}(\hat{\mathbf{s}}^{\prime},\cdot)- P^{\tau}(\hat{\mathbf{s}}^{\prime},\cdot)\|\\ &\leq& 4 \cdot \frac{\delta}{8} = \delta/2, \end{array} $$

where the last inequality is due to Lemma 4 by taking β sufficiently large (note that $\eta p \tau = \eta p_{\beta } t^{(\beta )}_{mix}(\delta /8)\leq \eta p_{\beta } \hat \tau _{\beta } \ln (8/\delta )$, which tends to 0 as $\beta \rightarrow \infty$ by hypothesis). Consider an interval T of length $R \cdot \left \lceil \frac {\ln (8\ell /\delta )}{\ln (1/\varepsilon )}\right \rceil$. By applying Lemma 2 with k=ℓ, (R,ε)=(T,δ/4ℓ) and β sufficiently large we have that for every s∈G

$$\underset{\mathbf{s}}{\text{Pr}}({X_{\ell T} \notin \hat{G}}) \leq \delta/8. $$

Let t ^⋆=ℓ T+τ and Q=P ^ℓT. Then, for every $\mathbf {s},\mathbf {s}^{\prime } \in G$

$$\begin{array}{@{}rcl@{}} \|{\pi - P^{t^{\star}}(\mathbf{s}^{\prime}, \cdot)}\| & \leq& \|{P^{t^{\star}}(\mathbf{s}, \cdot) - P^{t^{\star}}(\mathbf{s}^{\prime}, \cdot)}\| = \|{Q(\mathbf{s}, \cdot)P^{\tau} - Q(\mathbf{s}^{\prime}, \cdot)P^{\tau}}\|\\ \text{(triangle inequality)} & \leq& \|{Q(\mathbf{s}, \cdot)P^{\tau} - \hat Q(\mathbf{s}, \cdot)P^{\tau}}\| + \|{\hat Q(\mathbf{s}, \cdot)P^{\tau} - \hat Q(\mathbf{s}^{\prime}, \cdot)P^{\tau}}\|\\ &&+ \|{\hat Q(\mathbf{s}^{\prime}, \cdot)P^{\tau} - Q(\mathbf{s}^{\prime}, \cdot)P^{\tau}}\|, \end{array} $$

where, for every $\mathbf {s}, \mathbf {s}^{\prime } \in G$, we set

$$\hat Q(\mathbf{s},\mathbf{s}^{\prime}) = \left\{\begin{array}{ll} \frac{Q(\mathbf{s},\mathbf{s}^{\prime})}{Q(\mathbf{s},\hat G)}, & \text{if } \mathbf{s}, \mathbf{s}^{\prime} \in \hat G;\\ 0, & \text{otherwise.} \end{array}\right. $$

By (8) we obtain

$$\|{Q(\mathbf{s}, \cdot)P^{\tau} - \hat{Q}(\mathbf{s}, \cdot)P^{\tau}}\| \leq \|{Q(\mathbf{s}, \cdot) - \hat{Q}(\mathbf{s}, \cdot)}\| \leq \underset{\mathbf{s}}{\text{Pr}}\left({X_{\ell T} \notin \hat{G}}\right) \leq \delta/8. $$

By (10) we obtain

$$\|{\hat{Q}(\mathbf{s}, \cdot)P^{\tau} - \hat{Q}(\mathbf{s}^{\prime}, \cdot)P^{\tau}}\| \leq \max_{\hat{\mathbf{s}}, \hat{\mathbf{s}}^{\prime} \in \hat{G}} \|{P^{\tau}(\hat{\mathbf{s}}, \cdot) - P^{\tau}(\hat{\mathbf{s}}^{\prime}, \cdot)}\| \leq \delta/2 $$

and thus $\|{\pi - P^{t^{\star }}(\mathbf {s}^{\prime }, \cdot )}\| \leq 3\delta /4$. Finally, for every $\hat {\mathbf {s}} \in \hat {G}$, by triangle inequality

$$\begin{array}{@{}rcl@{}} \|{\pi - \hat{\pi}}\| & \leq& \|{\pi - P^{t^{\star}}(\hat{\mathbf{s}}, \cdot)}\| + \left\|{P^{t^{\star}}(\hat{\mathbf{s}}, \cdot) - \hat{P}^{t^{\star}}(\hat{\mathbf{s}}, \cdot)}\right\| + \left\|{\hat{P}^{t^{\star}}(\hat{\mathbf{s}}, \cdot) - \hat{\pi}}\right\|\\ & \leq &3 \delta/4 + \delta/8 + \delta/8 = \delta. \end{array} $$

□