[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

605.0. "Cost redistribution strategies among cooperating participants" by EAGLE1::BEST (R D Best, Systems architecture, I/O) Wed Oct 29 1986 21:00

  Note: I haven't solved this yet (there may be many different fair payback
strategies), but I have some ideas how to proceed.  I'd greatly
appreciate any strategies or algorithms along with the rationale for
why the strategy is fair.

Cost redistribution among cooperative participants
__________________________________________________
  Suppose you and I are planning a project which will incur for each of
us a cost that is a function of who we are and what the plan is:

Cost matrix:

	Plan1		Plan2
me	c1		c2
you	c3		c4

  We'd like to arrange to choose the scheme that yields the lowest global
cost (i.e. choose plan1 if c1 + c3 < c2 + c4.)

  Let's say that we choose plan1.

  Unfortunately, it may work out that, for the chosen plan, you wind up
paying more than me.  To be fair, it seems that I should pay you a certain
amount of money to make it worth your while to go along with plan1.

  But if I have to pay you enough that my cost rises above c4, then it no
longer makes sense for me to cooperate with plan1.  Also, neither one of
us likes to pay more than we have to.

  What are some fair strategies for redistributing the costs given the
constraint that we both agree to choose the plan with the least global
cost ?  In other words, how much should I pay you to participate in
plan1 ?

  It seems that the problem above generalises to an n by m matrix with
n participants and m plans.  How can a square matrix of size
n by n whose elements give the amount participant p should pay participant
q for taking part in the minimum global cost plan be derived from the cost
matrix ?  The same constraint as before holds: we agree to choose the
minimum global cost plan.

			/R Best
T.RTitleUserPersonal
Name
DateLines
605.13rd parties are not all badMODEL::YARBROUGHThu Oct 30 1986 11:3227
>Cost matrix:
>
>	Plan1		Plan2
>me	c1		c2
>you	c3		c4
>
>  We'd like to arrange to choose the scheme that yields the lowest global
>cost (i.e. choose plan1 if c1 + c3 < c2 + c4.)
>
>  Let's say that we choose plan1.
>
>  Unfortunately, it may work out that, for the chosen plan, you wind up
>paying more than me.  To be fair, it seems that I should pay you a certain
>amount of money to make it worth your while to go along with plan1.
>
>  But if I have to pay you enough that my cost rises above c4 [I think you
>mean c2; c4 is the other guy's cost], then it no longer makes sense for me
>to cooperate with plan1.  Also, neither one of us likes to pay more than we
>have to. 

But if you agree on plan 2, then an equitable cost division is going to be 
still worse. In other words, if your adjusted cost for plan 1 is greater 
than c2, then the other guy's c4 must be way out of line, so that an 
equitable adjustment for the c2-c4 cost will be more expensive for both
of you than the plan 1 adjustment. 

Sounds like it may be worth the money to agree to hire an arbiter.
605.2CLT::GILBERTeager like a childThu Oct 30 1986 21:1123
Right.  If the payments between the two parties are considered in
the cost to each party, the plan with smallest (summed) cost should
be chosen.

Suppose there are multiple parties and multiple plans, and each plan
has different benefits to the various parties.  For example:

	  Plan1     Plan2
PartyA   cA1 bA1   cA2 bA2
PartyB   cB1 bB1   cB2 bB2

Here, too, the plan that maximizes the sum of (Benefits-Costs) should
be chosen, and cross-player payments can redistribute the costs, possibly
in proportion to each player's benefits.


This reminds me of an old problem from the classic "Mathematical Snapshots".

Three brothers are to divide a rectangular plot of ground between themselves,
with vertical (North/South?) dividers.  However, the land varies in quality,
so some sections may be preferred over others, and the brothers may disagree
in their assesments of the land.  How can this be arbitrated so each brother
will be satisfied that he has received at least his 1/3 share of the land?
605.3Why No Math?CLOSUS::TAVARESJohn--Stay low, keep movingFri Oct 31 1986 13:266
    When I first saw this one, I thought you folks would come up with
    a generalized solution using linear programming.  Is the reason
    why linear programming won't work because the shares of each
    participant can't be put in equation form?  That is, the choice
    of "quality" is a judgement call, and as such subject only to
    negotiation? Hope I'm making my question clear.
605.4CLT::GILBERTeager like a childFri Oct 31 1986 14:1357
605.5got any more "Snapshots"?VINO::JMUNZERFri Oct 31 1986 14:2623
Re .2, last paragraph:

Require each brother to set boundaries of "thirds" that seem fair to him
(is this requirement permissible?); e.g.

		|AAAAAAAA-AAAAAA-AAAAAAA|
	West	|BBBBBBB-BBBBBB-BBBBBBBB|	East
		|CCCCCC-CCCCCCCC-CCCCCCC|

Give the Western piece to the brother who picked the Westernmost
Western/middle boundary (C).

Then give the middle piece to the remaining brother who picked the 
Westernmost Eastern/middle boundary (B).

Then give the Eastern piece to the remaining brother (A):

	West	|CCCCCC-BBBBBBB-AAAAAAAA|	East

(This extends to more than three siblings.)

John	
                     
605.6Another division problem from Mathematical SnapshotsCLT::GILBERTeager like a childFri Oct 31 1986 16:5035
From "Mathematical Snapshots", 1960 edition, page 68:

    "There is another problem of division encountered in economic life: the
division of indivisible objects like houses, domestic animals, pieces of
furniture, cars, and works of art.  If for instance, an inheritance composed of
a house, a mill, and a car has to be divided among four inheritors A, B, C, D
participating in equal shares, the division is generally made by a sworn
appraiser who deetrmines the values of the objects so that the inheritors can
choose the objects, and, if they agree, in principle, satisfy by payments in
cash the mutual claims arising from the differences in value. 

    This procedure has many inconveniences connected with the determination of
the objective value of things by an official appraiser or by a court of
justice.  It is possible to make a fair division without appealing to them: 

    An umpire, who has to act only as a sort of automaton to keep records and
make computations, summons the inheritors to write down their estimates of the
objects.  They are not supposed to discuss the matter among themselves but
every one of them is allowed to be helped by friends and experienced persons.
Thus a table of values is put down by the umpire: 

		   A	   B       C       D
	House	$6,000 $10,000  $7,000  $9,000
	Mill	 3,000   2,000   4,000   2,000
	Car	 1,500   1,200   1,000   1,000
..."

	[here, I've omitted the solution to the problem]

    "Thus everybody will finally get more than his due share of the inheritance,
the value of the total and of the objects given to him being estimated being
estimated according to his own valuation."


Alright, how did the umpire do it?
605.7BEING::POSTPISCHILAlways mount a scratch monkey.Fri Oct 31 1986 19:2617
    There is a fundamental difference between the division problems and the
    cooperation problem.  In the division problems, the people own equal
    shares of the property being divided or otherwise have some reason for
    getting equal shares -- "fairness" is already defined.
    
    In the cooperation problem, there is no ownership or other way to
    define "fairness".  If one party is stubborn and holds out for more
    money, they may be able to get more -- and there is no reason stated
    why they should not do that.  In the real world, and assuming people
    were rational and intelligent, the willingess of each person to pay or
    receive various amounts for various plans would actually depend upon
    external factors.  For example, somebody with another source of income
    would be more willing to take a risk of losing money if the expected
    gain is large enough.
    
    
    				-- edp
605.8Simpler than I thought at first glanceEAGLE1::BESTR D Best, Systems architecture, I/OFri Nov 07 1986 13:3510
re .1-.4:

  I see.  This problem is much simpler than I realised at first glance.
The best strategy is always to choose the minimum global cost plan and
split the difference.  I had also forgotten to factor in the effect of
relative benefit to each party.  Equal benefit seems a reasonable assumption
for a lot of situations.  If the benefits are not equal, we should use a
different matrix where the elements are ( benefit[i,j] - cost[i,j] ).
Thanks !