# Ideas for game-theoretic meta contest problems for HS students

$$\text{Hi,}$$ new contributor here. I am a teacher's assistant for a class in a Math Circle program for mathematically advanced high school (and occasionally a few middle school) students. I was planning to organize a contest for the students centered around the concepts of game theory and metastrategies, such that the "correct" answer will to some degree depend on how other students (and oneself) respond. Here are a few examples of problems that will almost certainly be on the contest (some devised by myself, some taken from contests I've seen, some previously known):

1. Pick any real number $$n, 0\le n\le 100$$. Let $$N$$ be the average of everyone’s picks. The winner will be anyone who minimizes $$\big|\frac23N-n\big|$$. (Known)
2. Pick any positive integer $$n$$. Let $$N$$ be the number of distinct answers across all students. The winner will be anyone who minimizes $$|N-n|$$. (From a contest)
3. Pick any positive integer $$n$$. The winner will be whoever picks the least number nobody else picks. (Mine)

To find problems for my contest, I have picked over several contests I've taken that included problems with this general concept and spent a while trying to come up with further questions with interesting consequences and intended emergent behaviors, yet I seem to be coming up a few questions short of the length I had hoped for. So my request is for any (old or new) problems in this sort of mold- wherein the correct answer depends on everyone's answers and the statement can be easily understood by bright high schoolers.

If this is the wrong setting in which to ask this question, please let me know a better forum and I will happily ask there instead. Any and all criticism is welcomed.

• Should the first one really be "pick any real number $o \leq n \leq 100$"? While there is nothings technically wrong with this, I have never called a non integer number $n$. Jul 30, 2022 at 12:43
• My issue was as regards uniformity- I wanted to use the same variable name across all questions, and using $n$ seemed less objectionable to me than calling necessarily integers $x$. Now that I think about it, maybe (?) $r$ would have been better? But if we're nitpicking, I said "$0\le n$", not "$o\le n$". :) Aug 1, 2022 at 13:37
• I think you should restrict to "explicit rational" rather than "real", because you do not want to get funny answers like "R(5,6)" where R denotes the Ramsey numbers. Aug 10, 2022 at 9:08
• Running the contest, my fellow teacher's assistants and I realized this weakness and specifically requested decimal expansions to avoid "$G_{64}$" or "$\text{the greatest number picked by anybody else}+1$" or that sort of thing. Aug 10, 2022 at 13:47

I'll start with something that is not a new game per se but a small remark about what constitutes "a correct answer" here.

The "best" strategy in such games is almost always a randomized one rather than a deterministic one. Let's simplify your third game to the extreme where the answer is still non-obvious: you have 3 contestants each picking either 0, or 1, or 2 (same rules). You want to maximize your chance to win. Suppose that you choose 0 with probability $$p$$, 1 with probability $$q$$, 2 with probability $$r$$, and everybody else does the same with probabilities $$P,Q,R$$ respectively. Then your opponents choose 00 with probability $$P^2$$, 11 with probability $$Q^2$$, 22 with probability $$R^2$$, 01 with probability $$2PQ$$, 02 with $$2PR$$ and $$12$$ with $$2QR$$, so your chance to win is $$P^2(q+r)+Q^2(p+r)+R^2(p+q)+2QRp \\ =(Q^2+R^2+2QR)p+(P^2+R^2)q+(P^2+Q^2)r\,.$$ If the maximum of this expression in $$p,q,r$$ is attained at $$P,Q,R$$, then one cannot improve his chances unilaterally when everybody else plays $$P,Q,R$$. This is what is called "Nash equilibrium". (Note, however, that certain ways of cooperation of two players can kill the third one: just choose 01 collectively). Here it happens when $$P=\frac{\sqrt 3}{\sqrt 3+2}, Q=R=\frac{1}{\sqrt 3+2}$$, so all expressions in parentheses are the same and you have the chance $$\frac 4{7+4\sqrt 3}\approx 0.287$$ to win no matter how you play if everybody else is playing those $$P,Q,R$$, so you have no real incentive to deviate from these common values if all other people stick to them.

This simple example can be explained to reasonably bright high school kids, so it may be worth discussing it before letting them to play the actual games of this type.

As for the games themselves, you seem to be looking for something that is symmetric and satisfies the property that making the common deterministic choice makes everybody a loser, so unilateral deviating from this strategy is beneficial. Having these two properties in mind, you can design as many games as you wish. Almost all such games can be described by the scheme

Everybody makes a choice $$x_i$$ and the (unique?) minimizer of $$F(x_i;x_1,\dots,x_n)$$ wins, where $$F(y;x_1,\dots x_n)$$ is a symmetric in $$x$$-variables function such that $$y=x$$ is never a minimum of $$F(y,x,\dots, x)$$.

Here are some other possibilities to implement that idea:

Everybody writes down names of some other people in the group (as many as he wants). The number of points one receives is the number of people not in his list who wrote his name plus the number of people on his list who did not write his name. The highest score wins.

This is of the type "Maximize the lack of reciprocity" (you can act in a certain number of ways towards every other person and your goal is to maximize the number of people who do not act in the same way towards you; I leave the analysis of this one with 3 people to you).

Democratic election in Wonderland: The students are split into two equal size parties, one supporting Tweedledee and another Tweedledum. They can vote (after a secret party meeting, if you want it to be a team game) in any way they want but nobody can abstain. The score of the candidate is $$\min(12q,5-3q)$$ where $$q$$ is the portion of people voting for him (so the optimal score is achieved by $$q=1/3$$ while $$1/6$$ loses to $$5/6$$, which in principle allows each party to win if they know exactly what the other party is doing by either making their candidate score exactly $$1/3$$ or making the opponent score exactly $$1/6$$, say. This is the only property of the score function one needs to make the game really interesting.) The candidate with the higher score gets elected (you can adjust the coefficients a bit depending on the number of players to make a tie impossible, so that you'll always have a winner. With my function all you need is that the total number of students be not a multiple of 9)

I wish something like that were implemented into the USA voting system instead of the mathematically boring "majority rule" with the trivial optimal strategy of "voting for your preferred candidate no matter what". Then the smarter people would have a chance to win even if they are not a majority (which they almost never are) but not if they are too few. Of course, if there are too many people, you may have more candidates but the score function should be chosen differently with the same underlying idea: each party should be able to win if it knows how the members of other parties are going to vote).

This was just to show you some possibilities. The key point is that, since the best strategies are probabilistic in nature, each such game should be played several times, if possible, to see who can really outsmart whom.

Just my 2 cents :-)

• Nice answer- that's a good analysis and those are some really interesting games! Oct 31, 2022 at 4:22