Subgroup Fairness in Two-Sided Markets
  It is well known that two-sided markets are unfair in a number of ways. For
instance, female workers at Uber earn less than their male colleagues per mile
driven. Similar observations have been made for other minority subgroups in
other two-sided markets. Here, we suggest a novel market-clearing mechanism for
two-sided markets, which promotes equalisation of the pay per hour worked
across multiple subgroups, as well as within each subgroup. In the process, we
introduce a novel notion of subgroup fairness (which we call Inter-fairness),
which can be combined with other notions of fairness within each subgroup
(called Intra-fairness), and the utility for the customers (Customer-Care) in
the objective of the market-clearing problem. While the novel non-linear terms
in the objective complicate market clearing by making the problem non-convex,
we show that a certain non-convex augmented Lagrangian relaxation can be
approximated to any precision in time polynomial in the number of market
participants using semi-definite programming. This makes it possible to
implement the market-clearing mechanism efficiently. On the example of
driver-ride assignment in an Uber-like system, we demonstrate the efficacy and
scalability of the approach, and trade-offs between Inter- and Intra-fairness.
