12
$\begingroup$

Let's say you have an arbitrary length of time. You are playing a game in which you want to push a button during this time span after a light comes on. If you do so, you win; if not, you lose. You can't see the light; you can only guess a random time to push the button. If you are playing all by yourself, the obvious way to guarantee winning is to push the button at the last possible instant, so that you will be after the light coming on no matter what.

Now let's say you are playing against another player. You both have the same goal: push your button after the light comes on but before the other player pushes their button. I'm sure the best solution in this case would be to push the button in the exact middle of the time range if the other player is pushing at a random time, but it could be that there is no optimal solution if both players are using a coherent strategy. This is complicated by the fact that one can lose either being first or third in the sequence of three events, and in some cases by being second, if the light is third. Also, both players can lose; you don't win by being closer if you're too early.

If there is an optimal solution for the second case, can that be generalized in any way? For a length of time t and a random number of players p is there a moment x that would give the best chance of being the winner? This is somewhat like the way bidding works on The Price is Right, except there is no real way to judge the "value", or correct time, to bid.

EDIT: Let's also take this one level higher. Consider playing multiple rounds of the game. You are allowed one button push per game, so the total number of rounds and pushes permitted are the same, but you can distribute your pushes however you like, anywhere from one per round to all in the same round. Is there an optimum mix at that level? Remember again that you wouldn't know when or if the other player was playing in any particular round, you would only know if you had won or lost that round, and it is possible to both win and lose whether or not the other player plays.

$\endgroup$
  • $\begingroup$ for me this game has no "best choice"... the light can come on in every moment of the time span... it´s coincidence when the light comes on. $\endgroup$ – Hiatus Nov 7 '13 at 20:28
  • 2
    $\begingroup$ Good question. I am guessing that there is a solution, but that it must be a continuously mixed strategy. (So, I disagree with your hunch on the exact middle wholeheartedly.) $\endgroup$ – Keep these mind Nov 7 '13 at 21:19
  • 1
    $\begingroup$ Exact middle cannot be right, as it is beaten by always pressing at $\frac 12-\epsilon$, which wins with probability $\frac 12-\epsilon$, loses with probability $\epsilon$ and draws with probability $\frac 12$. A similar argument shows the strategy must not be discrete. $\endgroup$ – Ross Millikan Nov 7 '13 at 21:40
  • 1
    $\begingroup$ @WillNelson Implicitly, the other player(s) is/are rational. So, a Nash equilibrium (most likely in continuous mixed strategies) is what is sought. $\endgroup$ – Keep these mind Nov 8 '13 at 19:26
  • 7
    $\begingroup$ @JoeMajsterski I will give 500 internet points for the 2-player/single-shot case (when the question becomes eligible in 25 hours time). Answers before that time will also be contenders. Please upvote this comment. $\endgroup$ – Keep these mind Nov 8 '13 at 19:28
4
+500
$\begingroup$

The big assumptions I'll make in my answer are (1) that all distributions are absolutely continuous (with respect to Lebesgue) everywhere, so we can employ probability densities, (2) The support of both players' strategies are the same and of the form $[a,b]$. Maybe someone can extend this answer by relaxing these assumptions.

Let $F$, $G_1$ and $G_2$ be the cdfs of the light and players 1 and 2 arrival times. Let $f$, $g_1$, and $g_2$ be the corresponding densitites.

Player 1's expectation of winning is $$ P = \int_0^{\infty} I(t) \ d G_1(t) $$ where $$ I(t) = F(t)(1-G_2(t)) + \int_0^t G_2(t') dF(t'). $$ The first term in the integrand corresponds to $\mathbb{P}(light \le 1 < 2)$. The second is $\mathbb{P}(2 \le light \le 1)$.

Player 1 chooses $G_1$ to maximize his payoff. That means he chooses $G_1$ with its support where the integrand $I(t)$ of $P$ above is maximized. If $G_1$'s support is $[a,b]$, that means that \begin{eqnarray} (1)\ \ I(t) \ \mbox{ is a constant on $[a,b]$} \\ (2)\ \ I([a,b])\ge I(t) \mbox{ for any $t\ge 0$}. \end{eqnarray} Differentiate, and we end up with the following boundary value problem: \begin{eqnarray} 0 &=& f(t) (1-G_2(t)) - F(t) G_2'(t) + G_2(t) f(t) \\ G_2(a) &=& 0 \\ G_2(b) &=& 1. \end{eqnarray} This simplifies to $$ f(t) = F(t) G_2'(t). $$ The BVP is easily solved: $$ (3)\ \ \ G_2(t) = \log\left(\frac{F(t)}{F(a)}\right) \ \ \mbox{ for $t\in[a,b]$}, $$ but we require $G_2(b) = 1$, so we must have $F(b) = e F(a)$.

Let $T$ be the end of the support of $F$, i.e., (informally) the last time the light might come on. We might have $T=+\infty$. Note that \begin{eqnarray} I(b) &=& \int_0^b G_2(t') dF(t') \\ I(T) &=& \int_0^T G_2(t') dF(t') \end{eqnarray} If $b<T$, then the second integral strictly exceeds the first, violating $(2)$ above. Thus, $b\ge T$. But by $(3)$, $G_2(t)$ is flat for $t>T$, so in fact, $b=T$.

In summary: choose $a$ such that $F(a) = e^{-1}$ and choose $G_2$ according to $(3)$. $G_1$ is the same.

Note in passing that I did not assume the players used the same strategy, just that the supports are the same.

Now I've done the easy part. How to deal with the possibility of different supports, supports that aren't intervals, non-absolutely continuous distributions, etc., I'll leave to someone else!

$\endgroup$
  • $\begingroup$ How is $I([a,b])$ defined? $\endgroup$ – Keep these mind Nov 9 '13 at 8:40
  • $\begingroup$ By $I([a,b])$, I just mean $I(t)$ for any $t\in[a,b]$. Remember, $I(t)$ is a constant on $[a,b]$, so $I([a,b])$ is just one value. $\endgroup$ – Will Nelson Nov 9 '13 at 8:41
  • $\begingroup$ By the way, this problem is a pretty standard type of game theory question studied in economics. $\endgroup$ – Will Nelson Nov 9 '13 at 8:42
  • $\begingroup$ Obviously, in equilibrium, all pure strategies in the support have equal expectation value. Is it immediately obvious that a deviation from this mixed-strategy Nash equilibrium by one of the players to a pure strategy $<a$ (with $F(a)=e^{-1}$) is disadvantageous to that player's expectation value? $\endgroup$ – Keep these mind Nov 9 '13 at 9:56
  • $\begingroup$ @Transmissionfrom Great question. In fact, I asked myself the exact same question but didn't include the answer in my writeup (it was getting long). For $x<a$, $I(x) = F(x)\le F(a) = I(a)$. If $I(x)$ were to exceed $F(a)$, then the strategies I described would not be a Nash equilibrium. But since the player can't strictly benefit by deviating, it's still an equilibrium. And $I(x)=I(b)=e^{-1}$ for $x>b$. (Do the integral in the definition of $I(t)$: it actually comes out to $e^{-1}$, as required.) Thus deviation to $x>b$ cannot yield a strict improvement either. $\endgroup$ – Will Nelson Nov 9 '13 at 10:16
2
$\begingroup$

We assume that the set of common knowledge of the game (each player knows it, and each player knows that the other player knows etc), is (skipping formalities):

$1)$ The rules of the game. These rules include that if the button is pushed after $T$ the player loses (only implicitly assumed in the OP's question).
$2)$ That both players are "rational" meaning in our case that they prefer winning to losing, and that they won't adopt strictly dominated strategies.
$3)$ That the "length of time" is finite, $[0,T]$.
$4)$ That the distribution of the timing of the light flash $\lambda$, is $G(\lambda)$, be it Uniform or other.
$5)$ That both players follow the principle of insufficient reason, whenever the need arises. This means that when no relevant information is available, chance is modelled as a uniform random variable. (Note: we need to assume that, because, although the principle of insufficient reason is a very intuitive argument, nevertheless philosophical and epistemological battles still rage over this principle, and so, "rationality" alone is not sufficient to argue that the PIR will be followed).

Denote $t_1$ the time-choice of player $1$ and $t_2$ the time-choice of player 2. Both $t_1$ and $t_2$ range in $[0,T]$. They cannot range below $0$ because it is impossible, and they don't range above $T$ because this is a strictly dominated strategy.

If we are player $1$, then $t_1$ is a decision variable, while, $\lambda$ and $t_2$ are random variables. The probability of us winnig is

$$P(\text {player 1 wins}) = P(\lambda \le t_1, t_2 > t_1) $$

Now, from the point of view of player 1, $\lambda$ and $t_2$ are independent random variables: if player $1$ "knows" that $\lambda = \bar \lambda$, this won't affect how he views the distribution of $t_2$. So

$$P(\text {player 1 wins}) = P(\lambda \le t_1) \cdot P(t_2 > t_1) = G(t_1)\cdot [1-F_2(t_1)]$$

where $F_2()$ is the distribution function of $t_2$. Player $1$ wants to maximize this probability over the choice of $t_1$:

$$\max_{t_1} P(\text {Player 1 wins})= G(t_1)\cdot [1-F_2(t_1)] $$

First order condition is

$$\frac {\partial}{\partial t_1} P(\text {Player 1 wins}) =0 \Rightarrow g(t_1^*)\cdot [1-F_2(t_1^*)] - G(t_1^*)f_2(t_1^*) =0 \qquad [1]$$

where lower case letters denote the corresponding density functions (which we assume they exist).

The second-order condition (because we have to make sure that this is a maximum), is

$$\frac {\partial^2}{\partial t_1^2} P(\text {Player 1 wins})|_{t^*_1} <0 \Rightarrow \\ g'(t^*_1)\cdot [1-F_2(t^*_1)] - 2g(t^*_1)f_2(t^*_1) - G(t^*_1)f'_2(t^*_1) <0 \qquad [2]$$

Now, since we have no other information on the timing of the light-flash, except its range, then by our assumptions regarding the common knowledge set, $\lambda \sim U(0,T)$. Then

$$[1] \rightarrow \frac 1T [1-F_2(t_1^*)] - \frac {t_1^*}{T}f_2(t_1^*) =0 \Rightarrow t_1^* = \frac {1-F_2(t_1^*)}{f_2(t_1^*)} \qquad [1a]$$

while $$[2] \rightarrow - \frac 2Tf_2(t^*_1) - \frac {t_1^*}{T}f'_2(t^*_1) =-\frac 1{T}\Big(2f_2(t^*_1)+t^*_1f'_2(t^*_1)\Big) \qquad [2a]$$

To cover a conjecture of the OP, that the button will be pushed in the exact middle of the time-length, this will happen if player $1$ models $t_2$ as being a uniform random variable, $t_2 \sim U(0,T)$. Then

$$[1a] \rightarrow t_1^* = \frac {1-(t_1^*/T)}{1/T} = T-t_1^* \Rightarrow t_1^* =T/2 \qquad [1b]$$ and $$[2a] \rightarrow -\frac 1{T}\frac 2T <0 \qquad [2b]$$ so it will indeed be a maximum (likewise for player 2).

Player $1$ will model $t_2$ as a Uniform, if he has no other information on it except its range. Well, does he know something more? By the set of common knowledge, he knows that player $2$ will also try to maximize from her part, and that she will model the timing of the light-flash as a uniform. So player $1$ knows that player $2$ will end up looking at the conditions

$$t_2^* = \frac {1-F_1(t_2^*)}{f_1(t_2^*)},\;\; [3] \qquad -\frac 1{T}\Big(2f_1(t^*_2)+t^*_2f'_1(t^*_2)\Big) <0 \qquad [4]$$

Does this knowledge permit player $1$ to infer something about the distribution of $t_2$? No, because $[3]$ and $[4]$ contain abstract information about how $t_2$ will be determined as a function of what, according to player $2$, is the distribution of $t_1$. They do not help player 2 in any way in relation to the distribution of $t_2$.

So we conclude, that given the assumed set of common knowledge, both will model each other distributions as Uniforms. Hmmm... does this tell us that indeed the solution of the game will be $(t_1^*,t_2^*) =? (T/2,\,T/2)$?
It appears that since both can essentially predict the choice of the other, they will then have an incentive to push the button earlier. It does not take much thinking to realize that this line of thinking would lead us to conclude that they would both hit the button at time $0$, thus a.s. "guaranteeing" that they will both lose, which they also know, because they both treat the light-flash as a continuous rv, and so the probability of the light flash occurring exactly at time zero, is zero. But this is a strictly dominated strategy and the players won't select it.

Does it pay to randomize over the interval $[0,T/2]$? Well, no, because probability of wining won't be at a maximum. So we conclude that indeed the solution to this game is

$$(t_1^*,t_2^*) = (T/2,\,T/2)$$

even though the players know a priori what each will play.It is not difficult to calculate that in this case the expected payoffs will be $$ (v_1,v_2) = (1/4,\; 1/4)$$ This pure strategy profile will be a rationalizible equilibrium if it is not strictly dominated by a mixed strategy.

$\endgroup$
  • $\begingroup$ This doesn't make sense to me. As you point out, unilateral deviation from $(T/2,T/2)$ to $(T/2-\varepsilon,T/2)$ is beneficial to player $1$. Hence, by definition, $(T/2,T/2)$ cannot be a Nash equilibrium. $\endgroup$ – Keep these mind Nov 17 '13 at 11:35
  • $\begingroup$ @Transmission from Did I characterize this as a Nash Equilibrium? No. $\endgroup$ – Alecos Papadopoulos Nov 17 '13 at 16:06
  • $\begingroup$ Well, you did call it "the solution" and "[t]his pure strategy equilibrium"... but it is neither. (Note that not every game must have a pure-strategy Nash equilibrium, so you cannot find one by elimination of the other pure-strategy contenders.) $\endgroup$ – Keep these mind Nov 17 '13 at 16:27
  • $\begingroup$ @ Transmission from These are all basic facts on games. But not every equilibrium is Nash. Nash equilibrium is a very strong concept, and in most cases it is a good guide to select equilibria. But players are rational, they are not constrained to implement an equilibrium only if it is Nash. So each player knows that the other player will think exactly the same, and that this chain of reasoning will lead them both to select pushing the button at zero, where they lose a.s. This creates the logical possibility that they may, after all, stick to this equilibrium. $\endgroup$ – Alecos Papadopoulos Nov 17 '13 at 16:50
  • $\begingroup$ I see. I would think that $(T/2,T/2)$ can't be rationalizable, because it doesn't appear to be an equilibrium in beliefs. Each player would have to believe that the other player will play $>T/2$, in which case it would be rational to move a little higher yourself. But I must admit that I'm a bit uncertain on how this works out in the continuous case, because I'm not sure about the format of the beliefs in that case. Happy to revert my downvote. Perhaps replace "This pure strategy equilibrium will be an equilibrium" by "This pure strategy profile will be a rationalizable equilibrium". $\endgroup$ – Keep these mind Nov 17 '13 at 17:47
1
$\begingroup$

Let me give a simple example of a symmetric mixed Nash equilibrium, where players are constrained to mix uniformly.

I assume that time is finite. Without loss of generality, consider the time interval $[0,1]$. Suppose we have two players, we are player 1, and we assume both players use a symmetric mixing strategy. The strategy is given by the cdf $G(x)=\frac{x}{1-a}$, i.e., uniform in $[a,1]$, $1> a \ge 0$. We assume that the only free choice is $a\in[0,1)$ (in particular, a player cannot deviate to another cdf $H(x)\neq G(x)$ for some $a$).

For simplicity, we further assume the light turning on is distributed $U[0,1]$ (i.e., with density $f(x)=1$ on $[0,1]$).

The expected payoff for us (player 1), given these assumptions, is (we only get a payoff of 1 if, when hitting the button, the light is on and the other player has not yet hit the button, or if the other player hits the button before the light turns on and we hit it after, otherwise 0) \begin{equation*} u=\int_a^1 \underbrace{F(x)}_{\text{Pr light comes on at $t\le x$ }} \underbrace{g(x)}_{\text{We hit the button at $x$ }} \underbrace{(1-G(x))}_{\text{Pr player 2 hits button at $t>x$ }} \underbrace{1}_{\text{we win 1}} dx \\ +\int_a^1 \underbrace{G(x)}_{\text{Pr player 2 hits button at $t\le x$ }} \underbrace{f(x)}_{\text{Light turns on at $x$ }} \underbrace{(1-G(x))}_{\text{Pr we hit the button at $t\ge x$ }} 1~ dx \\ =\int_a^1 xg(x)(1-G(x))dx+\int_0^a G(x)(1-G(x))dx\\ =2\int_a^1 x\frac{1}{1-a}(1-\frac{x}{1-a}) dx=2\int_a^1 G(x)(1-G(x)) dx\\ =2\int_a^1 G(x)-G(x)^2 dx. \end{equation*} We want to find the $a$ that maximizes the expected return given both players mix with density $g(x)$. Put differently, we want to find the $a$ such that strategy $g(x)$ is a best response to itself, which by definition constitutes a symmetric Nash equilibrium. Hence, by Leibniz' integral rule, the first order condition is \begin{equation*} \frac{\partial u}{\partial a}=2\int_a^1 \frac{x}{(1-a)^2}-2\frac{x^2}{(1-a)^3} dx-2G(a)+2G(a)^2\\ =\frac{1+a^2}{(1-a)^2}-\frac{4}{3}\frac{1-a^3}{(1-a)^3} -2\frac{a}{1-a}. \end{equation*} Now, $u'\to -\infty$ as $a\to 1$, and indeed $u'<0~\forall a\in[0,1)$, as can be seen here. Therefore, the corner solution $a=0$ is optimal, since the marginal utility as $a$ increases is negative.

We can repeat the whole exercise for cdf $J(x)=\frac{x}{b},~b\in(0,1]$, i.e., uniform mixing on $[0,b]$. The marginal utility is then always positive, and again the corner solution $b=1$ is optimal (i.e., again the widest possible interval).

This is a restrictive example, since I forced both players to play with a density of specific form, but at least in the class of symmetric uniform equilibria, putting positive density on the widest possible interval appears to be optimal. Perhaps this generalizes to other classes as well. Not imposing a functional form for the mixing density makes the problem quite hard, and assuming other specific forms is possible, but more tedious. Taking another density for light turning on is similarly possible. But, in the absence of any information about light turning on, the principle of insufficient reason calls for the assumption of a uniform distribution.

$\endgroup$
  • $\begingroup$ The cdf of the uniform distribution on $[0,a]$ is $x/a$, not $x/(1-a)$, but I'm sure the calculation can be redone with the correct value. $\endgroup$ – Will Nelson Nov 12 '13 at 21:31
  • $\begingroup$ Thanks, that's right. There was also another error. It now includes two cases of uniform cdfs, where the upper of lower threshold can be chosen, and for both the equilibrium is that both players mix with $U[0,1]$, i.e., the widest interval. $\endgroup$ – Nameless Nov 13 '13 at 1:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.