I've been struggling with proving a conjecture concerning order statistics of Brownian motions for a while. The conjecture I'm looking to prove is the following: (I have run Monte Carlo simulations that confirm the conjecture.)

Let $(q_1(t), …, q_n(t))$ be a vector of independent Brownian motions with $q_i(0) = 0$ for all $i$. Let $T > 0$. Each $q_i$ represents an object in a game, and each of $J < n$ players in the game can pick exactly one object $i$ at any time $t \in [0, T]$. Whenever a player picks an object, he picks the one that currently has the highest value amongst those that have not been picked before. A player's payoff is the value of the object at the time he picks it. Let $x_j(t_j; t_1, …, t_{j-1})$ denote the expected payoff (expectation taken at time 0) from picking at time $t_j$, given that players $1, …, j-1$ will pick at times $t_1, …, t_{j-1}$. I want to show that $x_j(t_j; t_1, …, t_{j-1})$ is decreasing in $t_1, …, t_{j-1}$.

I will need this for an economic theory paper I'm writing, and would be very grateful for any help!

Some things that I already thought through:

  • I have already shown that $x_j(t_j; t_1, …, t_{j-1})$ is increasing in $t$ and jointly continuous in all arguments.
  • The case $j=2$ is quite tractable, and for the case $j = 3$ I have the intuition on how to prove it. That intuition, however, doesn't extend to the general case.

The strategy of the other $n-1$ players can be viewed as a single adversary trying to minimize the payoff of the $n$th player. Picking the highest unpicked object is optimal for that adversary by coupling.

If $t_{i-1} \le t_i' \lt t_i$ then picking at time $t_i'$ instead of $t_i$ does an imperfect job of choosing the unpicked object which will be highest at time $t_i$. You can view picking at $t_i'$ as sometimes playing optimally at time $t_i$, and sometimes choosing a lower object at time $t_i$.

If you want to consider decreasing $t_i'$ past $t_{i-1}$ then you can view this as decreasing $t_i'$ to $t_{i-1}$, then replacing $t_{i-1}$ with a smaller $t_{i-1}'$.

  • $\begingroup$ Thanks a lot! However, either I misunderstand your reply, or you misunderstood my question. I'm interested the payoff to player $j$ holding fixed $t_j$, but varying $t_1, …, t_{j-1}$. (I'm only interested in the case $t_1\leq…\leq t_j$.) In case I misunderstood your reply, then it's probably the first two lines. $\endgroup$ – Sandro Jul 19 '14 at 6:07
  • $\begingroup$ @Sandro: I assumed $j=n$ because later players don't affect player $j$ so we might as well assume player $j$ is the last player. What don't you understand about the first two lines of my answer? $\endgroup$ – Douglas Zare Jul 19 '14 at 6:26
  • $\begingroup$ You use $i$ and $j$ interchangeably, right? I guess the stumbling block is the coupling (of I know the definition, but don't have experience with). Also, I'm not sure whether $j=n$ is w.l.o.g. (but that might be because I don't yet quite understand your proof.) If $j=n$ then any gain to the adversary is a loss to player $j$. If $j<n$, then a gain to the adversary can also be due to him picking the player who will be ranked second-to-worst rather than worst at $t_j$, which will not decrease player $j$'s payoff. $\endgroup$ – Sandro Jul 19 '14 at 7:59
  • $\begingroup$ @Sandro: No, I don't use $i$ and $j$ interchangeably. $i$ is an index of an opponent's choice. $\endgroup$ – Douglas Zare Jul 19 '14 at 9:12
  • $\begingroup$ Could you say which BMs you couple, and what coupling you choose? $\endgroup$ – Sandro Jul 19 '14 at 19:22

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.