Timeline for Painting $n$ balls from $2n$ balls red, and guessing which ball is red, game
Current License: CC BY-SA 3.0
43 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 30, 2016 at 5:46 | history | edited | Irvan | CC BY-SA 3.0 |
deleted 282 characters in body
|
| Nov 6, 2014 at 11:10 | vote | accept | Irvan | ||
| S Nov 1, 2014 at 8:49 | history | bounty ended | Irvan | ||
| S Nov 1, 2014 at 8:49 | history | notice removed | Irvan | ||
| Nov 1, 2014 at 2:45 | answer | added | Timothy Chow | timeline score: 8 | |
| Oct 28, 2014 at 9:14 | history | edited | Irvan | CC BY-SA 3.0 |
added 61 characters in body
|
| Oct 28, 2014 at 9:09 | history | edited | Irvan | CC BY-SA 3.0 |
added 61 characters in body
|
| Oct 27, 2014 at 19:14 | answer | added | domotorp | timeline score: 3 | |
| Oct 27, 2014 at 17:27 | comment | added | domotorp | Let us continue this discussion in chat. | |
| Oct 26, 2014 at 18:54 | comment | added | Irvan | Can you clarify? I checked wiki just now and I think I'm using Jensen's inequality in the correct direction ($f(E(x)) \le E(f(x))$). Here I just used $f(x) = (1/3)^x$. | |
| Oct 26, 2014 at 16:32 | comment | added | domotorp | Now I'm starting to understand the difficulties - this is a very nice problem! I've managed to calculate that X(r=1,b=1,e)=1-x/2, but this seems pretty useless as it does not have the main feature of Lucy picking an interesting strategy. | |
| Oct 26, 2014 at 14:18 | comment | added | Irvan | @domotorp: On second comment: That's correct. I thought parametrizing the thing make it more intractable -- if the number of balls were parametrized, I would not be able to prove the $O(\log \log n)$ lower bound, for example. However, if a general solution exists for the parametrized version, it would be more than welcome! However I am not even able to find an optimal strategy for very small values of $n$ (e.g., $n=2$). | |
| Oct 26, 2014 at 14:16 | comment | added | Irvan | @domotorp: On first comment: Yes, the balls are numbered -- ball number $i$ will be the $i$-th ball offered to Alice. However, she has to decide the colors of all balls before Alice is offered any ball (so she cannot change her strategy depending on whether or not Alice takes the first ball, for example). It can be assumed that they pick their strategies independently -- in particular for it to be a Nash equilibrium, no matter which strategy Alice decides to execute, the expected number of balls opened would still be the same. | |
| Oct 26, 2014 at 14:01 | comment | added | domotorp | I also think that the problem could become more tractable with the introduction of more parameters. Let say X(r,b,e) be the average number of balls that Alice has to pick to find a red ball from r red and b blue balls with a failure of chance e allowed. So your question in this notation is to determine X(n,n,1/n). First we should determine X(1,1,e) for all possible values of e and hope to find a recursion. This should not be hard but some things have to be clarified first. | |
| Oct 26, 2014 at 13:55 | comment | added | domotorp | I would like to have some things clarified in the problem. Does Lucy know which ball is which, so can she decide each time whether she gives a red or white ball? Do they pick their strategies independently? If yes, that means that Alice picks at most the given expected number of balls in average against ANY sequence, otherwise it would not be a Nash Equilibrium, right? | |
| S Oct 25, 2014 at 9:24 | history | bounty started | Irvan | ||
| S Oct 25, 2014 at 9:24 | history | notice added | Irvan | Draw attention | |
| Oct 23, 2014 at 13:03 | history | edited | Irvan | CC BY-SA 3.0 |
deleted 23 characters in body
|
| Oct 23, 2014 at 12:18 | history | edited | Irvan | CC BY-SA 3.0 |
added 76 characters in body
|
| Oct 23, 2014 at 10:45 | history | edited | Irvan | CC BY-SA 3.0 |
added 153 characters in body
|
| Oct 23, 2014 at 10:42 | comment | added | Irvan | I clarified a particular behavior of Lucy (it was not entirely clear before that she would not cooperate with Alice in any way). In simpler terms, Lucy's goal is the complete opposite of Alice's. | |
| Oct 23, 2014 at 10:39 | history | edited | Irvan | CC BY-SA 3.0 |
added 153 characters in body
|
| Oct 23, 2014 at 5:54 | history | edited | Irvan | CC BY-SA 3.0 |
added 5 characters in body
|
| Oct 23, 2014 at 5:51 | comment | added | Włodzimierz Holsztyński | @Irvan, thank you. I would rewrite (edit) the question. However people seem to understand it, and even myself I do (perhaps :-). | |
| Oct 23, 2014 at 5:46 | history | edited | Irvan | CC BY-SA 3.0 |
added 11 characters in body
|
| Oct 23, 2014 at 5:43 | comment | added | Irvan | I think there are already too many views and changing this may make things a little confusing. I changed a majority of "she" into Alice instead. P.s: I was following the same notation as found in Satlzer's book when he is talking about distributed systems (Lucy or other extensions of Lucifer acts as an adversary for Alice). I will keep this in mind for future questions. | |
| Oct 23, 2014 at 5:40 | comment | added | Włodzimierz Holsztyński | Would you mind substituting Adam for Alice? This introducing a male (in addition to a female) would induce SHE and HE (instead of she and she). | |
| Oct 23, 2014 at 5:32 | history | edited | Irvan | CC BY-SA 3.0 |
added 2 characters in body
|
| Oct 23, 2014 at 5:01 | history | edited | Irvan | CC BY-SA 3.0 |
added 322 characters in body
|
| Oct 23, 2014 at 4:51 | history | edited | Irvan | CC BY-SA 3.0 |
added 368 characters in body
|
| Oct 23, 2014 at 4:37 | comment | added | Irvan | That's a necessary condition, but not sufficient. In addition to the condition, we also want the strategy to minimize the expected number of balls taken. So, if we use Yao's principle, $E[\text{performance}]$ would be the expected number of balls taken, subject to the condition you mentioned. | |
| Oct 22, 2014 at 17:53 | answer | added | usul | timeline score: 1 | |
| Oct 22, 2014 at 17:02 | comment | added | usul | Can you clarify if this is correct? You want a strategy for Alice such that, for every permutation of the boxes, $\Pr[$find a red$] \geq 1-1/n$. | |
| Oct 22, 2014 at 15:37 | history | edited | Irvan | CC BY-SA 3.0 |
added 9 characters in body
|
| Oct 22, 2014 at 15:11 | history | edited | Irvan | CC BY-SA 3.0 |
added 8 characters in body
|
| Oct 22, 2014 at 14:40 | history | edited | Irvan | CC BY-SA 3.0 |
edited body
|
| Oct 22, 2014 at 14:30 | history | edited | Irvan | CC BY-SA 3.0 |
edited title
|
| Oct 22, 2014 at 14:23 | comment | added | Irvan | Good point. I've edited it and the answer below. | |
| Oct 22, 2014 at 14:20 | history | edited | Irvan | CC BY-SA 3.0 |
changed ball and bins to red paint.
|
| Oct 22, 2014 at 13:39 | answer | added | Brendan McKay | timeline score: 1 | |
| Oct 22, 2014 at 13:04 | comment | added | Per Alexandersson | Maybe you can change terminology a bit: There are $2n$ distinct (numbered) items. Lucy paints half of them red. Alice wants to find a red object. Usually, a box can contain arbitrary many balls, but for 0 or 1 balls only, it is easier to use color as a marker. | |
| Oct 22, 2014 at 11:12 | review | First posts | |||
| Oct 22, 2014 at 11:27 | |||||
| Oct 22, 2014 at 11:11 | history | asked | Irvan | CC BY-SA 3.0 |