! 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
|