Lindo Systems

! Unordered Lexico maximization of allocations
 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, given that, the second smallest
utility is maximized, given that, the third etc...
  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, Lexico-max, Minimax, Assignment problem,
      Unordered lexico-max, Inheritance, Allocation, Goal programming,
      Pre-emptive goal programming, Multi-criteria;
sets:
  party: x, base, sumjsmall;
  pxp(party, party): delta;
  thing;
  txp( thing,party) : val, 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;
  val =
  !Photos;    21     15     35     10
  !Silver;    19     20      5     11
  !Tables;    35     10     16     37
  !Books;     15     36      5     25
  !HiFi;      10     19     39     17;
 ! Note totals each add up to 100;
enddata

SUBMODEL MAXK:
! Maximize the sum of the k smallest x(i)
  Variables:
    x(j) = the utility (more is better) achieved by party j,
    base(j) = jth smallest x(i) when maximizing the
              sum of the j smallest x(i),
    delta(i,j) = amount by which x(i)
                 is less than base(j) when maximizing the
                 sum of j smallest, = 0 if >= base(j);
  MAX = SUMK;
  SUMK = k*base(k) - @sum(party(i): delta(i,k));
  ! For each party i, force delta(i,j) to be large enough;
  @for( party(i):
     @for(party(j) | j #LE# k: ! Enforce first k results;
       x(i) >= base(j) - delta(i,j) ;
         );
       );
  ! Notice or verify that in the expression,
      z(j) =  j*base(j) - @sum(party(i): delta(i,j)),
  if we set base(j)  = jth smallest of the x(i), then
  z(j) = sum of the j smallest.  Further, notice that
  for any other value of base(j), z(j) <= sum of j smallest; 
 
  @for( pxp(i,j)| j #LT# k:
    @free(base(j));  ! Allow < 0;
! Limit sum of j smallest for j < k;
    j*base(j) - @sum(party(i): delta(i,j))>= sumjsmall(j);
      );

! Constraints on permissible allocations;
!  Can assign object i to at most one party;
  @FOR(thing(i):
      @SUM( party(j): y(i,j)) <= 1;
      );
  @FOR(txp(i,j): @BIN(y(i,j)));

! x(j) = utility of pary j;
  @FOR( party(j):
     x(j) = @SUM(thing(i): val(i,j)*y(i,j));
      );
ENDSUBMODEL

CALC:
 !Algorithm:
   For k = 1, 2, ... N:
    {Minimize sumjsmall(k) = the sum of k smallest,
    Constrain sum of k smallest to >= sumjsmall(k),
    }
  Result:
    The smallest is maximized,
    Given the smallest 1 maximized, the 2nd largest is maximized,
    Given the smallest 2 maximized, etc.
   ;
 @SET("TERSEO",2);  !Turn off default output;
 ! Successively maximize the sum of the k smallest,
   for k = 1, 2, N;
 N = @SIZE(party);
 !Initialize;
  @for(party(i):
     sumjsmall(i) = -BigM;
      );

 PREV = 0;
 @for( party(iter):
   K = iter;
   @SOLVE( MAXK);
   @write(' Max sum of smallest ', K,' = ', @format(SUMK,'2.0f'),@newline(1));
   @write( '  ',K,'th smallest is ',@format(SUMK-PREV,'2.0f'), @newline(1));
   PREV = SUMK;
   sumjsmall(K) = SUMK;
     );
 @write(@newline(1),'   Allocation:  ', @newline(1),'       ');
 @for( party(j): @write(' ',party(j)));
 @write( @newline(1));
 @for( thing(t):
   @write(' ',thing(t));
   @for(party(j):
     @write( '   ',@format(y(t,j),'1.0f'),' ');
       );
   @write( @newline(1));
     );
 @write(' Total');
 @for( party(j):
   @write('  ',@format(x(j),'3.0f'));
     );
 @write(@newline(1));
ENDCALC