Monday, February 19, 2018

Making algorithms fair

Fairness is elusive, even in algorithms. "Color blindness" doesn't do the trick, since minority populations may differ in other ways from majority populations.
My attention was drawn to this news story  about ongoing work by U. Penn computer scientists: Combatting ‘Fairness Gerrymandering’ with Socially Conscious Algorithms

And here's the article on which the story is based:

Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness

The most prevalent notions of fairness in machine learning are statistical definitions: they fix a small collection of pre-defined groups, and then ask for parity of some statistic of the classifier across these groups. Constraints of this form are susceptible to intentional or inadvertent "fairness gerrymandering", in which a classifier appears to be fair on each individual group, but badly violates the fairness constraint on one or more structured subgroups defined over the protected attributes. We propose instead to demand statistical notions of fairness across exponentially (or infinitely) many subgroups, defined by a structured class of functions over the protected attributes. This interpolates between statistical definitions of fairness and recently proposed individual notions of fairness, but raises several computational challenges. It is no longer clear how to audit a fixed classifier to see if it satisfies such a strong definition of fairness. We prove that the computational problem of auditing subgroup fairness for both equality of false positive rates and statistical parity is equivalent to the problem of weak agnostic learning, which means it is computationally hard in the worst case, even for simple structured subclasses.
We then derive two algorithms that provably converge to the best fair classifier, given access to oracles which can solve the agnostic learning problem. The algorithms are based on a formulation of subgroup fairness as a two-player zero-sum game between a Learner and an Auditor. Our first algorithm provably converges in a polynomial number of steps. Our second algorithm enjoys only provably asymptotic convergence, but has the merit of simplicity and faster per-step computation. We implement the simpler algorithm using linear regression as a heuristic oracle, and show that we can effectively both audit and learn fair classifiers on real datasets.

Sunday, February 18, 2018

Harm reduction (for opioids) in Canada

Here's a story from the Washington Post:
At the heart of Canada’s fentanyl crisis, extreme efforts that U.S. cities may follow

"the Overdose Prevention Society, took over a vacant building next door, giving users a clean indoor place to inject drugs. There are 29 similar sites in British Columbia, the epicenter of Canada’s drug crisis, and more across the country.

“To save lives, you need a table, chairs and some volunteers,” said Sarah Blyth, the manager here.
"As fentanyl rampages across North America, several U.S. cities have announced that they will open the first supervised drug-consumption sites like those in Canada. Their plans illustrate the gulf between the two nations: While Justin Trudeau’s government is doubling down on its “harm reduction” approach, any U.S. organization that tries to follow suit would be violating federal law and risking a confrontation with the Justice Department.
See also this academic paper
Addressing the Nation’s Opioid Epidemic: Lessons from an Unsanctioned Supervised Injection Site in the U.S.
Kral, Alex H. et al.
American Journal of Preventive Medicine , Volume 53 , Issue 6 , 919 - 922

and this January 2017 news story
Awash in overdoses, Seattle creates safe sites for addicts to inject illegal drugs

Saturday, February 17, 2018

School choice and privilege in Washington D.C.

A benefit (or a cost) of having clearly defined rules is that you can see when exceptions are made. (What could look like flexibility in a private sector environment can look like corruption in a public school system.) The Washington Post has the story:

"A D.C. deputy mayor resigned Friday after helping the public schools chancellor bypass the city’s notoriously competitive lottery system and secure a coveted slot for his teenage daughter at a top high school.

"The resignation of Deputy Mayor for Education Jennifer C. Niles is immediate, Mayor Muriel E. Bowser said Friday. The mayor said in an interview that she has ordered Schools Chancellor Antwan Wilson to issue a public apology and has referred the matter to the Board of Ethics and Government Accountability and to the inspector general to examine whether the head of the city’s traditional public school system violated the code of conduct.

“My decision was wrong and I take full responsibility for my mistake,” Wilson said in a statement. “While I understand that many of you will be angered and disappointed by my actions, I’m here today to apologize and ask for your forgiveness.”

From the Mayor's twitter stream:

Friday, February 16, 2018

Sex work, Craigslist, and the law; podcast with Scott Cunningham

Here's a link to an interview with Scott Cunningham, whose work on sex work I've blogged about before. There's a surprising amount of discussion about causal inference and differences in differences. (I always suspected that econometrics was sexy, but this is the first time I’ve heard a podcast about that.)

Thursday, February 15, 2018

Bermuda steps backward on same sex marriage

The NY Times has the story:
Bermuda Outlaws Gay Marriage, Less Than a Year After It Became Legal

"Bermuda has forbidden same-sex marriage, only nine months after legalizing it, in what advocates for gay and lesbian rights called a disappointing setback.

"Same-sex marriage became legal in Bermuda, a British overseas territory, in May as a result of a ruling by the island’s Supreme Court.

"But the unions are unpopular with some voters.

"In 2016, Bermudians voted against same-sex marriage in a referendum, and after the court ruling in May, the territory’s legislature drafted a bill banning same-sex marriage but giving all couples legal recognition as domestic partners. Parliament adopted the Domestic Partnership Act in December, and on Wednesday the territory’s governor, John Rankin, signed it into law.

"The British prime minister, Theresa May, said Britain was “seriously disappointed,” but the Foreign Office said on Thursday it would be inappropriate to block the measure.

"Same-sex marriage became legal in England, Wales and Scotland in 2014, but it is not permitted in Northern Ireland. The issue has been divisive in Britain’s overseas territories, which control their own internal affairs but rely on Britain for defense and for representation in the international community."

Wednesday, February 14, 2018

Algorithms for Valentines Day, in the WSJ (update: and elsewhere)

The "Numbers" column in the Wall Street Journal salutes Valentines Day by discussing the deferred acceptance algorithm, and mentioning some of its applications.
You May Now Kiss the Algorithm
A mathematical solution ensures no one is paired with an unacceptable mate
by Jo Craven McGinty

It opens with this encouraging line about stable matching:
"Sorry, love birds. Sometimes, you have to take what you can get."

If you can't read the rest at the above link, try the link at Ms. McGinty's twitter account (or maybe it will even work from here:  via ).

One thing not emphasized in the column is that the man-optimal stable matching and the woman-optimal stable matching are very often the same or nearly so.

Update: even the Nobel foundation can't resist the Valentine's Day connection. Here's their facebook post

Tuesday, February 13, 2018

Market design and artificial intelligence (AI) by Milgrom and Tadelis

Two veteran market designers reflect on how AI is entering market design, building on their recent work on the incentive spectrum auction, and on identifying problematic online sellers from text analysis of post-transaction messaging:

How Artificial Intelligence and Machine Learning Can Impact Market Design

Paul R. MilgromSteven Tadelis

NBER Working Paper No. 24282
Issued in February 2018
NBER Program(s):Industrial OrganizationProductivity, Innovation, and Entrepreneurship 
In complex environments, it is challenging to learn enough about the underlying characteristics of transactions so as to design the best institutions to efficiently generate gains from trade. In recent years, Artificial Intelligence has emerged as an important tool that allows market designers to uncover important market fundamentals, and to better predict fluctuations that can cause friction in markets. This paper offers some recent examples of how Artificial Intelligence helps market designers improve the operations of markets, and outlines directions in which it will continue to shape and influence market design.

Here's an ungated version:
How Artificial Intelligence and Machine Learning Can Impact Market Design
by Paul R. Milgrom  and Steve Tadelis