- #1
- 587
- 329
- TL;DR Summary
- How to divide a bunch of goods so that everybody is happy with the outcome?
There's a lot of explanation before getting to my question. Sorry about that.
This came out of a Thanksgiving table discussion. There are a number of mathematicians in my extended family. The problem is how to divide things so that everybody is happy with the outcome, using inexact means of dividing and subjective measures of value.
It started out with my talking about the "I cut, you choose" rule for dividing something, for instance a piece of cake, between two people. I give you the choice after I make my cut. If one piece is obviously much larger than the other, then you're going to choose it and I will be cheating myself. So I will try to make a cut that I perceive as being as even as possible. That makes me happy with either piece, and you are happy as well because if you feel the pieces are different sizes, you can avoid the one you think is smaller.
The interesting thing about this problem: It doesn't matter which one is actually smaller. This is all about perceived value on both sides.
My family members introduced me to the generalization, which I'd forgotten. It's this: I start moving the knife along the piece of cake until somebody shouts "stop". Then they get that piece (between the start and stop points). For instance, if there are 5 of us, then the first piece should be approximately 1/5 of the cake. If you stay silent, hoping the knife will go well past 1/5, you run the risk that somebody else will call first. If you call too soon, you get a piece well below 1/5. So there's incentive for everyone to try to stop the knife at 1/5. (Truly simultaneous calls can be resolved by random choice). The next cut is 1/4 of the remainder, then 1/3, etc.
This reminded me of a fictional division-of-goods problem, that occurs in Neal Stephenson's Cryptonomicon (beginning on p. 776 in my paperback edition if anyone wants to check). I described the scene and was amazed that nobody else had read this book. So I'm happy to have introduced it to some new possible fans. In this scene, the mother's furniture is to be divided among the siblings. There are very strong feelings about some of the pieces, both positive and negative. So the scheme they've come up with is to physically put the furniture in a parking lot. Each sibling gets the opportunity to move the pieces to an (x,y) coordinate in the parking lot. x = perceived economic value, y = perceived emotional value.
My memory was that Stephenson had them iterating the position and then had some scheme for how the resulting division is achieved, taking into account everybody's scores, and I was unable to remember how that final division was achieved.
But I just reread it, and my memory was faulty. All the parking lot is for is to get each person's perceived ##(x_i, y_i)## for each item, which are then recorded. The result is two matrices (this is not Stephenson's notation, and yes this novel includes equations and mathematical notation). ##\mathbf V_x## and ##\mathbf V_y## with ##(V_x)_{ij}## representing the ##x## value assigned by person ##j## to item ##i##, and similarly for ##(V_y)_{ij}##. The columns are normalized so that everyone has a total perceived value of 1 over all items. And values are allowed to be negative.
It is then implied that a supercomputer will do the actual combinatorial optimization, assigning items to individuals in order to equalize as much as possible the perceived value of their share. Stephenson doesn't quite get to explaining what the objective function is or how both values are taken into account in that division.
My question (at last): Is anyone familiar with algorithms along these lines, equalizing perceived value (especially something like the two-dimensional value that Stephenson suggests people are working with in dividing household goods)? Are there some sort of heuristic algorithms that wouldn't require a supercomputer, but perhaps some sort of iterated approach with everybody taking a turn until convergence? Is this perhaps game theory, a subject about which I know nothing?
Any other fun examples of these kind of "minimum envy" problems?
This came out of a Thanksgiving table discussion. There are a number of mathematicians in my extended family. The problem is how to divide things so that everybody is happy with the outcome, using inexact means of dividing and subjective measures of value.
It started out with my talking about the "I cut, you choose" rule for dividing something, for instance a piece of cake, between two people. I give you the choice after I make my cut. If one piece is obviously much larger than the other, then you're going to choose it and I will be cheating myself. So I will try to make a cut that I perceive as being as even as possible. That makes me happy with either piece, and you are happy as well because if you feel the pieces are different sizes, you can avoid the one you think is smaller.
The interesting thing about this problem: It doesn't matter which one is actually smaller. This is all about perceived value on both sides.
My family members introduced me to the generalization, which I'd forgotten. It's this: I start moving the knife along the piece of cake until somebody shouts "stop". Then they get that piece (between the start and stop points). For instance, if there are 5 of us, then the first piece should be approximately 1/5 of the cake. If you stay silent, hoping the knife will go well past 1/5, you run the risk that somebody else will call first. If you call too soon, you get a piece well below 1/5. So there's incentive for everyone to try to stop the knife at 1/5. (Truly simultaneous calls can be resolved by random choice). The next cut is 1/4 of the remainder, then 1/3, etc.
This reminded me of a fictional division-of-goods problem, that occurs in Neal Stephenson's Cryptonomicon (beginning on p. 776 in my paperback edition if anyone wants to check). I described the scene and was amazed that nobody else had read this book. So I'm happy to have introduced it to some new possible fans. In this scene, the mother's furniture is to be divided among the siblings. There are very strong feelings about some of the pieces, both positive and negative. So the scheme they've come up with is to physically put the furniture in a parking lot. Each sibling gets the opportunity to move the pieces to an (x,y) coordinate in the parking lot. x = perceived economic value, y = perceived emotional value.
My memory was that Stephenson had them iterating the position and then had some scheme for how the resulting division is achieved, taking into account everybody's scores, and I was unable to remember how that final division was achieved.
But I just reread it, and my memory was faulty. All the parking lot is for is to get each person's perceived ##(x_i, y_i)## for each item, which are then recorded. The result is two matrices (this is not Stephenson's notation, and yes this novel includes equations and mathematical notation). ##\mathbf V_x## and ##\mathbf V_y## with ##(V_x)_{ij}## representing the ##x## value assigned by person ##j## to item ##i##, and similarly for ##(V_y)_{ij}##. The columns are normalized so that everyone has a total perceived value of 1 over all items. And values are allowed to be negative.
It is then implied that a supercomputer will do the actual combinatorial optimization, assigning items to individuals in order to equalize as much as possible the perceived value of their share. Stephenson doesn't quite get to explaining what the objective function is or how both values are taken into account in that division.
My question (at last): Is anyone familiar with algorithms along these lines, equalizing perceived value (especially something like the two-dimensional value that Stephenson suggests people are working with in dividing household goods)? Are there some sort of heuristic algorithms that wouldn't require a supercomputer, but perhaps some sort of iterated approach with everybody taking a turn until convergence? Is this perhaps game theory, a subject about which I know nothing?
Any other fun examples of these kind of "minimum envy" problems?
