Assassin Problem over the Internet

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

jewish_scientist
Posts: 679
Joined: Fri Feb 07, 2014 3:15 pm UTC

Assassin Problem over the Internet

Postby jewish_scientist » Wed Nov 08, 2017 11:25 pm UTC

How can you solve the Assassin Problem if everyone can only communicate using text or images? This is my solution:


Spoiler:
Two people are picked to be chiefs. The first chief sends everyone an unique number ranging from 1 to 'n', where 'n' is the number of players. The second chief picks a set of numbers such that 1 plus a number in the set results in an unique sum. [See post below] The one of the chiefs makes public a numbered list of people playing.

Each person finds the sum, mod 'n', of the numbers sent to them by the two chiefs. The person on the list who has their number's sum is their target.

Every person gets to play, the only information being sent is text, and only one person has to do math above a 1st grade level. It seems like a pretty good solution to me.
Last edited by jewish_scientist on Thu Nov 09, 2017 5:10 pm UTC, edited 1 time in total.

User avatar
chridd
Has a vermicelli title
Posts: 779
Joined: Tue Aug 19, 2008 10:07 am UTC
Location: ...Earth, I guess?
Contact:

Re: Assassin Problem over the Internet

Postby chridd » Thu Nov 09, 2017 4:12 am UTC

Spoiler:
Get one of the people to write a computer program that chooses an 8-cycle and emails/PMs each player their target. (This assumes that everyone can trust that player, though.)
:D
~ chri d. d. /tʃɹɪ.di.di/ (Phonotactics, schmphonotactics) · they (for now, at least) · Forum game scores
mittfh wrote:I wish this post was very quotable...
flicky1991 wrote:In both cases the quote is "I'm being quoted too much!"

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5963
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Assassin Problem over the Internet

Postby jestingrabbit » Thu Nov 09, 2017 7:36 am UTC

relatively straightforward

Spoiler:
Either get people to pick random numbers, or calculate a hash of some file they provide (a selfie or whatever). Person with the lowest hash attacks the person with the second lowest hash... person with the second highest attacks person with the highest, and person with the highest attacks the lowest. This does the right thing if people are killed too.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Tub
Posts: 320
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Assassin Problem over the Internet

Postby Tub » Thu Nov 09, 2017 3:13 pm UTC

I don't get it. What exactly is meant by the requirement for the cycle to be "secret"?

If it just means that nobody can pick their target, then taking a stack of cards and shuffling will suffice.

If it means that at the end of the procedure, everybody knows their target, but nobody else's target, then even the youtube guy's solution doesn't hold - if I have the stack, I can not only find my own target, but also everyone else's.

jewish_scientist
Posts: 679
Joined: Fri Feb 07, 2014 3:15 pm UTC

Re: Assassin Problem over the Internet

Postby jewish_scientist » Thu Nov 09, 2017 3:36 pm UTC

jestingrabbit, If the players publicly publish their hashes publicly, then each player knows who is targeting them. The challenging part of this problem is not making a cycle; it's making the cycle secret.

Tub, in a secret cycle everyone knows their target and does not know who is targeting them. In the example solution, the players search the deck in front of the other players. This way the can only turn over the card with their name and the card with their partner's name. Also, he does not make this clear; the players turn over the cards such that only they can see the name on the other side. I believe that players do not put the second card they draw back into the deck, so when it is the next player's turn, they do not know where this card was located. The third video in the series offers a few better solutions where every player has equal probability of targeting the other players.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25820
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Assassin Problem over the Internet

Postby gmalivuk » Thu Nov 09, 2017 4:42 pm UTC

My understanding of the problem (for people unfamiliar with Assassin or uninterested in watching the video):

Assassin Rules:
You have n people playing the game.
Each person has a target among the other people, whom they are supposed to "kill" (in some manner determined by the rules of the game).
When a target is "killed", their assassin learns the victim's original target and that becomes the assassin's new target.
Play proceeds until only one player remains.

The problem:
You need to arrange all n players in a cycle, so you're guaranteed to always have a living target (that isn't you) unless you've won the game.
You don't want any of the players to know anyone else's target. In particular you don't want anyone to know who's targeting them (until there are only two players remaining, of course).
In this particular case: no person (or program) outside the players is involved in arranging things, and no communication apart from text or images is allowed before the game starts.
---
jewish_scientist, I'm not clear on what you mean by your method, when you say
Spoiler:
"The second chief picks a set of numbers such that 1 plus a number in the set results in an unique sum."

If the set of numbers are all distinct, then the sum of 1 and all the numbers would also be distinct, so what do you mean by "unique sum"?
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

jewish_scientist
Posts: 679
Joined: Fri Feb 07, 2014 3:15 pm UTC

Re: Assassin Problem over the Internet

Postby jewish_scientist » Thu Nov 09, 2017 5:32 pm UTC

Yeah, I was tired when I wrote that and realized that no one was going to understand what I meant at all, partially because it is what I wrote is not what I meant to say. Just pretend that you never read that.

Spoiler:
GH + XH = GH+1
0 < H < n
GH =/= GJ
For a given 'n', find a set of values for X that makes the above statements true in mod n.

What you should end up with is something like [1 -> 5 -> 7 ... -> 1]The easiest solution is X = C, but more complicated fun solutions are also available.


Tangential question; what is the notation to say that an equation is written in modular arithmetic?

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25820
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Assassin Problem over the Internet

Postby gmalivuk » Thu Nov 09, 2017 5:40 pm UTC

Okay but now you need to explain what X and G are and where they come from. (Which are the numbers assigned by the captains?)

jewish_scientist wrote:Tangential question; what is the notation to say that an equation is written in modular arithmetic?
I usually say things like "a = b (mod n)", though technically the symbol for modular congruence is ≡.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Derek
Posts: 2154
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Assassin Problem over the Internet

Postby Derek » Fri Nov 10, 2017 11:25 pm UTC

I came up with a solution that requires a little bit of cooperation, but is probably workable practically:

Spoiler:
Assign everyone a number from 1 to N randomly and secretly (players know their own number but no one else's). There are many ways to do this, such as with a deck of cards, but it doesn't matter how you do it.

Now have everyone close their eyes or blindfolded. One player (doesn't matter who) is the announcer. The announcer calls for player 1 to raise their hand, then player 2 opens their eyes and looks for player 1. The announcer tells player 1 to put their hand down, and tells player 2 to close their eyes. Then the announcer calls for player 2 to put their hand up and player 3 to open their eyes. Repeat until everyone has recognized their target (to be clear, 2 is targeting 1, 3 is targeting 2, etc.).

Catching basic cheating is fairly easy, but requires a restart when caught: If no one raises their hand on their turn, or if multiple people raise their hand (I don't know why they would) the player who is looking announces it. If someone opens their eyes out of turn, the player who is supposed to be looking likewise announces it.

Problems are that more subtle cheating is difficult to catch. Such as if someone subtly peaks out of turn, this is why blindfolds may be preferable. Or if two player collaborate, then cheating is possible.

Runtime is O(n^2), assuming it takes O(n) time for a player to recognize their target.


I also saw a solution in the Youtube comments for one of the related videos that I think is ideal theoretically, but might have some practical difficulties:

Spoiler:
Prepare a deck of cards with two cards for each player's name. So the deck should start like AABBCCDD...

In some way attach the cards with the same name together (so they will shuffle as one unit), then shuffle the deck face down.

Unattach the cards and move the bottom card (without looking at it) to the top of the deck. Now attach the cards in the new pairs. So the deck should be something like (AC)(CB)(BD)(DA) (but players still can't see the cards). This creates a unique and secret cycle.

Now shuffle the deck again (still facedown).

Turn the deck over so the cards are face up. Give the top pair of attached cards to the player with the name on top. Note that noone should be able to see the bottom card of the pair. Distribute all pairs in this manner. Player's target the other name in their pair.

Runtime is O(n).

The difficulty arises in unattaching and then reattaching the cards without anyone seeing the order of the deck after the second shuffle. It is possible, but would require some care. Using card sleeves may be convenient here: Two cards can be placed in a sleeve, shuffling sleeves is easy, and the face up card will effectively cover the face down card in the sleeve (helpful for the distribution step). Then for the intermediate step one player must careful remove all cards from their sleeves without disturbing the order or looking at the cards, then after moving the bottom card to the top replace the cards in the sleeves.


EDIT: This solution appears to be equivalent to two of the solutions given in the third video in the series (Matt's solution and the last solution).

User avatar
Eebster the Great
Posts: 2769
Joined: Mon Nov 10, 2008 12:58 am UTC

Re: Assassin Problem over the Internet

Postby Eebster the Great » Sat Nov 11, 2017 1:55 am UTC

Derek, the idea is to create a method that works over the internet when no player trusts any other, including any software any of them writes.

jewish_scientist
Posts: 679
Joined: Fri Feb 07, 2014 3:15 pm UTC

Re: Assassin Problem over the Internet

Postby jewish_scientist » Mon Nov 13, 2017 1:37 pm UTC

If you publicly publish the source code, then you can write software. The problem you reach is how do you know that the person who runs the software reports the results without checking them.

User avatar
Xanthir
My HERO!!!
Posts: 5228
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Assassin Problem over the Internet

Postby Xanthir » Thu Nov 16, 2017 11:43 pm UTC

Hmm, watching the videos, I don't like the solutions presented. The originating person's proposal is, with the extraneous stuff removed:

Spoiler:
1. Number all the people 1-8.
2. Get cards numbered 1-8, in order. Cycle the deck (move top card to bottom) a random number of times.
3. Give the first card from the deck to #1, have them verify that it doesn't have #1 written on it. (If so, cycle the deck a random number of times again and repeat.)
4. Give the next card to #2, next to #3, etc.


The problem with this is:

Spoiler:
Once you know your target, you know the offset between you and your target - if you're #1 and your card says #4, you know everyone's target will be their number +3. In particular, you know who will target you - #6.


Jim's first proposal is much better, but still has some weaknesses. His is:

Spoiler:
1. Randomly group people into four pairs of "secret partners".
2. Create a deck of 8 cards, where the top of the card has each person's name, and the bottom has their partner's name.
3. Shuffle the deck.
4. First person takes the deck and, only cycling the deck, finds their card, and flips it over to find out who their secret partner is.
5. Person then cycles to their partner's card, then cycles once more (to reveal the card underneath their partners'), then flips it over to find *that* person's secret partner. That's their target.


It definitely works better - it works every time (no need to repeat until you don't get a collision) and it reveals much less information than the first one, but it still has some important weaknesses:

Spoiler:
If your partner's card ends up right after yours, you know that your partner is going to have *you* as their target. (They'll flip their card, see your name, find your card, go past it to pick up their card again, then flip it over to get your name as the target.) If your partner's card is not adjacent to yours, you learn a *small* amount of information about what other people's targets will be, because you learn one other pair of secret partners, but it's harder to extract something useful from that.


I haven't watched the third video yet, so I'm not sure how it might have been improved afterwards. I also don't have a solution of my own yet. ^_^

ETA: Derek, I like both of your solutions! They're both very practical for in-person playing. Here's your second solution, described slightly more concretely:

Spoiler:
1. Assign every player a number, 1-8. This is public information.
2. Take two playing cards with each number (two As, two 2s, etc). Sleeve each pair together into card sleeves.
3. Shuffle the deck.
4. Carefully remove each pair of cards from their sleeves, not revealing their numbers, and assemble them back into a stack of cards in the same order.
5. Move the top card to the bottom.
6. Re-sleeve pairs of cards, taking 2 at a time from the top of the stack.
7. Shuffle the deck.
8. Reveal the sleeved pairs (only one card should be visible now; the other is hidden behind) and hand each sleeve to the person matching that number. The hidden card in their sleeve is their target.


ETA2: Watched the third video, and yeah, yours is equivalent to Matt's solution, which is equivalent to GrandDizzy's solution. I wonder why they didn't notice that?

(And note that these solutions are nearly equivalent to the first one with an offset of 1 - the important difference is the shuffle at the end removing the ordering information.)

ETA3: Nah, Jim's solution is even worse than I thought. It will reveal your killer a substantial percentage if the time!

Spoiler:
So your killer will be the one who, in the last step, chooses your partner's card, as it has your name on the backside. This person thus has *their* partner's card immediately before that.

So, some bad situations arise. 1/7th of the time, your card will be immediately followed by your partner's card, which means, by the logic above, that your partner is your killer. That sucks - immediate secrecy failure 14% of the time!

But say that doesn't happen. When you find your target, you'll learn another secret pair (unless you're killing your partner). This gives you more information - if either of their cards precedes your partner's card, whoops, you found your killer again.

So 3/7ths of the time, you can discover your own killer with no cheating, just public knowledge and the knowledge you naturally obtain while finding your own target. 1/7th of the time you're killing your partner (and this they can discover their killer in the same way). Only in the remaining 3/7ths of the time do you not have an immediate obvious failure, and that's for just one person - the chance of all 8 people not running into these info leaks is miniscule.

Not to mention, the set-up is bad - you need a trusted external party to set up the secret pairs, because knowing then immediately lets you decipher the ordering and find every killer/victim assignment. You might as well just tell them to generate an 8 cycle and just tell everyone their target directly, is the same amount of trust needed.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
jaap
Posts: 2073
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Assassin Problem over the Internet

Postby jaap » Fri Nov 17, 2017 9:50 am UTC

Xanthir wrote:Hmm, watching the videos, I don't like the solutions presented. The originating person's proposal is, with the extraneous stuff removed:

Spoiler:
1. Number all the people 1-8.
2. Get cards numbered 1-8, in order. Cycle the deck (move top card to bottom) a random number of times.
3. Give the first card from the deck to #1, have them verify that it doesn't have #1 written on it. (If so, cycle the deck a random number of times again and repeat.)
4. Give the next card to #2, next to #3, etc.


The problem with this is:

Spoiler:
Once you know your target, you know the offset between you and your target - if you're #1 and your card says #4, you know everyone's target will be their number +3. In particular, you know who will target you - #6.

I have not watched the video, but there is a bigger problem with the solution as you describe it:
Spoiler:
If the cards are offset by an even number, you don't have a single cycle at all.
If it shifted by two, you get:
1 has card 3
2 has card 4
3 has card 5
4 has card 6
5 has card 7
6 has card 8
7 has card 1
8 has card 2

So you have two cycles (1,3,5,7) and (2,4,6,8). It is worse if it is offset by 4, in which case you get 4 pairs. This procedure is only guaranteed to work if the number of people is a prime number.

jewish_scientist
Posts: 679
Joined: Fri Feb 07, 2014 3:15 pm UTC

Re: Assassin Problem over the Internet

Postby jewish_scientist » Fri Nov 17, 2017 6:39 pm UTC

gmalivuk wrote:Okay but now you need to explain what X and G are and where they come from. (Which are the numbers assigned by the captains?

The 'X's are the numbers given out by one caption. The other caption gives out an unique number 1 through 'n'. 'G' and 'H' are positive integers.

Derek
Posts: 2154
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Assassin Problem over the Internet

Postby Derek » Fri Nov 17, 2017 8:21 pm UTC

Xanthir: I don't want to take credit for the second solution I posted. I found it in the comments on one of the related videos, and posted it because I liked it and think it's the ideal solution. My only contribution was adding the card sleeves (which I still like better than cutting index cards or playing cards).

As for doing this remotely (over the internet) as Eebster requested, I haven't found a solution that doesn't involve some trusted third party. The problem is that if the code and inputs are available to any of the players then it can be inspected, debugged, or modified to reveal what should be hidden information. The only possible solution would have to involve some sort of end-to-end encryption (or secret information or some other sort) (encrypting anything during execution of the program is useless since the players can just remove the encryption).

User avatar
Xanthir
My HERO!!!
Posts: 5228
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Assassin Problem over the Internet

Postby Xanthir » Fri Nov 17, 2017 10:11 pm UTC

jaap wrote: but there is a bigger problem with the solution as you describe it:
Spoiler:
If the cards are offset by an even number, you don't have a single cycle at all.
If it shifted by two, you get:
1 has card 3
2 has card 4
3 has card 5
4 has card 6
5 has card 7
6 has card 8
7 has card 1
8 has card 2

So you have two cycles (1,3,5,7) and (2,4,6,8). It is worse if it is offset by 4, in which case you get 4 pairs. This procedure is only guaranteed to work if the number of people is a prime number.

Spoiler:
Oh jeez, you're right - that explains why, in the video, the dude said "have the first person verify their target isn't their own card or [the card four spots down]". They didn't explain that bit at all, so I buzzed by it as just another of the overcomplications in their procedure, of which there were many. But yeah, if the offset isn't coprime to the total, you'll get sub-cycles instead of a full-cycle. (And they didn't even mention checking for a 2-offset, which means they had no idea what the weakness actually was; presumably they just accidentally ran into the 4-offset while playing around, since it immediately produces 2-cycles and is super obvious.)

The strategy already sucks a lot, but this just makes it much worse, so yay.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Tub
Posts: 320
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Assassin Problem over the Internet

Postby Tub » Sat Nov 18, 2017 1:01 am UTC

Derek wrote:As for doing this remotely (over the internet) as Eebster requested, I haven't found a solution that doesn't involve some trusted third party.

By using internet messages, you're already involving trusted third partys to relay the messages. Let's assume that people can create email addresses and send confidential mails over them.

Here's one possibility:
* Everyone has a public address, linked to their real name.
* Everybody creates a second, throwaway email, using it to send an email to the public list "I'm playing". Now everbody knows all secret emails, but (other than their own) not who they belong to.
* The oldest player (or whoever) selects a random secret identity and sends one email, from their public address to the chosen secret address: "you're starting.". From now on, only the secret addresses will be used, let's call them A .. G, with A being the one picked to start.

The players create a cycle by picking themselves a random assassin, telling them their target, and enough information to complete the cycle.

A picks a random identity from {B..G} (let's say B) and sends an email: "Your target is [A's real name]. Remaining players without a target: [C..G]. Started by A."
B notes their target, picks a random identity from the remaining players (let's say C) and sends an email: "Your target is [B's real name]. Remaining players without a target: [D..G]. Started by A."
etc
F sends to G: "Your target is [F's real name]. Remaining players without a target: none. Started by A."
G sends to A: "Your target is [G's real name]."

At this point, everyone knows their target. A's secret identity sends one last email to the list: "the targets are assigned.", and the game can begin.


Unless I'm mistaken, this will always create a random 8-cycle, and nobody knows anything but their own target. People will know both the public and secret identity of their target, but I don't see a way to misuse that information.

The obvious flaw is that it's easy to sabotage the game by not adhering to the protocol, like removing or re-adding an email, by telling the next person someone else's name instead of your own, or simply by not continuing the chain. As we rely on hidden communication, this cannot be prevented. But we can refine the protocol to make sure it is detectable:

After all targets are assigned, everyone confirms via their public email: "I have my target.", plus a hash of their secret identity, the email they received and the email they sent (plus maybe a small random salt). Post-game, all secret identities and messages are published; if something does not add up, everyone will know.

User avatar
Xanthir
My HERO!!!
Posts: 5228
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Assassin Problem over the Internet

Postby Xanthir » Sat Nov 18, 2017 5:42 am UTC

Tub: slightly less fiddly version of yours:

1. Everyone has a public email address, and there's a public mailing list they can all use and see.
2. Everyone generates a random private email address, and sends an email to the list from it, so everyone knows the full set of private emails.
3. Someone randomly generates an ordering of the private emails and sends it out to the list.
4. Each person finds their private email, and then, from their public email, sends a message to the *following* private email on the list, letting the private address know that they (the public address) are the private address's victim. Both the killer and victim then send confirmation emails to the list from their private addresses, letting people know that they sent the victim's name and received it.
5. Once the list has received confirmations from everyone, the game begins.

I think this works? And shouldn't be vulnerable to cheating or confusion, or sabotage beyond just failing to play at all.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

jewish_scientist
Posts: 679
Joined: Fri Feb 07, 2014 3:15 pm UTC

Re: Assassin Problem over the Internet

Postby jewish_scientist » Sat Nov 18, 2017 6:21 am UTC

Derek wrote:As for doing this remotely (over the internet) as Eebster requested, I haven't found a solution that doesn't involve some trusted third party.

Eebster did not request that; I did in the OP. The Assassin Problem has already been solved for in person play. This is objectively the best solution.

Tub
Posts: 320
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Assassin Problem over the Internet

Postby Tub » Sat Nov 18, 2017 11:46 pm UTC

@Xanthir: you're letting a single person generate all randomness, and the full random order is public, and both make me feel uneasy.. but as long as the private emails remain private until the game is over, I can't find any way to exploit that. So sure, your's is simpler and less fiddly than what I came up with as I was trying to fall asleep ;)

I cannot even come up with a protocol violation that wouldn't be cought before the game. I cannot send the wrong name (as I need to send from my public address), I cannot send to the wrong person (as they would complain about getting multiple targets), I cannot refuse to send an email because my assassin's confirmation is required.

So the game won't start without a valid cycle, but a saboteur can prevent the game from starting. If a cycle fails to be generated, require everyone to publish their private email and all communications. If there's only a single saboteur in the group, then they will eventuelly be found after a few failed games.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25820
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Assassin Problem over the Internet

Postby gmalivuk » Sun Nov 19, 2017 3:20 am UTC

jewish_scientist wrote:
Derek wrote:As for doing this remotely (over the internet) as Eebster requested, I haven't found a solution that doesn't involve some trusted third party.

Eebster did not request that; I did in the OP. The Assassin Problem has already been solved for in person play. This is objectively the best solution.
Is that one of the solutions whose faults have already been outlined and discussed in this thread?
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Derek
Posts: 2154
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Assassin Problem over the Internet

Postby Derek » Sun Nov 19, 2017 10:13 am UTC

gmalivuk wrote:Is that one of the solutions whose faults have already been outlined and discussed in this thread?

No, that's a version of the good solution that I and Xanthir discussed above.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25820
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Assassin Problem over the Internet

Postby gmalivuk » Sun Nov 19, 2017 3:27 pm UTC

I see.

(When I read the forums via mobile data on my phone, I never watch videos.)
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Eebster the Great
Posts: 2769
Joined: Mon Nov 10, 2008 12:58 am UTC

Re: Assassin Problem over the Internet

Postby Eebster the Great » Sun Nov 19, 2017 5:06 pm UTC

I think the problem with the secret email solution is that everybody knows both the public and secret email of their target, and therefore they can surreptitiously share this information with other assassins. For instance, imagine a 5-player game between Alice, Bob, Carol, Dave, and Eve. They have secret emails a@s.com, b@s.com, c@s.com, d@s.com, and e@s.com, but nobody knows whose is whose. Alice (whose secret email is a@s.com) starts the process by emailing b@s.com, telling them that she (a@s.com) is Alice, that she started the process, that she is their (b@s.com's) target, and that she, c@s.com, d@s.com, and e@s.com still have no target. Now suppose that Bob turns out to be b@s.com, so he gets this email, and now he knows Alice's secret identity. He can reveal this to Carol in exchange for Carol's secret identity. Then he will deliberately not choose Carol as his target, but rather a secret identity that must be either Dave or Eve. Now both he and Carol have some extra information: Carol knows Bob is not after her, and Bob knows he is not after Carol. Carol also knows who Alice is, so she will know whether or not Alice is her target and whether or not she is Alice's. This is all info that they should not have, and it is easy to obtain by just breaking the trust of teammates, even if there is a trustworthy third party.

User avatar
Sizik
Posts: 1159
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Assassin Problem over the Internet

Postby Sizik » Sun Nov 19, 2017 5:22 pm UTC

How can Bob "deliberately not choose Carol as his target", since the target ordering is fixed?
Edit: Also, Bob's target is Alice in your example.
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25820
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Assassin Problem over the Internet

Postby gmalivuk » Sun Nov 19, 2017 5:49 pm UTC

Yeah, there's some mixing up of the direction targeting goes in that explanation, but in any case if you're worried about people sharing information they shouldn't be sharing, that's something they could do in any arrangement (including the in-person version), so I'm not sure it counts as a weak point of this strategy.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Xanthir
My HERO!!!
Posts: 5228
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Assassin Problem over the Internet

Postby Xanthir » Sun Nov 19, 2017 6:22 pm UTC

Eebster the Great wrote:
I think the problem with the secret email solution is that everybody knows both the public and secret email of their target, and therefore they can surreptitiously share this information with other assassins.

This has nothing to do with the protocol; it's inherent to the game. Each assassin knows their own target, and could share that information if they felt like it. This is true no matter how targets were assigned, whether digitally or in person.

Tub wrote:
@Xanthir: you're letting a single person generate all randomness, and the full random order is public, and both make me feel uneasy.. but as long as the private emails remain private until the game is over, I can't find any way to exploit that.


If you want to avoid letting someone generate the randomness, there are various tricks you can do to avoid that. For example, have everyone agree on some unpredictable piece of information you can obtain in the future, such as the front-page headline text of a certain newspaper the next day. For each secret email, hash (email + text) with some good hash function. Sort the emails according to the hashed result they generate, and bam, random order obtained only from public information and that can't be manipulated.

(If you don't want to have to wait for something, here's a simple method that's immune to collaboration unless literally the entire group collaborates together: Sort the secret emails lexicographically. Have every secret email send in a small piece of text, just a few characters or so, then concat them in the order previously determined to obtain the text. Hash as above.)

Having the full random order be public is fine; nobody knows the identity of any of the secret emails except their own and their victim's, which is the minimum amount of knowledge necessary to play the game. As long as nobody ever references their secret emails ever again, there is no knowledge you can gain during the game that lets you further interpret the list, either - if you see A kill B, for example, you don't know which secret emails they had, so you can't tell what part of the list gets deleted (unless A is your victim, of course, but you already have that information - all you previously knew is that A had asdf1234 as target, but you didn't know who asdf1234 was, and now you know they have qwer5678 as target, and you still don't know who qwer5678 is).

Tub wrote:
So the game won't start without a valid cycle, but a saboteur can prevent the game from starting. If a cycle fails to be generated, require everyone to publish their private email and all communications. If there's only a single saboteur in the group, then they will eventuelly be found after a few failed games.


I don't really consider "fuck this game, I don't even want to play" to be a failure mode worth bothering over; we can assume that everyone wants to play, we're just trying to guard against cheating. After all, once you do generate a cycle, someone can still say "fuck this" and wander off, and now the game is unfinishable.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Eebster the Great
Posts: 2769
Joined: Mon Nov 10, 2008 12:58 am UTC

Re: Assassin Problem over the Internet

Postby Eebster the Great » Mon Nov 20, 2017 2:18 am UTC

Xanthir wrote:
Eebster the Great wrote:
I think the problem with the secret email solution is that everybody knows both the public and secret email of their target, and therefore they can surreptitiously share this information with other assassins.

This has nothing to do with the protocol; it's inherent to the game. Each assassin knows their own target, and could share that information if they felt like it. This is true no matter how targets were assigned, whether digitally or in person.

No it isn't. The problem is that Bob knows his target in advance of him being chosen as anyone's target, and moreover that he can choose who will target him. So by talking to Carol, he can ensure that Carol is not targeting him. If he fears Carol more than anyone else, but Carol wants to know Alice's secret identity, they can strike a deal that would be impossible in the in-person case described in the video.

jewish_scientist
Posts: 679
Joined: Fri Feb 07, 2014 3:15 pm UTC

Re: Assassin Problem over the Internet

Postby jewish_scientist » Mon Nov 20, 2017 1:40 pm UTC

gmalivuk wrote:When I read the forums via mobile data on my phone, I never watch videos.

I will keep this in mind in the future.

User avatar
Sizik
Posts: 1159
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Assassin Problem over the Internet

Postby Sizik » Mon Nov 20, 2017 3:25 pm UTC

Eebster the Great wrote:The problem is that Bob knows his target in advance of him being chosen as anyone's target, and moreover that he can choose who will target him.

Bob can't choose who targets him, he has to send his target email to the next person on the list of random emails. If he targets anyone else, they will get two target emails, and will know that someone is playing wrong.
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25820
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Assassin Problem over the Internet

Postby gmalivuk » Mon Nov 20, 2017 4:30 pm UTC

It looks like that's a difference between Derek's description and Xanthir's.

(But yeah, in Xanthir's description, Bob doesn't get to make any choices. Everyone knows the full cycle as soon as it's posted, they just don't know which real people correspond to which secret email address until their target emails them and gives this information.)
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Sizik
Posts: 1159
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Assassin Problem over the Internet

Postby Sizik » Mon Nov 20, 2017 4:38 pm UTC

Ah yes, it seems like Eebster's talking about Tub's email solution, not Xanthir's.
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

MostlyHarmless
Posts: 149
Joined: Sun Oct 22, 2006 4:29 am UTC

Re: Assassin Problem over the Internet

Postby MostlyHarmless » Mon Nov 20, 2017 10:39 pm UTC

If Bob wants to target Alice, he can wait to see who his target is before sending his own email. If someone other than Alice is his target, he then sends an email to the wrong person, which will cause the game to fail. He could keep doing this until he gets Alice as a target.

I think an obvious solution is just to agree beforehand that if the game fails then you won’t start over with the same players (i.e., if you sabotage the game then you don’t get to play).

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25820
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Assassin Problem over the Internet

Postby gmalivuk » Mon Nov 20, 2017 10:43 pm UTC

Again, the fact that people can completely sabotage the game if they want to isn't a weakness of any particular method of assigning roles, because someone could refuse to play in any system.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Eebster the Great
Posts: 2769
Joined: Mon Nov 10, 2008 12:58 am UTC

Re: Assassin Problem over the Internet

Postby Eebster the Great » Tue Nov 21, 2017 6:35 am UTC

I hadn't even noticed the difference. Xanthir's version looks good to me.

jewish_scientist
Posts: 679
Joined: Fri Feb 07, 2014 3:15 pm UTC

Re: Assassin Problem over the Internet

Postby jewish_scientist » Tue Nov 21, 2017 4:04 pm UTC

Assume that everyone wants to play the game and are willing to cheat in order to win.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25820
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Assassin Problem over the Internet

Postby gmalivuk » Tue Nov 21, 2017 5:23 pm UTC

Then people will cheat regardless of the method you use, including in person.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Xanthir
My HERO!!!
Posts: 5228
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Assassin Problem over the Internet

Postby Xanthir » Tue Nov 21, 2017 7:02 pm UTC

And my method (particularly with the addendum that publicly creates the random ordering) is then robust to cheating, as far as I can tell (at least, any that can occur during the assignment of victims). Any cheating (outside of all players collaborating together at once, for some reason) will be detected by people being confused and the protocol visibly not being followed.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

MostlyHarmless
Posts: 149
Joined: Sun Oct 22, 2006 4:29 am UTC

Re: Assassin Problem over the Internet

Postby MostlyHarmless » Tue Nov 21, 2017 8:08 pm UTC

gmalivuk wrote:Again, the fact that people can completely sabotage the game if they want to isn't a weakness of any particular method of assigning roles, because someone could refuse to play in any system.


There’s some difference, because “refusing to play” is public, but in this case you can sabotage the game privately. If Bob announces publicly that he won’t play this game, then obviously everyone else just sets up a new game without him. If Bob sabotages the game completely anonymously, he can just claim it wasn’t him. There’s no longer the obvious solution of kicking out the person who refused to play, because no one knows who did it.

I agree that there’s no point in worrying about someone sabotaging the game forever, but it seems very easy for Bob to sabotage the game once if he doesn’t get Alice, then deny that it was him, then play the game normally next time. This would give him a better than even chance of having Alice as a target. If he only does this once, the person who got two emails will know that Bob is one of two potential saboteurs, but won’t be able to prove it.

Again, this seems easy to fix by saying that if anyone sabotages the game then no one gets to play. Since we’re assuming that everyone wants to play the game, this forces people to play by the rules.

Edit: After looking at this some more, I think you might be right in the sense that any acceptable method allows people to anonymously break the game. (I haven’t watched the videos because I’m on mobile too, so maybe that’s not true.) If that is true, then this rule should just be added to every method.

jewish_scientist
Posts: 679
Joined: Fri Feb 07, 2014 3:15 pm UTC

Re: Assassin Problem over the Internet

Postby jewish_scientist » Tue Nov 21, 2017 8:29 pm UTC

gmalivuk wrote:Then people will cheat regardless of the method you use, including in person.

If people realize that someone has cheated, even if they cannot determine who it was, then the game will have to be reset. Since everyone wants to play the game, any form of cheating that is detectable will not happen.


Return to “Mathematics”

Who is online

Users browsing this forum: Yahoo [Bot] and 18 guests