Yes, (Kleinberg et al, 2016)… Do not read it. Really, don’t. The derivation is extremely clumsy (and my professor said so too).
The proof has been considerably simplified in subsequent works. Look around for papers that cite that paper should give a published paper that does the simplification...
Actually, Kleinberg et al. 2016 isn’t all that bad. They have a small paragraph at the beginning of section 2 which they call an “informal overview” over the proof. But it’s actually almost a decent proof in and of itself. You may accept it as such, or you may write it down a bit more formally, and you end up with a short, sweet proof. The reason they can’t use a graphical approach like the one in this blog entry is that the above diagram with the squares only applies to the special case of scores that either output 0 or 1, but nothing in between. That is an important special case, but a special case nevertheless. Kleinberg et al. deal with the more common and slightly more general case of scores which can take any real value from 0 to 1. Also the COMPAS score, which is the topic of the ProPublica report cited above, can take other values than just 0 and 1.
By the way, also the introductory section of the Kleinberg-et-al-paper is definitely worth reading. It gives an overview over the relevance of the problem for other areas of application. So only their attempt at a formal proof is kind of a waste of time to read.
Yes, (Kleinberg et al, 2016)… Do not read it. Really, don’t. The derivation is extremely clumsy (and my professor said so too).
The proof has been considerably simplified in subsequent works. Look around for papers that cite that paper should give a published paper that does the simplification...
Actually, Kleinberg et al. 2016 isn’t all that bad. They have a small paragraph at the beginning of section 2 which they call an “informal overview” over the proof. But it’s actually almost a decent proof in and of itself. You may accept it as such, or you may write it down a bit more formally, and you end up with a short, sweet proof. The reason they can’t use a graphical approach like the one in this blog entry is that the above diagram with the squares only applies to the special case of scores that either output 0 or 1, but nothing in between. That is an important special case, but a special case nevertheless. Kleinberg et al. deal with the more common and slightly more general case of scores which can take any real value from 0 to 1. Also the COMPAS score, which is the topic of the ProPublica report cited above, can take other values than just 0 and 1.
By the way, also the introductory section of the Kleinberg-et-al-paper is definitely worth reading. It gives an overview over the relevance of the problem for other areas of application. So only their attempt at a formal proof is kind of a waste of time to read.