wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> A bargaining theory problem
        
(Message started by: BenVitale on Jun 20^th, 2009, 11:31am)

Title: A bargaining theory problem
Post by BenVitale on Jun 20^th, 2009, 11:31am

I submit to this community a bargaining theory problem :

$400 is to be divided among creditors who claim $100, $200, and $300.

They are awarded $50, $125, and $225.

Why is this consistent?

Title: Re: A bargaining theory problem
Post by towr on Jun 20^th, 2009, 2:46pm

Beats me. You'd think that with A+B together having the same sized claim as C, they should be able to secure an equal share to C. And if they'd split that $200 proportionally, they'd both be better of than they are now ($67 > $50, $133 > $125), so C clearly hasn't offered either of them anything to dissuade them from cooperating.
This doesn't seem like a division they should agree to.

Title: Re: A bargaining theory problem
Post by BenVitale on Jun 21^st, 2009, 12:57pm

I found the explanation in this document (http://www.landsburg.com/ptalmud.pdf) which did surprise me.

Title: Re: A bargaining theory problem
Post by Ronno on Jun 21^st, 2009, 10:45pm

I have read about this division elsewhere. Although it is consistent, (in the sense that any subset of the claims and awards determine the same division on application of the rules) it does not mean that it is acceptable to the creditors as towr points out.
There are more (perhaps an infinite number) equally consistent solutions to the problem (I can think of at least two other) and I don't think there is an unique "fair" division process.

Title: Re: A bargaining theory problem
Post by towr on Jun 22^nd, 2009, 2:12am

I can't really say I find the solution all that consistent, precisely for the reason I already stated.
A could sell his claim to B, who'd then have a $300 claim, equal to C's; and so the Talmudic solution would then also give them equal shares. Or suppose C has three claims of $100, because he gave three different loans; then he should suddenly get much less.
You will need pretty complicated rules to avoid this. It just doesn't add up (quite literally).

How many solutions can you think up there are consistent under this constraint? The only one I see is proportional division.

Title: Re: A bargaining theory problem
Post by Grimbal on Jun 22^nd, 2009, 4:41am

The article lays down the principle that "If A claims half and B claims all, one half is claimed by A and B and the other half is claimed only by B. Therefore A gets 1/4 and B gets 3/4."

But according to the same principle, if A claims half and B claims half, the first half is claimed by A and B and the other half is unclaimed. So A and B should get 1/4 each. Clearly, it doesn't make sense that A and B claim the same half. A and B's claims should be arranged to not overlap.

So, if now A claims 1/3, B claims 2/3 and C claims 3/3, It would be unreasonable to assume that A and B claim the same 1/3 while leaving another 1/3 undisputed.

I would say the goal of such a definitive rule is not so much fairness as to settle conflicts. The less people can argue, the faster they go on and proceed to more constructive activities.

You could argue that the proportional split isn't totally fair either. Someone who lends $200 knows that the 2nd $100 are a bit more risky than the first $100. It could be argued that he was ready to take more risks and should receive less back.

Another idea of fairness would be to pay back the debts in the order they were created.

Title: Re: A bargaining theory problem
Post by towr on Jun 22^nd, 2009, 5:38am

on 06/22/09 at 04:41:55, Grimbal wrote:

You could argue that the proportional split isn't totally fair either. Someone who lends $200 knows that the 2nd $100 are a bit more risky than the first $100. It could be argued that he was ready to take more risks and should receive less back.

That does, incidentally, avoid the coalition problem, since pooling debts would decrease what you get together.
But it just implies you should use proxies to lend someone one dollar at a time. Because then those proxies have the (proportionally) highest claims, and you can recuperate more of the debt than if you lent it directly. (Granted, there's some cost involved there, like administration and of course those proxies will need some compensation as well.)

Quote:

Another idea of fairness would be to pay back the debts in the order they were created.

That requires good administration though, otherwise it just opens up another line of argument.

Title: Re: A bargaining theory problem
Post by Ronno on Jun 22^nd, 2009, 6:08am

How about this division:
You keep distributing the money equally until the one with lowest claim is fully credited. Then the rest of the money goes to the others in the same way.
For example, for A, B, C, A gets 100, B & C get 150 each.

Title: Re: A bargaining theory problem
Post by Grimbal on Jun 22^nd, 2009, 6:14am

Honestly, I also prefer the proportional division.

Title: Re: A bargaining theory problem
Post by BenVitale on Jun 22^nd, 2009, 11:28am

on 06/22/09 at 02:12:15, towr wrote:

......
The only one I see is proportional division.

on 06/22/09 at 06:14:19, Grimbal wrote:

Honestly, I also prefer the proportional division.

And thank you Ronno for your input.

Fair division is a concept that depends as much on logic as it does on social custom ... There might not be one correct answer.

To see why, consider the following 3 situations that present very different solutions:

Suppose I owe debts of $100, $200, and $300 to you guys

Ronno -----> $100,
Grimbal ---> $200
Towr ------> $300

But I have less than $600, say $400

(1) Suppose that we are all related, we could be brothers or cousins ... and I don't have
$600 to pay my debts to you

(2) Suppose we are partners and running for example, a limited partnership

(3) Suppose we go out for a dinner and each of us order food items on the menu at the
restaurant with promises to pay, and then ... here comes the stinkin' diaper situation:
how are we going to split the bill?

In each case, we could have a different scheme to split the money.

I don't think there's just one way, or a right way to approach these types of problems.

That's why we end up with conflicts, litigations, lawsuits everyday ... Lawyers must be very happy people ... and I must be in the wrong racket.

Disputes, conflicts are a matter of perspectives.

See other similar problems (http://bbs.cenet.org.cn/uploadImages/20034317262972259.pdf) :

- The disputed garment problem
- Sharing the Cost of a Runway
- The Marriage Contract Problem
- The Bankruptcy Game
- Some Lawyer’s Arguments
- Nash’s Bargaining Game

Title: Re: A bargaining theory problem
Post by Obob on Jun 22^nd, 2009, 1:42pm

In current financial matters, these types of problems have come up. For instance, in the collapse of the Madoff pyramid scheme, I seem to recall investors were repaid up to the first million of their investment, and then further claims were divided proportionally from any remaining funds.

Title: Re: A bargaining theory problem
Post by BenVitale on Jun 22^nd, 2009, 2:16pm

on 06/22/09 at 13:42:43, Obob wrote:

Do you have the details?
I thought that Madoff's direct customers would be covered by Securities Investor Protection Corp. , which typically covers up to $500,000 in losses.

Here's a Physical Interpretation in part #4

http://dept.econ.yorku.ca/~jros/docs/AumannGame.pdf

Title: Re: A bargaining theory problem
Post by towr on Jun 22^nd, 2009, 10:58pm

on 06/22/09 at 14:16:40, BenVitale wrote:

Here's a Physical Interpretation in part #4

http://dept.econ.yorku.ca/~jros/docs/AumannGame.pdf

That's the same thing as in that other article, except it's drawn differently.

Title: Re: A bargaining theory problem
Post by BenVitale on Jun 23^rd, 2009, 3:46pm

on 06/22/09 at 22:58:33, towr wrote:

That's the same thing as in that other article, except it's drawn differently.

Oh, yeah ... sorry.

Title: Re: A bargaining theory problem
Post by BenVitale on Jun 24^th, 2009, 9:14am

Another example that I enjoy is the problem of splitting up rent.

It's the old roommate/rent Dilemma (http://freakonomics.blogs.nytimes.com/2009/05/08/our-daily-bleg-the-old-roommaterent-dilemma/)

Quote:

Two friends — a merchandising analyst and a law student — and I are attempting to split up rent of a three-bedroom apartment with two common bathrooms. All rooms have their pros and cons, with the major differentiators being closet space and sheer square footage:

Room # 1 ..... 15 ft. x 15 ft. = 225 sq.ft.
Room # 2 ..... 12 ft. x 12 ft. = 144 sq.ft.
Room # 3 ..... 20 ft. x 8 ft. = 160 sq.ft.

(Room # 1) - (Room # 2) = 225 - 144 = 81 sq.ft.
(Room # 1) - (Room # 3) = 225 - 160 = 65 sq.ft.

Rent is $2,200 per month and the apartment is approximately 2,200 square feet.

Simple math shows one would pay $1 per sq.ft.

That goes out the window with the ranking intangibles, and the fact that no one necessarily
wants the big room.

The roommates threw out these prices:

Room # 1: $800/month
Room # 2: $710/month
Room # 3: $690/month

over the course of a year
Room # 1: $800/month X 12 = $9,600
Room # 2: $710/month X 12 = $8,520
Room # 3: $690/month X 12 = $8,280

Differences show
9,600 - 8,520 = $1,080
9,600 - 8,280 = $1,320

How do you recommend solving this situation?

[proposed suggestions are at the bottom of the document]

Title: Re: A bargaining theory problem
Post by towr on Jun 24^th, 2009, 3:50pm

on 06/24/09 at 09:14:08, BenVitale wrote:

How do you recommend solving this situation?

Maybe turn it into a bidding problem instead.

Title: Re: A bargaining theory problem
Post by BenVitale on Jun 24^th, 2009, 10:23pm

on 06/24/09 at 15:50:59, towr wrote:

Maybe turn it into a bidding problem instead.

how we can model this situation as a game?
Do you agree with these prices:
Room # 1: $800/month
Room # 2: $710/month
Room # 3: $690/month

Would you like to start the opening bid for the better room? In your opinion, which room is the better room? How to allocate the rights to joint furniture purchases? groceries?

Would you propose a bid on the good room with chores -- meaning the person who is willing to do the most domestic chores to compensate wins the auction and the room?

Bidding may look like as a fair system, but it presents a problem : The winner's curse (http://en.wikipedia.org/wiki/Winner's_curse)

Winner’s curse was originally studied in the laboratory by Bazerman and Samuelson (1983) using “the jar game”, in which participants bid on a jar full of change.

Bazerman and Samuelson's experiment : bid on a jar of nickels

The winner's curse is frequently observed in auctions: The person who bids the most and wins
the auction may ultimately regret the bid since it often exceeds the value of the object being auctioned.

It's when we get the feeling in our stomach when we realize that we paid much more for something that it is actually worth. This is a bad enough situation when it happens every once in a while.

The trick is to recognize this problem and avoid it.

Read about The Winner’s Curse in The bidding game (http://www.beyonddiscovery.org/content/view.article.asp?a=3681)

Quote:

Why did the oil companies -— which on average are pretty good at guessing how much oil lies buried in a tract -— seem so often to pay more than the tract turned out to be worth?

As an analogy, imagine that a jar of nickels is being sold in a sealed first-price auction. The jar holds $10 in nickels, but none of the bidders know that; all they can see is how big the jar is. The players independently estimate how much the jar is worth. Maybe Alice guesses right, while Bob and Charlie guess the jar holds $8 and $12, respectively. Diane and Ethel are farther off, putting the value at $6 and $14, respectively.

If all the bidders bid what they think the jar is worth, Ethel will win, but she’ll pay $14 for $10 in nickels—what economists call the “winner’s curse.” Even if the jar is sold in a second-price auction, she will still overpay. Although on average the bidders are correct about how much money is in the jar, the winner is far from correct; she is the one who has overestimated the value the most ...

Title: Re: A bargaining theory problem
Post by towr on Jun 25^th, 2009, 12:25am

on 06/24/09 at 22:23:09, BenVitale wrote:

Bidding may look like as a fair system, but it presents a problem : The winner's curse (http://en.wikipedia.org/wiki/Winner's_curse)

That only occurs in some bidding schemes, you can easily avoid it. I forgot what it's called, but if you use a closed bidding system, and the winner pays the second highest bid, then people should not overbid.

Quote:

how we can model this situation as a game?
Do you agree with these prices:
Room # 1: $800/month
Room # 2: $710/month
Room # 3: $690/month

Of course not, it depends on how much people value the rooms.

Quote:

Would you like to start the opening bid for the better room?

I'd use a closed bidding system, so there isn't an opening bid.
I haven't really thought about the specific scheme. I suspect it would work best if everyone presents a closed bid for all the rooms at once, i.e. how much they're willing to pay to end up in each room.
One problem, however, is that the solution might not necessarily add up to the total rent; depending on the details. As I said, I haven't really thought it out yet.

Quote:

In your opinion, which room is the better room?

I'd have to see them. But the apartment is probably way too expensive. The rooms are twice as expensive as the one I have, and I have everything (utilities, maintenance etc) included.

Quote:

How to allocate the rights to joint furniture purchases?

"Rights to joint furniture purchases"? You mean like how long they can sit on the couch? WTF?

Quote:

groceries?

If they eat together, I'd say split it, or alternate. If someone has special dietary needs/habits, then it could reasonably be separate. And if someone wants to have a claim on an item of food, obviously they need to pay for it themselves and label it accordingly.

[quote]Would you propose a bid on the good room with chores -- meaning the person who is willing to do the most domestic chores to compensate wins the auction and the room?[quote]I wouldn't. But it's an alternative if the people involved want it.
You can use bidding to divide chores, so each gets those chores best suited to him. One person might like cooking more than vacuuming, the other might like vacuuming more than cooking. So you can maximize satisfaction in domestic life by arranging the chores accordingly.

Title: Re: A bargaining theory problem
Post by BenVitale on Jun 25^th, 2009, 10:20am

Yes, the winner's curse does not apply here, because it's a private bid ... independent of the market value.

The rent that must be paid is $2,200 per month ... that's a fixed price, a market value.

When the 3 roomates threw out the following prices

Room # 1: $800/month
Room # 2: $710/month
Room # 3: $690/month

That was their first bid.

Title: Re: A bargaining theory problem
Post by BenVitale on Jun 25^th, 2009, 12:39pm

It also depends on your roommates ... say you and your roommates are all math major students ... and all of you are big fans of Game Theory. And you guys get together discussing this problem before getting an apartment or a 3-bedroom house.

The rent is $2,200 per month not including utilities and such.
A 3-way split (= $2,200/3) would be unfair since the rooms have different sizes.

As for utilities and other matters, they are divided up individually.

How do you like the following scheme:

Rent is $2,200 per month and the apartment is approximately 2,200 square feet. That means one would pay $1 per sq.ft.

We know that:
Room # 1 ..... 15 ft. x 15 ft. = 225 sq.ft.
Room # 2 ..... 12 ft. x 12 ft. = 144 sq.ft.
Room # 3 ..... 20 ft. x 8 ft. = 160 sq.ft.

Total area = 529 sq.ft.
Remaning area = 2200 - 529 = 1671 sq.ft.
Split in 3: 1671/3 = 557

Rent for room #1: (225 sq.ft. * $1) + (557 sq.ft. * $1) = $782
Rent for room #2: (144 sq.ft. * $1) + (557 sq.ft. * $1) = $701
Rent for room #3: (160 sq.ft. * $1) + (557 sq.ft. * $1) = $717

Title: Re: A bargaining theory problem
Post by towr on Jun 25^th, 2009, 12:51pm

Do you think a room of 1 ft x 300 ft would be more desirable than one that's 10 ft x 10 ft, just because it has three times the surface?
And what about view? How close they are to the bathroom? How easily you can get to a fire escape? How resilient the door is against zombie attacks? People have different priorities and can value the same thing differently. I would think that's one thing you'd need to find out first.

I'm not going to like any division that doesn't take people's individual valuation into account.

Title: Re: A bargaining theory problem
Post by Eigenray on Jun 25^th, 2009, 12:58pm

You should take advantage of the fact that different people will value a room differently. If everybody agrees on how much each room is worth there is no problem. Otherwise, each person makes a list of how much the rooms are worth to them, so that the sum of their values is equal to the total rent. Then assign the rooms to maximize the sum of the values chosen. This will be strictly larger than the rent due, so you can scale back the payments and everybody wins.

Title: Re: A bargaining theory problem
Post by BenVitale on Jun 26^th, 2009, 11:14am

on 06/25/09 at 12:51:52, towr wrote:

I agree with you ... you're right to raise these questions ... we don't have much info on the location of this apartment, about these rooms ... we only know about the rent and the surface areas of these rooms. I've worked with what we got.

Title: Re: A bargaining theory problem
Post by BenVitale on Jun 26^th, 2009, 11:25am

on 06/25/09 at 12:58:39, Eigenray wrote:

A bid was offer in the story. So, I offered a bid ... naturally, my offer is open for negotiations.

We see these problems all too often to the delight of mathematicians, and math students (myself included) ... attaching numerical values to human feelings is the first obstacle whenever we need to divide a finite resource in a fair, envy-free manner. The second obstacle is to find a workable algorithm, formula to produce such a division.

Problems such the one that started this thread ... and other problems, namely:

(1) Cake-cutting problem, see in Wolfram (http://mathworld.wolfram.com/CakeCutting.html) and in wiki (http://en.wikipedia.org/wiki/Fair_division)

Here we ask: Can a cake be cut into 3 pieces and allocated so that every person believes he or she
receives the most desirable piece?

(2) How to split a shared cab ride? Very carefully, say economists (http://online.wsj.com/public/article/SB113279169439805647-jP1H4pfk3i2ACypy26ghtvTlJ30_20061207.html)

Here, the story is: 3 economists get into a cab. They're each getting off at different places along the route. How should they split the bill?

I see a parallel between all these wonderful problems.

Title: Re: A bargaining theory problem
Post by towr on Jun 26^th, 2009, 2:31pm

on 06/26/09 at 11:25:02, BenVitale wrote:

Here we ask: Can a cake be cut into 3 pieces and allocated so that every person believes he or she
receives the most desirable piece?

The answer is yes, and interestingly it only gets easier as they value the various elements of the cake more differently.

Quote:

Here, the story is: 3 economists get into a cab. They're each getting off at different places along the route. How should they split the bill?

I think not looking like a penny-pinching ass might be a good investment in future social relations; so you could do worst than paying more than your "fair share".
I mean, really, a $10 cab ride is not exactly going to drive you into bankruptcy as a well-paid economist. I'd happily let A ride for free if I was B or C, and as A I'd happily pay the entire fee up to that point if they hadn't suggested otherwise. As B, again, I'd happily pay the fee up to my stop; and as C as well, presuming the cab ride wasn't absurdly much longer; and even then. I'd be happy to have good company on the way; and if they're not good company I'd take another cab.

Title: Re: A bargaining theory problem
Post by BenVitale on Jun 27^th, 2009, 9:52pm

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." (http://www.ams.org/notices/200611/fea-brams.pdf)

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

Title: Re: A bargaining theory problem
Post by BenVitale on Jun 27^th, 2009, 10:09pm

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 (http://everything2.com/index.pl?node_id=739831)

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

Title: Re: A bargaining theory problem
Post by towr on Jun 28^th, 2009, 7:04am

on 06/27/09 at 21:52:00, BenVitale wrote:

You cannot think of a pie. There is a difference between cake and pie cutting.

Title: Re: A bargaining theory problem
Post by Grimbal on Jun 28^th, 2009, 7:44am

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.

Title: Re: A bargaining theory problem
Post by towr on Jun 28^th, 2009, 7:57am

on 06/28/09 at 07:44:56, 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.

Title: Re: A bargaining theory problem
Post by Grimbal on Jun 28^th, 2009, 9:49am

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.

Title: Re: A bargaining theory problem
Post by towr on Jun 28^th, 2009, 12:26pm

on 06/28/09 at 09:49:54, Grimbal wrote:

But what is the benefit?

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.

Title: Re: A bargaining theory problem
Post by BenVitale on Jun 28^th, 2009, 12:37pm

on 06/28/09 at 07:04:35, 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 (http://ideas.repec.org/p/pra/mprapa/12772.html) suggests that pie-cutting is much harder than previously thought.

Title: Re: A bargaining theory problem
Post by BenVitale on Jun 28^th, 2009, 12:44pm

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?

Title: Re: A bargaining theory problem
Post by BenVitale on Jun 30^th, 2009, 4:18pm

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.

Title: Re: A bargaining theory problem
Post by Ronno on Jul 1^st, 2009, 8:38pm

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.

Title: Re: A bargaining theory problem
Post by BenVitale on Jul 2^nd, 2009, 8:47am

You could use vertical lines.

http://mathworld.wolfram.com/CakeCutting.html

Title: Re: A bargaining theory problem
Post by BenVitale on Jul 3^rd, 2009, 1:52am

The cake cutting problem is an example of an Optimization (http://en.wikipedia.org/wiki/Optimization_%28mathematics%29) 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?

Title: Re: A bargaining theory problem
Post by towr on Jul 3^rd, 2009, 2:14am

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?

Title: Re: A bargaining theory problem
Post by BenVitale on Jul 6^th, 2009, 3:39pm

on 07/03/09 at 02:14:10, 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.

Title: Re: A bargaining theory problem
Post by BenVitale on Jul 6^th, 2009, 3:42pm

Chocolate Cake With Vanilla Frosting

http://www.clipartguide.com/_small/1386-0903-1511-3326.jpg

That's too easy to cut!

Perhaps this next cake is more interesting from game theory perspective:

Chocolate-Pumpkin Marble Cake

http://libertypark.files.wordpress.com/2008/11/marble-cake-su-633351-l.jpg

My source (http://images.google.ca/images?sourceid=navclient&hl=en-GB&rlz=1T4GZEZ_en-GB&q=picture+of+a+marbled+cake&um=1&ie=UTF-8&ei=uXtSSqeUI5GoswOV_fmFBw&sa=X&oi=image_result_group&ct=title&resnum=1
)

Title: Re: A bargaining theory problem
Post by towr on Jul 6^th, 2009, 11:51pm

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.

Title: Re: A bargaining theory problem
Post by Grimbal on Jul 7^th, 2009, 7:37am

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.

Title: Re: A bargaining theory problem
Post by rmsgrey on Jul 7^th, 2009, 12:37pm

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 :)

Title: Re: A bargaining theory problem
Post by BenVitale on Jul 7^th, 2009, 5:41pm

on 07/07/09 at 12:37:13, rmsgrey wrote:

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.

Title: Re: A bargaining theory problem
Post by BenVitale on Jul 7^th, 2009, 5:55pm

Please read: Divide and choose (http://en.wikipedia.org/wiki/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 (http://en.wikipedia.org/wiki/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) (http://en.wikipedia.org/wiki/Surplus_procedure) 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

Title: Re: A bargaining theory problem
Post by BenVitale on Jul 8^th, 2009, 12:40am

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

Title: Re: A bargaining theory problem
Post by Grimbal on Jul 8^th, 2009, 6:23am

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.

Title: Re: A bargaining theory problem
Post by BenVitale on Jul 9^th, 2009, 10:52am

on 07/08/09 at 06:23:26, Grimbal wrote:

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.

Title: Re: A bargaining theory problem
Post by BenVitale on Jul 17^th, 2009, 12:44am

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 (http://www.youtube.com/watch?v=AdYFVN35h5w)

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 (http://en.wikipedia.org/wiki/Moving-knife_procedure)

Stromquist moving-knife procedure (http://en.wikipedia.org/wiki/Stromquist_moving-knife_procedure)