p**e 发帖数: 41 | 1 A company has a competition to win a car. Each contestant needs to pick a
positive interger. If there's at least one unique choice, the person who
made the smallest unique choice wins the car. If there are no unique
choices, the company keeps the car and there's no repeat of the competition.
It turns out that there are only three contestants, and you are one of
them. Everyone knows before picking their numbers that there are only 3
contestants.
How should you make your choice? |
p**e 发帖数: 41 | 2 还有一道, 不难, 但是做出来不知道对不对, 因为result不简洁
Consider a set SIGMA with N distinct members, and a function f defined on
SIGMA tha takes the values 0 or 1 such that (1/N)* sum_{x belongs to SIGMA}
f(x) = p.
For a subset S belonging to SIGMA of size n, define the sample proportion:
q:= q(S) = (1/n)* sum{x belongs to S} f(x)
If each subset of size n is chosen with equal probability, calculate the
expectation and standard deviation of the r.v. q
competition.
【在 p**e 的大作中提到】 : A company has a competition to win a car. Each contestant needs to pick a : positive interger. If there's at least one unique choice, the person who : made the smallest unique choice wins the car. If there are no unique : choices, the company keeps the car and there's no repeat of the competition. : It turns out that there are only three contestants, and you are one of : them. Everyone knows before picking their numbers that there are only 3 : contestants. : How should you make your choice?
|
n****e 发帖数: 629 | 3 Collaborate with another guy and declare that one of you will pick 1 and the
other one will pick two. Whatever the outcome is, you two will split the
prize. In this way you are guaranteed to win 1/2 of the grand prize.
competition.
【在 p**e 的大作中提到】 : A company has a competition to win a car. Each contestant needs to pick a : positive interger. If there's at least one unique choice, the person who : made the smallest unique choice wins the car. If there are no unique : choices, the company keeps the car and there's no repeat of the competition. : It turns out that there are only three contestants, and you are one of : them. Everyone knows before picking their numbers that there are only 3 : contestants. : How should you make your choice?
|
a****9 发帖数: 418 | 4 my answer:
if the optimal strategy is to pick number i at prob p_i
denote q_i = p_1+...+p_i
max p_i*(1-q_i)*(1-q_i) for i = 1,2..
thus
p_1 = 1/3
p_2 = 2/9
...
p_i = (2/3)^(i-1)*(1/3)
competition.
【在 p**e 的大作中提到】 : A company has a competition to win a car. Each contestant needs to pick a : positive interger. If there's at least one unique choice, the person who : made the smallest unique choice wins the car. If there are no unique : choices, the company keeps the car and there's no repeat of the competition. : It turns out that there are only three contestants, and you are one of : them. Everyone knows before picking their numbers that there are only 3 : contestants. : How should you make your choice?
|
n****e 发帖数: 629 | 5 What if the third person always chooses 1 now?
His probability of winning is:
1*(1-1/3)*(1-1/3) = 4/9 > 1/3
Clearly this is not an optimal strategy.
【在 a****9 的大作中提到】 : my answer: : if the optimal strategy is to pick number i at prob p_i : denote q_i = p_1+...+p_i : max p_i*(1-q_i)*(1-q_i) for i = 1,2.. : thus : p_1 = 1/3 : p_2 = 2/9 : ... : p_i = (2/3)^(i-1)*(1/3) :
|
a****9 发帖数: 418 | 6 这个Game的nash 均衡就应该是大家都永远选1阿好像
那没的搞
【在 n****e 的大作中提到】 : What if the third person always chooses 1 now? : His probability of winning is: : 1*(1-1/3)*(1-1/3) = 4/9 > 1/3 : Clearly this is not an optimal strategy.
|
n******r 发帖数: 1247 | 7 this is not NE
【在 a****9 的大作中提到】 : 这个Game的nash 均衡就应该是大家都永远选1阿好像 : 那没的搞
|
w*****e 发帖数: 197 | 8 I think the best strategy is to choose number i with prob
pow( 2, -i ). It can be shown that in this case, each player
has a winning prob of 2/7.
And if you always pick 1, you winning chance is just 1/4, which
is dominated by the best one.
competition.
【在 p**e 的大作中提到】 : A company has a competition to win a car. Each contestant needs to pick a : positive interger. If there's at least one unique choice, the person who : made the smallest unique choice wins the car. If there are no unique : choices, the company keeps the car and there's no repeat of the competition. : It turns out that there are only three contestants, and you are one of : them. Everyone knows before picking their numbers that there are only 3 : contestants. : How should you make your choice?
|
n****e 发帖数: 629 | 9 Hmm. Now if you always pick 2 you'll have a winning probability:
(1/2)*(1/2) + (1-1/2-1/4)*(1-1/2-1/4) = 5/16 > 2/7
Sorry this is still not optimal.
【在 w*****e 的大作中提到】 : I think the best strategy is to choose number i with prob : pow( 2, -i ). It can be shown that in this case, each player : has a winning prob of 2/7. : And if you always pick 1, you winning chance is just 1/4, which : is dominated by the best one. : : competition.
|
l**********t 发帖数: 5754 | 10 If there were an "optimal" strategy that leads to a specific integer, all 3
players will follow the same strategy and get the same integer....
it is about "what the other guys know about what I know about what the
others know..."... the workable solution depends on the level of knowledge. |
n******r 发帖数: 1247 | 11 No one says the optimal strategy has to lead to a specific integer
3
【在 l**********t 的大作中提到】 : If there were an "optimal" strategy that leads to a specific integer, all 3 : players will follow the same strategy and get the same integer.... : it is about "what the other guys know about what I know about what the : others know..."... the workable solution depends on the level of knowledge.
|
n******r 发帖数: 1247 | 12 no assumptions about the other two? Don't see the logic here
【在 n****e 的大作中提到】 : Hmm. Now if you always pick 2 you'll have a winning probability: : (1/2)*(1/2) + (1-1/2-1/4)*(1-1/2-1/4) = 5/16 > 2/7 : Sorry this is still not optimal.
|
a****9 发帖数: 418 | 13 我搜了一下,这个其实叫Unique bid auction
这里有一篇paper
www.stat.purdue.edu/~mdw/papers/paper010full.pdf
paper里没有给出exact opt solution
competition.
【在 p**e 的大作中提到】 : A company has a competition to win a car. Each contestant needs to pick a : positive interger. If there's at least one unique choice, the person who : made the smallest unique choice wins the car. If there are no unique : choices, the company keeps the car and there's no repeat of the competition. : It turns out that there are only three contestants, and you are one of : them. Everyone knows before picking their numbers that there are only 3 : contestants. : How should you make your choice?
|
p*****k 发帖数: 318 | 14 if this game is only played once, i'm with the frequentist view:
the problem seems more of a behavior or psychological question
(or the interviewer is looking for answers like native's)
if the game is repeated, you can find the solution on
mathproblems.info, #199.
wushine's answer is to a related problem: #198.
also some discussions here:
http://wilmott.com/messageview.cfm?catid=26&threadid=67944 |