! 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