0
$\begingroup$

The choice engineering competition describes a game where a user makes 100 sequential choices between two alternatives. Opposing the user is an engineer whose goal is to allocate a total of 25 binary rewards to each of the alternatives, deciding on the allocation of the next trial based on the current hisoty of choices. My question is how many different engineers exist?

(The goal of the engineer is to create such an allocation that will drive the user to choose one of the alternatives as many times as possible; how the engineer can be successful in this task depends on the model the engineer has on the user's behavior, and is not relevant for the current question).


With some more elaborative explanation - in each of the 100 trials, right before the user chooses one of the two alternatives, the engineer needs to decide on the reward for the two alternatives. So, in each trial, the engineer can choose to allocate a reward to the first alternative only, to the second alternative only, to non, or to both {(1,0), (0,1), (0,0), (1,1)}. Following this allocation (which is unknown to the user) the user chooses an alternative and if it had a reward allocated to it, the user accumulates one more reward (and otherwise does not), without learning about the allocation of the other alternative. The engineer is constrained by having to allocate:

  1. No more than 25 rewards for both alternatives - so if in trial t, 25 rewards have been allocated to one of the alternatives, the engineer has no degrees of freedom in regards to this alternative in future trials (there are no more decisions to make for this alternative as there are no more rewards for allocation). If in trial t, 25 rewards have been allocated to both alternatives there are no more decisions for the engineer to take (there are no more rewards to allocate in either of the alternatives, in spite of the user's interaction with the game that will continue until the 100'th trial).
  2. Not less than 25 rewards - so if it's trial 80 and the engineer allocated only 5 out of the 25 rewards for one of the alternatives, there are 20 remaining rewards that needs to be allocated in 20 trials and thus no more decisions to make regarding this alternative (a reward must be allocated for this alternative in all future trials).

The engineer decides on the allocation of the next trial based on the current history of the game, basing its allocation decisions on the following factors:

  1. t (1..100) - current trial number - the engineer can make different allocation decisions depending on what stage it is in the game.
  2. (r1, r2) (0..25, 0..25) - the number of remaining rewards to each of the alternatives.
  3. User's choices - the engineer can base its allocation in the current trial on the specific history of choices the current user made. The current history consists of the sequence of binary decisions the user made (in trial t the user could have made 2^t different choice sequences; regardless of the engineer's allocations).

Taken together, an engineer is a function that maps (r1, r2, t, choices) to a valid reward allocation, where:

  1. r1 are the remaining rewards for alternative 1.
  2. r2 are the remaining rewards for alternative 2.
  3. t is the current trial number
  4. choices - is a binary sequence of t-1 previous choices
  5. and a its output - a valid reward, is one of {(1,0), (0,1), (0,0), (1,1)} under the engineer's constraints.

I want to calculate - how many such different unique functions exist?


What have I tried

What I have in mind is a recursive solution - but I don't know if it makes sense (whether I'm counting the right things and counting them correctly) or if there is a more elegant closed-form solution.

I figure that the number of different enginners for (r1, r2, t) is the sum of engineers in trial t+1 that either allocated or did not allocate a reward to either of the alternatives and this should be multiplied (but I'm not sure) in the different possible histories (a sequence of t binary choices). So a number that Counts Engineers:

ce(r1, r2, t) =  2^t*(ce(r1, r2, t+1) + ce(r1-1, r2, t+1) + ce(r1, r2-1, t+1) + ce(r1-1, r2-1, t+1))

With an appropriate stopping condition - ce(0,0,t) = 1; ce(0,0,100) = 1; and additional slightly more complex rules on what to do when just one alternative is exhausted or that all rewards must be allocated from now on - I put a testable implementation in this colab notebook (or repl.it).

I would appreciate any ideas, comments, and suggestions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.