Let's say I'm playing a game that works likes this: I have n bowls that are each filled with a different number of marbles, and I know how many marbles are in each bowl. At each round, the dealer goes to each bowl one at a time, and decides to add or remove some number of marbles from that bowl. He decides how much to add or remove from each bowl based on a set of rules that only take into account the number of marbles currently in each bowl, though I have no idea what those rules are. I am able to see the changes he makes. After he has made his changes, I have to make a decision: I can either have him give me a dollar for each marble in each of the bowls, or I can have him undo all the changes he just made to the bowls. After I have made my decision and the dealer has either paid me or undid his changes to the number of marbles in each bowl, I begin the next round with the bowls as they currently are. My goal is to maximize the average amount of dollars I get per round.

My question is, what's the optimal strategy for playing this game?

  • $\begingroup$ I would engage this with Q-learning and let the computer tell me. $\endgroup$ – EngrStudent Sep 14 '16 at 19:02
  • 1
    $\begingroup$ I only have a very basic understanding of Q-learning, but it seems to me that given there's no upper bound on the number of marbles in a bowl and that n may be very large, there would be way too many states for Q-learning to work $\endgroup$ – ricky Sep 14 '16 at 19:35
  • $\begingroup$ I was presuming physicality, so the marble count might be in the realm of chinese checkers or the stones of backgammon. $\endgroup$ – EngrStudent Sep 14 '16 at 19:58
  • $\begingroup$ this problem is actually just a simple analogy for non-physical problem I'm dealing with $\endgroup$ – ricky Sep 14 '16 at 20:00
  • $\begingroup$ I must be missing something, because the game appears to reduce to this choice: either you are paid an amount equal to the total number of marbles (and the state of the game can change for the next round) or you are paid nothing (and the state of the game does not change). Isn't the optimal strategy obvious? You cannot possibly make any money until you choose to be paid! The only way in which the game might be more complex than this would be if the dealer's strategy were non-deterministic. Perhaps you could tell us a little more about the nature of this strategy, then. $\endgroup$ – whuber Sep 15 '16 at 15:10

The dealer has enough power to make any strategy wortheless. I would argue that this falls under the no free lunch theorem.

As a small reasoning by the absurd, let's suppose that you have a strategy X, that is supposed to be optimal, and I'm the dealer. Because I'm the dealer I've thought long and hard about the problem and found that same strategy X. I start by removing every marble from every bowl.

Now, you follow your optimal strategy. But as I know that's the optimal one, I will do my utmost to fight it. Thus, if you do the moves that someone playing the optimal strategy does, I will keep you at 0 marbles all the time (or oscillate between 0 and 1 if I'm forced to add/remove). If you don't, then i'll choose to add a lot of marbles all the time, because I like people that disregard strategy and play less than perfect.

Thus non-optimal strategies are better than the optimal strategy, which is a contradiction. Hence there is no optimal strategy.

Edit : With the update to the question : the dealer now has a pre-determined f(number of marbles) strategy. Yes, there is an optimal strategy for the player : always take.

If you don't take, the number of marbles stays the same, the dealer will do the exact same thing, and you've just done a 0-round, which is always worst case (you can't have negative rounds), so you lost on the average $/round.

  • $\begingroup$ What if the dealer's behavior at each round is determined entirely by the number of marbles in each bowl? So there's some function that maps the state of the bowls to the dealer's behavior, and it doesn't change, though I still don't know what that function is. Could there be an optimal strategy then? $\endgroup$ – ricky Sep 14 '16 at 18:40
  • $\begingroup$ Just because it is fixed, and you don't know it, the above still applies. What if it was fixed to that? $\endgroup$ – EngrStudent Sep 14 '16 at 19:11
  • $\begingroup$ The dealer couldn't use that strategy because he wouldn't be allowed to take my strategy into account, he would be forced to only take the combined states of the bowls into account $\endgroup$ – ricky Sep 14 '16 at 19:26
  • $\begingroup$ @BobJones - he doesn't have to know your particular strategy, just the optimal strategy. If you happen to use the allegedly optimal strategy, then it is the one he works against. I think this might work in practice a little like Warren Buffets delight in non-transitive dice. $\endgroup$ – EngrStudent Sep 14 '16 at 20:00
  • $\begingroup$ @BobJones Updated answer for the updated question $\endgroup$ – Jenkar Sep 15 '16 at 7:24

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.