Byzantine Bettors

image from book

In the popular imagination, Byzantium is famous for the incessant intrigues and plotting that supposedly took place among the courtiers of the palace. Apparently, the Byzantine court in no way deserved this reputation. Modern historical research suggests that Byzantium achieved a remarkable stability and harmony by the standards of the first millennium. Reputations die hard, however, and this puzzle concerns a game show inspired by the imagined intrigues of Byzantium. We call it Byzantine Bettors.

Each bet works as follows. There are some number of “advisors” and you. One advisor will write either 1 or 0 on a piece of paper, show it to the other advisors but not to you, and put that paper face down in front of you. Each advisor will tell you what the value is. They are all very good actors, so no obvious tick or facial expression will reveal to you who is telling the truth. The amount you can wager on each bet is anything from 0 to the total amount you have.

Warm-Up

Suppose there are four advisors, two of whom always tell the truth, though you don’t know which ones. You get three even money bets. You start with $100. How much can you guarantee to win?

Solution to Warm-Up

If all four or three out of four agree on the first bet, then bet the maximum. There must be at least one truth teller in that group. If they are two and two, then bet nothing. After the first bet, you will know who the truth tellers are and will be able to bet the maximum each time. Thus, at least two times you will be able to bet all you have and be sure to win. This will give you a total of $400 at the end.

Now suppose there are only three advisors and only one of them always tells the truth. Again, you can make three even money bets. You start with $100. How much can you guarantee to win?

The game has just become a little longer but also a lot more nasty. You have four bets, but there is no longer a truth teller, but merely a “partial truth teller.” That advisor is not guaranteed to tell the truth all the time, but must do so at least three out of four times. Further, the advisors can actually substitute what’s on the paper for a worse result for you once they hear your bet. However, they cannot change the result if so doing would eliminate the possibility that at least one of them is a partial truth-telling advisor.

What can you guarantee to win in four bets, with four advisors, three of whom can lie at will, and one who must tell the truth at least three out of four times?
Under the reliability conditions of one partial truth teller who tells the truth four out of five times and three liars at will, but assuming you have five bets, can you guarantee to end with at least $150?