Quickly approximating Shapley Games

Posted on September 15, 2025 by mishai in Uncategorized // 0 Comments

An example Shapley game

In this blog post, we will talk about some recent advances in algorithms for approximately solving Shapley Games.

What is a Shapley Game?

At an intuitive level, Shapley games capture the idea of extending one-shot 2-player games to be occurring over multiple stages.

Explicitly, Shapley games are played on an underlying state space V. At each v\in V, the two players can each choose one of p actions. Based on their choices i and j, the first player receives a reward A_v[i,j]\in \mathbb R (and the second player receives -A_v[i,j]) and the game moves to state u with probability P_v[i,j](u). Furthermore, at each time step there is a probability q that the game ends (thus, \sum_{u\in V} P_v[i,j](u) = 1 - q). The goal of each player is to maximize their earnings.

These games were introduced by [Shapley’53], where he also proved that when q > 0, the Shapley game has a value: that is, this maximum exists.

Furthermore, this value can be characterized as the solution to a specific fixed point equation: defining \text{val}(X) to be the optimal payoff of a two-player game on the payoff matrix X, the value of a Shapley Game is the unique vector x satisfying x_v = \text{val}(A_v + P_v \cdot x) for all v\in V (here, P_v\in \mathbb R^{p\times p\times |V|}). Intuitively, this makes sense: a player’s expected payoff at a given state v is determined exactly by their current payoff A_v and their future payoff P_v\cdot x.

We are often interested in the setting where q is exponentially small (in fact, it was later proven that Shapley games have a value when q = 0 but we will not focus on this case).

Connecting Shapley Games to Fixed Point Theorems

As we talked about above, the value of a Shapley Game is the unique vector x satisfying x_v = \text{val}(A_v + P_v \cdot x) for all v\in V. If we define f(x) to be the vector consisting of the right hand side over all $\latex v\in V$, then it turns out that in addition to being polynomial-time computable, f actually satisfies two special properties:

  • Monotonicity: for every x \le y, f(x) \le f(y)
  • Contraction: for every x, y, \|f(x) - f(y)\|_{\infty} \le (1 - q) \|x - y\|_{\infty}
    • Later, we will also care about defining a contraction property for discrete functions: in this case, we loosen the constraint to be \|F(x) - F(y)\|_{\infty} \le \|x - y\|_{\infty} (else, all values are actually equal)

By Tarski’s Fixed Point Theorem, every monotone function has a fixed point; and by Banach’s Fixed Point Theorem, every contracting function also has a fixed point.

For our algorithms, we will not be interested in the exact Shapley value, but just an \varepsilon-approximation of it. To define this, let d = |V| and n = O\left(\frac{\|A\|_{\infty}}{q\varepsilon}\right).

Then, [EPRY’20] constructs a (discrete) monotone contraction F: [n]^d \rightarrow [n]^d such that

  1. A query to F requires one query to an oracle for f.
  2. Given any x with F(x) = x, we can construct in polynomial time an x^\ast such that \|f(x^\ast) - x^\ast\|_{\infty} \le \varepsilon.
  3. F satisfies that \|F(x) - x\|_\infty \le 1. This last condition is an implementation detail which will make some of the later exposition simpler.

With this reduction in mind, the challenge for approximately solving Shapley Games has just become one of finding monotone/contracting/both fixed points of a function over [n]^d. In the next few sections, we will talk about some recent algorithms for accomplishing this.

It’s important to note which factors are important for the runtime and query and complexity here: we will often consider d and \log n to be “reasonable” (since this is the size of the state space and the bit complexity of the input, respectively). In a reasonable application, we would expect d to generally be fairly small, likely o(\log n).

Complexity Implications

Before describing algorithms for approximately solving Shapley Games, let’s take a look at the complexity landscape surrounding it.

Above is a diagram of the relevant complexity classes surrounding Shapley Games. These are, in order:

  1. PPAD: A prototypical complete problem for PPAD is End-Of-Line: Given an (exponentially large) directed graph consisting of lines and cycles and a start point of a line, find the end of one of the lines. Two famous examples of problems complete for PPAD are finding (approximate) Nash Equilibria and Brouwer Fixed Points (Given a compact domain D and a continuous function f: D\rightarrow D, find an x such that f(x) = x).
  2. PLS (Polynomial Local Search): A prototypical complete problem for PLS is the following: given an (exponentially large) DAG and a potential function p which only decreases along directed edges, find a local optimum. It is believed that neither PLS nor PPAD are subsets of each other.
  3. CLS (Continuous Local Search): An example complete problem for CLS is Gradient Descent. It is also known that \mathsf{CLS} = \mathsf{PPAD} \cap \mathsf{PLS} (shown in [FGHS’22]).
  4. UEOPL (Unique End of Potential Line): There is a hidden class not in the above diagram: EOPL (End Of Potential Line). This marries the prototypical complete problems for PPAD and PLS by adding a potential function to End-Of-Line. Building on this, UEOPL asks for there to be exactly one line (and hence exactly one solution). By definition, this lies within \mathsf{CLS}.

From first principles, it is true that computing the (approximate) Shapley values lies both within PPAD and PLS (and hence within CLS), by noticing that it is a special case of Brouwer’s Fixed Point Theorem and admits the potential function \|f(x) - x\|_{\infty}, respectively. Furthermore, by Shapley’s Theorem, we know that there is a unique solution. Recently, [BFGMS’25] showed that computing approximate Shapley Values is within UEOPL. More generally, they showed that computing a fixed point of any monotone contraction is within UEOPL.

Algorithms

Inefficient Algorithms

Let’s begin by “forgetting” the contracting constraint and just trying to find a fixed point of a monotone F : [n]^d\rightarrow [n]^d. A simple algorithm for this task is to consider the sequence of iterates \vec 1, F(\vec 1), F(F(\vec 1)), \ldots. Since F is monotone, \vec 1 \le F(\vec 1), and F(x) \le \vec n for all x, it follows that there must be a repeat in this sequence. Unfortunately, the query complexity of this algorithm is O(d\cdot n) = O(d\cdot \frac{\|A\|_{\infty}}{q\cdot \varepsilon}). Since we are often interested in the setting where q and \varepsilon are exponentially small, this is too slow.

In the opposite direction, suppose we just knew that f was contracting, and not monotone. In this case, we can find an \varepsilon-approximate fixed point of f directly by starting at an arbitrary point and considering the sequence \vec x, f(\vec x), f(f(\vec x)),\ldots which will require O(\frac 1q \log \frac 1\varepsilon) iterations and is also too slow.

On the other hand, exciting new work by [CLY’24] gave an algorithm with query complexity O(d\log n) for the task when F is just contracting. Unfortunately, the runtime of this algorithm depends on factors of at-least n (there is a brute-force grid search over [n]^d between each query).

By contrast, in the upcoming algorithms, we will have the property that the “external” runtime is at most some \text{poly}(d,\log n) times the query complexity. Here, by external runtime, we mean the work in between oracle calls to F.

We will now describe some algorithms for computing fixed points of monotone contractions. The current state of the art is an algorithm by [BFGMS’25] that takes O(\log^{\lceil d/3\rceil} n) queries to F to find such a fixed point. Here, we will present a simplified version of this algorithm that takes O(\log^{\lceil d/2\rceil} n) queries to find this fixed point.

First Pass: Monotone Fixed Point Algorithms

On the path to faster algorithms, let’s begin with d = 1. Here, we know that 1\le F(1) and F(n) \le n. We can then binary search for a fixed point, preserving the invariant that \text{lo} \le F(\text{lo}) and F(\text{hi}) \le \text{hi} at each iteration. This takes O(\log n) queries to F.

Similarly, we can do a recursive d-layer binary search to find a fixed point when F is d-dimensional, which requires O(\log^d n) queries to F.

To improve this algorithm, let’s decompose it into two parts: a base case and a gluing theorem.

  1. The base case here is solving d = 1 in O(\log n) queries.
  2. The “gluing theorem” says that if we can find a fixed point of a d-dimensional F in time T(d), then we can find a fixed point of a d + 1-dimensional F in time T(d) \cdot \log n.

One road to improving the runtime of this algorithm is to improve the base case. That is, is there some fixed constant k\ge 2 where we can find a fixed point of a k-dimensional F in o(\log^k n) queries?

Recent work in [BPR’25] has given a lower bound of \Omega(\frac{d\log^2 n}{\log d}) for all d\ge 2, and there is a natural \Omega(\log n) lower bound for d = 1. However, we can do better for d = 3, as shown in [FPS’22]:

Given a monotone F: [n]^3\rightarrow [n]^3, there is an algorithm which takes O(\log^2 n) queries and outputs an x for which F(x) = x.

Immediately, this implies an algorithm taking O(\log^{d-1} n) queries for finding a fixed point of a d-dimensional F. However, this is not the end of the story, as we can also derive a more general gluing theorem, also shown in [FPS’22]:

If we can find fixed points of d_1, d_2 dimensional Fs in query complexity T(d_1), T(d_2) respectively, then we can find the fixed point of a d_1 + d_2 dimensional F in query complexity O(T(d_1)\cdot T(d_2)).

Together, these imply an algorithm running in time O(\log^{\lceil 2d/3\rceil} n) for finding a fixed point.

Gluing Theorem

Let’s begin by discussing a variant of the gluing theorem from [BFGMS’25]. In particular, suppose that we have oracles \mathcal A and \mathcal B for the d_1 and d_2 dimensional monotone contraction problems, respectively.

As a first pass, consider giving to \mathcal A the function F'(x) = F(x,\mathcal B(F(x,\cdots)))_{\le d_1}: in other words, call \mathcal B on the slice where the first d_1 coordinates are fixed to be x and return the result of calling F on this fixed point. Naively, this seems reasonable: \mathcal B is guaranteed to return a fixed point and hence when \mathcal A returns a fixed point in the first d_1 coordinates it must be the case that we know its fixed part in the last d_2 coordinates.

The issue, however is that F' is not monotone nor contracting: for example, suppose that F was just the identity function: now, \mathcal B is free to return any point in [n]^{d_2} on each run. To fix this, we will follow [BFGMS’25] and suppose that, magically, \mathcal A and \mathcal B both return the Least Fixed Point (LFP) of their input function (by Tarski’s Theorem, the set of fixed points form a sublattice so there exists an LFP: the meet of all of the fixed points).

Proof

We claim that this is sufficient to force F' to be a monotone contraction. To prove this, suppose we have two queries x and x^\ast, and suppose that y = \mathcal B(F(x,\cdots)) and y^\ast = \mathcal B(F(x^\ast ,\cdots)). We show the two necessary facts:

  1. If x \le x^\ast, then y\le y^\ast.
  2. It is true that \|y - y^\ast \|_{\infty} \le \|x - x^\ast \|_{\infty} (we prove this when \|x - x^\ast\|_{\infty} = 1, which can then be extended by induction)

To prove the first fact, we claim that for every y such that F(x,y)_{>d_1} = y, there exists a y'\ge y with \|y - y'\|_{\infty} \le 1 such that F(x^\ast,y')_{>d_1} = y', and that a similar statement holds in reverse (i.e., given a y^\ast we can find y' \le y^\ast with similar properties). The key observation is that y\le F(x^\ast, y) \le F(x^\ast, y + \vec 1) \le y + \vec 1, where the last inequality follows from \|F(x,y) - F(x^\ast,y+\vec 1)\|_{\infty} \le 1.

Thus, we may consider the sequence F(x^\ast,y), F(x^\ast, F(x^\ast, y)), F(x^\ast, F(x^\ast, F(x^\ast, y))),\ldots. Each of these is upper bounded by y + \vec 1 and they form an increasing sequence, so one of the values among them must yield a fixed point y'. We can do a similar argument in the reverse direction, so this implies that when x\le x^\ast we also have \|y - y'\|_{\infty} \le 1. Furthermore, this also implies that y\le y'.

Now, suppose x and x^\ast are incomparable. Then, compute x_m = x\land x^\ast (the meet of the two) and x_j = x\lor x^\ast (the join of the two) which satisfy x_m \le x_j. It follows that if y_m and y_j are the least fixed points for x_m and x_j (and, as before, y and y^\ast are the fixed points we are looking for), then y_m \le y, y^\ast \le y_j and thus \|y - y^\ast\|_{\infty} \le \|y_m - y_j\|_{\infty} \le 1. Hence, we are done.

With this in mind, the final question is: how can we find a Least Fixed Point? If F were just monotone, then [EPRY’20] showed that this was NP-Hard. It turns out that when F is 2-dimensional, there is a reduction from [BFGMS’25] that gives us the LFP with constantly many extra queries. We now have that the query complexity of gluing the two instances requires T(d_1)\cdot T(d_2) queries to F.

Base Case of [FPS’22]

We will briefly describe the parts of the base case algorithm from [FPS’22] that we will later use to inform our algorithm for monotone contractions.

To describe the base case algorithm, we need the following definition:

Given a function F: [n]^d \rightarrow [n]^d, we let \text{Up}(F) = \{x\in [n]^d: f(x) \ge x\} and \text{Down}(F) = \{x\in [n]^d : f(x) \le x\}.

Finding a fixed point is equivalent to finding a point in \text{Up}(F)\cap \text{Down}(F). With this definition in mind, we can break up the [FPS’22] base case algorithm into two steps:

  1. For a fixed c, find some vector x\in \text{Up}(F)\cup \text{Down}(F) with x_3 = c in O(\log n) queries.
  2. Binary search on c to find a fixed point.

Overall we run the first step O(\log n) times which gives the final O(\log^2 n) number of queries.

Brief Aside: Gluing Up & Down Points

Before discussing the [BFGMS’25] result, it’s worth mentioning that it is also possible to write a gluing theorem which uses just the first step of the above base case: that is, given oracles which compute either an Up or Down point (given a fixed coordinate), glue them together to find either an Up or Down point of a d-dimensional instance. This result was shown in [CL’22] and immediately gives an algorithm running in time and queries O(\log^{\lceil (d+1)/2\rceil} n).

The Power of Monotone Contractions

We are finally ready to bring everything together to describe our O(\log^{\lceil d/2\rceil} n) algorithm. The key idea is to strip wasteful work from the above base case. In particular, when we search for an Up or Down point along a particular slice x_3 = c, we are often redoing similar work (for example, we may have gained some information telling us that there is no Up/Down point in a given region of the grid, so there is no use re-searching there).

We will apply this idea to re-use work from prior iterations, so that the total amortized cost of the binary searches comes out to O(\log n). In [BFGMS’25], they do this directly on 3-dimensional instances. In this overview, we will instead show how to compute a LFP of a 2-dimensional monotone contraction in O(\log n) queries, which, combined with the above gluing theorem, yields the desired query complexity.

We will require two properties to hold for our F: [n]^2\rightarrow [n]^2:

  1. \|F(x) - x\|_{\infty} \le 1: recall that we have this for free from the [EPRY’20] reduction.
  2. If F(x,y)_1 = x then there exists no other x' with F(x',y)_1 = x'; and similarly for y. Equivalently, each 1-dimensional slice of F has a unique fixed point.
    • We can achieve this as follows: if F(x, y)_1 = x and F(x-1,y)_1 = x - 1, then set F'(x,y)_1 = x - 1 (else, set it to F(x,y)_1). We can do the same in the y direction. In this way, a consecutive sequence of fixed points will all move down except for the first instance.

Since each 1-dimensional slice of F now has a unique fixed point, let’s define g(x) to be the unique fixed point y for a given x, and similarly define h(y).

With this in mind, we can plot these functions:

Here, the blue line corresponds to g(x) and the red line corresponds to h(y) (we have also increased the bounds so that g(x) hits both the top and bottom edge). In fact, we can also say more: the salmon-colored region is exactly the Up set and the green region is exactly the Down set, and where the two lines meet is the set of fixed points!

Note that both g(x) and h(y) have slope at most 1 in their respective directions, which suggests the following: if \text{Up}(f) \cap \{x = i\} = [a_i, b_i] and j > i, then \text{Up}(f) \cap \{x = j\} \subseteq [a_i + (j - i), b_i + (j - i)], and similarly (but in the opposite direction) for the Down set. The reasoning for this is simply the observation that the distance between the two lines is non-increasing.

From this, we can derive our final algorithm: for a given x, conduct a binary search to find either an Up or Down point (we are guaranteed at most one, unless there is a fixed point), but keep track of the interval which contains the whole Up/Down slice along that x value. In future binary searches, reuse this interval (shifted appropriately by j - i) instead of starting with [1, n]. In this way, the total number of queries is O(\log n) since over the course of the algorithm we do at most two full binary searches (one for Up and one for Down points).

Open Problems

There are a wealth of open problems left here, but we’ll mention two.

  • What is the true complexity of computing fixed points of monotone, contracting, and monotone contracting functions? This includes both the query complexity and the runtime, as currently we have a large gap between lower and upper bounds.
  • Are there other properties of Shapley Games that allow us to get faster approximate algorithms beyond just using monotonicity and contraction?

Acknowledgements: I would like to thank my quals committee: Nima Anari, Aviad Rubinstein, and Tselil Schramm for the useful feedback on my quals talk and some suggestions on this blog post. I would also like to thank Spencer Compton for valuable comments on this blog post.

References

[BFGMS’25] Batziou, E., Fearnley, J., Gordon, S., Mehta, R., & Savani, R. (2025, June). Monotone Contractions. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (pp. 507-517).

[BPR’25] Brânzei, S., Phillips, R., & Recker, N. (2025). Tarski Lower Bounds from Multi-Dimensional Herringbones. arXiv preprint arXiv:2502.16679.

[CL’22] Chen, X., & Li, Y. (2022, July). Improved upper bounds for finding tarski fixed points. In Proceedings of the 23rd ACM Conference on Economics and Computation (pp. 1108-1118).

[CLY’24] Chen, X., Li, Y., & Yannakakis, M. (2024, June). Computing a Fixed Point of Contraction Maps in Polynomial Queries. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (pp. 1364-1373).

[EPRY’20] Etessami, K., Papadimitriou, C., Rubinstein, A., & Yannakakis, M. (2020). Tarski’s Theorem, Supermodular Games, and the Complexity of Equilibria. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) (pp. 18-1). Schloss Dagstuhl–Leibniz-Zentrum für Informatik.

[FGHS’22] Fearnley, J., Goldberg, P., Hollender, A., & Savani, R. (2022). The complexity of gradient descent: CLS= PPAD∩ PLS. Journal of the ACM, 70(1), 1-74.

[FPS’22] Fearnley, J., Pálvölgyi, D., & Savani, R. (2022). A faster algorithm for finding Tarski fixed points. ACM Transactions on Algorithms (TALG), 18(3), 1-23.

[Shapley’53] Shapley, L. S. (1953). Stochastic games. Proceedings of the national academy of sciences, 39(10), 1095-1100.

Leave a comment

Copyright © 2025 Create a website or blog at WordPress.com