Games between Programs: The Ruliology of Competition

The Basic Setup Whether one’s dealing with biology, economics, politics or a host of other fields, it’s common to encounter situations that can be modeled as involving two agents that repeatedly compete with each other. One imagines that at each step each agent can take one of a certain set of actions, and that then—in a classic game theory way—each agent (or “player”) gets a certain fixed “payoff” based on the action they and their opponent take. But how do the agents decide what action to take? We imagine that each agent has a certain fixed procedure—or “strategy”—for making its decisions. And we imagine that the input to each of those decisions is the sequence of past actions that the agent and its opponent have taken. There’s been lots of work done over the course of nearly a century on particular choices of strategies. But something I’ve long been curious about is what happens if one systematically considers all possible strategies. And if we think of strategies as programs this becomes a question to which we can immediately apply ruliological methods. Which is what I’m going to do here. To be more specific about the setup, let’s assume that at each step, each agent takes one of two possible actions, indicated by and . And for now let’s take the payoffs to be the ones for the classic “match-or-not” (“matching pennies”) game—in which player 1 has the bigger payoff when there’s a match, and player 2 has the bigger payoff when there isn’t a match: So what happens when agents repeatedly play this game? Well, it depends on their strategies. Here are a few examples for several different choices of each agent’s strategy: Plotting the cumulative payoffs for the two agents (represented by and ) in each of these cases we get: Often we’ll consider the “winning agent” to be the one that has the numerically largest cumulative payoff (i.e. is eventually on top in these plots) after a certain number of steps. And with a criterion like this, we’ll be able to rank different programs against each other—and in general explore the ruliology of competition.

With the basic setup we’re using, we can represent all possible sequences of actions by a multiway graph: For any given sequence of actions, there is then a cumulative payoff for each agent for our match-or-not game: If each agent adopts a particular strategy, this will define a particular path through the multiway graph. For the strategies used in the examples above, the paths are: What does it take to have a winning strategy? In what follows, we’ll consider strategies based on several different types of programs. But one basic question we can always ask is whether what turn out to be the winning strategies tend to be based on programs that are more complicated, or less so—or to show behavior that is more complicated, or less so. In other words, if you want to win, should you typically be trying to build up something complicated? Or should you instead expect to be able to find a “simple hack” that will “crack the game” and—at least usually—let you win? In effect, we’re asking whether competition tends to lead to complexity, or simplicity. I’ve recently looked at minimal models of both biological evolution and machine learning, in which one is adaptively evolving programs in order to maximize some externally imposed fitness function. And what I’ve found is that even when the fitness function one uses is simple, the behavior of the programs that maximize it is normally quite complex. In other words, adaptive evolution will tend to make even a simple, fixed objective be achieved in a complicated way. So what if instead of having a fixed, externally imposed objective, our goal is just broadly to win against other agents? Does such—potentially open-ended—competition lead us to more complex behavior (or more complex programs), or not? That’s the kind of question we’re going to be able to explore here by looking at the ruliology of competition. Strategies from Finite State Machines Finite state machines can be thought of as defining extremely simple programs (that might model pathways in biology, decision processes in economics, etc.). And to start our investigation of the ruliology of competition we’re going to look at strategies defined by finite state machines. A typical example of a finite state machine (here with 3 states) is: We’re going to use this finite state machine to define a strategy for an agent.

To see how this works, let’s say that the sequence of actions taken by the agent’s opponent have been: The idea is to use this sequence of actions to define a path in the finite-state-machine graph, then to determine the next action from the color of the state reached. We start at the vertex with the incoming arrow, then successively follow the edge whose color matches the next move made by the opponent: At the end of this process we’ll reach some vertex in the graph (i.e. some state in the finite state machine). In the particular case shown here, the state we reach is . And then we take the output of the strategy—i.e. the next action for the agent to take—to be . It’s sometimes convenient to show the states of the finite state machine arranged on a line: And then we can summarize the path taken with a certain input by showing the successive states reached: So what happens if two finite state machines compete? The basic idea is that the successive outputs from one machine become the successive inputs to the other, and vice versa. If our second machine is then we can represent the behavior of the machines by: If the payoffs we use are for the match-or-not game, then their cumulative values for these machines are so that in the end agent 2 can be considered the winner. It’s important to note here that in the setup we’re using, everything is deterministic: at every step, each agent takes an action that is deterministically computed using its strategy from the past history of moves. It’s a different setup from what’s most often studied in game theory, where each move is in effect considered independently, but where there can be probabilities for different actions (“mixed strategies”)—and where in the end averaging is done over “different possible rolls of the dice”. The Space of Possible Finite State Machines The number of possible graphs for finite state machines with s states is (2 s2)s. But some of those graphs correspond to machines with identical behavior—so that the number of distinct machines is smaller: 2-State Machines In the 2-state case, the 22 distinct machines are where we’ve identified each machine by a number. So what happens if pairs of these machines compete?

Here are a few examples, where in each case we’re identifying the average payoff (here for 10 rounds of the match-or-not game): (In all competitions between pairs of finite state machines, the sequence of moves ultimately has to become periodic—with a period equal at most to the product of the number of states in each machine.) What happens if each of the 22 distinct 2-state machines competes against each of the other ones? We can summarize the results by showing the mean (long-term) payoff for every pair of machines (the payoff is for each machine “playing as agent 1”; in match-or-not, the payoff is negated if “playing as agent 2”): So what machine is the “overall winner”? One way to assess this is to look at the average of the mean payoffs achieved by a given machine when competing with all other (distinct) machines: The winner by this measure is then machine 26: Running this machine against all (distinct) 2-state machines we get the following mean payoffs: The actual behavior in each case—which doesn’t itself depend on the payoffs, only on the machines involved—is: What are the “runners-up” to the winning machine? Here are all the distinct machines, ranked by their mean payoffs: Here’s what happens if we play the top 3 runners-up against all machines: We can summarize how a machine behaves by showing the history of its behavior when playing against all other machines (or, in effect, by putting together the first columns in pictures like the ones above). Here are the results for all the machines (for 15 steps), ordered from highest average score down: (Once again, these pictures are completely determined just from the machines involved; the payoffs in the match-or-not game determine only their ordering.) One footnote to what we’ve been saying here has to do with how many steps of competition we are getting the machines to do. For all finite-state machines, the behavior must eventually become periodic—and for 2-state machines the maximum period is 4 steps, with a maximum transient of 3 steps.

But the actual average mean payoffs vary with the total number of steps one considers: It’s notable that at the least for the first few steps, the rankings move around: But in this case it doesn’t take too many steps for the ultimate winner to be clear (later on we’ll see examples where it takes much longer). (There are other subtleties as well. One of them is that we are computing average payoffs by playing every machine against every other distinct machine. In principle we could also include other equivalent machines—which would slightly change the weighting of our averages. But since we’re really concerned with strategies, not machines as such, the scheme we’re using seems more appropriate.) 3-State Machines For the 956 distinct machines with s = 3 states, the corresponding “competitive array” (after 1000 steps) is: The average mean payoff for each of the machines (i.e. the average across each row in the “competitive array”) is then while the distribution of these average mean payoffs is: The top few machines for the match-or-not game are then: Running the top machine (s = 3 machine 1164) against all (distinct) 3-state machines we get the following mean payoffs: The distribution of possible limiting mean payoffs here is: And the most common forms of behavior seen are: The maximum possible period for a competition between two 3-state machines is 9. Machine 1164 never quite achieves this; its maximum period of 7 occurs when competing with machines 2546 and 2755 (both giving limiting mean payoff –1): If one looks at all possible pairs of 3-state machines, there turn out to be 792 that yield period-9 behavior, examples being: (These have no transients; the maximum transient for 3-state machines turns out to be 8.) An Aside: What Do We Mean by “Average”? We’ve talked about how a machine does “on average” when competing with all other (distinct) machines. But what do we mean by “on average”? So far, we’ve taken the “average” to be the mean of the payoffs obtained by competing with each other machine (and the payoffs here are themselves means across successive steps). But what if we use the median instead of the mean?