Author |
Topic: A bargaining theory problem (Read 2818 times) |
|
Benny
Uberpuzzler
Gender: 
Posts: 1024
|
 |
Re: A bargaining theory problem
« Reply #25 on: Jun 27th, 2009, 9:52pm » |
 Quote  Modify
|
Quote:
I think not looking like a penny-pinching ass might be a good investment in future social relations....
|
|
You're right ... the cake, the cab fare are all a metaphor for dividing a divisible good, an item that people may have different preferences for.
Under special circumstances, two people can split something up and both feel like they got more than half.
A paper appeared in the December issue of Notices of the American Mathematical Society, is entitled
"BetterWays to Cut a Cake."
It does not deal with knife-sharpening technology.
This is about the theory and method behind slicing up an object to maximize the satisfaction of those parties, possibly at a party, who will then receive the slices.
This is not just about a cake. The cake is a metaphor for dividing a divisible good
The cake could be just about anything. It could be an apartment w/ 3 small rooms with views, a tract of land, a chicken with white meat and dark meat, the Thanksgiving turkey with the dressing, etc.
You cannot think of a pie. There is a difference between cake and pie cutting.
There's the pie-cutting theory which is different from the cake-cutting one. David Gale (1993) was perhaps the first to suggest that there is a difference between cake and pie cutting.
if a cake is half chocolate and half vanilla, and one person likes chocolate a lot and the other person is indifferent, then there's a way to have both people, in their opinions, receive more than half the cake.
If you are a cake maker, you'll probably have an economic motivation to complicate your cakes and hike your prices
|
| « Last Edit: Jun 27th, 2009, 9:57pm by Benny » |
 IP Logged |
If we want to understand our world or how to change it we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: A bargaining theory problem
« Reply #26 on: Jun 27th, 2009, 10:09pm » |
Quote Modify
|
Concerning the cab fare: contributions vary from nothing to the full fare. we know what's like when you go to a bar with friends, sometimes somebody will pay for your drink, and at other times you'll buy a round for everyone.
However, let's look for a mathematical solution.
Consider two situations: in the first situation, we have 3 stops, and in the second one 4 stops.
Document : A mathematically fair way to split a taxi ride with multiple stops
With 3 stops :
a = $1, b = $5, c = $9, a+b+c = $15
the first would pay ......... ac/(a+b+c) = 9/15 = $0.60
the second would pay ........ bc/(a+b+c) = 45/15 = $3.00
the third would pay ........ c^2/(a+b+c) = 81/15 = $5.40
the first would pay ........ a/N = 1/3 = $0.33
the second would pay ....... a/N + (b-a)/(N-1) = 1/3 + 4/2 = $2.33
the third would pay ........ a/N + (b-a)/(N-1) + (c-b)/(N-2) = $2.33 + $4.00 = $6.33
----------------------------------
With 4 stops :
a=5, b=10, c=17, d=20, a+b+c+d = 5+10+17+20 = 52
ad/(a+b+c+d) = 100/52 = $1.92
bd/(a+b+c+d) = 200/52 = $3.85
cd/(a+b+c+d) = 340/52 = $6.54
dd/(a+b+c+d) = 400/52 = $7.69
a/N
a/N + (b-a)/(N-1)
N=4
a/4 = 5/4 = $1.25
a/4 + (b-a)/3 = 5/4 + 5/3 = $1.25 + $1.67 = $2.92
a/N + (b-a)/(N-1) + (c-b)/(N-2)
5/4 + 5/3 + 7/2 = $2.92 + $3.50 = $6.42
a/N + (b-a)/(N-1) + (c-b)/(N-2) + (d-c)/(N-3)
$6.42 + $3.00 = $9.42
Method #1 .......... Method #2
---------------------------------
..$0.60 ............ $0.33
..$3.00 ............ $2.33
..$5.40 ............ $6.33
Method #1 .......... Method #2
---------------------------------
..$1.92 ............ $1.25
..$3.85 ............ $2.92
..$6.54 ............ $6.42
..$7.69 ............ $9.42
|
| « Last Edit: Jun 27th, 2009, 10:11pm by Benny » |
IP Logged |
If we want to understand our world or how to change it we must first understand the rational choices that shape it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A bargaining theory problem
« Reply #27 on: Jun 28th, 2009, 7:04am » |
Quote Modify
|
on Jun 27th, 2009, 9:52pm, BenVitale wrote:| You cannot think of a pie. There is a difference between cake and pie cutting. |
|
?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: A bargaining theory problem
« Reply #28 on: Jun 28th, 2009, 7:44am » |
Quote Modify
|
Isn't it a bit odd that there are 2 fair methods that give a different result?
With 4 people, when it comes to choosing a method, everyone but the last passenger would opt for method 2, which the last passenger would consider unfair.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A bargaining theory problem
« Reply #29 on: Jun 28th, 2009, 7:57am » |
Quote Modify
|
on Jun 28th, 2009, 7:44am, Grimbal wrote:| Isn't it a bit odd that there are 2 fair methods that give a different result? |
|
That depends on your definition of fair. How should the benefit each gets be split? should it be split equally, or proportionally, or yet another way?
If everyone pays less than they would otherwise, that might be enough to call it fair. Whether it's also envy-free is another matter.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: A bargaining theory problem
« Reply #30 on: Jun 28th, 2009, 9:49am » |
Quote Modify
|
But what is the benefit? It is the benefit as compared to a hypothetical situation where everybody takes his own cab. That is arbitrary because that situation doesn't happen. If you calculate the benefits/losses as compared to using method 1, then switching to method 2 is a loss for #4.
If #4 insits "It is method 1 or I take my own cab"*, that makes still another baseline and it would be beneficial (but fair?) to everybody to split 4-ways with method 1 rather than 3-ways with method 2.
*and that might well happen if #4 really feels cheated or if he is a shrewd negotiator.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A bargaining theory problem
« Reply #31 on: Jun 28th, 2009, 12:26pm » |
Quote Modify
|
on Jun 28th, 2009, 9:49am, Grimbal wrote:The sum of what people are willing to pay for sharing the cab ride (without knowing what the others will pay) minus the cost of the cab rid.
Any way of distributing the excess where people get anything at all, they'll be better off than what they would settle for. The only hazard to their happiness is envy.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: A bargaining theory problem
« Reply #32 on: Jun 28th, 2009, 12:37pm » |
Quote Modify
|
on Jun 28th, 2009, 7:04am, towr wrote:
I agree that my sentence is not clear enough.
I meant that there's a difference between pie-cutting and cake-cutting ... in 1993, David Gale suggested that there is .
This paper suggests that pie-cutting is much harder than previously thought.
|
|
IP Logged |
If we want to understand our world or how to change it we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: A bargaining theory problem
« Reply #33 on: Jun 28th, 2009, 12:44pm » |
Quote Modify
|
The article of the Wall Street Journal goes on to propose splitting the surplus proportionally, that is, take the savings, and assuming that each person knows his usual fare, then we split the money that is saved.
I was thinking about the problem of carpooling
Owning a vehicle these days costs the average driver just over half a buck per mile ... expenses such as, gas, insurance, oil changes and air fresheners, etc.
So, how would you split gas between passengers of your own car for car trips to the university or place of work?
|
|
IP Logged |
If we want to understand our world or how to change it we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: A bargaining theory problem
« Reply #34 on: Jun 30th, 2009, 4:18pm » |
Quote Modify
|
Let's find another way to cut a cake fairly between 3 people: A, B and C.
Let's define a fair division as a situation where each person believes that he or she receives at least a third of the value of the cake.
When two people want to share a cake fairly, they adopt the "I cut, you choose" method. Assuming this is a fair scheme, let's devise a similar scheme for 3 people and 1 cake. Nobody should get short caked even if the other 2 cooperate.
|
|
IP Logged |
If we want to understand our world or how to change it we must first understand the rational choices that shape it.
|
|
|
Ronno
Junior Member
Gender:
Posts: 140
|
|
Re: A bargaining theory problem
« Reply #35 on: Jul 1st, 2009, 8:38pm » |
Quote Modify
|
A cuts out what he believes to be 1/3 of the pie. B is then given the choice of reducing the piece if he believes it to be more than a third. The same option is then given to C. The piece goes to whoever last modifies it. The rest of the pie is then divided by the "I cut you choose" method between the other two.
This can be further generalized to any number of people.
|
|
IP Logged |
Sarchasm: The gulf between the author of sarcastic wit and the person who doesn't get it..
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: A bargaining theory problem
« Reply #36 on: Jul 2nd, 2009, 8:47am » |
Quote Modify
|
You could use vertical lines.
http://mathworld.wolfram.com/CakeCutting.html
|
|
IP Logged |
If we want to understand our world or how to change it we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: A bargaining theory problem
« Reply #37 on: Jul 3rd, 2009, 1:52am » |
Quote Modify
|
The cake cutting problem is an example of an Optimization problem.
Imagine you and your buddy have a cake and want to divide it between the two of you.
And, imagine that you're having a two-flavor cake, say a half chocolate and half vanilla cake --- a cake that cannot be cut into pieces that have exactly the same composition.
For simplification, let's quantify how much you and your friend want chocolate or vanilla you have
assigned monetary values in dollars to each section of the cake. You have assigned the values $2 for chocolate and $0.75 for vanilla. Your friend has assigned the values $1 for chocolate and $1.25 for vanilla. Thus the chocolate part of the cake is worth $2 to you and $1 to your friend.
Division must be envy-free
Assumption : all players are assumed to be risk-averse: They never choose strategies that might yield them larger pieces if they entail the possibility of giving them less than their maximin pieces.
>Divide the chocolate part of the cake so that each of you receives pieces of the same worth.
>Divide the vanilla part of the cake so that each of you receives pieces of the same worth.
>What fraction of the cake did you receive? What fraction did your friend?
|
| « Last Edit: Jul 3rd, 2009, 1:55am by Benny » |
IP Logged |
If we want to understand our world or how to change it we must first understand the rational choices that shape it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A bargaining theory problem
« Reply #38 on: Jul 3rd, 2009, 2:14am » |
Quote Modify
|
Are you assuming the chocolate is on one side and the vanilla on the other?
A marbled cake is much more interesting.
And of course "so that each of you receives pieces of the same worth" is rather meaningless. Should what I think my piece of cake is worth match what he thinks his piece of cake is worth, or what I think his piece of cake is worth.
And if I say the cake is worth nothing to me, do I get it all?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: A bargaining theory problem
« Reply #39 on: Jul 6th, 2009, 3:39pm » |
Quote Modify
|
on Jul 3rd, 2009, 2:14am, towr wrote:| Are you assuming the chocolate is on one side and the vanilla on the other? |
|
No, that would be too easy to cut.
Quote:
A marbled cake is much more interesting. |
|
I agree.
Quote:
And of course "so that each of you receives pieces of the same worth" is rather meaningless. Should what I think my piece of cake is worth match what he thinks his piece of cake is worth, or what I think his piece of cake is worth.
And if I say the cake is worth nothing to me, do I get it all? |
|
I'll come back later to post my comments + questions.
|
|
IP Logged |
If we want to understand our world or how to change it we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: A bargaining theory problem
« Reply #40 on: Jul 6th, 2009, 3:42pm » |
Quote Modify
|
Chocolate Cake With Vanilla Frosting
That's too easy to cut!
Perhaps this next cake is more interesting from game theory perspective:
Chocolate-Pumpkin Marble Cake
My source
|
| « Last Edit: Jul 6th, 2009, 3:43pm by Benny » |
IP Logged |
If we want to understand our world or how to change it we must first understand the rational choices that shape it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A bargaining theory problem
« Reply #41 on: Jul 6th, 2009, 11:51pm » |
Quote Modify
|
See, in such a case, aside from the value the players place on the different flavours, you need a distribution function for how the two flavours are distributed int he cake. Otherwise you can't find an answer.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: A bargaining theory problem
« Reply #42 on: Jul 7th, 2009, 7:37am » |
Quote Modify
|
More realistic would be that we have a probability distribution, giving the a likelihood for each actual distribution of vanilla and chocolate within the cake.
Of course, that would require an utility function on how much each participant values receiving a certain combination of vanilla and chocolate.
This makes me think that it is not necessary that everybody perceives receiving a larger half for the splitting to be fair. It is enough that everybody believes he got a fair chance (i.e. at least as good as the other's). For instance, if they toss a coin and the winner gets all, one of them receives nothing but would still say it is a fair split. Also, if people decide on a split without knowing the pattern inside the cake, they might be disappointed but still accept it as being fair.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: A bargaining theory problem
« Reply #43 on: Jul 7th, 2009, 12:37pm » |
Quote Modify
|
Excess cake has negative utility - eating too much makes me feel sick, stale cake sucks, and disposing of mouldy cake is decidedly unpleasant... I'd far rather take a smaller "share" and stockpile some goodwill 
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: A bargaining theory problem
« Reply #44 on: Jul 7th, 2009, 5:41pm » |
Quote Modify
|
on Jul 7th, 2009, 12:37pm, rmsgrey wrote:| Excess cake has negative utility - eating too much makes me feel sick, stale cake sucks, and disposing of mouldy cake is decidedly unpleasant... I'd far rather take a smaller "share" and stockpile some goodwill |
|
Yeah, when the utility of something approaches zero, then the rational thing to do is to stop consumming it, because its utility is gone ... but some may be tempted to have lot of it (it's not just cake, it could be any other type of foods, burgers, french fries, pizzas, ...) and one of the excuses is that otherwise it will go to waste. The fact is when the utility equals zero, it has no value to us. It becomes negative if we continue consumming it.
|
| « Last Edit: Jul 7th, 2009, 5:43pm by Benny » |
IP Logged |
If we want to understand our world or how to change it we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: A bargaining theory problem
« Reply #45 on: Jul 7th, 2009, 5:55pm » |
Quote Modify
|
Please read: Divide and choose
Quote:
Analysis of the method becomes more difficult if two players place different values on some subsets of the resource. One commonly used example is a cake that is half vanilla and half chocolate. Suppose Bob likes only chocolate, and Carol only vanilla. If Bob is the cutter and he is unaware of Carol's preference, his optimal strategy is to divide the cake so that each half contains an equal amount of chocolate. But then, regardless of Carol's choice, Bob gets only half the chocolate and the allocation is clearly not Pareto efficient. It is entirely possible that Bob, in his ignorance, would put all the vanilla (and some amount of chocolate) in one larger portion, so Carol gets everything she wants while he would receive less than what he could have got by negotiating.
In 2006 Steven J. Brams, Michael A. Jones, and Christian Klamler detailed a new way to cut a cake called the surplus procedure (SP) that satisfies equitability and so solves the above problem.[2] Both people's subjective valuation of their piece as a proportion of the whole is the same.
If Bob knew Carol's preference and liked her, he could cut the cake into an all-chocolate piece, and an all-vanilla piece, Carol would choose the vanilla piece, and Bob would get all the chocolate. On the other hand if he doesn't like Carol he can cut the cake into slightly more than half vanilla in one portion and the rest of the vanilla and all the chocolate in the other. Carol might also be motivated to take the portion with the chocolate to spite Bob. There is a procedure to solve even this but it is very unstable in the face of a small error in judgement.[3] More practical solutions that can't guarantee optimality but are much better than divide and choose have been devised by Steven Brams and Alan Taylor, in particular the Adjusted Winner procedure (AW).[4][5]
The divide and choose method does not guarantee each person gets exactly half the cake by their own valuations, and so is not an exact division. There is no finite procedure for exact division but it can be done using two moving knives. [6]
A divide and choose scenario is the subject of a Jif peanut butter commercial in which the older brother cuts before his mother tells him that the younger brother will get to choose. As a result, the younger brother gets a noticeably larger slice of the sandwich.
|
|
To be continued
|
| « Last Edit: Jul 7th, 2009, 5:56pm by Benny » |
IP Logged |
If we want to understand our world or how to change it we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: A bargaining theory problem
« Reply #46 on: Jul 8th, 2009, 12:40am » |
Quote Modify
|
We all value things differently.
Suppose that we don't have agreement on how to cut the cake.
Then, we need to turn to market valuation. That means, we sell the cake (at fair market value) and divide the cash proceeds. Then, each of us could buy smaller cakes with or without frosting.
Well, since I'm not too crazy about the frosting, I'll just buy a smaller chocolate cake without frosting.
To be continued
|
| « Last Edit: Jul 8th, 2009, 12:41am by Benny » |
IP Logged |
If we want to understand our world or how to change it we must first understand the rational choices that shape it.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: A bargaining theory problem
« Reply #47 on: Jul 8th, 2009, 6:23am » |
Quote Modify
|
Changing it to money is the easy way out. But it still doesn't work.
You go from an optimal sharing of a cake between 2 people to an optimal sharing of a cake and some money between 3 people. Because below some price, one or both participants might prefer the cake. So you don't really improve things.
And I for instance prefer some currencies to others. Some I need to go to the bank and change it with a small loss. So the participants might not agree in which currency the cake should be evaluated.
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: A bargaining theory problem
« Reply #48 on: Jul 9th, 2009, 10:52am » |
Quote Modify
|
on Jul 8th, 2009, 6:23am, Grimbal wrote:Changing it to money is the easy way out. But it still doesn't work.
You go from an optimal sharing of a cake between 2 people to an optimal sharing of a cake and some money between 3 people. Because below some price, one or both participants might prefer the cake. So you don't really improve things.
And I for instance prefer some currencies to others. Some I need to go to the bank and change it with a small loss. So the participants might not agree in which currency the cake should be evaluated. |
|
Yes, it is an easy way out .... and, market transactions are not free, as you pointed out ... there's almost always a transaction cost.
that was Plan B.
I'll come back later to continue the discussion.
|
|
IP Logged |
If we want to understand our world or how to change it we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: A bargaining theory problem
« Reply #49 on: Jul 17th, 2009, 12:44am » |
Quote Modify
|
We know that we can cut a cake thanks to the Intermediate Value Theorem... as I've mentioned already on another thread.
This theorem states that for a function f that is continuous on the interval [a, b], if there exists a value d between f(a) and f(b), then there is a value of c in (a, b) such that f(c) = d. For example, if someone was 5 feet tall last year and is now 5 feet 2 inches tall, at some point that person was 5 feet 1 inch tall. With the same reasoning, there is at least one place a person can cut a cake to create two pieces of equal value.
The trick, of course, is to find that place. This theorem guarantees that a value exists, but it does not show how to find it.
But, here, we are not interested in solving this problem using Calculus or Algebra. We want to use Game Theory.
Similarly to the Jif Peanut Butter Commercial
We have: 1 cake and 2 players.
We ask, "can we cut fairly this cake?"
The answer is "yes."
One of the player would have to cut the cake using the Moving knife procedure in a such a way that each player will believe that his half of the cake is bigger than the other player's half.
Read about:
Moving-knife procedure
Stromquist moving-knife procedure
|
| « Last Edit: Jul 17th, 2009, 12:45am by Benny » |
IP Logged |
If we want to understand our world or how to change it we must first understand the rational choices that shape it.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print