0

I thought I'd read about this problem years ago, but cannot find the answer online. There is a more well-known dining philosophers problem that is vaguely similar.

https://en.wikipedia.org/wiki/Dining_philosophers

Here is my problem: three metaphysicians go out to dinner. When it is time to pay the bill, they settle the bill as follows:

(1) one of them will pay the entire bill

(2) the other two will not know who paid the bill

(3) all three have a random generator of some sort (coin, dice)

(4) they can communicate with each other and have a plan beforehand, but they are not allowed to exchange physical objects

(4) is necessary because an easy solution for this problem would be to have two black tokens and one white token in a bag and each metaphysician draw one in secret.

Another way to think about this problem is playing werewolf in a group of three. One person needs to be the werewolf, two people are the villagers, but the villagers need to not know who the werewolf is. There is no physical contact; they can only exchange verbal information. However, two of the three can exchange information without the third person hearing it.

maibaita
  • 566
  • 2
  • 11
  • Let me give an example for an algorithm. Each metaphysician tosses a coin in secret and takes note of the result. Then they each tell their left neighbour the outcome of their coin toss. If their outcome differs from the outcome of their right neighbour then they do not pay the bill. This would work for HTT, THH, HTH, THT, HHT, and TTH; but not for HHH and TTT, because then all three of them would want to pay the bill. So this is not a solution. – maibaita Jul 12 '16 at 01:19
  • Here is a more sophisticated algorithm that is also a solution once the functions $f$ and $g$ are specified. Let $R={r_{0},\ldots,r_{n}}$, $S={0,1}$, and $T$ suitable. The elements of $R$ are the results of the random generator that each metaphysician has. Let $f:R\rightarrow{}S$ and $g:R\rightarrow{}T$. Let $r_{x},r_{y},r_{z}$ be the results for the respective metaphysicians, and $f_{x}=f(r_{x})$ etc. One metaphysician knows her own $f$-value and the $f$-value of her right neighbour, but not of her left neighbour. All metaphysicians know all $g$-values. $f$ and $g$ need to fulfill ... – maibaita Jul 12 '16 at 14:28
  • ... the following conditions: (i) knowing all the $g$-values determines whether $f_{x}=f_{y}=f_{z}$ or not (in which case the metaphysicians need to repeat the procedure), and (ii) the probability of $f_{x_{L}}=f_{x}$ conditional on knowing $(g_{x},g_{y},g_{z})$ and $f_{x}\neq{}f_{x_{R}}$ is 0.5. $x_{R}$ is the right neighbour of $x$. (ii) needs to hold also for $y$ and $z$. (i) ensures that using the algorithm in my first comment that one and only one person will pay the bill. (ii) ensures that the non-bill-payers don't know who paid the bill. The problem is, I don't what $f$ and $g$ might be – maibaita Jul 12 '16 at 14:31

0 Answers0