Finding maximal minimum value set

Question

I'm attempting to write a (naive, or semi-naive) program that given a set of elements and a number of players divides it to this number of players, and for each such division takes the minimal value (by sum) subset. Then, I want to calculate the maximum of all these minimal divisions.

This is known as the https://en.wikipedia.org/wiki/Maximin_share .

For example, if we look at the set {1,4,6} we can divide it for 2 players such that one receives {1,4} and the other {6}, the minimalk value here is 5. For all other divisions, it is easy to see that the minimal value will be less than 5.

I want to write a prolog predicate maximin(+Elements,+Players,-Value) that given a list of Elements (positive integers) and a number of Players returns the maximin Value.

I tried a very naive approach:

Wrote a predicate that calculates a certain division.
Used find all to find all the divisions.
For each division returned the value of the minimal subset.
Calculated the maximum of them.

However, this program runs only for small inputs. For example, if I take a 10 elements list Elements and attempt to divide it to 3 players, I get an error of out of stack, even though I tried to increase the program memory as best as I could with set_prolog_stack.

My code:

% returns the smaller item
mini(A,B,B):- A > B.
mini(A,B,A):- A =< B.

% Returns the Sum of the minimal subset in a division (+,-)
min_subset_value([P1],Sum1):-subset_value(P1,Sum1).
min_subset_value([P1|RestP],Min) :-  RestP \= [], min_subset_value(RestP, OtherMin), subset_value(P1,A1)
                                     , mini(A1, OtherMin, Min).


% divide_to_players(+,+,-) : Generate a division of all the Elements to N subsets
divide_to_players([],N,EmptySets):- N>=1, generate_empty_sets(EmptySets,N).
divide_to_players(Elements, 1, [Elements]):-Elements \= [].
divide_to_players(Elements, N, [P1|RestP]):- N>1, Elements \= [], subseti(P1,Elements)
                                             , remove_subset(Elements,P1,OtherElements)
                                             , N1 is N-1
                                             , divide_to_players(OtherElements, N1, RestP).
% Generates all divisions (+,+,-)
generate_all_divisions(Elements,N,AllDivs) :- findall(Div,divide_to_players(Elements,N,Div),AllDivs).

% From all the given divisions, which one has the maximal minimal subset
find_max_division([],0).
find_max_division([Set1|RestSets],Max) :- find_max_division(RestSets, OtherMin)
                                         , min_subset_value(Set1,LocalMin)
                                         , maxi(LocalMin, OtherMin, Max).

% uses the previous functions as described above (+,+,-)
maximin_player(Elements,N,Maximin) :- generate_all_divisions(Elements,N,AllDiv)
                                     , find_max_division(AllDiv,Maximin).

However, I am wandering if there is another way to go on it? Maybe finding the maximin value without using findall? I only used findall because I did not have any better idea for an approach, so I'd appreciate to hear other ideas or approaches to this problem.

user_463243 · Answer

If the elements are all integers (i.e. no variables and no floating point values) I believe this works fine:

maximin(Elements, N, Maximin, LDistribution):-
  sumlist(Elements, Sum),
  TargetMaximin is -Sum//N,
  once(
  (
    between(TargetMaximin, -1, NMaximin),
    Maximin is -NMaximin,
    distribute(Elements, [], n, Maximin, N, 0, [], LDistributionOnce)
  )),
  LDistribution=LDistributionOnce.
  
distribute([], [], _, _, 0, _, _, []).
distribute(Elements, Skipped, y, Maximin, N, Cur, Distribution, [Distribution|LDistribution]):-
  N>0,
  Cur >= Maximin,
  succ(N1, N),
  append(Elements, Skipped, NElements),
  distribute(NElements, [], n, Maximin, N1, 0, [], LDistribution).
distribute([Element|Elements], Skipped, _, Maximin, N, Cur, Distribution, LDistribution):-
  N>0,
  NCur is Cur+Element,
  distribute(Elements, Skipped, y, Maximin, N, NCur, [Element|Distribution], LDistribution).
distribute([Element|Elements], Skipped, _, Maximin, N, Cur, Distribution, LDistribution):-
  N>0,
  distribute(Elements, [Element|Skipped], n, Maximin, N, Cur, Distribution, LDistribution).

The idea of the algorithm is to start with the maximum target mininum value (the integer division of the sum of the elements divided by the number of players) and try to fit the elements in N slots where each slot sums at least the target minimum. If you find such distribution then you are done, otherwise decrement the target minimum value by 1 and repeat.

The algorithm here also gives the only one distribution it finds.

Sample runs:

?- maximin([11,17,19],3,Maximin, LDist).
Maximin = 11,
LDist = [[11], [17], [19]].

?- maximin([5,7,1,3,3,7,4,3,8,2,5,1],3,Maximin, LDist).
Maximin = 16,
LDist = [[3, 1, 7, 5], [3, 4, 7, 3], [1, 5, 2, 8]].

Finding maximal minimum value set

1 Answers