Epistemic status: rough sketch, there might be holes but I don’t see any atm.
I think you need to slightly weaken the definition of an MLL and then you’ll have an existence theorem.
Let’s start with general discontinuous games. We have a game between two players, with pure strategy spaces X1 and X2 that we assume to be compact Polish spaces and (discontinuous) utility functions u1,2:X1×X2→[0,1]. Then we can take the closure of the graphs of u1,2 and get upper hemicontinuous multivalued utility functions. I claim that for such multivalued games, Nash equilibria (in some sense) exist.
Let X be a compact Polish space and f⊆X×[0,1] a multivalued upper hemicontinuos function on it. What does it mean for x∈X to be a “maximum” of f? We can define it as follows: for any y∈X, the maximal possible value of f(x) is greater or equal to the lowest possible value of f(y). It is not hard to see that maxima form a non-empty closed set. This leads to a corresponding notion of “best response” in multivalued games, and a corresponding notion of Nash equilibrium.
Notice that since we only care about the maximal and minimal possible values of f(x), we might as well require that f takes convex multivalues (i.e. closed intervals), since otherwise we can always take pointwise convex hull. Expected values of intervals can be defined by separately taking the expected value of the upper and lower ends of the interval.
I think that the existence of Nash equilibria follows from the Kakutani theorem in the usual way. The key observation is, for an upper hemicontinuous function, the maximal possible value is a (single-valued) upper semicontinuous function and the lowest possible value is a (single-valued) lower semicontinuous function. This implies that the best-response mapping is upper hemicontinuous.
Applying it to MLL, what I think we get is a notion of “weak” dominance where we only require that Pr[v(B)>v(A)]≤12, and otherwise the definition is the same.
Yes, this is a good point. Maybe we can strengthen the “weak-MLL” criterion in other ways while preserving existence. For example, we can consider the “p-dominance” condition Pr[v(B)>v(A)]≤1−p and look for an LL that is “weak p-maximal” for the highest possible p. The function on the LHS is lower-semincontinuous, hence there exists a maximal p for which a weak p-maximal LL exists.
Epistemic status: rough sketch, there might be holes but I don’t see any atm.
I think you need to slightly weaken the definition of an MLL and then you’ll have an existence theorem.
Let’s start with general discontinuous games. We have a game between two players, with pure strategy spaces X1 and X2 that we assume to be compact Polish spaces and (discontinuous) utility functions u1,2:X1×X2→[0,1]. Then we can take the closure of the graphs of u1,2 and get upper hemicontinuous multivalued utility functions. I claim that for such multivalued games, Nash equilibria (in some sense) exist.
Let X be a compact Polish space and f⊆X×[0,1] a multivalued upper hemicontinuos function on it. What does it mean for x∈X to be a “maximum” of f? We can define it as follows: for any y∈X, the maximal possible value of f(x) is greater or equal to the lowest possible value of f(y). It is not hard to see that maxima form a non-empty closed set. This leads to a corresponding notion of “best response” in multivalued games, and a corresponding notion of Nash equilibrium.
Notice that since we only care about the maximal and minimal possible values of f(x), we might as well require that f takes convex multivalues (i.e. closed intervals), since otherwise we can always take pointwise convex hull. Expected values of intervals can be defined by separately taking the expected value of the upper and lower ends of the interval.
I think that the existence of Nash equilibria follows from the Kakutani theorem in the usual way. The key observation is, for an upper hemicontinuous function, the maximal possible value is a (single-valued) upper semicontinuous function and the lowest possible value is a (single-valued) lower semicontinuous function. This implies that the best-response mapping is upper hemicontinuous.
Applying it to MLL, what I think we get is a notion of “weak” dominance where we only require that Pr[v(B)>v(A)]≤12, and otherwise the definition is the same.
Yeah, I believe this works, and that it feels too weak.
For example, if there is a unanimous winner, you only have to pick them half the time, and can do whatever you want the other half of the time.
Yes, this is a good point. Maybe we can strengthen the “weak-MLL” criterion in other ways while preserving existence. For example, we can consider the “p-dominance” condition Pr[v(B)>v(A)]≤1−p and look for an LL that is “weak p-maximal” for the highest possible p. The function on the LHS is lower-semincontinuous, hence there exists a maximal p for which a weak p-maximal LL exists.