1 Correction to: Mathematical Programming https://doi.org/10.1007/s10107-020-01604-z

This note contains a correction of Theorems 1 and 2 and the subroutine \(\textsc {Restore}\) of the article Harks, T., Timmermans, V. Equilibrium computation in resource allocation games. Math. Program. (2021) https://doi.org/10.1007/s10107-020-01604-z, see [3]. The correction leads to slightly increased sensitivity bounds (by a factor n) but all main results of the original paper contained in the previous version remain qualitatively intact. In the following, we describe the corrected sensitivity results of Theorems 1 and 2 and prove correctness and running time of the changed subroutine \(\textsc {Restore}\). The full and corrected version including all changed bounds can be found at [2]. We thank Alex Skopalik who communicated to us that the proof of Theorem 1 is incorrect.

The actual error of the proof of the sensitivity result (Theorem 1) appears after inequality (4): The factor \(|N_{e_1}^+\cap N_f^-|\) is used on the right-hand side of the subsequent inequality without imposing a condition on f so that the derivation of (5) is incorrect. This error also affects the correctness of the former algorithm \(\textsc {Restore}\) as it relies on Corollary 3 (cf. Section 6.1.): For any \(e\in E\) with \((x_k)_e-(x_{k/2})_e\ge 2 mk\), there must exist \(i\in N\) and \(f\ne e\) so that i has a restricted improving move of a packet of size k/2 from f to e. This statement is flawed and renders the former algorithm \(\textsc {Restore}\) incorrect.

1.1 Corrected sensitivity results for equilibria

We use the notation as in the original paper [3].

Theorem 1

Let \(x_k\) be an equilibrium for game \(\mathcal {G}_k\), and \(x_{k/r}\) be an equilibrium for game \(\mathcal {G}_{k/r}\). Then \(|(x_k)_e-(x_{k/r})_e| \le n(m-1)(1 + \tfrac{1}{r})k\) for all \(e \in E\).

Proof

In order to prove the theorem we need to show:

  1. 1.

    \((x_k)_e-(x_{k/r})_e \le n(m-1)(1 + \tfrac{1}{r})k\) and

  2. 2.

    \((x_{k/r})_e - (x_k)_e \le n(m-1)(1 + \tfrac{1}{r})k.\)

As the proofs for both statements are similar, we only prove the first statement here. Assume that there exists a resource \(e_1\) with \( (x_k)_{e_1}-(x_{k/r})_{e_1} > n(m-1)(1 + \tfrac{1}{r})k.\) We introduce the two edge sets \(E^+ = \{e \in E | (x_{k})_{e} \ge (x_{k/r})_{e} \}\) and \(E^- = \{e\in E | (x_{k})_{e} < (x_{k/r})_{e} \}\). We get

$$\begin{aligned} \sum _{e \in E^+} ( (x_{k})_{e} - (x_{k/r})_{e}) =\sum _{i\in N}\sum _{e \in E^+} ( (x_{k})_{i,e} - (x_{k/r})_{i,e}) > n(m-1)(1 + \tfrac{1}{r})k. \end{aligned}$$

Using \(n=|N|\), there exists \(i\in N\) with

$$\begin{aligned} \sum _{e \in E^+} ( (x_{k})_{i,e} - (x_{k/r})_{i,e}) > (m-1)\left( 1 + \tfrac{1}{r}\right) k. \end{aligned}$$
(1)

With \(|E^+|\le m-1\), there exists \(e\in E^+\) with \( (x_{k})_{i,e} - (x_{k/r})_{i,e} > (1 + \tfrac{1}{r}) k.\) With (1) and the balance constraint \(\sum _{e\in E}(x_{k})_{i,e} - (x_{k/r})_{i,e}=0\), we get \( \sum _{e \in E^-} ( (x_{k})_{i,e} - (x_{k/r})_{i,e}) < - (m-1)(1 + \tfrac{1}{r}) k.\) Again using \(|E^-|\le m-1\), there is \(f\in E^-\) with

$$\begin{aligned} (x_{k})_{i,f} - (x_{k/r})_{i,f} < - \left( 1 + \tfrac{1}{r}\right) k.\end{aligned}$$
(2)

Note that (2) implies \((x_{k/r})_{i,f}>0\). Altogether we have for some \(i\in N, e\in E^+, f\in E^-\) the following conditions:

$$\begin{aligned}&(x_{k})_{e} - (x_{k/r})_{e}+ (x_{k})_{i,e} - (x_{k/r})_{i,e} > \left( 1 + \tfrac{1}{r}\right) k \end{aligned}$$
(3)
$$\begin{aligned}&(x_{k})_{f} - (x_{k/r})_{f}+ (x_{k})_{i,f} - (x_{k/r})_{i,f} < - \left( 1 + \tfrac{1}{r}\right) k. \end{aligned}$$
(4)

We rearrange Equations (3), (4) by first multiplying the respective inequalities with \(a_{i,e}, a_{i,f}\) and then adding \(b_{i,e}, b_{i,f}\) to the respective sides to obtain

$$\begin{aligned} a_{i,e}((x_{k})_{e} + (x_{k})_{i,e} -k) +b_{i,e}&> a_{i,e}\left( (x_{k/r})_{e}+(x_{k/r})_{i,e} + \tfrac{k}{r}\right) +b_{i,e}\\ a_{i,f}((x_{k})_{f} + (x_{k})_{i,f} +k) +b_{i,f}&< a_{i,f}\left( (x_{k/r})_{f}+(x_{k/r})_{i,f} - \tfrac{k}{r}\right) +b_{i,f}. \end{aligned}$$

We multiply both inequalities with \(\tfrac{k}{r}>0\) and obtain

$$\begin{aligned} \tfrac{k}{r}(a_{i,e}((x_{k})_{e} + (x_{k})_{i,e} -k) +b_{i,e} )&> \tfrac{k}{r}\left( a_{i,e}\left( (x_{k/r})_{e}+(x_{k/r})_{i,e} + \tfrac{k}{r}\right) +b_{i,e}\right) \end{aligned}$$
(5)
$$\begin{aligned} \tfrac{k}{r}(a_{i,f}((x_{k})_{f} + (x_{k})_{i,f} +k) +b_{i,f})&< \tfrac{k}{r}\left( a_{i,f}\left( (x_{k/r})_{f}+(x_{k/r})_{i,f} - \tfrac{k}{r}\right) +b_{i,f}\right) . \end{aligned}$$
(6)

We combine Eqs. (5), (6) and the fact that \(x_k\) is an equilibrium for packet size k to obtain (using \((x_{k})_{i,e}>0\) and \((x_{k/r})_{i,f}>0\) ):

$$\begin{aligned} \mu ^{+k/r}_{i,e}(x_{k/r}) \underset{(5)}{<} \frac{1}{r}\mu ^{-k}_{i,e}(x_{k}) \le \frac{1}{r} \mu ^{+k}_{i,f}(x_{k}) \underset{(6)}{<} \mu ^{-k/r}_{i,f}(x_{k/r}). \end{aligned}$$

Hence, player i has a restricted improving move in \(x_{k/r}\) shifting a packet of size k/r from f to e, which contradicts the fact that \(x_{k/r}\) is an equilibrium strategy. \(\square \)

We obtain the following corrected Corollary 1:

Corollary 1

Let x be the unique equilibrium for an atomic splittable game, and \(x_k\) be an equilibrium for a k-integral splittable game. Then \(|(x_k)_e-x_e| \le n(m-1)k\) for all \(e \in E\).

We obtain a similar (corrected) result for player-specific load differences:

Theorem 2

Let \(x_k\) be an equilibrium for game \(\mathcal {G}_k\), and \(x_{k/r}\) be an equilibrium for game \(\mathcal {G}_{k/r}\). Then \(|(x_k)_{i,e}-(x_{k/r})_{i,e}| \le m n (m-1)(1 + \tfrac{1}{r})k\) for all \(e \in E, i\in N\).

Proof

As in the proof of Theorem 1, assume that there exists a resource \(e_1\) and a player \(i\in N\) with \((x_k)_{i,e_1}-(x_{k/r})_{i,e_1} > m n(m-1)(1 + \tfrac{1}{r})k\). By Theorem 1, we know that \((x_{k})_{e_1}-(x_{k/r})_{e_1} \ge - n (m-1)(1 + \tfrac{1}{r})k \). Adding both inequalities, we get:

$$\begin{aligned} (x_{k})_{e_1}-(x_{k/r})_{e_1}+(x_k)_{i,e_1}-(x_{k/r})_{i,e_1}>n(m-1)^2\left( 1 + \tfrac{1}{r}\right) k.\end{aligned}$$
(7)

The total load distributed by all player is the same in both \(x_{k/r}\) and \(x_{k}\). Thus, we obtain:

$$\begin{aligned} \textstyle \sum _{e \ne e_1} (x_{k})_{e}-(x_{k/r})_{e}+(x_k)_{i,e}-(x_{k/r})_{i,e} < - n(m-1)^2\left( 1 + \tfrac{1}{r}\right) k. \end{aligned}$$

Using \(|E\setminus \{ e_1\}|\le m-1\), there must exist at least one resource \(f \in E, f\ne e_1\) such that:

$$\begin{aligned} (x_{k})_{f}-(x_{k/r})_{f}+(x_k)_{i,f}-(x_{k/r})_{i,f} < - n(m-1)\left( 1 + \tfrac{1}{r}\right) k. \end{aligned}$$
(8)

Note that \((x_{k/r})_{i,f} > 0\), as \((x_{k/r})_{i,f} = 0\) implies \((x_{k/r})_f - (x_{k})_f > n(m-1)(1 + \tfrac{1}{r})k\), which contradicts Theorem 1. Using (7) and (8), we obtain in a similar fashion as in the proof of Theorem 1 a contradiction. \(\square \)

Corollary 2

Let x be the unique equilibrium for an atomic splittable game, and \(x_k\) be an equilibrium for the corresponding k-integral splittable game. Then \(|(x_k)_{i,e}-x_{i,e}| \le nm(m-1)k\) for all \(i \in N\) and \(e\in E\).

The above sensitivity bounds are further used in Section 4 (Theorem 4) of the original paper and for the corrected version, one just needs to insert the corrected bounds, see [2].

1.2 Corrected algorithm \(\textsc {Restore}\).

This section replaces Section 6.1 and Section 7.2. on the analysis of the former algorithm \(\textsc {Restore}\). The changed subroutine, \(\textsc {Restore}\), takes as input an equilibrium \(x_{k}\) for packet size k and game \(\mathcal {G}_k((d_i)_{i \in N})\), and constructs an equilibrium for game \(\mathcal {G}_{k/2}((d_i)_{i \in N})\) with packet size k/2. It uses as a subroutine the algorithm of Harks, Klimm and Peis [1,  Algorithm 1] which we denote here by PAlg. The algorithm PAlg computes an equilibrium for any integer-splittable congestion game with player-specific discrete-convex cost functions in pseudo-polynomial time of order \(O(n^2m(\frac{\delta }{k})^3)\), where \(\delta :=\max _{i\in N} d_i\). \(\textsc {Restore}\) relies on the sensitivity result of Theorem 2 which shows that for any two equilibria \(x_k, x_{k/2}\) of the respective games, we get \(|(x_{k})_{i,e}-(x_{k/2})_{i,e}|\le 2m^2nk\) for all \(i\in N, e\in E\). Hence, we know already that any equilibrium \(x_{k/2}\) satisfies \((x_{k/2})_{i,e}\ge y_{i,e}\) for all \(i\in N, e\in E\), where

$$\begin{aligned} y_{i,e}:=\max \{(x_{k})_{i,e}- 2m^2nk, 0\} \text { for all}\; i\in N, e\in E. \end{aligned}$$
(9)

It follows that we can safely fix \((y_{k/2})_{i,e}:=y_{i,e}, i\in N, e\in E\) according to (9). The idea is to construct a new game with reduced demands \( \bar{d}_i = \sum _{e \in E} ((x_k)_{i,e} - y_{i,e}), i \in N\) leading to at most \(4 m^3n^2\) packets of size k/2 and strategies \(z_{k/2}\in \mathcal {S}_i(\bar{d}_i,k/2)\). The new private cost functions for players \(i\in N\) are defined as

$$\begin{aligned} \hat{\pi }_i(z_{k/2}):= \sum _{e\in E}a_{i,e} ((z_{k/2})_e+(y_{k/2})_e) ((z_{k/2})_{i,e}+(y_{k/2})_{i,e})+b_{i,e}((z_{k/2})_{i,e}+(y_{k/2})_{i,e}), \end{aligned}$$
(10)

where \(y_{k/2}\) appears as a parameter. The form of \( \hat{\pi }_i(z_{k/2})\) in (10) is designed to replicate the original cost function \( \pi _i(x_{k/2})\) for \(x_{k/2}:=z_{k/2}+y_{k/2}\). By multiplying out terms in (10), it follows that the expressions \(\sum _{e\in E}a_{i,e}(((z_{k/2})_{-i,e}+(y_{k/2})_e)(y_{k/2})_{i,e})+b_{i,e}(y_{k/2})_{i,e}\) are independent of \((z_{k/2})_i\) and can thus be left out (without losing equilibria). We obtain a strategically equivalent game by replacing \(\hat{\pi }_i(z_{k/2})\) with

$$\begin{aligned} \bar{\pi }_i(z_{k/2})&:= \sum _{e\in E}a_{i,e} ((z_{k/2}+y_{k/2})_e (z_{k/2})_{i,e}+(z_{k/2})_{i,e}(y_{k/2})_{i,e})+b_{i,e}(z_{k/2})_{i,e}\\&=\sum _{e\in E}a_{i,e} (z_{k/2})_e (z_{k/2})_{i,e}+(b_{i,e}+a_{i,e}((y_{k/2})_e+(y_{k/2})_{i,e})) (z_{k/2})_{i,e}. \end{aligned}$$

Defining \(\bar{b}_{i,e}:=b_{i,e}+a_{i,e}((y_{k/2})_e+(y_{k/2})_{i,e}), i\in N, e\in E\), we obtain a standard integer-splittable singleton congestion game with packet size k/2 and affine player-specific cost functions \(\bar{c}_{i,e}(z_e):= a_{i,e} z_e+\bar{b}_{i,e}, i\in N, e\in E\). This new game is denoted by \(\bar{\mathcal {G}}_{k/2}((\bar{d}_i)_{i \in N}) \). \(\textsc {Restore}\) uses now PAlg on \(\bar{\mathcal {G}}_{k/2}((\bar{d}_i)_{i \in N})\) to compute an equilibrium. The pseudo-code of subroutine \(\textsc {Restore}\) can be found in Fig. 1.

Fig. 1
figure 1

Subroutine \(\textsc {Restore}(x_{k},\mathcal {G}_{k}((d_i)_{i \in N}))\)

Full size image

Recall that a strategy profile \(z_{k/2}\) for the game \(\bar{\mathcal {G}}_{k/2}\) is an equilibrium if and only if \(\bar{\mu }^{-k/2}_{i,e}(z_{k/2})\le \bar{\mu }^{+k/2}_{i,f}(z_{k/2})\) for all \(i\in N, e,f\in E\) with \((z_{k/2})_{i,e}>0,\) where \(\bar{\mu }^{-k/2}_{i,e}(z_{k/2})\) and \(\bar{\mu }^{+k/2}_{i,e}(z_{k/2})\) denote the respective marginal costs for game \(\bar{\mathcal {G}}_{k/2}\). We need to show that the combined profile \(x_{k/2}:=(z_{k/2}+y_{k/2})\) satisfies these conditions for the original game \(\mathcal {G}_{k/2}\). For this, we first relate the different marginal costs with each other.

Lemma 1

Let \(x_{k/2}:=(z_{k/2}+y_{k/2})\). Then, the following holds true:

  1. 1.

    \(\bar{\mu }^{-k/2}_{i,e}(z_{k/2})=\mu ^{-k/2}_{i,e}(x_{k/2})\) for all \(e\in E, i\in N\) with \( (z_{k/2})_{i,e}>0\),

  2. 2.

    \(\bar{\mu }^{+k/2}_{i,e}(z_{k/2})=\mu ^{+k/2}_{i,e}(x_{k/2})\) for all \(e\in E, i\in N\).

Both statements follow by simple calculations, see [2]. With Lemma 1 it follows that for an equilibrium \(z_{k/2}\) of game \(\bar{\mathcal {G}}_{k/2}\), the strategy profile \(x_{k/2}:=(z_{k/2}+y_{k/2})\) is an equilibrium for \(\mathcal {G}_{k/2}\) provided \((y_{k/2})_{i,e}>0\Rightarrow (z_{k/2})_{i,e}>0\) holds true for all \(i\in N, e\in E\). For proving this, we first show a further sensitivity result for the profiles \(x_k\) and \((z_{k/2}+y_{k/2})\).

Lemma 2

Let \(x_k\) be an equilibrium for \(\mathcal {G}_{k}\) and let \(z_{k/2}\) be an equilibrium for the corresponding game \(\bar{\mathcal {G}}_{k/2}\). Then, \(|(z_{k/2})_e+(y_{k/2})_e-(x_k)_e|< 2nmk\) for all \(e\in E\).

Proof

Assume \((z_{k/2})_e+(y_{k/2})_e-(x_k)_e\ge 2nmk\). Define \(E^+=\{e\in E\vert (z_{k/2})_e+(y_{k/2})_e-(x_k)_e\ge 0\}\) and \(E^-=\{e\in E\vert (z_{k/2})_e+(y_{k/2})_e-(x_k)_e< 0\}\). We get \(\sum _{i\in N}\sum _{e\in E^+} (z_{k/2})_{i,e}+(y_{k/2})_{i,e}-(x_k)_{i,e}\ge 2nmk.\) Hence, there is \(i\in N\) with

$$\begin{aligned} \sum _{e\in E^+} (z_{k/2})_{i,e}+(y_{k/2})_{i,e}-(x_k)_{i,e}\ge 2mk > \tfrac{3}{2}mk.\end{aligned}$$
(11)

Load balance implies \(\sum _{e\in E^-} (z_{k/2})_{i,e}+(y_{k/2})_{i,e}-(x_k)_{i,e}\le -2mk < - \tfrac{3}{2}mk.\) From (11) we get that there is \(e\in E^+\) with

$$\begin{aligned} (z_{k/2})_{i,e}+(y_{k/2})_{i,e}-(x_k)_{i,e}>\tfrac{3}{2}k.\end{aligned}$$
(12)

With \((y_{k/2})_{i,e}\le (x_k)_{i,e}\) (cf. (9)), we have \((z_{k/2})_{i,e}>0\). Moreover, there is \(f\in E^-\) with

$$\begin{aligned} (z_{k/2})_{i,f}+(y_{k/2})_{i,f}-(x_k)_{i,f}<-\tfrac{3}{2}k.\end{aligned}$$
(13)

It follows that \((x_k)_{i,f}>0\). Altogether, with \((z_{k/2})_{i,e}>0, (x_k)_{i,f}>0\), and (12),(13) we obtain a contradiction to the fact that \(z_{k/2}\) is an equilibrium for game \(\bar{\mathcal {G}}_{k/2}\). \(\square \)

Now we are ready to prove that \(x_{k/2}:=(z_{k/2}+y_{k/2})\) is an equilibrium for \(\mathcal {G}_{k/2}\).

Lemma 3

If \(z_{k/2}\) is an equilibrium for game \(\bar{\mathcal {G}}_{k/2}\) w.r.t. an equilibrium \(x_k\) for game \(\mathcal {G}_{k}\), then \(x_{k/2}:=(z_{k/2}+y_{k/2})\) is an equilibrium for \(\mathcal {G}_{k/2}\).

Proof

With Lemma 1, it suffices to show that for all \(e\in E, i\in N\), it holds \((y_{k/2})_{i,e}>0\Rightarrow (z_{k/2})_{i,e}>0.\) Assume by contradiction that there is \(i\in N\), \(e\in E\) with \((y_{k/2})_{i,e}>0, (z_{k/2})_{i,e}=0\). By (9), this implies \( (x_{k})_{i,e}-((z_{k/2})_{i,e}+(y_{k/2})_{i,e})= 2 m^2nk.\) It follows that \((x_{k})_{i,e}>0\). With Lemma 2, we get \((x_{k})_{e}-((z_{k/2})_{e}+(y_{k/2})_{e}) \ge - 2mnk.\) Hence,

$$\begin{aligned} (x_{k})_{e}-((z_{k/2})_{e}+(y_{k/2})_{e})+ (x_{k})_{i,e}-((z_{k/2})_{i,e}+(y_{k/2})_{i,e})\ge 2m(m-1)nk>2k.\end{aligned}$$

Balance constraints imply

$$\begin{aligned} \sum _{f\ne e} (x_{k})_{f}-((z_{k/2})_{f}+(y_{k/2})_{f})+ (x_{k})_{i,f}-((z_{k/2})_{i,f}+(y_{k/2})_{i,f})\le - 2m(m-1)nk.\end{aligned}$$

Thus, there is \(f\ne e\) with

$$\begin{aligned} (x_{k})_{f}-((z_{k/2})_{f}+(y_{k/2})_{f})+ (x_{k})_{i,f}-((z_{k/2})_{i,f}+(y_{k/2})_{i,f})\le - 2mnk<-2k.\end{aligned}$$

Using \((x_{k})_{i,f}\ge (y_{k/2})_{i,f}\), the case \((z_{k/2})_{i,f}=0\) implies that the sensitivity bound of Lemma 2 applied on f is violated, hence \((z_{k/2})_{i,f}>0\) must hold. Applying the same argumentation regarding the marginal cost (as in the proof of Theorem 1) we get that \(z_{k/2}\) is not an equilibrium for game \(\bar{\mathcal {G}}_{k/2}\) leading to a contradiction. \(\square \)

Lemma 4

\(\textsc {Restore}\) has running time \(O(n^5m^{10})\).

Proof

Applying PAlg on the game \(\bar{\mathcal {G}}_{k/2}\) yields a running time of \(n^2m(\frac{\delta }{k/2})^3\), where \(\delta :=\max _{i\in N}\bar{d}_i\). By construction of the game \(\bar{\mathcal {G}}_{k/2}\), the demands satisfy \(d_i\le 2m^3nk\) for all \(i\in N\). Thus, we get \(\delta \le 2m^3nk\) yielding the desired result. \(\square \)

For the resulting changed running time of the main algorithm PacketHalver (that uses Restore as a subroutine), one needs to use the corrected run time as above, see [2].