• Secret Santa Strategies

    From leflynn@21:1/5 to All on Wed Nov 18 11:35:02 2020
    Seven greedy smart people are participating in a Yankee Swap.
    Rules as given here:
    Each participant brings a wrapped gift and places it with the others.
    Participants are given random letters from A to G, and they select and unwrap gifts from the pile in alphabetical order.
    The person who receives A will pick a gift from the pile and open it for all to see.
    The person who receives B then chooses a gift and opens it, and then must decide whether to keep it or swap it for the first player’s gift.
    This continues -- each person in order selects a present, opens it and decides whether to keep it or swap it for any other gift someone has already opened.
    Opening of gifts and swapping takes place until all the presents have been chosen. Finally, the person (A) who picked first gets to choose from all the gifts or keep what he/she has already received.

    Notice, these are rules for a very simplified version as there is at most one swap per round.

    Case 1. All participants will evaluate/rank the gifts the same once they are opened and there are no ties. Except for your gift, you do not know what the other gifts are (and how they will rank) until they are opened. All gifts are identically wrapped,
    that is they are indistinguishable until opened. What are the strategies for each player based on their selection positions?

    Case 2. Similar to Case 1 but the gifts are wrapped uniquely so each participant knows which one they brought. Case 2.a. You may not pick your own gift to open unless you are the last picker. Case 2.b. You may pick your own to open. What are the
    strategies for each player based on their selection positions?

    L. Flynn

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Edward Murphy@21:1/5 to leflynn on Sun Nov 22 10:30:41 2020
    On 11/18/2020 11:35 AM, leflynn wrote:

    Seven greedy smart people are participating in a Yankee Swap.
    Rules as given here:
    Each participant brings a wrapped gift and places it with the others.
    Participants are given random letters from A to G, and they select and unwrap gifts from the pile in alphabetical order.
    The person who receives A will pick a gift from the pile and open it for all to see.
    The person who receives B then chooses a gift and opens it, and then must decide whether to keep it or swap it for the first player’s gift.
    This continues -- each person in order selects a present, opens it and decides whether to keep it or swap it for any other gift someone has already opened.
    Opening of gifts and swapping takes place until all the presents have been chosen. Finally, the person (A) who picked first gets to choose from all the gifts or keep what he/she has already received.

    Notice, these are rules for a very simplified version as there is at most one swap per round.

    Case 1. All participants will evaluate/rank the gifts the same once they are opened and there are no ties. Except for your gift, you do not know what the other gifts are (and how they will rank) until they are opened. All gifts are identically wrapped,
    that is they are indistinguishable until opened. What are the strategies for each player based on their selection positions?

    Assumption: The selection of what (and how valuable) gifts to bring in
    the first place is essentially random.

    Start at the end and go backward:

    A, knowing the rank of all seven gifts and able to pick any of them,
    will pick the most valuable gift (call it G1).

    G, knowing the rank of all seven gifts and able to pick any of them,
    will pick the second most valuable gift (G2), i.e. the most valuable
    gift that A won't pick afterward.

    F is where it starts to get interesting. They know the relative rank of
    six gifts (call them Ga through Gf, where Ga is the most valuable), but
    the seventh (G*) is equally likely to be G1 or G2 or etc.

    * Regardless of strategy, the best they can get is G3, i.e. the most
    valuable gift that neither G nor A will pick afterward.

    * If they pick Gc, then expected outcomes are (G3 G3 G3 G3 G4 G4 G4).

    * There's no point picking Gd or lower (guaranteed less valuable
    than Gc).

    * There's apparently no point picking Ga or Gb either. In either case,
    their expected outcomes after G and A are (G3 G3 G3 G4 G5 G6 G7).

    So F probably just picks Gc (third most valuable of the six known).

    Assuming that the same pattern holds (I didn't crank through the
    arithmetic to verify), E would pick the fourth most valuable gift of
    the five known, which may turn out to be G4 or G5 or G6.

    What about D? D knows the relative rank of four gifts (Ga through Gd),
    and can't do better than G5. None of them are guaranteed safe from
    pilfering, but Ga (which will turn out to be G4 or better) definitely
    will be. I suspect that their best option is to just pick Gb.

    C knows the relative rank of three gifts, and can't do better than
    G6. Ga (G5 or better) will definitely be pilfered. Probably pick Gb.

    B invariably gets G7, so it doesn't matter whether they keep or
    switch. And of course A's initial choice, being random, doesn't
    matter either.

    Case 2. Similar to Case 1 but the gifts are wrapped uniquely so each participant knows which one they brought. Case 2.a. You may not pick
    your own gift to open unless you are the last picker. Case 2.b. You
    may pick your own to open. What are the strategies for each player
    based on their selection positions?

    This one gets even messier. Each person /potentially/ has more
    knowledge, but only if their gift hasn't already been picked, and
    may still be stuck picking a less valuable one. (Does "last picker"
    refer to G, or A who gets to pick twice?)

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From leflynn@21:1/5 to Edward Murphy on Mon Nov 23 15:37:19 2020
    On Sunday, November 22, 2020 at 1:30:48 PM UTC-5, Edward Murphy wrote:
    On 11/18/2020 11:35 AM, leflynn wrote:

    Seven greedy smart people are participating in a Yankee Swap.
    Rules as given here:
    Each participant brings a wrapped gift and places it with the others. Participants are given random letters from A to G, and they select and unwrap gifts from the pile in alphabetical order.
    The person who receives A will pick a gift from the pile and open it for all to see.
    The person who receives B then chooses a gift and opens it, and then must decide whether to keep it or swap it for the first player’s gift.
    This continues -- each person in order selects a present, opens it and decides whether to keep it or swap it for any other gift someone has already opened.
    Opening of gifts and swapping takes place until all the presents have been chosen. Finally, the person (A) who picked first gets to choose from all the gifts or keep what he/she has already received.

    Notice, these are rules for a very simplified version as there is at most one swap per round.

    Case 1. All participants will evaluate/rank the gifts the same once they are opened and there are no ties. Except for your gift, you do not know what the other gifts are (and how they will rank) until they are opened. All gifts are identically
    wrapped, that is they are indistinguishable until opened. What are the strategies for each player based on their selection positions?
    Assumption: The selection of what (and how valuable) gifts to bring in
    the first place is essentially random.
    Thanks for adding this assumption. Otherwise rec.puzzlers would give these answers:
    1. Don’t participate. It is a zero sum game on average, so you will be wasting your time.
    2. Go but bring a worthless present – so will everyone else, so don’t go. 3. Everyone else is not really as smart as me.

    Start at the end and go backward:

    A, knowing the rank of all seven gifts and able to pick any of them,
    will pick the most valuable gift (call it G1).

    G, knowing the rank of all seven gifts and able to pick any of them,
    will pick the second most valuable gift (G2), i.e. the most valuable
    gift that A won't pick afterward.

    F is where it starts to get interesting. They know the relative rank of
    six gifts (call them Ga through Gf, where Ga is the most valuable), but
    the seventh (G*) is equally likely to be G1 or G2 or etc.

    * Regardless of strategy, the best they can get is G3, i.e. the most valuable gift that neither G nor A will pick afterward.

    * If they pick Gc, then expected outcomes are (G3 G3 G3 G3 G4 G4 G4).
    1/7 of the time the last unopened gift will be F's, and since they can see the other six gifts, they will know whether it is in the top three or not. If it is, 3/49, they should pick Gb instead of Gc to ensure they end up with G3. This improves their
    expected gift position from 3 3/7 to 3 18/49 .


    * There's no point picking Gd or lower (guaranteed less valuable
    than Gc).

    * There's apparently no point picking Ga or Gb either. In either case,
    their expected outcomes after G and A are (G3 G3 G3 G4 G5 G6 G7).
    I'm not sure where you get these results. Picking Ga will usually get you whatever A currently has and that will depend on what the previous traders' strategies were.

    So F probably just picks Gc (third most valuable of the six known).
    As you say things get more complicated after that... In particular, who gets gift #3 when F doesn't?

    L. Flynn


    Assuming that the same pattern holds (I didn't crank through the
    arithmetic to verify), E would pick the fourth most valuable gift of
    the five known, which may turn out to be G4 or G5 or G6.

    What about D? D knows the relative rank of four gifts (Ga through Gd),
    and can't do better than G5. None of them are guaranteed safe from pilfering, but Ga (which will turn out to be G4 or better) definitely
    will be. I suspect that their best option is to just pick Gb.

    C knows the relative rank of three gifts, and can't do better than
    G6. Ga (G5 or better) will definitely be pilfered. Probably pick Gb.

    B invariably gets G7, so it doesn't matter whether they keep or
    switch. And of course A's initial choice, being random, doesn't
    matter either.
    Case 2. Similar to Case 1 but the gifts are wrapped uniquely so each participant knows which one they brought. Case 2.a. You may not pick
    your own gift to open unless you are the last picker. Case 2.b. You
    may pick your own to open. What are the strategies for each player
    based on their selection positions?
    This one gets even messier. Each person /potentially/ has more
    knowledge, but only if their gift hasn't already been picked, and
    may still be stuck picking a less valuable one. (Does "last picker"
    refer to G, or A who gets to pick twice?)

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Edward Murphy@21:1/5 to leflynn on Fri Nov 27 10:08:08 2020
    On 11/23/2020 3:37 PM, leflynn wrote:

    * If they pick Gc, then expected outcomes are (G3 G3 G3 G3 G4 G4 G4).
    1/7 of the time the last unopened gift will be F's, and since they can see the other six gifts, they will know whether it is in the top three or not. If it is, 3/49, they should pick Gb instead of Gc to ensure they end up with G3. This improves their
    expected gift position from 3 3/7 to 3 18/49 .

    Ooh, nice refinement.

    * There's no point picking Gd or lower (guaranteed less valuable
    than Gc).

    * There's apparently no point picking Ga or Gb either. In either case,
    their expected outcomes after G and A are (G3 G3 G3 G4 G5 G6 G7).
    I'm not sure where you get these results. Picking Ga will usually get you whatever A currently has and that will depend on what the previous traders' strategies were.

    Okay, so F is looking at
    Ga Gb Gc Gd Ge Gf
    which are most to least valuable in that order, and Gx which could turn
    out to be anywhere relative to the others. (If Gx is F's gift, then F
    can definitely get G3 as noted above, so let's stick to the cases where
    it isn't.)

    Remember that G always takes G2 and A always takes G1.

    If F picks Gb:

    * If Gx is G1 or G2, then Gb is G3 and F keeps it.

    * If 6x is G3 or G4 or G5 or G6 or G7, then Gb is G2, G takes it and
    sticks F with Gx, and A takes G1.

    If F picks Ga:

    * If Gx is G1, then Ga is G2, G opens G1 and takes G2 (F temporarily
    gets G1), then A takes G1 (sticking F with whatever A had right
    before that, often not the same as A's original random pick).

    * If Gx is G2, then Ga is G1, G opens G2 and keeps it, then A takes
    G1 (again sticking F with whatever A had right before that).

    * If Gx is G3 or G4 or G5 or G6 or G7, then Ga is G1, G opens Gx and
    takes G2 (sticking someone else - possibly A - with Gx), then A
    takes G1 (again sticking F with whatever A had right before that).

    And that's as far as I know to go with it, at least via direct logical analysis. It would be interesting to throw this problem at an AlphaGo
    type system, where each candidate strategy for F E D C B assigns a
    probability distribution of choices to each possible set of inputs,
    then they're put through a series of trials and the losers are weeded
    out and the winners are mutated to produce new competitors.

    I'm no longer convinced that B is guaranteed to get G7, and their
    strategy is also more complex than I realized: 5/7 of the time, B's
    gift remains unopened, so B knows the relative rank of 3 gifts rather
    than just 2.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)