Get Rank-Maximal Allocation

Input: n subjects ranked i items (in example below i = 3) by preference, e.g.:

% Rank:  1 2 3
Alice = [x y z];
Bobby = [y x z];
Carlo = [x z y];

S = [Alice; Bobby; Carlo];

Problem: Find a fair allocation of items to subjects, e.g. through Rank-maximal allocation (but not necessarily)

Desired output:

% Subjects[A; B; C]
outRank = [1; 1; 2]; % Tells me the rank of the received items
% OR:
outItem = [x; y; z]; % Tells me directly which subject gets which item. outItem = S(i,outRank(i))

Wikipedia article about the problem with algorithm. I just can't make sense of the outputs of any of the MATLAB functions with seemingly useful names.

Answer 1

[Anurag]

Hi Stefan,

I understand that you want to implement the Rank-Maximal allocation algorithm, please refer to the following code for the same.

% Input: n subjects ranked i items

% Create a matrix where each row represents a subject's preference ranking
Alice = [2, 1, 3];
Bobby = [1, 2, 3];
Carlo = [2, 3, 1];

% Stack the preferences of all subjects into a single matrix
S = [Alice; Bobby; Carlo];



% Number of subjects and items
[n, i] = size(S);

% Initialize output arrays
outRank = zeros(n, 1);
outItem = strings(n, 1); % Initialize outItem as a string array


% Find the rank-maximal allocation
for subject = 1:n
    
    % Find the item with the lowest rank for the current subject
    
    [~, minRank] = min(S(subject, :));
    
    % Find the subject who prefers this item the most
    
    [~, maxPreference] = max(S(:, minRank));
       
    % Assign the item with the lowest rank to the subject who prefers it the most
    
    outRank(maxPreference) = minRank;
    
    outItem(maxPreference) = char('A' + subject); % Assign the subject letter
        
    % Set the rank of the assigned item to a high value to avoid reassignment
    
    S(maxPreference, minRank) = i + 1;
    
end

% Output the results
disp('Subjects [A; B; C]:');
disp(['outRank = ', num2str(outRank')]);
disp(['outItem = ', outItem']);

Hope this helped.

Regards,

Anurag