3 ms·

The classic algorithm to solve the https://en.wikipedia.org/wiki/Stable_marriage_problem https://en.wikipedia.org/wiki/Stable_marriage_problem is a pretty strai

by geofft 5y ago

The classic algorithm to solve the https://en.wikipedia.org/wiki/Stable_marriage_problem https://en.wikipedia.org/wiki/Stable_marriage_problem is a pretty straightforward and frankly introductory-level example of an algorithm which is not impartial (and not just because it ought to be called the stable heterosexual monogamous marriage problem). The algorithm outputs a matching between two sets A and B (e.g., bachelors and bachelorettes) where each member of set A has ranked each member of set B in preference order and vice versa. The output is called stable because there's no situation where any pair would prefer to be with each other than their current partners, e.g., there's never a case where Alice prefers Bob to her current partner and Bob prefers Alice to his current partner and are tempted to run away with each other. But a curious property of this algorithm is that the matching is always best for one group and always worst for the other. Of the possible answers to the problem, this algorithm an answer that is at least as good for set A as any other one, and at least as bad for set B as any other one. You can, of course, flip sets A and B when running the algorithm, and it will them be optimal for set B and pessimal for set A. This has absolutely nothing to do with ML or data fitting or anything. It's a deterministic, classical algorithm. And yet it is clearly partial, and you must choose when using it whether to be partial to set A or set B, to the men or to the women, to med school students or to their employers, etc. It would be silly to say that the algorithm is impartial and that it's solely the operator's choice to make it impartial - this particular algorithm forces the operator to make some choice. I think in the end you're agreeing with the author, who is saying that you must make a tradeoff of some sort, and the question is which tradeoff to choose. The author (and I) would describe that as the algorithm being partial, and the operator only being able to make some choice about what to do with that.

macleginn 5y ago
"This has absolutely nothing to do with ML or data fitting or anything. It's a deterministic, classical algorithm." --- that's why I wouldn't use it as an example to analyse the question under discussion. If we disregard the name of the algorithm, it's just a non-commutative function: there are lots of those in CS and data analysis (e.g., KL divergence), and people have more or less learned how to deal with them. Generally, I do not agree with the author in what they call "bias". Sometimes algorithms are too noisy for particular data subsets; quite often they are over-confident in their predictions, thus exacerbating the differences between small and large sub-populations. These are all _technical_ issues that surely need to be taken into account when making decisions based on systems' outputs and when designing new systems, but the general idea of the ethical AI literature seems to be to recast these technical issues as ethical issues and to ask AI people to strive to eliminate those altogether. I think that this is misguided and very unlikely to work.
twic 5y ago
This feels a bit like saying that subtraction is partial because it always treats its first argument as positive and its second as negative. It's important to be aware of the asymmetry in the Gale-Shapley algorithm (and i wasn't - thank you), and to not accidentally (or intentionally!) use it in an unfair way. But if someone does, it is they who have introduced the partiality, not the algorithm. PS It seems there are at least two algorithms for solving the stable marriage problem equitably, one given in this paper, and one it mentions given by Knuth and attributed to Selkow: https://epubs.siam.org/doi/10.1137/0216010 https://epubs.siam.org/doi/10.1137/0216010

by geofft 5y ago

macleginn 5y ago

"This has absolutely nothing to do with ML or data fitting or anything. It's a deterministic, classical algorithm." --- that's why I wouldn't use it as an example to analyse the question under discussion. If we disregard the name of the algorithm, it's just a non-commutative function: there are lots of those in CS and data analysis (e.g., KL divergence), and people have more or less learned how to deal with them. Generally, I do not agree with the author in what they call "bias". Sometimes algorithms are too noisy for particular data subsets; quite often they are over-confident in their predictions, thus exacerbating the differences between small and large sub-populations. These are all _technical_ issues that surely need to be taken into account when making decisions based on systems' outputs and when designing new systems, but the general idea of the ethical AI literature seems to be to recast these technical issues as ethical issues and to ask AI people to strive to eliminate those altogether. I think that this is misguided and very unlikely to work.

twic 5y ago

This feels a bit like saying that subtraction is partial because it always treats its first argument as positive and its second as negative. It's important to be aware of the asymmetry in the Gale-Shapley algorithm (and i wasn't - thank you), and to not accidentally (or intentionally!) use it in an unfair way. But if someone does, it is they who have introduced the partiality, not the algorithm. PS It seems there are at least two algorithms for solving the stable marriage problem equitably, one given in this paper, and one it mentions given by Knuth and attributed to Selkow: https://epubs.siam.org/doi/10.1137/0216010 https://epubs.siam.org/doi/10.1137/0216010