Fair division of treasure

The Game Room
1

I’ve got a scenario here that arose in a game, and which would be dealt with via game theory, that I’d like some suggestions on.

There are two factions, call them the Heroes and the Guild. These two factions have come into possession of a significant amount of treasure, and have agreed to share it equally. But while both factions are at peace with each other, and neither is spiteful towards the other, neither actually trusts the other, nor is there any third party available whom both can trust.

The treasure consists of items in two broad categories, call them magic and jewels. The jewels are fairly straightforward: Both factions can basically agree on the relative value of all of the jewel items. The magic items, however, are idiosyncratic: Their relative values, or value relative to the jewels, are much harder to pin down. There’s also an asymmetry between the factions: The hero faction is likely to value the magic higher, relative to the jewels, than the guild faction does.

There’s also an information asymmetry, going both ways. Not only does neither side know exactly how much any given magic item is worth to the other side, but for some items, one side may not even actually know how much it’s worth to themselves, and the different sides probably have knowledge of different items.

Now, this asymmetry of values is both good news and bad news. The good news is that different people placing different relative values on various goods is the basis of commerce, and in the optimal case, both sides can go away thinking that they have the better half. The bad news is that it means that traditional answers, like one faction dividing the loot into two piles with the other choosing one pile, won’t work as well: The one making the piles can make them almost equal in value, by the other’s judgement, and thus end up with significantly more than half of the value in their own estimation.

So far, the best I can think of is either to split the jewels equally, then divide the magic items into two piles via coin flip, then have each faction split one of the coin-flip piles and let the other faction choose one of those (so both sides would have a chance at the player-one advantage), and then allow the sides to negotiate trades for individual items. But that seems rather clunky.

Any other suggestions?

2

I’d consider doing a coin flip to see which faction goes first, and then let them each pick items-- after the first pick, each side should probably pick twice in a row, which has the effect of moderating the advantage from first pick. (Basically it’s the same as having them switch first pick after each has picked once.)

But depending on how much more valuable individual items are than the rest, this might or might not be a good choice. I thought I’d mention it at least.

3

The canonical way to do this is that the first person splits the goods up into two piles any way they want and then the second person chooses which pile they want to take. It’s called the fair division problem.

4

Since pieces have variable value maybe you could split the gems and then have each side bid the jewels for the magic items with the jewels being split equally again at the end. This way the team that values gems more should end up with more gems and each side should get the magic items they desire.

5

If neither trusts the other, then both are untrustworthy. Each side agreed to split the treasure in bad faith and are actively stealing from the other. I suggest a sneak attack, then the winner gets all the treasure.

6

Shalmanese, I already said why that won’t work this time: With the two sides putting different values on different items, the side that makes the two piles has an advantage.

Oredigger, that was actually the other possibility I was thinking of, and the reason my last paragraph says “either”, but I forgot to mention it in the OP. It’d work, but it probably isn’t optimal, since there’s a decent chance that the optimum solution would leave one side with no jewels at all.

EDIT: Oh, and watchwolf, there’s a difference between being trustworthy, and it being known to be trustworthy. But I guess now we know who’s Chaotic Neutral, eh?

7

Give each faction a virtual treasure of, say, 1,000,000 quatloos. Then have a sealed first-price auction on each item individually (both magic and jewels)–that is, each party submits a blind bid and the high bidder wins and pays that price.

8

What we’ve done in similar situations is take turns. Sometimes we’d split the easy part first and then take turns, sometimes the other way 'round.

Having two factions which are interested in different items is actually easier than having two parties which both want the Sword of Twisted Archaeology (+3 to finding a needle on a haystack) and don’t really give a shit about the rest.

9

Huh? How do you split something into two parts and make it so that each part is worth more than half of the whole?

10

We have 9 ice cream cones: 3 each of vanilla, strawberry, and chocolate. I like vanilla the most but all three are ok. The other guy only likes chocolate.

I win the coin flip and split the piles as 3V-3S-1C and 2C. As expected, the other guy picks the 2C since it’s better than 1C from his perspective. However, this seems like an unfair division. 3V-3S and 3C would be more equitable, and still leave each party thinking they got more than half.

11

Even more extreme: Suppose that both like their preferred flavors much more than the others, but still place a small (but nonzero) value on the other flavors. Then you could end up with one side’s proposed split being 3V-3S-1C to 2C, while the other’s proposed split is 1V-3S-3C to 2V. The final deal ends up being radically different depending on who gets to make the piles, which means that they can’t possibly both be fair. And since they were both done under the same rules, that means that the rules must not be fair.

12

Wouldn’t it make just as much sense for the other guy to choose 3V-3S-1C and then try to trade for one of your two chocolate cones? Presumably you have some value for V and/or S or you wouldn’t have split them up the way you did.

13

This is exactly the problem the fair division algorithm is meant to solve. You flip a coin to determine who is the splitter and who is the chooser. More specifically, this procedure is meant to produce an envy free distribution which is perhaps a different definition of fairness than you had in mind. The adjusted winner protocol also maximizes equitability which might fit your needs better.

14

If trading is allowed and the other guy knows exactly how much I value V and S, then sure. But it’s a risky gambit. If I know that’s a possibility, I might not be forthcoming about my personal valuation.

15

A shame it’s patented :). It’s not too different from what I suggested above, except that with my suggestion, each party can adjust their bids based on their remaining points. There’s no need for a final equalization pass, since the loser of a bid on a particular item can then overbid on the remaining items.

16

Good news is that the patent just expired in July so have at it!

17

Hm, it looks like that might work… My only worry is “As patented, this method does not handle multiple identical assets with diminishing marginal utility.”. It’s quite possible that there are some such items in the treasure.

But then, we don’t actually know any specifics about the treasure yet, so this is all rather hypothetical.

18

I forgot to add the final though to my solution which is redivide the gems that were used to pay for the auctioned goods. So if one team didn’t want magical items they would increase their number of gems by 50%. If they split the magic items equally by number then they would end up with the same value of gems and the same number of items.

19

The method is still open to blatant manipulation.

We each get half a million in gems and now we want to ‘buy’ the magic items. However, in an item by item negotiation, I manage to get what I want for less than I make you pay for yours (by driving the price up on things I know you want). I pay 200k for my half of the stuff, you pay $350k for yours. Now we split that, each getting 275k. I now have 575k and all the stuff I want. You have 425k and the stuff you want. Then it becomes a consideration of what you thought the value was and I would hope that you consider your items worth 150k more than the ones I got, at least in utility to you, while I know I made you pay top dollar for it.

20

It seems to me that the method would work just fine. The “dividing side” should try to maximize its guaranteed amount, and not worry about how the “choosing side” values items. Presumably, both sides will desire items that the other side has, and that is where commerce comes in.