What is it about?

Games are thought experiments to help us learn how to predict rational behavior in situations of conflict.

Rational: The players want to maximize their own expected utility. No altruism, envy, masochism, or externalities (if my neighbor gets the money, he will buy louder stereo, so I will hurt a little myself...).[1]

Situation of conflict: Everybody's actions affect others. This is captured by the tabular game formalism.

Predict: We want to know whant happens in a game. Such predictions are called solution concepts (e.g., Nash equilibrium).

This is the CS Division. Why study games?

Scott Shenker: “The Internet is an equilibrium; we just have to identify the game.”

Your system today must contain incentives for others to adopt it, be compatible with it, not attack it, etc. The inputs to your algorithm are provided by rational agets who are interested in its output.

We shall also talk about Game Engineering, or Mechanism Design: How to create and launch a game in which rational agents will do exactly what you want them to do. This certainly belongs in CS.

In AI, we have multi-agent systems. This is something different (these agents are not selfish), with only tenuous connections with games.

Games

Introduce and discuss:

Prisoner's dilemma

Tragedy in the commons

Penalty shot and rock-paper-scissors

Chicken

Battle of sexes

Play (with real $?) 2/3 of average

Play majority RPS (we all play RPS, and the majority wins and splits all money, ties are resolved by RPS rules)

Notice from playing that we allow no repetition, binding contracts or cheap talk; these can be incorporated to create new games though.

The numbers in the games are not money, but utilities. Recall Bernoulli's St Petersburg paradox (and the other Bernoulli's solution).

Powerful influence in GT (and Economics): von Neumann – Morgenstern “Expected Utility Theory”.

A risk valuation is a function mapping V: ΔR --> R (this could be any set of events instead of the first R). That is, given a lottery L = (x1,p1;...xn,pm) it gives back a number.

Basic assumption of EUT: V is linear in the p_i's.

If so, there is a function U: R --> R such that V(L) = p1U(x1)+ ... + pnU(xn)

Note: Outside GT, and especially in Finance, nobody believes EUT.

Solution concepts

Most rudimentary: Rationalizability, or iterated elimination of strongly dominated strategies. Easy to do (even though P-complete, cannot be parallelized!). Universal but not very informative, most interesting games begin like that.

Pure Nash equilibrium: Combination of strategies (cell in the table) that is better in every dimension, no player has an incentive to deviate. Great when it exists. Not universal.

Nash equilibrium: Combination of randomized strategies such that every player has no better randomized (actually, pure) strategy.

Basic Theorem: Any strategy in the support of a Neq is a best response.

Theorem (Nash 1950) Every game has a Neq.

(We'll prove it).

Algorithms

Btw, why the “A” in “AGT”? Two reasons:

  1. We'll focus on CS-related games and issues.
  2. We'll be interested in algorithms for solving and designing games.

First algorithm for Neq: Support enumeration. (It's not a numerical problem, it's combinatorial, at least for 2 players).

m + n equations with m + n unknowns. For 2 players, linear. If anything goes wrong (singular, negative solution) go to the next support. Also for 2 players, elegant Lemke-Howson algoritthm (we'll do it). Both exponential.

For 3 players? Other algorithms, all exponential in the worst case.

NP-complete? No, thanks.

Zero Sum Games

Presidential example.

Introduce LP and duality. Consequences:

Any zero-sum game has a Neq.

Which can be found quickly.

Minmax theorem

Multiple equilibria OK: EQ = EQR x EQC, all three convex.

All Neq have same payoff.

Aumann: “Zero-sum games are the only situation in social sciences where we actually know what will happen...”

Succinctness

Example: three-person poker. How do you put in tabular form?

How about chess? Is chess “succinct,” by the way?

Fine, but how do we model with these tables the behavior of Internet users, social network participants, advertisers, and smart crowds? Problem: n players require > 2^n data.

Succinctness: symmetric, anonymous, graphical, polymatrix, congestion.

Problems

Do any two of these, and hnd them in at next week's class.

  1. How about three-person zero-sum games? (No money enters or exits the triad for any strategy combination.) Can we find a Neq in those easily? (Recall that general two-person games are hard to find Neq.)
  1. But suppose that we have three players, L, M, and R. L and M play a zero-sum game, in which M has n strategies. M and R play a zero sum game in which M also has n strategies. M must play the same strategy both left and right, simulatneously. Extend the zero-sum games result to show that this can be solved.
  1. In the Presidential zero-sum game, 3D-plot x^T R y as a function of x1 and y1.

But people are irrational! True. Much of this “irrationality” (altruism, spitefulness, terrorism, etc.) is just nonstandard utility functions. For other kinds, such as stupidity, would you trust a theory that argues that people are stupid and so they will act not to their best interests but as the theory predicts? Indeed, “rationality” also means that the players are at least as clever as you, in the sense that they have internalized anything that you may ever think about the game.