Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Hallo all, I would like some insight on this one:

There are two players A and B each having a countable set of naturals lets say Sa and Sb. Initially Sa has cardinality n and Sb has cardinality 0 (empty set) and player B does not know the elements on Sa.

The goal is for player B to "take" all the elements in Sa (or at least as much as he can) by repeatedly "asking" player A if he has an element and place them in Sb. Player A responds if the element asked is “near” an element on his set. Therefore player A has a rule like “if the distance of input with one or more of my elements is less than x then give it”. Player A always follows this rule.

Player B may have some knowledge on the elements of Sa (like the max or min number in the set) therefore he could make “smart” questions or may have no knowledge therefore he asks randomly. If player B does not find much elements after a number of questions, he loses. If player A responds with “I have no more elements” then player B wins.

I would like to discuss if Game Theory is appropriate for approaching this problem. Thanks in advance

share|improve this question
    
I'm not sure where the set theory part comes in... –  Asaf Karagila Jul 20 '11 at 9:38
    
Yes you're right its not related to set theory. I removed the tag –  palahniuk Jul 20 '11 at 10:23
add comment

1 Answer

First of all, $S_a,S_b$ are finite at each step as I understand from your description - so you do not need to use the word countable whic also relates to some infinite sets.

Let us assume that $x>0$ is predefined before the game starts. If $B$ knows $n,\max S_a$ and $\min S_a$ or at least $n$ and upper (lower) bound $C$ ($D$) on $\max S_a$ ($\min S_a$) then the naive strategy for $B$ is to make an $x$-grid on $[C,D]$ and repeatedly ask if $C+\frac{kx}{D-C}$ belongs to $S_a$ or not for $$k = 0,1,...,N=\lfloor\frac{D-C}{x}\rfloor+1.$$

In this case it's sufficient for him to make $Nn$ turns.

Even if he does know only $n$ then he can make a grid on $\mathbb R$ and starting from $0$ ask $A$ about $kx$ for $k = 0,1,-1,2,-2,...$ in exactly this order asking this question $n-m$ times for each value of $k$ where $m$ is the number of elements $B$ already discovered. This procedure will always finish in a finite time, though only $A$ knows when, $B$ does not.

I would not say that it is a game-theoretical problem since for the strict solution it is the same like $A$ answers randomly if there are several elements $x$-close to the element $B$ asked about.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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