Assassin Problem over the Internet

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

jewish_scientist
Posts: 652
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: 761
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: 309
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: 652
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: 25783
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: 652
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: 25783
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: 2145
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: 2739
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: 652
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: 5212
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: 2071
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: 652
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: 2145
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: 5212
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: 309
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: 5212
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: 652
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: 309
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: 25783
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)


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 23 guests