Complete lattice

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 equilibra. But when you take any set of these, so let's think of these as x'. 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 6 individuals connected in a network. we can think of them as playing all 0:

(0,0,0,0,0,0)

one possibility is that they play all 1:

(1,1,1,1,1,1)

some of them play 1, some of them play 0:

(0,0,1,1,0,0)

we'll say that one vector is bigger than another if all of its entries are at least as big as the other.

so (1,1,1,1,1,1) > (0,0,1,1,0,0) > (0,0,0,0,0,0)

neither one is bigger than the other:

(0,0,1,1,0,0) and (1,1,0,0,1,1)

• Complete lattice: for every set of equilibria X

  • there exists an equilibrium x' such that $x' \ge x$ for all x in X, and

  • there exists an equilibrium x'' such that $x'' \le x$ for all x in X

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 somehting else which is at least as small as all of them.

Lattice

Why is that going to be useful? Let's think of our equilibrium structure, so our six objects of 0 and 1 are 6 dimensions of 0 and 1 in term of equilibira. So in the game where we had that people wanted to do something if at least 2 of their neighbors did.

we have a situation where one possible equilibrium is all 1(upper right), another possible equilirbrium is all 0(lower left), it could be that these 3 people take action 1(upper left), it could be that these 4 people take action 1(lower right). 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(upper right), there's a minimal equilibrium, a smallest one, everybody taking action 0(lower left). So if we take this set(upper left and lower right) so 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.

We can find in the biggest 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.

Proposition

If in a game of strategic completements where the individual strategy sets are complete lattices:

the set of pure strategy equilibria are a (noneempty) 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 corollary to this, there always existed pure strategy equilibria because complete lattices have to be nonempty, so that's something that comes for free.

That also means there's going to be nice ways of finding these equilibria: so suppose that we've got a world where we're dealing with strategic complements and people could take action 0 or 1, and we want to find the highest equilibrium possible. So what could we possiblely do? So let's supppose that there's a society, and we start with that society. there's, say, 7 individuals:

(1,1,1,1,1,1,1)

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. 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 a an equilibrium, well, then that means even when everybody else is taking the action, doesn't want to take the action, so suppose one person don't want to take the action:

(1,1,1,1,1,1,0)

So instead we say that that if everybody else was taking the action all these other people would have been happy, but the last person would really rather not take the action. 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 complemetns, 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( (1,1,1,1,1,1,0) ), we know that any equilibrium has to have them as a 0. 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.

(1,0,1,1,1,1,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.

Contrast: Complements and Substitutes

• In a game of complements: pure strategy equilibria are a nonempty complete lattice

• In a game of strategic substitutes:

  • Best shot game: pure strategy equilibria exist and are related to maximal independent sets
  • Others: pure strategy may not exist, but mixed will (with finit action spaces)
  • Equilibria usually do not form a lattice

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.

Best Shot Public Goods

• invest if and only if no neighbors do(threshold is 1)

• again, multiple equilibria

• but, no lattice structure...

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.

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. 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.