Lindo Systems

! 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,
    Multi-criteria;
SETS:
  party: x;
  thing;
  txp( thing,party) : value, y;
ENDSETS
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