Conference rusure::math

>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.

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?

    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.

No, the reason that a fancy linear programming solution wasn't
suggested is because it's not needed.  There is a 'falacy' in .0:

>  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.

The 'falacy' is in the last sentence.  The cost (to you) of the plans are not
c3 � adjustment3 and c4; the costs are c3 � adjustment3 and c4 � adjustment4.


Consider the cost matrix:

	Plan1		Plan2
me	10		100
you	 2		  2

Assume that 'me' and 'you' benefit equally from the alternative plans,
and so decide to evenly split the costs between us.  If plan1 is adopted,
then you should pay me an additional 4 (dollars):

	Plan1		Plan2
me	10-4		100
you	 2+4		  2

Now you argue that you're paying more than you would've had we adopted plan2.
This is not quite true; if plan2 were adopted, you'd have to pay me *more*
to share the costs equally:

	Plan1		Plan2
me	10-4		100-49
you	 2+4		  2+49


Which plan should be adopted?  Well, because we agreed to split the
costs between us, each of us will pay 1/2 of the total cost:

	Plan1		Plan2
me	10-4		100-49
you	 2+4		  2+49
total	----		------
cost    12+0		102+ 0

The total cost is independent of the 'cross-payments' we make between
ourselves; it is simply the sum of the original costs.  Thus, to minimize
the amount that you have to pay, you should prefer the plan that minimizes
the total cost (since you'll pay 1/2 of the total cost).  Deciding which
plan minimizes the total cost is easy -- sum the costs for each plan, and
take the plan having the smallest sum.

Having decided on the plan, the 'cross-payments' are easily computed.
It simply adjusts each of our costs to be 1/2 the total cost of the plan.

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	
                     

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?

    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

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 !