Get Rank-Maximal Allocation

Question

Stefan Michael Popp 2022-9-6

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1795635-get-rank-maximal-allocation

回答： Anurag 2023-10-25

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.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Anurag 2023-10-25

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1795635-get-rank-maximal-allocation#answer_1340671

在 MATLAB Online 中打开

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']);