Help improving this definition of a "game"?

Question

My professor defined a game as follows:

• a set of $n$ players
• a set of strategies $s_i$ for each player $i$
• a set of payoffs $p_i$ for each player $i$
• turn-taking: sequential or simultaneous
• repetition: $k$ rounds, where $k\geq1$ and $k \in \Bbb{N}$

I have three problems with this definition:

1. He didn't define turn-taking mathematically, so I feel like it's a vague definition. There should be like an index of possible turns with max value $n$. But I'm not sure how to write it formally.
2. He doesn't define how we map from strategies selected to payoffs. Presumably, the set of payoffs should include a value for every possible combination of strategies selected. But there should be a way to state this formally as well.
3. He doesn't define what a strategy is. I suppose one could simply say that a strategy is the object we map from in the domain to an element in the set of payoffs (ie codomain). In that sense, anything that can be valued is a strategy, ie a possible action.

My Question:

Can someone offer a more complete definition than the one given? Specifically make sure it improves upon the concerns I mentioned.

Answer 1

Your question is a little bit vague, but I'll do my best.

Your professor was motioning in the correct mathematical direction, but I think that what you're asking for is a more complete formalization.

Any game can be thought of as a tree (i.e. a non-cyclic graph). So to answer your first point about turn-taking, you might think about a function which maps nodes of the tree to some $i\in\{1,2,...n\}$ In the picture below, you might be able to define a formula to characterize the turn taking, but you can't necessarily do this in general. In this example $P_1$ and $P_2$ take alternating sequential turns. $P_1$ can choose $L$ or $R$, then $P_2$ can see which he chose, and then also choose $L$ or $R$.

Before going on to your second point, I need to take a moment to define information sets, which it doesn't sound like you've gotten to yet. Colloquially, an infoset is a set of vertices that represent uncertainty. The root of a game tree is always a singleton infoset, for example. Consider the game where you and I simultaneously choose heads or tails. When $P_2$ chooses whether or not to play heads or tails, she doesn't know if I have chosen to play heads or tails either. Thus while the game tree will have 3 internal vertices (1 that is the root for $P_1$, and 2 for $P_2$, reflecting $P_1$'s choice) there will only be 2 infosets because both vertices for $P_2$ will be contained in the same infoset. In games where turn-taking is sequential, all infosets should be singleton.

Now back to your question about strategies. Each player has a set of strategies. In the example tree provided above $S_1 = \{LLLLL,LLLLR,...,RRRRR\}$. This might seem a little bit confusing at first as it seems like each element of $S_1$ goes above and beyond defining a path. Each player's strategy is defined in terms of infosets. Therefore, the element $LLLLL$ should be read as, when $P_1$ finds herself at the top, she will choose $L$, and when she finds herself at the vertex that is farthest on the left and 1 down from the top, she will also choose $L$. It then also says that if $P_2$ were to choose $R$ instead, that $P_1$ would choose $L$. Thus a strategy is the set of all possible actions a player might take under all possible contingencies.

Finally, how do we state the mapping from strategies to payoffs? First we note that ever player has a strategy set $S_i$, and then form the cartesian product $S=S_1 \times S_2 \times ... \times S_n$, which characterizes all possible strategy combinations for all possible players. Then our payoff will be $\pi:S\to\mathbb{R}^n$. In our example $\pi(LLLLL,LLLLLLLLLL) = (4,2)$.