Implement "popularity comparison" for rules

[DominikPeters]

In Wieliczka and in Świece, MES is run with an additional step at the end, where the outcome of the greedy rule is computed, and it is counted how many voters prefer MES to greedy, and how many prefer greedy to MES (evaluated using cardinality satisfaction). The final outcome is the one that has more people preferring it.

This step avoids some pathological behavior of MES, for example in the presence of very expensive projects and few other projects.

It would be good to implement this. The most elegant way would probably mirror the implementation of completion_by_rule_combination, i.e., as a wrapper function. The wrapper function would take as input the satisfaction function for doing the popularity comparison, and would allow passing dictionaries of options to the child rules.

[Simon-Rey]

Done. See pabutools.rules.composition. It is for now irresolute since there are no ways to break ties between sets of projects at the moment.

[DominikPeters]

Thanks, cool! 🔥

I think you've implemented "take the output with higher social welfare", which is different from what is done in Poland, where it is about the number of people who prefer A over B, compared to vice versa. This is also why I called it "popularity" (e.g. a "popular matching" is one that is majority preferred to any other matching).

My (pseudo) code for Wieliczka was:

    W_mes = mes(e)
    W_greedy = utilitarian_greedy(e)
    satisfaction_mes = {v : utility(v, W_mes) for v in e.voters}
    satisfaction_greedy = {v : utility(v, W_greedy)  v in e.voters}
    prefer_greedy = len([v for v in e.voters if satisfaction_mes[v] < satisfaction_greedy[v]])
    prefer_mes = len([v for v in e.voters if satisfaction_mes[v] > satisfaction_greedy[v]])
    if prefer_mes > prefer_greedy:
        return W_mes, res_mes
    else:
        return W_greedy, None

But I guess this only works for pairs of rules, not a list of more than 2 rules. Regarding tie-breaking, I think it would be natural to take the output of the first rule in the list of rules.

The social welfare version also makes sense, so it could be an alternative function provided (or not).

[Simon-Rey]

Indeed, I went too fast! Now should be good!

[DominikPeters]

Cool, nice solution!