! Unordered Lexico Maximization of Muli-Criteria.   Given a number of participants(parties/criteria), 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...
  It follows that the solution is Pareto optimal.
  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;

! References:
Serafini, P. (1996), "Scheduling Jobs on Several Machines with the Job Splitting Property",
Operations Research, Vol. 44, No. 4, (July-August), pp. 617-628.

Maschler, M., B. Peleg, and L. S. Shapley (1979), 
"Geometric Properties of the Kernel, Nucleolus, and Related Solution Concepts",
 Mathematics of Operations Research, vol. 4, No. 4 (Nov), pp. 303-338.

!Keywords: Allocation, Assignment problem, Fair allocation, Goal programming,
     Inheritance, Knapsack, Lexico-max, Minimax, Multi-criteria, Nucleolus,
     Pareto optimal, Pre-emptive goal programming, Unordered lexico-max;

SETS:
 CRITERIA: VAL_REC,
      base, sumjsmall, sofs;

 ITEM: WGT, Z; !Each item has a wgt, value, yes/no var;
 CXI( ITEM, CRITERIA) : VALUE;
 CxC( CRITERIA, CRITERIA): delta;
ENDSETS
DATA: ! Case 1; !Case01; ITEM WGT = ANT_REPEL 1 SIX_PACK 3 BLANKET 4 BRATWURST 3 BROWNIE 3 FRISBEE 1 SALAD 5 WATMELON 10 ; ! The value of the items to the various 'players', based on allocating 100 points to the items; !Case01; CRITERIA = TOM DICK JANE!Case01; VALUE = 3 9 12 !Case01; 14 20 2 !Case01; 5 11 14 !Case01; 13 21 11 !Case01; 6 12 11 !Case01; 10 19 13 !Case01; 8 2 28 !Case01; 41 6 9!Case01; CAP = 15 ! Case 2; !Case02 ITEM WGT = ITEM1 15 ITEM2 14 ITEM3 7 ITEM4 8 ; !Case02 CAP = 15; !Case02 CRITERIA = DICK JANE; !Case02 VALUE = 70 0 !Case02 0 70 ! ITEM1; !Case02 14 16 !Case02 16 14;! ITEM1 ENDDATA SUBMODEL ULexMxMn: ! Maximize the sum of the k smallest VAL_REC(i) Variables: VAL_REC(j) = the utility (more is better) achieved by CRITERIA j, base( j) = jth smallest VAL_REC(i) when maximizing the sum of the j smallest VAL_REC(i), delta( i, j) = amount by which VAL_REC(i) is less than base( j), when maximizing the sum of j smallest, = 0 if >= base(j) sofs( k) = sum of k smallest values received; MAX = sofs( kn); ! Force delta( i, j) @FOR( CRITERIA( i): @FOR( CRITERIA( j) : [NFORC] delta( i, j) >= base( j) - VAL_REC( i) ; ); ); ! Notice or verify that in the constraints, sofs( k) = k* base( k) - @sum( CRITERIA( i): delta( i, k)), and delta( i, j) >= base( j) - VAL_REC( i) We can maximize sofs( k) if we set base( k) = kth smallest of the VAL_REC( i), then sofs( k) = sum of the k smallest. Notice that for any other value of base( k), sofs( k) <= sum of k smallest; @FOR( CRITERIA( j): @free( base( j)); ! Allow < 0; @FREE( sofs( j)); [LVL] sofs( j) = j* base( j) - @SUM( CRITERIA( i): delta( i, j)); ! Limit sum of j smallest for j < k; [PREVP] sofs( j) >= sumjsmall( j); ); ! Here insert the regular constraints; @FOR( CRITERIA( k): ! Value of soln for criterion k; VAL_REC( k) = @SUM( ITEM( j): VALUE( j, k)* Z( j)); ); @SUM( ITEM(j): WGT(j)*Z(j)) <= CAP;! Wgt constraint; @FOR( ITEM(j): @BIN( Z(j))); ! All vars 0/1; ENDSUBMODEL
CALC: !Algorithm: For k = 1, 2, ... @SIZE( CRITERIA): {Minimize sumjsmall( k) = the sum of k smallest values received, Constrain sum of k smallest to >= sumjsmall(k), } Result: The smallest is maximized, Given the smallest 1 maximized, the 2nd smallestest is maximized, Given the smallest 2 maximized, etc. ; @SET( "TERSEO", 2);! Turn off default messages; for k = 1, 2, N; N = @SIZE( CRITERIA); !Initialize; @FOR( CRITERIA( i): sumjsmall( i) = - BigM; ); PREV = 0; @FOR( CRITERIA( kk): kn = kk; ! @gen( ULexMxMn); @SOLVE( ULexMxMn); @WRITE(' Max sum of smallest ', kk,' = ', @FORMAT( sofs( kk),'2.0f'),@NEWLINE(1)); @WRITE( ' ',kk,'th smallest is ',@FORMAT( sofs( kk)-PREV,'2.0f'), @NEWLINE(1)); PREV = sofs( kk); sumjsmall( kk) = sofs( kk); ); ! Display the solution; @FOR( CRITERIA(c): @WRITE( @FORMAT( CRITERIA( c),'5s')); ); @FOR( ITEM(j): @WRITE( @FORMAT( ITEM( j),'10s'))); @WRITE( @NEWLINE(1)); @FOR( CRITERIA( c): @WRITE( @FORMAT( VAL_REC( c),'5.0f')); ); @FOR( ITEM(j): @IFC( Z( j) #GT# .5: !Either; @WRITE(' 1'); @ELSE @WRITE(' '); ); ); ! End FOR; ENDCALC