! Allocation of objects to several parties/participants.
  Given a number of participants(parties) each with their
own objective or utility function, we want to
find a solution to a shared problem so that the smallest
utility is maximized, with a little bit of weight to
minimizing the maximum, to reduce inequality.
  The specific shared problem is to allocate a number
of discrete items from an inheritance to the heirs, with
each heir having her own set of values for each of the
items to be allocated;
!Keywords: Fair allocation, Minimax, Assignment problem,
    Inheritance, Allocation, Goal programming, Pareto optimal,
  party: x;
  txp( thing,party) : value, y;
DATA: BigM = 9999; ! A number > any possible allocation; thing = Photos, Silver, Tables, Books HiFi; ! The parties receiving the allocations; party = Tom Dick Harry Joan; value = !Photos; 21 15 35 10 !Silver; 19 19 5 11 !Tables; 35 10 16 37 !Books; 15 37 5 25 !HiFi; 10 19 39 17 wgtmx = 0.1; ! Weight applied to minimizing the maximum; ! Do not make wgtmx too large, - this may give a solution that is equitable but not Pareto optimal; ! Comments on this data set. Notice that each person's valuations sum to 100. Thus, if all had identical valuations, the average that each would get would = 25. A good solution is: Tom Dick Harry Joan !Photos 21 !Silver 19 !Tables 37 !Books 37 !HiFi 39 Total 40 37 39 37; ENDDATA SUBMODEL MINGAP: ! Variables: x(j) = the utility (more is better) achieved by party j; ! Maximize the minimum allocation, but give a little weight to minimizing the maximum, i.e., improve equity; MAX = xmin - wgtmx*xmax; ! Constraints on permissible allocations; ! Assign object i to exactly one party; @FOR(thing(i): @SUM( party(j): y(i,j)) = 1; ); @FOR(txp(i,j): @BIN(y(i,j))); ! Compute x(j) = utility of pary j; @FOR( party(j): x(j) = @SUM(thing(i): value(i,j)*y(i,j)); xmax >= x(j); ! Max allocated to anyone; xmin <= x(j); ! Min allocated to anyone; ); ENDSUBMODEL
CALC: N = @SIZE(party); @SET( 'TERSEO',2); ! Output level (0:verb, 1:terse, 2:only errors, 3:none); @SOLVE( MINGAP); ! Write a little report of who gets what; @WRITE(@NEWLINE(1),' Allocation: ', @NEWLINE(1),' '); @FOR( party(j): @WRITE(' ',@FORMAT(party(j),'5s'))); @WRITE( @NEWLINE(1)); @FOR( thing(t): @WRITE(' ',@FORMAT(thing(t),'6s')); @FOR(party(j): @WRITE( ' ',@FORMAT(y(t,j),'1.0f'),' '); ); @WRITE( @NEWLINE(1)); ); @WRITE(' Total'); @FOR( party(j): @WRITE(@FORMAT(x(j),'6.0f')); ); @WRITE(@NEWLINE(1)); ENDCALC