dining metaphysicians problem
Using secure multi-party computation, there exists a polynomial-time protocol for this problem.

The functionality is

$$F_i(r_1,r_2,r_3)=((r_1 \ne r_2) \lor (r_2 \ne r_3) \lor (r_1 \ne r_3), (r_i = r_{i+1}) \land (r_i \ne r_{i-1})).$$

In other words, in the ideal world, participant $i$ flips a coin to get $r_i \in \{0,1\}$ and sends it to the trusted third party; they receive $F_i(r_1,r_2,r_3)$ back, and the first bit of the result indicates whether to repeat or not and the second bit indicates whether to pay.

It's a powerful theorem from the cryptographic literature that there exists a protocol for any functionality, with computational security and running in polynomial time.  Thus, there exists a protocol for this problem, too.  It will be secure as long as no more than 1 of the 3 participants are malicious.

See https://en.wikipedia.org/wiki/Secure_multi-party_computation and a good textbook on theoretical cryptography.