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