Puzzling Adventures, Dennis Shasha The Smuggler and the Merchant The merchant Harout has just acquired a certain number of very valuable gold coins. He wants to send them from Yerevan to Zurich. Doing so by land requires passing through many unfriendly countries. Doing so by insured carrier is safe but requires paying 50% in insurance and shipping. He discusses all this over tea with a rather untrustworthy but very capable smuggler who calls himself Jack. Jack says, "No matter how many coins you send with me in a shipment, I'll take a commission of only one gold coin for that shipment." Harout smiles then breathes deeply, "Both of us know that you may just steal the whole shipment from me. I promise you one thing: if you ever steal from me, I'll never do business with you again." Jack nods: "True. I have a bad reputation. But then again, it's either me or the insurance premiums." Harout: "Right. Let's start with the assumption that you know how many coins I have. Given your spy network, I must assume that. You also know that I'm unlikely to get any more given the recent government crackdown. If I have one coin left, you'll consume it entirely even without stealing. Also, if I send my last two with you, you'll steal those for sure. You have no incentive to do otherwise and I know you to be entirely rational." Warm-up: What if Harout has four coins? Should he send any with Jack? Solution to warm-up: If Harout sends all four, Jack will steal them. If he sends three, Jack will steal them since Jack stands more to gain by stealing them than by being honest. If Harout sends two at first, then, Jack, knowing that Harout will use the insured carrier for the last two might as well steal these first two. 1. How many coins must Harout have for it to be worth it for him to use Jack at all? Harout and Jack worked out the above question together. After seeing what would happen if they both played without any trust, Harout makes a proposal, "Look Jack, you know I'm an honest man. I suggest the following protocol. I will divide up my coins into a series of lots whose sizes I will tell you from the beginning. If you are honest for the first k lots, for k >= 0, I will send you the next lot. But, if you steal even once, I will use the insured carrier from then on. Note that this means that I will send even the last lot with you if you've been honest with me up to that point. Who knows? Maybe you have changed your ways." Jack laughed. "I didn't want to claim to have become as honorable a man as you, but now that you mention it, my children have been pressing me to live by the Zoroastrian virtues. That may be too much to ask, but if I can profit as much from being honest as being dishonest, I will be honest. Further, I know you have earned your reputation for honor." Suppose that Harout will live up to the protocol he promises and Jack knows this. Suppose that Jack will prefer honesty to dishonesty if his profit remains the same. If not, he will choose the most profit every time. 2. For 10 coins, what should the lot sizes be in order for Harout to get as many coins to Zurich as possible? If done that way, how many will Harout get to Zurich, how many will Jack get by payment or theft, and how many will go via the insured carrier? 3. What about 20 coins? 4. What about 50 coins? 5. How would you answer questions 2, 3, and 4 if Jack were less influenced by his children than by a long-lived insult he feels he has suffered at the hands of Harout? So, given equal profits, he would steal from Harout rather than give Harout the satisfaction of greater deliveries. Assume Harout knows this. Solution: 1. Harout will never use Jack without some added assumption. There is no number of gold coins high enough. To see why, consider the following inductive argument. From the warm-up, we know that Harout would not use Jack for his last one, two, three, or four coins. Suppose Harout would not use Jack for his last k or fewer coins but will for k+1 coins. Consider his thinking. Sending one coin is pointless because Jack will take it regardless of honesty. Sending all k+1 coins gives Jack no incentive to be honest. Suppose Harout sends some number m in between: 1 < m < k+1. Harout can imagine Jack reasoning as follows: "Even if I'm honest, Harout will use the insured carrier the next time because the number remaining will be less than k. So I might as well steal these m coins." 2. For 10 coins under the trust until cheated protocol, Harout will prepare packets of size 4, then 3, then 2, then 1. Assuming Jack is honest every time, Harout will see 6 coins get to Zurich with four going to the smuggler. It's not in Jack's interest to cheat at any time because he'll never get more than 4 by doing so. 3. For 20 coins, Harout will set up lots of size 5, 5, 4, 3, 2, and 1. The smuggler will receive 6 coins if he is honest and no more in any other case. 4. For 50 coins, Harout will set up 5, 9, 8, 7, 6, 5, 4, 3, 2, 1. The smuggler Jack will get 10 of these coins. Dishonesty will not help him. 5. Assume that Jack would prefer to be dishonest (when profits are equal) in order to exact revenge on Harout and Harout knows this. For 10 coins, the lots become 3, 3, 2, 2. Harout will get 5 to Zurich and Jack will get 5. For 20, the lots will be 4, 5, 4, 3, 2, and 2. The smuggler will get 7 and Harout will get 13 delivered to Zurich. For 50, the lots will be 4, 9, 8, 7, 6, 5, 4, 3, 2, and 2. The smuggler will receive 11 and 39 will be delivered to Zurich. Here is how to calculate the lot sizes when Jack prefers to be honest. (I had a complex method involving dynamic programming but Peter Carpenter showed me a much more elegant one.) The last lot Harout sends should have one coin. If he sends more coins at the end, Jack will certainly steal them. The next to last lot should have 2, then 3 and so on. This tells us how many to send if Harout's initial coin collection is of size 1 coin, 3 coins, 6, 10, 15, 21, 28, 36 ... coins. These "perfect coin numbers" are derived from the series 1, 1+2, 1+2+3, 1+2+3+4, .... If Harout has 1+2+3+...+n coins initially, then he divides them into lots of size n, n-1, n-2, ..., 1 and sends in descending order. If Harout's initial collection is not perfect, then his first lot is the number that will reduce his collection size to the next lower perfect coin number. For example, if he has 31 coins, his first lot will consist of 3 coins. If Jack prefers to be dishonest when profits are equal, then the argument becomes somewhat more complex. I sketch this using "dynamic programming" and "recursion". If you find this to be too rough going, then you get something very close by following Peter Carpenter's approach: given n coins, divide the lots based on the Jack-the-good-guy model for n-1 coins and then send 1 coin at the end. The following approach is just slightly better: Let Merchant(n) = the number the merchant will get from the last n coins if the smuggler has been honest until that point and the merchant plays optimally. Smuggler(n) = number he will get from the last n coins assuming the merchant follows the merchant's optimal strategy. The function try(n,k) determines what will happen when k are sent from the remaining n. If the smuggler will make at least as much from stealing the k as from taking a commision of 1 plus whatever the smuggler would earn from the merchant's strategy for n-k, then the smuggler will steal. Otherwise he won't. Each option has measurable outcomes. That reasoning generates an optimal division of lots.