Okay, so we're going to talk a little bit now about properties of equilibria in these game zone networks. And that will give us a little bit more structure to understanding how these work. And again, we're going to stick with the idea of strategic complements and strategic substitutes. And I just want to sort of point out one really nice feature of complements, and also explain why substitutes are going to be much more complicated to work with. And to do this, we're going to need the notion of what's called a complete lattice. And so you can skip this if you're not interested in the mathematics, but I'll give you a quick lesson in lattices, so say that quickly a bunch of times. So a quick lesson in lattices. And so a lattice is going to be a set of points. So in particular what we're going to be looking at is equilibria. But you've got some set of objects and these are partially ordered so you've got some notion of, say, a partial order, use the sign greater than or equal to. So you've got some notion that some things are bigger than other things. And you don't necessarily have to be able to compare all objects, but some things will be bigger than others. And what's important in terms of having a complete lattice is that when you take any set of objects. In this case, what we're going to be looking at is a set of equilibria. But when you take any set of these, so let's think of these as x's. So in our world what are we going to be thinking of as the space? We can think of the action. So suppose that we have six individuals connected in a network. We can think of them as playing all 0's. So one possibility is that they play all 0's. One possibility is that they play all 1's. Some of them play 1's, some of them play 0's. Okay, and we'll say that one vector is bigger than another if all of its entries are at least as big as the other, right? So we'll say that this one is greater than or equal to this one. This one is also greater than or equal to this one. This one is greater than or equal to that one. But we couldn't compare this one. These two you can't compare. So neither one is bigger than the other. It's because some of the entries of this are 1's, some of the entries of this are 1's, and so forth. So these two don't compare, but the other ones you could rank. And you could rank this one compared to the other two, right? So you could say that this one is bigger than this one, and this one is bigger than this one, and so forth. So we have some rankings, but not all possible rankings. So we're going to be working with a space of 0's and 1's. But the notion of a complete lattice in terms of equilibria, basically, is going to be that if we look at any set of these things, there exists some object which is at least as big as all of them in the set, okay? So in this case, if we look at these three objects, this one, this one, and this one, we've got something which is this big. And there also exists something which is smaller than any of them, okay? So something is going to be a complete lattice if, when we take any subset of objects, we've got something which is at least as large as all of them and something else which is at least as small as all of them. Why is that going to be useful? Let's think of our equilibrium structure, so our six objects of 0's and 1's are six dimensions of 0's and 1's in terms of equilibria. So in the game where we had that people wanted to do something if at least two of their neighbors did. We have a situation where one possible equilibrium is all 1's. Another possible equilibrium is all 0's. It could be that these three people take action 1. It could be that these four people take action 1. These are all pure strategy equilibria of this game and they form a lattice. There's in some sense a biggest equilibrium, everybody taking 1. There's a minimal equilibrium, a smallest one, everybody taking action 0. And so if we take this set to be our set X, there exists something else, which is at least as large as either of these where every entry here is at least as large as every entry in here, okay? So that's the notion of a lattice. We can find in the biggest equilibrium or maximum equilibrium for any set. We can find a minimum equilibrium. So give me any set, I can find something which is at least as big as all of its elements. I can find something else which is at least as small as all of its elements. And so that's going to be quite useful in terms of this structure of the games of complements. So games of complements are going to have that property. And particularly where there's a proposition that says if we're looking at a game of strategic complements where the individual strategy sets are each complete lattices, then the set of pure strategy equilibria are nonempty complete lattice. So this is a theorem which follows fairly directly out of standard game theory. But what it does is it says that when we're looking for equilibria, there's going to be a nice mathematical shape to these things. And the complete lattice is a nice object to work with. And what that also tells us, is that directly, in games of complements, there exists an equilibrium as a corollary to this. There always existed peer strategy equilibrium because complete lattices have to be nonempty, so that's something that comes for free. So there will be nice properties to these things. That also means there's going to be nice ways of finding these equilibria. And I'll say a little bit about that in a moment. So before I go on to contrasting, let me say a little bit about them finding an equilibrium. So suppose that we've got a world where we're dealing with strategic complements and people could take 0's or 1's, action 0 or 1 and we want to find the highest equilibrium possible, okay? So what could we possibly do? So let's suppose that there's a society, and we start with that society. And there's, say, seven individuals. What we could do is just start and check, first of all, whether this is an equilibrium. Just start everybody at 1, that's the biggest possible point we could imagine being in equilibrium. So try that out. Okay, so what this says is if everybody was taking 1, would everybody want to take action 1? Maybe not, maybe some individuals wouldn't want to. So if this is an equilibrium then that's our maximum equilibrium, we found it. If it's not an equilibrium, well, then that means even when everybody else is taking the action, doesn't want to take the action, right? So let's suppose this person didn't want to take the action. So instead we say that if everybody else was taking the action all these other people would have been happy, but this person would really rather not take the action, okay? So given that this is a game of strategic complements, if they don't want to take the action when everybody else is taking it, then no matter what happens, even when some subsets are taking it, they're not going to want to take the action. So this person is always going to be 0 now. We never have to worry about that person flipping back up to be a 1. They didn't want to take it, they're going to be stuck at 0 forever. If they didn't want to take it when everybody took the action given that this a game of strategic complements, that means their threshold is above the highest possible threshold. That means that they're never going to take the action. So we can count this person as 0 forever. We know that any equilibrium has to have them as a 0, okay? So they're going to take action 0 no matter what. So now we just go back and repeat this. Now see if anybody else wants to take action 0. Now that we've put this person in action 0, either this is in equilibrium, or maybe now somebody says, well, given that the last person is taking action 0, now I want to take action 0. And if that's the case, maybe this person says, now I'm going to go to a 0. While given that this person was always a 0, then this person's always going to be a 0, this same kind of logic. They're never going to move back up because it's a game of strategic complements, we know that this person always has to be 0 and so forth. And we just keep following this. And either eventually we stop at an equilibrium or we reach all 0's. And if we reach all 0's, then that has to be equilibria. So now there's a very simple algorithm that takes at most n steps to find an equilibrium. So in a game of strategic complements, there exists an equilibrium, they form lattices, they're very easy to find. So this is a wonderful structure of these games. And think about it for a moment, try and see if you can name an algorithm that finds the minimal equilibrium. Right, so find the minimal equilibrium. How would you do that? So think about a variation on this equilibria. Instead of trying to find the highest equilibrium, try and find the lowest possible equilibrium. What would that algorithm look like? So you can find the max and the min fairly easily. A very nice structure to these things, games of complements are really nice to work with. Okay, contrast, games of substitutes, not so nice. In the games of complements we found that this, we have a nice structure. Games of substitutes, well, for the best shot public goods that we've looked at, that example, pure strategy equilibria exist and they're related to maximal independent sets. Other cases, equilibria may not exist in pure strategies. They will exist with some randomization, but that's going to be a little tougher in this kind of network setting. Equilibria generally will not form a lattice structure, unless you're in a very trivial case. Equilibria will not form a lattice and generally you're going to have problems, because when one person wants to take action 1 and other people go to 0 and vice versa. So you get this flipping condition rather then conditions where everybody goes up or everybody goes down. So the fact that everybody's preferences are moving in the same direction gives us the nice structure and complements. But the substitutes means that when we change one person from 1 to 0, other people can flip, and then things can flip back and forth and it's going to be very hard to find equilibrium in a lot of these games. So games of strategic substitutes are going to be more difficult to deal with, more difficult to say things about than games of strategic complements where there's this nice structure and mathematical structure to the equilibria. So for instance, when we look at the best shot public goods game, we can sort of, as we flip, given an individual on or off, that's going to affect what's happening. And we get this person doing a 1, this person doing a 0 or vice versa, but we're not going to be able to order these things. So we can't have them, there's not going to be a better equilibrium or a lower one. And actually finding these things, finding all the independent sets can be quite difficult. Finding one maximal independent set in a best shot public goods game is not hard. Finding all of them can be very difficult. And, in fact, is a difficult computational problem as known in computer science. But there can exist multiple equilibria and no lattice structure. Okay, so before I end, let me say a little bit more about generally, so best shot public goods are going to be one of the cases in the public goods case where we can actually say something about finding them. So let's suppose you wanted to find one equilibrium, say find one maximal independent set. Well, there's one algorithm that's fairly easy. One possibility is I just pick some node and I make that a 1, okay? So I'm going to say this person is definitely got 1, and I'm going to have them choose the action. Okay, how am I going to make sure that this person wants to take the action if it's a public goods game? So they only want to buy the book if none of their neighbors do. So now all their neighbors have to be 0's. So I pick this person to be 1, now I fill in all the 0's for their neighbors, okay? Now I've got a bunch of people who are still left. Pick any one of those people who are still left. They're not one of the neighbors of the first person, so they still don't have any neighbors who have taken any action, put them as a 1. Now all of their neighbors would have to be 0's, okay? Now pick anybody who's left, make them a 1, their neighbors become 0's and so forth. That algorithm will give you one of the maximum independent sets. Now if you did that over every possible ordering that you could pick nodes and you can find all the maximum independent sets. The difficulty is that there's many possible orderings I could have done that in, right? So you've got n factorial, you've got a huge number of possible orderings you could think of in sort of running that algorithm. And so the difficulty in finding all the maximum independent sets is going to be much more difficult. And it's going to be very hard even to find the best one in terms of having most or fewest actions. Whereas that was easier in a game of complements, where we could find a very quick and simple algorithm for finding equilibria. So complements, nice structure. Substitutes, there's also nice structure in terms of payoffs but not as nice structure in terms of equilibrium. Nonetheless, these are interesting games to look at, and both classes will be interesting in terms of applications. So we'll talk more about understanding equilibrium structure next.
