Game-theoretic Protesters

Recent reading inspired some game-theoretic doodling this morning, and the results were a fascinating look at incentive structures and how unintuitive they can be.

Suppose the citizenry of our fair nation are outraged by some recent corporate excess. A group of activists are organizing a protest and begging others to take part. Of course, the protest hopes to achieve mass media coverage, which would force the corporation to fold to public pressure and revert its unethical course. But the media does not cover small protests, so success can only be achieved if sufficiently many people make it to the protest. I would like to know: if each citizen is an independent actor with myopic, greedy interests, what will happen? And, how will this change as the citizenry adopts more better values?

We can model these questions with a game-theoretic game, where each citizen is a player and makes one choice (simultaneous with everyone else) either to protest or not. Protesting is a pain—going to the protest, standing there for a while, potentially being rained on—so costs \(\beta\) utility no matter if it succeeds or fails.11 This is unrealistic for human psychology—starting with a notion that humans have a singular notion of utility—but the point of game theory is that weirdly human-like behavior can occur even without considering the quirks of human psychology. Unrealistic models are still useful. But if sufficiently many people protest—more than \(n\) of the \(N\) citizens, say—the protest will be a success and shower every citizen, including those that did not protest, with \(\alpha\) utility. So: what will the citizens do?22 This question is trivial if \(n = 0\) or \(n = N\), so let’s ignore those cases.

Solutions and solution concepts

Some of the biggest breakthroughs in game theory (it’s a young field) are in figuring out what that question—what will the citizens do—even means. I mean, who knows what they’ll do? Some will stay home, some of them will protest; who knows? And all of my experience with people, which already wasn’t tell me what the citizens will do, is even less applicable to perfectly-rational citizens.

Game theory provides many notions of “what the players will do”, in a bountiful cornucopia that makes you wary of asking questions you don’t want the answer to. These are called solution concepts, and at least my game theory course involved learning a new one every week.

A reasonable solution concept to start with is a Nash equilibrium, where we say that whatever it is that happens, it at least must be the case that each citizen makes the best possible choice given what the other citizens do. This makes sense, because our players are rational, so they don’t make suboptimal choices.33 Nash equilibria seem unintuitive at first, then really obvious, then confusing again. If my experience is a guide, you then read the SEP entry on Nash equilibria and get even more confused. I’ve come to peace with it, but cannot explain it; I hope one day to internalize Nash equilibria on a deeper level.

If each citizen chooses whether or not to protest, then in equilibrium every protester must be getting more value out of protesting than not (and the reverse for non-protesters). So if there are any protesters, there must be exactly \(n\) of them—because otherwise the success or failure of the protest is independent of any one protester’s actions, whose protesting costs time and effort. And for a solution with exactly \(n\) protesters to work, each of these protesters will have to find protesting less painful than the reward of a successful protest; we must have \(\alpha > \beta\).

There are choices of \(\alpha\) and \(\beta\) where \(\alpha < \beta\) but having some protestors is still good for society. For example, if two protestors out of a million citizens is sufficient to “win” the protest, then even if protesting is a net loss for the two protestors, we’d still like them to do it. Unfortunately, that does not happen.

Symmetry

So there is an equilibrium where no one protests, and another for each group of \(n\) potential protesters. But this is unsatisfying: which equilibrium actually happens? For example, it’s nice that there are equilibria with protesters, but they all involve two distinct groups of citizens that act differently (the protesters always protest, the others don’t). How do citizens know what group they are in? If I am one of the citizens, what should I do?

A better theory would involve every citizen executing the “same” algorithm, one which doesn’t involve asking “am I going to protest” before deciding if one will protest. You might say that I don’t just want an answer to the game-theoretic question (what will happen?), but also an answer to the decision-theoretic question (what should I do?). There’s a fascinating interplay between these two fields, and one approach to linking them is to look for symmetric Nash equilibria.44 This is not the start-and-end of the connection. There can be several symmetric equilibria. Social choice theory also has something to add here. And so on. But it’s a start.

Now, so far I have one symmetric equilibrium: no one protests. But this is not a great equilibrium, because it leads to a subpar outcome. To find more, I need to broaden the “algorithms” that citizens can run. So far, the algorithm was either “protest” or “don’t protest”, but there can be more.

The simplest more-general algorithm is one where a citizen flips a weighted coin, then protests if it comes up heads. Do equilibria exist where everyone protests with probability \(p\)?

There’s a beautiful insight that solves questions like this: if you are choosing randomly between two options, then you must not care which one you get. Otherwise you would just pick the better option. So if every citizen protests with probability \(p\), then protesting and not protesting must bring the same value.

How can that occur? Well, the value of not protesting is the \(\beta\) utility saved thereby. And the value of protesting? It is not \(\alpha\), because no citizen is guaranteed to get \(\alpha\); and even non-protesters sometimes get the communal benefit, because enough others protested. In fact, protesting is only superior to not doing so if you are going to be the pivotal, last protester needed to make the protest a success. So the benefit of protesting is \(\alpha\), times the probability that you are the tipping point.

And since everyone is running the same algorithm, we know that probability. It is the probability that exactly \(n\) heads come up if we flip \(N\) weighted coins of probability \(p\); it is \(\binom{N-1}{n}p^n (1 - p)^{N-1-n}\). (The \(N - 1\) is because we are adding up what everyone else does.) So, we have the equality: \[ \alpha \binom{N-1}{n} p^n (1 - p)^{N - 1 - n} = \beta \] We want to solve this for \(p\), but I don’t know how to do that for general \(N\) and \(n\).55 It definitely is while I don’t have access to Mathematica. Luckily, there are good approximate solutions using Poisson distributions. If \(n\) and \(N\) are both large, that probability is pretty close to \(e^{-p(N - 1)} (p(N - 1))^n / n!\). So we have

\begin{align*} \alpha e^{-p(N - 1)} (p(N - 1))^n &= \beta n! \\ (p(N - 1))^n e^{-p(N - 1)} &= \frac{\beta}{\alpha}n! \\ -\frac{p(N - 1)}{n} e^{-p(N - 1) / n} &= - \frac1n \sqrt[n]{\frac\beta\alpha n!} p &= -\frac{n}{N - 1} W\left(-\frac1n\sqrt[n]{\frac\beta\alpha n!}\right) \end{align*}

where \(W\) is the Lambert W function, the solution to \(y e^y = x\).

Ok, so what does this tell us? Well, firstly, \(W\) is undefined for arguments less than \(-1/e\). Another way of putting this: if that mess that we pass to \(W\) grows too large66 In magnitude; it is always negative., then there is no reasonable \(p\) value, and our fantasy citizens never lift up their chains and push back the excesses of their corporate overlords. That would be a pity.

So let’s look at that argument to the W function. We have an $n$-th root of \(n!\), which suggests using Stirling’s approximation to the factorial, \(n! \approx \sqrt{2 \pi n} (n / e)^n\): \[ -\frac1n\sqrt[n]{\frac{\beta}{\alpha} n!} \approx -\frac1n \sqrt[n]{\left(\frac{n}{e}\right)^n \sqrt{2 \pi n} \frac{\beta}{\alpha}} = -\frac1e \sqrt[2n]{2n \pi \frac{\beta^2}{\alpha^2}} \] Now, let’s look at that $2n$-th root. It can be either greater or less than 1, depending on \(\beta / \alpha\). But if it is greater than 1, then whole expression is less than \(-1/e\), and there is no symmetric solution. Since we aren’t interested in those situations, we must have \[2 n \pi \frac{\beta^2}{\alpha^2} < 1\text{, or }\alpha > \beta \sqrt{2 \pi n}.\]

This is already a fascinating fact: a protest doesn’t happen in our model unless \(\alpha\) is large, larger than \(\beta\) by \(\Theta(\sqrt{n})\). A protest can only occur if a successful protest is an exceptionally valuable thing. Note a similarity with the non-symmetric pure Nash equilibria from above: there we required that \(\alpha > \beta\) even though society as a whole benefits from a successful protest as long as \(N \alpha\), the total good from a successful protest outweighs \(n\beta\), the total cost of \(n\) protesters protesting. And if each protester is deciding probabilistically, they have even less information and \(\alpha\) must be even bigger for a protest to occur.

\(W\) is a multivalued function, so it produces two answers. This gives us two values of \(p\): a “high protest” and “low protest” condition. The closer we get to zero for \(W\)’s argument, the more different the two probabilities of protest. So for example, if \(\alpha\) is exactly \(\beta \sqrt{2 \pi n}\), the smallest value it can have, then $p = - n W(-1/e) / (N - 1) = n / (N - 1)$—that is, everyone’s probability of protesting is just about exactly the fraction of the nation that would have to protest for the protest to succeed. Which is to say, a very reasonable value, where the protesting gets done with a minimum of fuss. On the other hand, if \(\alpha\) were very large—if it went to infinity—then the argument to \(W\) would tend to 0, and the two possible values of \(p\) would tend toward \(0\) and \(1\). Both of these solutions are pretty silly, since a successful protest is either fantastically unlikely, or the entire country riots when a small protest would do.77 Is this a feature of the real world? I don't broach political opinions on this website, but do think about it for yourself.

Luckily, error in \(\alpha\) is tolerable: \[ W(-\frac1e + x) \approx \pm \sqrt{x} - 1 \] so if \(\alpha = \beta \sqrt{2 \pi n} (1 + \epsilon)\), then the argument to \(W\) is approximately \(-(1 / e) (1 - \epsilon / n) = -1/e + \epsilon / (e n)\) and the final \(p\) value is \[ p \approx \frac{n}{N - 1} \pm \sqrt{\frac{\epsilon}{e}} \frac{\sqrt{n}}{N - 1} \] so we can see that the fraction of the nation that protests departs from the ideal fraction as \(O(\sqrt{\epsilon / n})\). This is ignorable until we are order-of-\(n\) times larger than the critical threshold.

So \(\alpha\) must be greater than the large lower bound \(\beta \sqrt{2 \pi n}\), but it can be much, much bigger without the number of protestors changing much.

In fact, what are the chances of success, versus \(\alpha\) and \(\beta\)? I don't know enough about the Poisson's CDF to answer this question directly, but I can do some numerical simulations. Let's imagine a universe where we need 10,000 protestors for the protest to succeed.88 For comparison: this is an order of magnitude smaller than the student protests in Beijing 1989, and 1½ orders larger than the Kent State protests. Then we must have at least \(\alpha > 250\) or so, already an incredibly demanding bar. This is incredibly sad, because it means that basically all but the worst excesses cannot be curbed by protest.

As \(\alpha / \beta\) increases, the probability of the protest succeeding increases, from about 50% at the critical value. By the time \(\alpha / \beta\) is a thousand times the critical value, we have a 53% chance of the protest succeeding, and the number of protestors has barely budged. The probability of a protest does not dramatically change even if \(\alpha / \beta\) is billions of times the critical value. So sadly, no matter how valuable a successful protest would be, the chance of a successful protest barely budges.

Changing things

How do we make protests more likely? The main problem is that there's no incentive for protesting other than the small chance of being pivotal. So some other mechanism must either punish non-protestors or reward protestors.

One mechanism could involve non-protestors paying protestors when a protest succeeds. Another would involve protestors paying a little bit to punish non-protestors when the protest succeeds. I invite the interested reader to investigate either.

1
This is unrealistic for human psychology—starting with a notion that humans have a singular notion of utility—but the point of game theory is that weirdly human-like behavior can occur even without considering the quirks of human psychology. Unrealistic models are still useful.
2
This question is trivial if \(n = 0\) or \(n = N\), so let’s ignore those cases.
3
Nash equilibria seem unintuitive at first, then really obvious, then confusing again. If my experience is a guide, you then read the SEP entry on Nash equilibria and get even more confused. I’ve come to peace with it, but cannot explain it; I hope one day to internalize Nash equilibria on a deeper level.
4
This is not the start-and-end of the connection. There can be several symmetric equilibria. Social choice theory also has something to add here. And so on. But it’s a start.
5
It definitely is while I don’t have access to Mathematica.
6
In magnitude; it is always negative.
7
Is this a feature of the real world? I don't broach political opinions on this website, but do think about it for yourself.
8
For comparison: this is an order of magnitude smaller than the student protests in Beijing 1989, and 1½ orders larger than the Kent State protests.

By on . Share it—it's CC-BY-SA licensed.

Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation.