∎

11institutetext:  Université Paris-Saclay, CNRS, CentraleSupélec, Laboratoire
Interdisciplinaire des Sciences du Numérique, 91190 Gif-sur-Yvette, France
11email<EMAIL_ADDRESS>
11email<EMAIL_ADDRESS>
# Controlling the C3 super class linearization algorithm for large hierarchies
of classes

Florent Hivert  Nicolas M. Thiéry

###### Abstract

C3 is an algorithm used by several widely used programming languages such as
Python to support multiple inheritance in object oriented programming (OOP):
for each class, C3 computes recursively a linear extension of the poset of all
its super classes (the Method Resolution Order, MRO) from user-provided local
information (an ordering of the direct super classes). This algorithm can fail
if the local information is not consistent.

For large hierarchies of classes, as encountered when modeling hierarchies of
concepts from abstract algebra in the SageMath computational system,
maintaining consistent local information by hand does not scale and leads to
unpredictable C3 failures.

This paper reports on the authors’ work to analyze and circumvent this
maintenance nightmare. First, we discovered through extensive computer
exploration that there exists posets admitting no consistent local
information; we exhibit the smallest one which has 10 elements. Then, we
provide and analyze an algorithm that, given a poset and a linear extension,
automatically builds local information for C3 in such a way that guarantees
that it will never fail, at the price of a slight relaxation of the
hypotheses. This algorithm has been used in production in SageMath since 2013.

###### Keywords:

class hierarchies; multiple inheritance; linearization; C3

###### MSC:

06A06 68N15

††journal: Order

##  1 Introduction

To assume no programming experience from the reader, we start by briefly
recalling the basics of object oriented programming required to understand the
motivations. To make it concrete, we illustrate this paper with examples in
the Python programming language; up to syntactic details that may be ignored,
they should be self-explanatory. Then, we describe the C3 algorithm, introduce
our use case, state the problem at hand, and announce the work reported on and
the structure of the paper.

Readers that wish to quickly grasp the mathematical problem at hand may skip
the motivations and jump directly to Section 1.6.

###  1.1 Classes and multiple inheritance

In a programming language supporting object oriented programming, the
programmer can implement _classes_ which defines the _data structure_ and
_operations_ for all objects of a given nature.

Here is an example of a definition of a class called $A$:

⬇

>>> class A:

... x: int

... def f(self): return 42 + self.x

From this class, we may create any number of _instances_ ; each has a data
structure made of an integer x, and a _method_ f:

⬇

>>> a = A() # Create an instance a of A

>>> a.x = 2 # Set the value of x for a

>>> a.f() # Call the method f for a

44

Classes can be combined by inheritance: in the following example, the class
$C$ is a subclass of both $A$ and $B$:

⬇

>>> class A:

... def f(self): return "Calling f from A"

>>> class B:

... def g(self): return "Calling g from B"

>>> class C(A, B):

... def h(self): return "Calling h from C"

Thereby, each instance of $C$ _inherits_ the methods f, g, and h provided
respectively by the classes $A$, $B$, and $C$:

⬇

>>> c = C()

>>> c.f()

Calling f from A

>>> c.g()

Calling g from B

>>> c.h()

Calling h from C

As we are about to see, the order in which the direct super classes of $C$ are
listed when we write $C(A,B)$ _is_ relevant; it is called the _local
precedence order_ at $C$.

###  1.2 Method Resolution Orders

Now what happens if several classes define methods with the same name?

⬇

>>> class A:

... def f(self): return "Calling f from A"

>>> class B:

... def f(self): return "Calling f from B"

>>> class C(A, B):

... def f(self): return "Calling f from C"

Now the following call becomes a priori ambiguous and the system must first
_resolve_ that ambiguity:

⬇

>>> c = C()

>>> c.f() # Calls f from A, B, or C?

Calling f from C

Over the years, programming languages have explored various method resolution
strategies, some requiring manual resolution by the programmer (as in C++),
others automating the process, culminating with the C3 algorithm C3.1996 ;
Python’s founder Guido van Rossum presents it as follows in vanRossum.2010.MRO
: “Basically, the idea behind C3 is that if you write down all of the ordering
rules imposed by inheritance relationships in a complex class hierarchy, the
algorithm will determine a monotonic ordering of the classes that satisfies
all of them. If such an ordering cannot be determined, the algorithm will
fail.“.

Let’s briefly review the history and rationale behind C3. In C3.1994 , the
authors advocated that a guiding principle for automated resolution should be
that of least surprise for the programmer: up to exceptional cases, she should
not have to reason on the technical details of the method resolution strategy
to predict the behaviour of a program.

A first step is to ensure that the resolution does not depend on the specific
method at hand. Typically, for each class $C$, a Method Resolution Order (MRO,
or linearization) is computed: this is a linear order starting with $C$
followed by all its super classes. Then, a method call c.f() for an instance c
of $C$ is resolved by searching for the first class in the MRO that defines a
method with that name.

A comparative review of popular linearization algorithms is conducted in
C3.1992  (see also C3.1996 ). In C3.1994 , the authors propose desirable
properties for MROs to support the principle of least surprise.

Three of the desirable properties are for the MROs themselves; all three are
about consistency with the constraints laid out by the programmer:

  * •

_Consistency with the hierarchy of classes_ (called Masking in C3.1992 ): a
class $C$ in the hierarchy _specializes_ its super classes: if $C$ defines a
method f, then this method should take precedence over methods defined in its
super classes. In other words, the MRO should be a linear extension of the
hierarchy of super classes.

When there is no multiple inheritance, this fully specifies the MRO. Note that
many early MRO computation algorithms produced MROs that did not respect this
consistency (e.g. in Python $<$ 2.3, Perl, MuPAD, …).

  * •

_Consistency with the local precedence order_ : assume that $B$ appears before
$A$ in the local precedence order of some class $C$ in the hierarchy; then $B$
must appear before $A$ in the MRO of $C$.

  * •

_Consistency with the extended precedence graph_ : this a strengthening of the
previous property: under the same assumption, not only must $B$ appear before
$A$ in the MRO, but also all its super classes that are not also super classes
of $A$.

In addition, C3.1994  propose two additional desirable properties for
linearization algorithms:

  * •

_Monotonicity_ : the MRO of a super class $A$ of a class $C$ should be the
restriction of the MRO of $C$ to the super classes of $A$.

  * •

_Acceptability_ : the MRO of a class should only depend on the subhierarchy of
its super classes considered up to isomorphism, together with the local
precedence orders for each super class. The computation should thereby not
depend on external factors, nor on, e.g. class names.

###  1.3 The C3 algorithm

In C3.1996 , the authors invented the C3 algorithm by cross-breeding the
linearization algorithm of the Dylan programming language (originating from
the Common List Object System) and that proposed in C3.1994 . The name comes
from the fact that C3 respects the three consistency properties, and in fact
all the aforementioned desirable properties. C3 became the standard
linearization algorithm of Dylan, and then was adopted in other widely used
languages, such as Python $\geq$2.3, Perl 5.10, Raku, Parrot, Solidity,
PGF/Tikz Wikipedia.C3 . We recommend this article Simionato.2003.C3  from the
Python documentation, which contains many details and examples.

In practice, C3 is based on a routine C3_merge – similar in nature to the
merge step in the merge sort algorithm:

###### Algorithm 1

C3_merge takes several duplicate-free lists as input and merges them together,
removing duplicates and preserving the linear orders prescribed by the input
lists, or failing if these are inconsistent. Specifically, call _head_ the
first element of a list, and _tail_ the rest of it. The head of an input list
is _good_ if it does not appear in the tail of any of the other input lists.
C3_merge starts from an empty result and searches for a good head, starting
from the first input list. This good head is appended to the result and
removed from the input lists. Then that step is repeated until all the input
lists are empty or there is no good head. The latter case certifies that the
linear orders prescribed by the lists are inconsistent, and C3_merge fails (in
Python with the dreaded “could not find a consistent method resolution order”
exception).

###### Algorithm 2

The C3 linearization algorithm computes the MRO of a class $C$ by calling
C3_merge on the MROs of its direct super classes, computed recursively, and
followed by the local precedence order at $C$.

Acceptability, monotonicity and consistency with the class hierarchy and local
precedence orders are given by construction. Consistency with the extended
precedence graph takes a proof.

The MRO of a class is typically cached. Thereby a natural complexity metric is
the cost of computing the MRO of a newly added class. It is linear in the sum
of the lengths of the MROs of its direct super-classes; typically, there are
very few of them, so this is essentially linear in the length of the MRO.

The total cost of computing the MRO’s for all classes in a hierarchy is
typically between linear and quadratic in the number of classes, depending on
the depth of the hierarchy. Given that the computation occurs only once and
that class hierarchies rarely exceed hundreds of classes, this is not a
bottleneck in practice. That being said, and this will be relevant in the
sequel, the worst case complexity is cubic with a badly set up class
hierarchy.

###  1.4 The use case: computational mathematics with SageMath

We now turn to the use case in computational mathematical systems that
triggered our work. Abstract algebra provides a large range of concepts (e.g.
fields, vector spaces or groups, for some of the most well-known) which are
effective: for example, being a vector space brings a range of generic
algorithms from linear algebra. Modeling these concepts in a computational
mathematics systems is a tool of choice to structure code, documentation, and
even tests to maximize reusability.

Figure 1: The hierarchy of about 400 concepts modeled in SageMath as of 2022

Following e.g. Axiom, Aldor or MuPAD, and consistently with the choice of the
programming language Python, SageMath has made the decision to model these
concepts using a hierarchy of classes (other systems, like GAP, have taken
different approaches).

So far, this follows the classical pattern of modeling the business logic to
increase expressiveness. A striking aspect of algebra however is that there
are relatively few core concepts (operations such as addition and
multiplication, axioms like associativity, distributivity, …) and that all the
richness comes from the many interactions between these concepts, with a
plethora of interesting combinations that deliver dedicated computational
methods. As a programmer, you just want to state which core concepts are
satisfied by your object at hand, and automatically benefit from all the
methods provided by their various combinations.

In SageMath, this makes for a deep hierarchy of about one thousand abstract
classes – each bringing some non-trivial content – involving massive multiple
inheritance (see Figure 1). Automation is key to keep such a hierarchy
maintainable. There is indeed a lot of redundancy in the inheritance diagram,
as it encodes, for example, that a finite group is a finite magma, an element
of a group is an element of a magma, a group morphism is a magma morphism, and
so on and so forth. This maintenance issue and similar ones are mitigated by
generating the class hierarchy at runtime from mixins and semantic information
that model the relevant mathematical fact at a single point of truth; in the
above example: a group is a magma. See SageCategories  for more details about
the underlying SageMath’s _category infrastructure_.

###  1.5 The problem

While developing SageMath’s hierarchy of classes and designing the underlying
category infrastructure, the second author was constantly hitting or receiving
reports of C3 failures. In their simplest form, they were triggered by classes
such as in the following synthetic example:

class $A$class $B$class $C(A,B)$

MRO: $C,A,B$

class $B$class $A$class $D(B,A)$

MRO: $D,B,A$

These two classes independently are perfectly sane and sound. However, when
combined as in

class $E(C,D)$

C3 rightfully reports that it “Cannot create a consistent method resolution
order (MRO)”: the order of $A$ and $B$ in the MROs of $C$ and $D$ are indeed
inconsistent. See also (C3.1994, , Figure 4) which exhibits another example
where the inconsistency is indirect.

This was to be expected: in large class hierarchies, developed by dozens of
independent developers, each with a given use case in mind, you can’t expect
local decisions to be consistent globally without choosing and enforcing some
conventions.

This was the occasion for formalizing a convention that was emerging, prompted
by the observation that, at the scale of SageMath’s abstract classes, it is
illusory to get a fine control on the MRO, beyond monotonicity.

###### Convention 1

All the methods that one could inherit through different inheritance paths
should be semantically equivalent, and only possibly differ by their
efficiency. Whenever a specific choice is desirable (e.g. for a $C$, it is
more efficient to call f from $A$ than f from $B$), that choice should be
implemented and documented explicitly using a method f in $C$.

Based on this convention, the next attempt was to try to formalize some global
order on the abstract classes, and enforce that the local precedence order be
consistent with that global order. This revived an old tension between local
and global approaches (see discussion p.174 of C3.1994 ). And indeed C3 –
being by design not aware of non-local information (acceptability) –
occasionally produces MROs that do not respect the global order as in the
upcoming example.

###### Example 1

For the following class hierarchy, where the local precedence order have been
chosen according to the global order $E,D,C,B,A$, the algorithm C3 produces
the MRO $E,D,B,A,C$.

class $B$class $A$class $C$class $D(B,A)$class $E(D,C)$

Again, this attempt did not scale; whichever global order was tried,
inconsistencies emerged sooner or later when extending the hierarchy.

This problem is particularly acute in SageMath because extensibility is at the
core of the development model: by design, the SageMath library is meant as a
toolbox from which end users can create bespoke classes to model their
favorite newly invented mathematical objects. Manually resolving MRO issues –
which may require tweaking the local precedence orders in the SageMath library
itself – imposes an insurmountable barrier.

###  1.6 Formal background

In this section, we briefly formally recap the main definitions and results
from the literature in the language of order theory.

Let $P$ be a poset. An _MRO_ of $P$ is a total ordering of its elements. A
_local precedence order_ at an element $C$ of the poset is a total ordering of
the upper covers of $C$. Choose a local precedence order $l(C)$ at each
element $C$ of $P$. An MRO $l$ is _consistent_ with $P$ and the local
precedence orders if

  1. 1.

$l$ is a linear extension of $P$;

  2. 2.

for any element $C$ of $P$, any two upper covers $B<_{l(C)}A$ of $C$ and any
$B^{\prime}$ such that $B^{\prime}>B$ but $B^{\prime}\not>A$, we have
$B^{\prime}<_{l}A$.

Note: condition 2 as defined above deviates slightly from the original
condition of _consistency with the extended local precedence orders_ as stated
in C3.1994  or C3.1996 ; nevertheless, the two conditions are equivalent as
soon as $l$ is a linear extension of the poset $P$.

######  Proposition 1 (See paragraph just before Result 2, p. 22 of C3.1992 )

Let $P$ be a poset endowed with a local precedence order $l(C)$ at each
element $C$ of $P$. Then, $(P,\\{l(C)\mid C\in P\\})$ admits at most one
consistent MRO.

When $(P,\\{l(C)\mid C\in P\\})$ admits no consistent MRO, the local
precedence orders $\\{l(C)\mid C\in P\\}$ are called C3-_inconsistent_.

######  Proposition 2 (See Result 2, p. 22 of C3.1992 )

Let $P$ be a poset endowed with a local precedence order $l(C)$ at each
element $C$ of $P$. Then, the algorithm C3 applied to $(P,\\{l(C)\mid C\in
P\\})$ computes the unique consistent MRO if it exists, and fails otherwise.

Moreover, the C3 algorithm is acceptable and monotonic.

###  1.7 Description of the work

Wondering whether the repeated C3 failures encountered in our application were
intrinsic to the problem triggered the following mathematical question:

###### Question 1

Does there exist a poset admitting no consistent MRO, whichever local
precedence orders are chosen?

In Section 2 we describe the computer exploration that followed and elucidate
the question by a positive answer, exhibiting the smallest example which has
10 elements.

This fact supported our practical assessment that, under usual practice, C3
linearization did not scale in the SageMath use case.

Switching to another linearization algorithm was not an option: this would
have required to either use a patched version of Python – thereby creating a
barrier between SageMath and the rest of the Python ecosystem – or requesting
a change in the linearization algorithm in Python itself – nowadays a mature
and widely adopted language, with millions of programmers and billions of
lines of code that could get broken.

So instead we investigated how to gain control over C3 to force it to produce
MROs satisfying the somewhat different desirable properties for our use case;
this is reported on in Section 3.

##  2 A partial order with no C3-consistent local precedence orders

To explore Question 1, we performed a systematic computer search on posets of
small size. This required, for increasing $n$, to iterate through all linear
extensions of all posets up to isomorphism with $n+1$ elements and a least
element (the class inheriting from all the others), computing the MRO of this
class with C3 starting from the local precedence orders induced by the linear
extension, and collecting the success and failure counts per poset. Without
loss of generality, one may choose $0,1,\dots,n$ as labels and linear
extension and drop the least element, and thereby reduce the enumeration to
the collection $\mathcal{A}_{n}$ of posets (stored as transitively reduced
digraphs) admitting $1<\dots<n$ as linear extension.

n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---|---
A000112 | 1 | 1 | 2 | 5 | 16 | 63 | 318 | 2 045 | 16 999 | 183 231
# $\mathcal{A}_{n}$ | 1 | 1 | 2 | 7 | 40 | 357 | 4 824 | 96 428 | 2 800 472 | 116 473 461
Table 1: Number of posets on $n$ elements up to isomorphism (OEIS A000112
OEIS.A000112 ) and of posets admitting $1,\dots,n$ as linear extension (OEIS
A006455 OEIS.A006455 ).

The graded set $\mathcal{A}:=\biguplus_{n\in\mathbb{N}}\mathcal{A}_{n}$ is
naturally endowed with a tree structure: the root is the trivial digraph in
$\mathcal{A}_{0}$; the parent of a poset in $\mathcal{A}_{n}$ is obtained by
taking in $\mathcal{A}_{n-1}$ the induced subgraph on $\\{1,\dots,n-1\\}$;
reciprocally, the children of a poset in $\mathcal{A}_{n-1}$ are obtained by
taking each of its antichains in turn, and adding $n$ as a cover of the
elements in that antichain.

This tree structure on $\mathcal{A}$ enables to iterate recursively through
the elements of each $\mathcal{A}_{n}$ without storing them, and use a
parallel map-reduce algorithm to apply C3 on each of them and collect the
desired success and failure counts per poset up to isomorphism (using
canonical labelling).

The computation took two days on the 8 cores of a 2012 personal laptop for
$\mathcal{A}_{9}$, that is testing C3 for all linear extensions of all posets
up to isomorphism on $10$ elements and with a least element. The computation
was performed with SageMath’s parallel infrastructure for map-reduce
operations on recursive enumeration trees
Sage.RecursivelyEnumeratedSets.MapReduce . Implemented by the first author,
this infrastructure is based on work stealing to achieve load balancing even
with branches of very irregular size Hivert.PASCO.2017 . The computation
served as use case and benchmark for this infrastructure while it was
developed.

The proposition below summarizes the findings of this computation.

###### Proposition 3

Consider the following poset $H$ on $10$ elements:

ABC$D_{1}$$E_{1}$$D_{2}$$E_{2}$$D_{3}$$E_{3}$F

Then, $H$ admits no consistent method resolution order as computed by C3,
whichever local precedence orders are chosen. The same holds for any
linearization algorithm satisfying acceptability, monotonicity and consistency
with the extended local precedence order.

###### Proof

Fix a choice of local precedence orders, and assume that there exists a
consistent MRO for $H$ as computed by C3, or any linearization algorithm which
is acceptable, monotonic and consistent with the extended local precedence
orders.

Consider the restriction $H_{1}$ of $H$ on $\\{A,B,C,D_{1},E_{1}\\}$. Up to
isomorphism, this is the poset underlying Example 1. The MRO on $H_{1}$
depends solely on the local precedence orders at $D_{1}$ and $E_{1}$. If the
local precedence order at $E_{1}$ is $D_{1},C$, then $C$ comes after $A$ and
$B$ in the MRO; otherwise it comes before $A$ and $B$. By monotonicity, $C$
never lies between $A$ and $B$ in the MRO of $H$.

The restriction $H_{2}$ of $H$ on $\\{A,B,C,D_{2},E_{2}\\}$ is again the poset
underlying Example 1, but this time with the roles of $A,B,C$ shifted
cyclically. Repeating the previous argument, $B$ never lies between $A$ and
$C$ in the MRO of $H$.

The same holds for the restriction $H_{3}$ of $H$ on
$\\{A,B,C,D_{3},E_{3}\\}$; thereby $A$ never lies between $B$ and $C$ in the
MRO of $H$, a contradiction since one of $A$, $B$, and $C$ must lie between
the others.

A systematic computer search revealed no other poset on at most $10$ elements
with this property. So we moreover claim that

###### Claim

Up to isomorphism, $H$ is the unique poset with this property among posets
having a least element with at most $10$ elements.

##  3 C3 under control

###  3.1 Taking over control

It is now time to unveil a trivial yet decisive remark to break out of the
apparent dead end for using C3 in our use case.

###### Remark 1

Example 1 and Proposition 3 rely on an unspoken hypothesis: that the local
precedence order at a given class lists only its direct super classes.

As pointed out in C3.1996 , this is in fact not required by the C3 algorithm.
This is not required either by the implementation of classes in, e.g., Python.

###### Example 2

Consider the following minor variant of Example 1:

class $B$class $A$class $C$class $D(B,A)$class
$E(D,C{\color[rgb]{0.78515625,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.78515625,0,0}{,B}})$

Adding $B$ to the local precedence order for $E$ does not change the
underlying poset – that is the semantic of the class inheritance – since the
edge $E\rightarrow B$ is obtained by transitivity. Yet adding this additional
bit of information about the global order is sufficient to make the algorithm
C3 produce the desired MRO $E,D,C,B,A$.

This immediately brings the next question:

###### Question 2

Take a poset and a global order (linear extension) for that poset. Which
elements should be inserted in the local precedence order (sorted according to
the global order) to ensure that C3 reproduces the given global order as MRO.

###### Exercise 1

Resolve that question for the poset $H$ of Proposition 3.

A brute force solution is to choose, for each element $C$, the desired MRO for
that element as local precedence order. Consider indeed the execution of
C3_merge to compute the MRO of a given element. By construction, the first
input list is the MRO for that element, and by induction all input lists
follow the global order. It is easy to check that, at each step of the
execution, the head of the first list is always good; therefore the result is
the desired MRO.

This solution is however not desirable. Consider for example a linear order
$A_{n}<\dots<A_{1}$. Then, the local precedence order for $A_{k}$ is
$A_{k},\dots,A_{1}$, and the complexity of computing the MRO with C3 is cubic
in $n$. When $n$ is of the order of magnitude of $1000$, this becomes non-
negligible. This theoretical evidence is confirmed by practice: our first
prototype in SageMath used this brute force approach; the slowdown was
noticable not only at class construction, but also for many other operations
(like introspection) involving a recursive exploration of the class hierarchy.

###  3.2 Automation

After carrying out Exercise 1, the reader is presumably convinced that
resolving Question 2 by hand for each class is certainly not practical, even
for hierarchy of classes of moderate size. As suggested in the discussion p.
75 of C3.1996  this form of manual tuning is fragile. It also introduces
redundancy which is subject to changes each time the class hierarchy evolves.

We thus take an alternative route, considering the local precedence orders as
technical details that should be computed automatically.

###### Algorithm 3

[Instrumented C3 ]

C3_instrumented takes the same input as C3, together with the desired global
order. The algorithm proceeds as in C3. However, C3_merge is instrumented as
well so that, when computing the MRO for a element $C$:

  * •

The local precedence order $c_{C}$ is initialized with the direct super
classes of $C$, sorted decreasingly according to the global order.

  * •

At each step, if the search for a good head results in a element $A$ which is
distinct from the desired next element $B$ in the MRO, then $A$ is inserted in
both the last list and $c_{C}$; if required, $B$ is inserted as well to ensure
that $A$ is in the tail of the last list. Then the search for a good head is
restarted until it results in $B$.

At the end, C3_instrumented returns all the computed local precedence orders
$\\{l(C)\mid C\in P\\}$.

The greedy algorithm C3_instrumented resolves Question 2 optimally:

###### Proposition 4

Take a poset and a global order (linear extension) for that poset. Use
C3_instrumented to compute the local precedence orders. Then, these local
precedence orders are the minimal ones (in size) such that C3 reproduces the
given global order as MRO.

###### Proof

By construction.

This procedure – which admits a natural incremental implementation – has been
adopted by SageMath 5.12 in 2013 SageMath.13589 : at runtime, whenever the
class hierarchy is about to be extended with a new class, the local precedence
order for that class is computed using C3_instrumented, and passed as list of
_bases_ to Python’s class constructor which uses C3 to build its MRO as usual.
In addition a key is computed for that class that defines its position in the
global order (more on this later) for later MRO computations.

###  3.3 Performance overhead

At this stage it is natural to assess the performance overhead of this
procedure. The first one is that the C3 algorithm is called twice, once
instrumented, once not. The second one is that the complexity of both calls
may be increased by the insertion of new elements in the local precedence
orders.

###### Problem 1

Estimate the number of additional elements that are inserted in the local
precedence orders by C3_instrumented.

We have no theoretical bounds. However the two upcoming pieces of practical
evidence and practical experience suggest that few additional elements need to
inserted in the local precedence orders, and that the complexity of running
C3_instrumented followed C3 is commensurate to two calls of the original C3.

###### Example 3

Solution to Exercise 1 Let us choose
$F,E_{3},E_{2},E_{1},D_{3},D_{2},D_{1},C,B,A$ as global order. The picture
below depicts the local precedence orders computed by C3_instrumented. It also
shows in red, the four elements that have been inserted to ensure that C3
reproduces the desired global order.

$A$$B$$C$$D_{1}(B,A)$$E_{1}(D_{1},C{\color[rgb]{0.78515625,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.78515625,0,0}{,B}})$$D_{2}(C,A)$$E_{2}(D_{2},B{\color[rgb]{0.78515625,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.78515625,0,0}{,A}})$$D_{3}(C,B)$$E_{3}(D_{3},A)$$F(E_{3},E_{2},E_{1}{\color[rgb]{0.78515625,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.78515625,0,0}{,D_{3},D_{2}}})$

If instead one chooses $F,E_{3},D_{3},E_{2},D_{2},C,E_{1},D_{1},B,A$, a single
element needs to be added:

$A$$B$$C$$D_{1}(B,A)$$E_{1}(C,D_{1})$$D_{2}(C,A)$$E_{2}(D_{2},B{\color[rgb]{0.78515625,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.78515625,0,0}{,A}})$$D_{3}(C,B)$$E_{3}(D_{3},A)$$F(E_{3},E_{2},E_{1})$

Note that the fact that all additional elements appear at the end of the local
precedence orders is an artifact of the given choice of total order.

Consider now all 720 linear extensions of the poset. The following table
counts them according to the number of elements that need to be inserted in
the local precedence orders in addition to the original 15 elements:

# additional elements | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---
# linear extensions | 36 | 108 | 180 | 216 | 180

###### Example 4

Consider the 103 common categories in SageMath 9.3 taken from the
category_sample catalog. The following table counts them according to the
number of elements that need to be inserted in their local precedence order:

# additional elements | 0 | 1 | 2 | 5
---|---|---|---|---
# categories | 96 | 5 | 1 | 1

###  3.4 Choosing a global order

We have assumed so far that, in use cases where Convention 1 is acceptable, it
is possible to define a global order on the class hierarchy. To illustrate
that this is not necessarily a strong assumption we conclude this section by a
brief description of the strategy used in SageMath to define such a global
order.

Under Convention 1, the semantic should not depend on the global order as long
as it is a linear extension of the class hierarchy. Therefore, a naive
strategy is to exploit the fact that classes are always constructed from
existing super classes, and use the creation order as global order (in
practice, use a global counter and assign to each class an integer
successively, integer which is used as comparison key to define the global
order).

This strategy is non-deterministic however: the obtained global order is
subject to change whenever the code is modified; it may even vary from one
session to the other depending on the order in which the code is loaded. This
behavior is unusual and thus surprising to developers; it also makes it
difficult to reproduce and analyze bugs.

To make the strategy more deterministic and regain – as often desirable – some
coarse control on the MRO, we refined this strategy by exploiting that the
hierarchy of categories underlying SageMath’s abstract classes forms a
lattice. A total order is chosen on a collection $\mathcal{C}$ of important
categories of the lattice (about twenty of them as of SageMath 9.3, most being
meet-irreducible). Each category in $\mathcal{C}$ is assigned a distinct power
of two (seen as bit flag) following this total order. Then each category is
assigned as comparison key the sum of the flags of its super categories in
$\mathcal{C}$; the obtained order is then refined lexicographically to a total
order using a counter as above.

##  4 Conclusion

The C3 linearization algorithm was designed around a collection of generally
desirable properties which makes it suitable for a wide range of use cases.
This comes at a price: it may fail, and these failures can become a
maintenance burden that prevents scaling to large hierarchies of classes.

In this paper, we provided theoretical evidence for this scaling issue by
exhibiting a hierarchy of 10 classes for which C3 always fails.

We showed that this can be circumvented with a small relaxation of the
hypotheses: at the price of adding a bit of redundancy in the defining
relation of the class hierarchy (adding a few transitivity edges to the Hasse
diagram of the poset), one may take control over C3 and guide it to any
desired solution. Better, this process may be automatized to produce the
optimal number of additional edges, with minimal impact on the computational
complexity.

This resolves the scalability limitation of C3 and guarantees extensibility in
use cases – like in SageMath – where one can afford to drop the acceptability
property and define a global order on the class hierarchy. This solution has
been in continuous production in SageMath since its original implementation in
2013 by the second author. Other than speed optimizations in 2013 and 2014 it
has required no further attention. For almost a decade now it has resolved MRO
issues in a large variety of computational applications, without the users or
programmers even noticing it (there remains MRO issues in SageMath, but due to
another, independent, source of inconsistencies). This suggests not only that
the proposed solution is robust, but that the underlying approach is sound to
tackle large extensible hierarchies of classes.

This also confirms the flexibility of C3 which, by design, satisfies the
desirable properties of linearization in general use cases, and, with some
control, can be made to satisfy other desirable properties arising in specific
use cases.

###### Acknowledgements.

The authors would like to thank the SageMath community for their feedback on
and review of the implementation of C3 under control in SageMath, and in
particular Simon King who optimized the implementation in Cython
SageMath.13589  to achieve the same constant time factors as in Python’s
native C3 implementation.

## Conflict of interest

The authors declare that they have no conflict of interest.

## Data availability

The manuscript has no associated data, as the data underlying the computer
search was generated on the fly. The code is available in the following public
repository https://gitlab.dsi.universite-paris-saclay.fr/nicolas.thiery/C3/.

## References

  * (1) Barrett, K., Cassels, B., Haahr, P., Moon, D.A., Playford, K., Withington, P.T.: A monotonic superclass linearization for Dylan.  In: Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, pp. 69–82 (1996)
  * (2) Ducournau, R., Habib, M., Huchard, M., Mugnier, M.L.: Monotonic conflict resolution mechanisms for inheritance.  ACM SIGPLAN Notices 27(10), 16–24 (1992)
  * (3) Ducournau, R., Habib, M., Huchard, M., Mugnier, M.L.: Proposal for a monotonic multiple inheritance linearization.  In: Proceedings of the ninth annual conference on Object-oriented programming systems, language, and applications, pp. 164–175 (1994)
  * (4) Hivert, F.: High Performance Computing Experiments in Enumerative and Algebraic Combinatorics.  In: Proceedings of the 8th International Workshop on Parallel Symbolic Computation (PASCO), pp. 1–4. ACM Press, Kaiserslautern, Germany (2017).  DOI 10.1145/3115936.3115938.  URL https://hal.archives-ouvertes.fr/hal-01691051
  * (5) Hivert, F., et al.: Parallel computations using recursivelyenumeratedset and map-reduce.  SageMath reference manual (2009–).  URL https://doc.sagemath.org/html/en/reference/parallel/sage/parallel/map_reduce.html
  * (6) OEIS Foundation Inc.: The on-line encyclopedia of integer sequences (2021).  URL http://oeis.org/A000112
  * (7) OEIS Foundation Inc.: The on-line encyclopedia of integer sequences (2021).  URL http://oeis.org/A006455
  * (8) van Rossum, G.: Method resolution order.  Blog: The History of Python (2010).  URL http://python-history.blogspot.co.uk/2010/06/method-resolution-order.html
  * (9) Simionato, M.: The Python 2.3 method resolution order.  Python Release 2.3 Documentation (2003).  URL https://www.python.org/download/releases/2.3/mro/
  * (10) Thiéry, N.M., King, S.: Sagemath Ticket #13589: Controlling C3 to solve once for all the Method Resolution Order issues for category classes.  SageMath development tracking system (2013).  URL https://trac.sagemath.org/ticket/13589
  * (11) Thiéry, N.M., et al.: Elements, Parents, and Categories in Sage: a primer.  SageMath reference manual (2009–).  URL https://doc.sagemath.org/html/en/reference/categories/sage/categories/primer.html
  * (12) Wikipedia (2021).  URL https://en.wikipedia.org/wiki/C3_linearization


# Proportionally Representative Clustering*00footnotetext: * We owe thanks to
John Dickerson and Bo Li for helpful comments and feedback.

Haris Aziz<EMAIL_ADDRESS>UNSW Sydney
Sydney, Australia  Barton E. Lee<EMAIL_ADDRESS>ETH Zürich, Switzerland
Sean Morota Chu<EMAIL_ADDRESS>UNSW Sydney
Sydney, Australia

(15 Oct 2022)

###### Abstract

In recent years, there has been a surge in effort to formalize notions of
fairness in machine learning. We focus on _clustering_ —one of the fundamental
tasks in unsupervised machine learning. We propose a new axiom that captures
proportional representation fairness (PRF). We make a case that the concept
achieves the raison d’être of several existing concepts in the literature in
an arguably more convincing manner. Our fairness concept is not satisfied by
existing fair clustering algorithms. We design efficient algorithms to achieve
PRF both for unconstrained and discrete clustering problems.

##  1 Introduction

As artificial intelligence and machine learning serves as the ‘new
electricity’ of systems, it is becoming increasingly important to ensure that
AI systems embody societal values such as privacy, transparency, and fairness.
Fairness is a growing concern, as AI systems are used to make decisions that
can critically affect our daily lives, finances, and careers [22]. The impulse
to tackle the issue of fairness in AI is prominently reflected in several
governmental policy documents (see, e,g, [23, 3, 32]), the emergence of
dedicated conferences on Ethical AI, and the formation of AI ethics boards by
various big tech companies. Over the past years, several developments have
taken place in the theory and application of fairness in supervised learning.
One prominent approach is to use information derived from labelled data in
supervised learning to formalize some notions of equity within and across
(pre-specified and) protected attributes (see, e.g., [29]). In contrast, in
several models of unsupervised learning, protected attributes or their
labelling are unknown. Fairness in unsupervised machine learning is becoming
important with the growth of data collection both in public (e.g., via IoT
devices) and private sectors (e.g., map services and social media). Unfettered
and irresponsible use of such data has the danger of increasing inequity [45].

We focus on fairness in clustering which is one of the most widely applied
tasks in unsupervised machine learning. A (centroid selection) clustering
problem has a metric space $\mathscr{X}$ with a distance measure
$d:\mathscr{X}\times\mathscr{X}\rightarrow\mathbb{R}^{+}\cup\\{0\\}$, a
multiset ${\mathscr{N}}\subseteq\mathscr{X}$ of $n$ data points (agents), a
set ${\mathscr{M}}$ of candidate centers, and positive integer $k\leq n$. In
many clustering problems, each data point corresponds to an individuals’
attribute profile; thus, we refer to the data points as _agents_. The goal is
to find a size-$k$ subset of centers, $Y\subseteq{\mathscr{M}}\ :\ |Y|=k$.
Such _centroid selection_ problems can be widely applied to various
applications including recommender systems and data-compression. The problem
also captures social planning scenarios where $k$ facility locations need to
be chosen to serve a set of agents.

In such a (centroid selection) clustering problem, there are two versions of
the problem. In the _discrete_ version, ${\mathscr{M}}$ is a finite set. In
the _unconstrained_ or _continuous_ setting, ${\mathscr{M}}=\mathscr{X}$. We
first focus on the unconstrained setting as done by Micha and Shah [43]. Later
we discuss how our concepts and ideas extend to the discrete setting. For a
location $i$ and set of locations $S{\subseteq{\mathscr{M}}}$, we will denote
$\min_{c\in S}d(i,c)$ as $d(i,S)$. Standard clustering solutions include
$k$-center, $k$-medians, and $k$-means.111 The $k$-center solution outputs a
subset
$Y\in\arg\min_{W\subseteq{\mathscr{M}},|W|=k}\max_{i\in{\mathscr{N}}}d(i,W)$.
The $k$-medians solution outputs a subset
$Y\in\arg\min_{W\subseteq{\mathscr{M}},|W|=k}\sum_{i\in{\mathscr{N}}}d(i,W)$.
The $k$-means solution outputs a subset
$Y\in\arg\min_{W\subseteq{\mathscr{M}},|W|=k}\sum_{i\in{\mathscr{N}}}d(i,W)^{2}$.
These standard objectives can be viewed as achieving some form of global
welfare but are not well-suited for proportional representational and fairness
concerns. They are also NP-hard (see, e.g.,[41, 5]).

We seek a suitable concept for clustering that captures general fairness
principles such as non-discrimination, equality of opportunity, and equality
of outcome. In many applications, the data point correspond to real
individuals or their positions or opinions. Such individuals may expect the
clustering outcome to capture natural fairness requirements. In particular,
they may expect an appropriate number of centers to be close enough to them.
The number of clusters and their proximity would depend on how many (or what
proportion of) data points are tightly clustered together. The issue of
finding fair and proportionally representative cluster centers can be
especially important in applications such as hiring where the data points
correspond to qualified individuals that have been short-listed for a set of
positions and the centers are the selected (or successful) set of individuals.
Similarly, computing a fair clustering is also meaningful in facility
location, where the location of the facility should depend on the density and
the number of people it is serving. In this paper, we consider the following
fundamental research question. _What is a meaningful concept of proportional
fairness in centroid clustering? Is such a concept guaranteed to be
achievable?_

### Contributions

In contrast to traditional optimization objectives in clustering and centroid
selection, we take an axiomatic fairness perspective. We first identify a
potential shortcoming of some recently introduced concepts that aim to capture
proportional fairness for clustering; in particular, we show how the concepts
do not capture an aspect they attempt to capture. We then propose a new axiom
called _proportional representative fairness (PRF)_ , which is our central
conceptual contribution. We propose PRF for both the unconstrained and
discrete clustering setting. We discuss how PRF overcomes some of the
drawbacks of the previously introduced concepts. In particular, it implies
unanimous proportionality, which can be viewed as a minimal requirement of
proportional fairness. PRF has several other desirable features : a PRF
outcome is guaranteed to exist, the axiom does not require a preset
specification of protected groups and it is robust to outliers and
multiplicative scaling. We show that none of the traditional clustering
algorithms or new algorithms for fair clustering satisfy PRF. We design
polynomial-time algorithms to achieve PRF both in the unconstrained and
discrete settings.222The results for unconstrained and discrete settings are
incomparable in the following sense. The guarantee of existence of a fair
outcome in the discrete setting guarantees the existence of a fair outcome in
the unconstrained setting; however, a polynomial-time algorithm for computing
a fair outcome in the discrete setting does not apply the same for the
unconstrained setting.  Finally, we experimentally compare our algorithm with
two standard algorithms and show that it performs especially well when the
mean square distance of the agents is calculated based on their distance from
not only the closest center but also the next $j$-closest centers (for large
$j$).

##  2 Related Work

Fairness in machine learning and computer systems is a vast topic [37]—for an
overview, see Chouldechova and Roth [22] or the survey by Mehrabi et al. [42].
We focus on the fundamental learning problem of clustering, which is a well-
studied problem in computer science, statistics, and operations research (see,
e.g., [33]). Our approach is axiomatic, focused on the concept of proportional
fairness (or representation), and does not rely on the use of a pre-specified
or protected set of attributes. Thus, the most closely related papers are
those of Chen et al. [19], Micha and Shah [43], Li et al. [40], and Jung et
al. [38], which we review below.

Chen et al. [19] proposed the concept of _proportional fairness_ (PF) for the
discrete setting, which is based on the entitlement of groups of agents of
large enough size. They reasoned that PF is a desirable fairness concept but
it is not guaranteed to be achievable for every instance. On the other hand,
they showed that outcomes satisfying reasonable approximations of PF are
guaranteed to exist and can be computed in polynomial time via the ‘Greedy
Capture’ algorithm.

Micha and Shah [43] analyzed the proportional fairness axiom in the
unconstrained setting and presented similar results to those obtained by Chen
et al. [19]. They showed that the natural adaptation of the Greedy Capture
algorithm finds an approximately PF outcome. On the other hand, they showed
that checking whether a PF outcome exists is NP-hard and that the clustering
returned by the ‘greedy capture’ algorithm cannot be computed in polynomial
time unless P = NP. Li et al. [40] consider the same discrete clustering
setting as Chen et al. [19] and propose a stronger version of proportional
fairness called _core fairness._ They present results on lower and upper
approximation bounds for various restrictions of the discrete setting. Because
core fairness is stronger than proportional fairness, the negative existence
results of Chen et al. [19] also hold for core fairness.

Jung et al. [38] consider the discrete clustering problem in which the set of
agents and candidate centers coincide. For this setting, they propose a
fairness concept that has a similar goal as that of Chen et al. [19]. In
subsequent work, it has been referred to as _individual fairness_ [49, 17].
Individual fairness requires that, for each agent $i$, there is a selected
center that is at most $r(i)$ from $i$, where $r(i)$ is the smallest radius
around $i$ that includes $n/k$ agents. As is the case for proportional
fairness, only a constant-factor approximation can be achieved for two or more
dimensions.

There are also several concepts and algorithms in clustering where the
protected groups are pre-specified based on protected attributes [1, 2, 13,
12, 39, 20, 21, 30]. In contrast, we are seeking fairness properties that
apply to arbitrarily defined groups of all possible sizes. In our proposed
axiom, these groups are _endogenously_ determined from data points; in some
real-world settings, this is a legal requirement since it can be forbidden by
law to have decision-making processes use certain attributes as inputs. Some
recent papers also use randomization to achieve probabilistic fairness
objectives [16, 31]. We do not explore randomization since our proposed axiom
is defined on the (ex-post) clustering outcome and can be achieved via
deterministic algorithms.

Fairness and representation are important concerns in economic design [44].
Issues related to proportional representation and fairness have been
considered in many settings, including apportionment [47, 15], participatory
budgeting [9], portioning [7, 4], probabilistic voting [10], and multi-winner
voting [34, 8, 27, 28, 48]. Group fairness has also been examined in the
context of resource allocation [14, 24, 11]. This literature has largely
focused on settings where agents have _ordinal_ preferences over candidates.
Our fairness (or proportional representation) axioms take into account the
additional cardinal information available when the candidates belong to a
general metric space. Hence, our axioms formalize a notion of proportional
representation for $m$-dimensional Euclidean space for $m>2$. The standard
fairness axioms such as proportionality of solid coalitions for ordinal
preferences [8] are too weak when applied to our spatial context. Naively
applying them to our spatial problem also results in a reduction from our
unconstrained problem to a multiwinner voting problem with an infinite number
of candidates.

The clustering problem has natural connections with multi-winner voting [34,
35, 46]. Agents and centers in the clustering context correspond to voters and
candidates in multi-winner voting. Each agent’s (voter’s) preference over
centers (candidates) can then be derived using the distance metric with closer
centers being more preferred. With this view, multi-winner voting rules imply
clustering solutions. For example, the Chamberlin–Courant rule takes agents’
distances from candidates using Borda count and then implements the $k$-median
objective. Relatedly, clustering can also be viewed as a facility location
problem [36], where multiple facilities (centers) are to be located in a
metric space; for a recent overview, see the survey by Chan et al. [18].

##  3 Limitation of Existing Proportional Fairness Concepts

Proportional fairness for clustering has been considered in a series of recent
papers. Chen et al. [19] first proposed a proportional fairness axiom that is
based on the idea that more dense groups of data points require more
centers—in their words, _“any subset of at least $r\lceil n/k\rceil$
individuals is entitled to choose $r$ centers”_. Their proposed formal
specification of proportional fairness requires the clustering solution to be
such that there is no set of agents of size at least $n/k$ that can find an
unselected center that is “better” (i.e., located closer than the closest
selected center) for each of them. The concept was studied in detail for the
discrete and unconstrained settings by Chen et al. [19] and and Micha and Shah
[43], respectively.

######  Definition 1 (Proportional Fairness [19]).

$X\subseteq{\mathscr{M}}$ with $|X|=k$ satisfies proportional fairness if
$\forall S\subseteq{\mathscr{N}}$ with $|S|\geq\lceil\frac{n}{k}\rceil$ and
for all $c\in{\mathscr{M}}$, there exists $i\in S$ with $d(i,c)\geq d(i,X)$.

The idea of proportional fairness was further strengthened to core fairness
that requires that there is no set of agents of size at least $n/k$ that is
better for them in aggregate.

######  Definition 2 (Core Fairness [40].).

$X\subseteq{\mathscr{M}}$ with $|X|=k$ is _core fair_ if $\forall
S\subseteq{\mathscr{N}}$ with $|S|\geq\lceil\frac{n}{k}\rceil$ and for all
$c\in{\mathscr{M}}$, $\sum_{i\in S}d(i,c)\geq\sum_{i\in S}d(i,X)$.

One rationale for proportional fairness is explained in the following example,
which was first presented by Micha and Shah [43] and then reused by Li et al.
[40]. We reuse the same example.

######  Example 1.

Consider a set of data points/agents. The agents are divided into 11 subsets
of clusters each of which is densely clustered. One cluster of agents has size
10,000. The other 10 clusters have sizes 100 each. The big cluster is very far
from the smaller clusters. The small clusters are relatively near to each
other.

Micha and Shah [43] and Li et al. [40] are of the view that any set of centers
that satisfies a reasonable notion of proportional fairness would place 10
centers for the big cluster and 1 center serving the small clusters. Next, we
point out that proportional fairness and core fairness do not necessarily
satisfy this minimal requirement, which we formalize via the _unanimous
proportionality_ axiom below.

######  Definition 3 (Unanimous Proportionality (UP)).

$X\subseteq{\mathscr{M}}$ with $|X|=k$ satisfies _unanimous proportionality_
if $\forall S\subseteq{\mathscr{N}}$ with $|S|\geq\ell\lceil\frac{n}{k}\rceil$
and each agent in $S$ has the same location $x\in\mathscr{X}$, then $\ell$
possible locations closest to $x$ are selected.

UP captures a principle that Chen et al. [19] were seeking that requires that
_“any subset of at least $r\lceil n/k\rceil$ individuals is entitled to choose
$r$ centers”_.333In the term unanimous proportionality, unanimous refers to
the condition where a set of agents have the same location, and
proportionality refers to the requirements that such agents get an appropriate
number of centers in proportion to the number of agents. The following example
shows that proportional fairness [19] and core fairness [40] do not imply
Unanimous Proportionality. Similarly, it can be shown that the fairness
concept proposed by Jung et al. [38] does not imply unanimous fairness.

######  Example 2 (Limitation of proportional fairness and core fairness).

Suppose agents are located in the $[0,1]$ interval. 10,000 agents are at point
0 and 1000 agents are at point 1. Suppose we want to find $k$ centers. UP
requires that 10 centers are at or just around point 0 and 1 center is at
point 1. However, placing 1 center at point 0 and 10 centers at point 1
satisfies the proportional fairness concept of Chen et al. [19] and also the
core fairness concept of Li et al. [40].

The example above shows that there is a need to formalize new concepts that
capture proportional representative fairness. The property should imply
unanimous proportionality but should also be meaningful if no two agents /
data points completely coincide in their location. One reason why proportional
fairness and core fairness do not capture UP is that they make an implicit
assumption that may be suitable in some contexts of facility location but
possibly not in the context of certain unsupervised learning problems. The
assumption is that an agent _only_ cares about the distance from the nearest
center and not on how many centers are nearby. Another issue is that a PF
outcome may not exist. We introduce an example presented by Micha and Shah
[43] that shows that a PF outcome may not exist. We will use the same example
to illustrate our new fairness concept.

######  Example 3.

Consider Figure 1. For the 6 agents and $k=3$, it has been shown by Micha and
Shah [43] that a PF outcome may not exist.

123546

Figure 1: An example instance with 6 agents and $k=3$ for which a PF outcome
does not exist.

##  4 Fairness for the Unconstrained Setting

We propose a new concept _Proportionally Representative Fairness (PRF)_ that
captures proportional representation fairness concerns. The intuition behind
the concept is based on two natural principles: (1) A set of agents that is
large enough deserves to have a proportional number of centers ‘near’ it, and
(2) The requirement of proximity of the nearby centers from a subset of agents
should also depend on how densely together the particular subset of agents
are. We use these two principles to propose a new fairness concept.

######  Definition 4 (Proportionally Representative Fairness (PRF) for
Unconstrained Clustering).

An outcome $X\subseteq{\mathscr{M}}$ with $|X|=k$ satisfies _Proportionally
Representative Fairness (PRF)_ if the following holds. For any set of agents
$S\subseteq{\mathscr{N}}$ of size at least $|S|\geq\ell n/k$ such that the
maximum distance between pairs of agents in $S$ is $y$, the following holds:
$|c\in X\mathbin{:}\exists i\in S\text{ s.t }d(i,c)\leq y|\geq\ell$.

PRF has the following features: it implies unanimous proportionality; it is
oblivious to and does not depend on the specification of protected groups or
sensitive attributes; it is robust to outliers in the data, since the fairness
requirements are for groups of points that are sizable enough; and it is scale
invariant to multiplication of distances (PRF outcomes are preserved if all
the distances are multiplied by a constant).

Next, let us illustrate an example where proportional fairness is not
achievable but one of the most natural clustering outcomes satisfies PRF.

######  Example 4 (Requirements of PRF).

We revisit Example 3 to illustrate the requirements that PRF imposes. For each
set $S$ of size at least $\ell\lceil\frac{n}{k}\rceil=2\ell$, PRF requires
$\ell$ centers in the relevant neighborhood of agents in $S$ (see Figure 2).
Therefore, for agent 1 and 2, PRF requires that one selected candidate center
should be in one of the circles around 1 or 2. For the set of agents
$\\{1,2,3\\}$, PRF also requires that one candidate center should be in one of
the circles around 1, 2 or 3. A natural solution is to have one center located
between agents 1, 2, and 3, another center located between agents 4, 5, and 6,
and the final center located somewhere not too far from all agents (e.g.,
between the two groups of agents). Such solutions are intuitively reasonable
and fair and, furthermore, satisfy PRF; however, as mentioned in Example 3,
this instance does not admit a proportional fairness solution.

123546

Figure 2: Some of the requirements of PRF for instance in Example 1 .

Next, we highlight that the well-known $k$-means or $k$-median solutions do
not necessarily satisfy PRF. Example 5 is adapted from an example by Chen et
al. [19].

######  Example 5 ($k$-means does not satisfy PRF.).

Consider Figure 3 in which there are $n/3$ agents / data points uniformly
distributed on the perimeter of each of the three circles. If $k=3$, a
$k$-means or $k$-median solution will place one center close to the small
circles and two centers insider the big circle. In contrast, PRF requires that
each of the circles gets its own center facility.

$n/3$ points$n/3$ points$n/3$ points

Figure 3: The k-means solution may not satisfy PRF.

PRF is a property that requires conditions on an exponential number of subsets
of agents. For each subset of agents, it enforces representational constraints
pertaining to an infinite number of neighborhood distances. On face value, it
is not clear whether an outcome satisfying PRF exists as similar concept such
as proportional fairness cannot always be guaranteed [43]. Secondly, even if a
PRF outcome is guaranteed to exist, the complex constraints seem
computationally challenging. Perhaps surprisingly, we show that not only is a
PRF outcome guaranteed to exist, it can be computed in polynomial time.

The algorithm intuitively works as follows. Firstly, instead of considering
infinite possible centers, we restrict our attention to the $n$ candidates
centers that coincide with each agent’s location. Each agent is given an
initial weight of 1. This weight dynamically decreases over the course of the
algorithm. The algorithm can be viewed as gradually expanding the
neighborhoods of each of the agents.444The idea of expanding neighborhoods is
used in other algorithms in the literature such as the Greedy Capture
algorithm studied by Micha and Shah [43] for the unconstrained setting that is
a continuous algorithm that grows neighborhoods of each possible point. Unlike
our algorithm, it does not involve reweighting of agents. More importantly,
Greedy Capture does not satisfy PRF. Instead of continuously expanding the
neighborhood, we only consider at most $n^{2}$ possible values of radii for
which the neighborhoods of the agents are considered. If there exists some
location in the candidate set such that it is in the intersection of the
neighborhoods of a group of agents with total weight of at least $n/k$, we
select one such candidate. The process is continued until $k$ centers are
chosen. The algorithm is formally specified as Algorithm 1.

Algorithm 1 Algorithm for Unconstrained Clustering

Input: metric space $\mathscr{X}$ with a distance measure
$d:\mathscr{X}\times\mathscr{X}\rightarrow\mathbb{R}^{+}\cup\\{0\\}$, a finite
multiset ${\mathscr{N}}\subseteq\mathscr{X}$ of $n$ data points (agents), and
positive integer $k$.

Output: A multiset of $k$ centers

$w_{i}\longleftarrow 1$ for each $i\in{\mathscr{N}}$

Consider the set $D=\\{d(i,i^{\prime})\mid i,i^{\prime}\in N\\}$. Order the
entries in $D$ as $d_{1}\leq d_{2}\leq\cdots d_{|D|}$.

${\mathscr{M}}\longleftarrow{\mathscr{N}}$

$j\longleftarrow 1$

$W\longleftarrow\emptyset$

while $|W|<k$ do

$C^{*}=\\{c\in{\mathscr{M}}\mid\sum_{i\in{\mathscr{N}}\mid d(i,c)\leq
d_{j}}w_{i}\geq n/k\\}$

if $C^{*}=\emptyset$ then

$j\longleftarrow j+1$

else

Select some candidate $c^{*}$ from $C^{*}$ such that
$c^{*}=\arg\max_{c^{\prime}\in C^{*}}\sum_{i\in{\mathscr{N}}\mid
d(i,c^{\prime})\leq d_{j}}w_{i}$:$W\longleftarrow W\cup\\{c^{*}\\}$;
${\mathscr{M}}\longleftarrow{\mathscr{M}}\setminus\\{c^{*}\\}$

$N^{\prime}\longleftarrow\\{i\in{\mathscr{N}}\,:\,d(i,c^{*})\leq d_{j}\\}$

Modify the weights of voters in $N^{\prime}$ so the total weight of voters in
$N^{\prime}$, i.e., $\sum_{i\in N^{\prime}}w_{i}$, decreases by exactly $n/k$.

Return $W$

######  Lemma 1.

Algorithm 1 terminates in polynomial time $O(n^{4}k^{2})$ and returns $k$
centers.

###### Proof.

We prove by induction that if the number of candidates selected is less than
$k$, then there is a way to select at least one more center. If the number of
candidates selected is less than $k$, there is still aggregate weight of at
least $n/k$ on the set of all agents. These agents can get a candidate
selected from their neighborhoods if the neighborhood radius is large enough.
In particular, for $d_{|D|}=\max_{i,j\in N}d(i,j)$, some unselected candidate
from $M$ can be selected. Note that for a given radius $d_{j}$, at most $k$
candidates can be selected. If no more candidates can be selected for a given
$d_{j}$, the next radius $d_{j+1}$ is considered. There are $O(n^{2})$
different distances that are to be considered. Next, we bound the running
time. There are $(n^{2})$ different distances that are to be considered. These
distances are sorted in $O(n^{2}\log(n^{2}))$ time. For each distance that we
consider, we check for each of the $kn$ locations whether they get sufficient
support of $n/k$. It takes time $kn^{2}$ to check if some location has support
$n/k$ for the current neighborhood distance. If no location has enough
support, we move to the next distance. If some location has enough support, we
need to select one less location. Therefore, we need to check whether some
location has enough support at most $\max(k,n^{2}k)$ times. Therefore the
running time is $O(n^{2}\log(n^{2}))+O((kn^{2})(n^{2}k))=O(n^{4}k^{2})$. ∎

######  Lemma 2.

Algorithm 1 finds a set of $k$ centers that satisfies PRF.

###### Proof.

Suppose for contradiction that the algorithm finds a set of $k$ centers $W$
that violates PRF. In that case, there exist a set of agents
$S\subseteq{\mathscr{N}}$ of size at least $|S|\geq\ell n/k$ such that the
maximum distance between pairs of agents in $S$ is $y$ but the number of
locations that are within $y$ of some agent in $S$ is at most $\ell-1$. In
that case, consider the snapshot of the algorithm when neighborhood distance
$y=\max_{i,j\in S}d(i,j)$ is considered. At this point, $|c\in
X\mathbin{:}\exists i\in S\text{ s.t }d(i,c)\leq y|\leq\ell^{\prime}-1$ Since
agents in ${\mathscr{N}}$ have only used their weight towards selecting
locations within $y$ up till this point, it follows that $\sum_{i\in
S}w_{i}\geq\ell\frac{n}{k}-(\ell-1)\frac{n}{k}=\frac{n}{k}$. It follows that
the agents in $S$ still have total weight at least $\frac{n}{k}$ to select one
more location that is at distance at most $y$ from some agent in $S$. Hence,
at this stage, when the neighborhood distance is $y$, the algorithm would have
selected at least one more center within distance $y$ than in the outcome $W$.
∎

##  5 Fairness for the Discrete Setting

We presented PRF as a desirable concept for the unconstrained setting. It is
not immediate how to adapt the concept to the discrete setting. Applying the
unconstrained PRF definition to the discrete setting leads to issues of non-
existence. On the other hand, some natural attempts to account for the
coarseness of the candidate space, ${\mathscr{M}}$, can lead to a concept that
is too weak. For example, one alternative is to require that an outcome $X$ be
such that if, for any set of agents $S\subseteq{\mathscr{N}}$ of size at least
$|S|\geq\ell n/k$ such that the maximum distance between pairs of agents in
$S$ is $y$, the following holds: $|c\in X\mathbin{:}\exists i\in S\text{ s.t
}d(i,c)\leq y|\geq\min\\{\ell,|\cup_{j\in S}B_{y}(j)\cap{\mathscr{M}}|\\}$,
where $B_{r}(i)$ denote a ball of radius $r$ around agent $i$. Alternatively,
we could replace the right-hand side of the final inequality with
$\min\\{\ell,|\cap_{i\in S}B_{y}(i)\cap{\mathscr{M}}|\\}$. Both of these
versions are too weak. To see this, suppose $k=1$, all agents are located at
$0$, and ${\mathscr{M}}=(\ldots,-2,-1,1,2,3,\ldots)$, then neither version
places any restriction on the facility location and do not even imply UP.

To resolve these issues, we need to take into account that the nearest
candidate locations may be very far from a subset of agents. We adapt our PRF
concept for the discrete setting via a careful adaptation of the PRF concept
for the unconstrained setting.

######  Definition 5 (Proportionally Representative Fairness (PRF) for
Discrete Clustering).

For any set of agents $S\subseteq{\mathscr{N}}$ of size at least $|S|\geq\ell
n/k$, if there are $\ell^{\prime}\leq\ell$ candidates from ${\mathscr{M}}$
that are at distance at most $y$ from all agents in $S$, the following holds:
$|c\in X\mathbin{:}\exists i\in S\text{ s.t }d(i,c)\leq y|\geq\ell^{\prime}$.

For the discrete setting, we propose a new algorithm (Algorithm 2). Algorithm
2 is similar to Algorithm 1, which was designed for the unconstrained setting.
Similar to Algorithm 1, Algorithm 2 terminates in polynomial time and returns
$k$ centers (Lemma 3) and its output satisfies PRF (Lemma 4). The proofs of
these lemmas are similar to Lemmas 1 and 2.

Algorithm 2 Algorithm for the Discrete Clustering

Input: metric space $\mathscr{X}$ with a distance measure
$d:\mathscr{X}\times\mathscr{X}\rightarrow\mathbb{R}^{+}\cup\\{0\\}$, a finite
multiset ${\mathscr{N}}\subseteq\mathscr{X}$ of $n$ data points (agents), a
finite set of candidate locations ${\mathscr{M}}$, and positive integer $k$.

Output: A multiset of $k$ centers

$w_{i}\longleftarrow 1$ for each $i\in{\mathscr{N}}$

Consider the set $D=\\{d(i,c)\mid i\in{\mathscr{N}},c\in{\mathscr{M}}\\}$.
Order the entries in $D$ as $d_{1}\leq d_{2}\leq\cdots\leq d_{|D|}$.

$j\longleftarrow 1$

$W\longleftarrow\emptyset$

while $|W|<k$ do

$C^{*}=\\{c\in{\mathscr{M}}\mid\sum_{i\in{\mathscr{N}}\mid d(i,c)\leq
d_{j}}w_{i}\geq n/k\\}$

if $C^{*}=\emptyset$ then

$j\longleftarrow j+1$

else

Select some candidate $c^{*}$ from $C^{*}$ such that
$c^{*}=\arg\max_{c^{\prime}\in C^{*}}\sum_{i\in{\mathscr{N}}\mid
d(i,c^{\prime})\leq d_{j}}w_{i}$ :$W\longleftarrow W\cup\\{c^{*}\\}$;
${\mathscr{M}}\longleftarrow{\mathscr{M}}\setminus\\{c^{*}\\}$

$N^{\prime}\longleftarrow\\{i\in{\mathscr{N}}\,:\,d(i,c^{*})\leq d_{j}\\}$

Modify the weights of voters in $N^{\prime}$ so the total weight of voters in
$N^{\prime}$, i.e., $\sum_{i\in N^{\prime}}w_{i}$, decreases by exactly $n/k$.

Return $W$

######  Lemma 3.

Algorithm 2 terminates in polynomial time $O({|{\mathscr{M}}|}^{2}n^{2})$ and
returns $k$ centers.

###### Proof.

We prove by induction that if the number of candidates selected is less than
$k$, then then there is a way to select at least one one more center. If the
number of candidates selected is less than $k$, there is still aggregate
weight of at least $n/k$ on the set of all agents. These agents can get a
candidate selected from their neighborhood if the neighborhood distance is
large enough. In particular, for $d_{|D|}=\max_{i\in
N,c\in{\mathscr{M}}}d(i,c)$, some unselected candidate from $M$ can be
selected. Note that for a given radius $d_{j}$, at most $k$ candidates can be
selected. If no more candidates can be selected for a given $d_{j}$, the next
distance $d_{j+1}$ is considered.

Next we bound the running time. There are $(n\cdot|{\mathscr{M}}|)$ different
distances that are to be considered. These distances are sorted in
$O(n\cdot|{\mathscr{M}}|\log(n\cdot|{\mathscr{M}}|))$ time. For each distance
that we consider, we check for each of the $|{\mathscr{M}}|$ locations whether
they get sufficient support of $n/k$. It takes time $|{\mathscr{M}}|\cdot n$
to check if some location has support $n/k$ for the current neighborhood
distance. If no location has enough support, we move to the next distance. If
some location has enough support, we need to select one less location.
Therefore, we need to check whether some location has enough support at most
$\max(k,n\cdot|{\mathscr{M}}|)$ times. Therefore the running time is
$O(n\cdot|{\mathscr{M}}|\log(n\cdot|{\mathscr{M}}|))+O((|{\mathscr{M}}|\cdot
n)(k+n\cdot|{\mathscr{M}}|))=O({|{\mathscr{M}}|}^{2}n^{2})$. ∎

######  Lemma 4.

Algorithm 2 finds a set of $k$ centers that satisfies PRF.

The running time analysis is similar to the proof of Lemma 1.

###### Proof.

Suppose for contradiction that the algorithm finds a set of $k$ centers $W$
that violates PRF. In that case, there exist a set of agents
$S\subseteq{\mathscr{N}}$ of size at least $|S|\geq\ell n/k$ such that there
are at least $\ell^{\prime}\leq\ell$ locations in ${\mathscr{M}}$ that are
within distance $y$ of some agent in $S$, but the number of locations in $W$
that are within $y$ of at least some agent in $S$ is at most $\ell-1$. In that
case, consider the snapshot of the algorithm when neighborhood distance $y$ is
considered. At this point, the the number of locations that are within $y$ of
at least some agent in $S$ is at most $\ell-1$. Since agents in
${\mathscr{N}}$ have only used their weight towards selecting locations within
$y$ up till this point, it follows that $\sum_{i\in
S}w_{i}\geq\ell\frac{n}{k}-(\ell-1)\frac{n}{k}=\frac{n}{k}$. It follows that
the agents in $S$ still have total weight at least $\frac{n}{k}$ to select one
more location that is at distance at most $y$ from some agent in $S$. Hence,
at this stage, when the neighborhood distance is $y$, the algorithm would have
selected at least one more center within distance $y$ than in the outcome $W$.
Thus $W$ is not the correct output of the algorithm, a contradiction. ∎

######  Remark 1.

Algorithm 1 can be viewed as first setting ${\mathscr{M}}$ to the multiset of
candidate locations corresponding to agents in ${\mathscr{N}}$ and then
running Algorithm 2.

######  Remark 2.

Chen et al. [19] present an algorithm called “Greedy Capture.” An equivalent
algorithm, called ALGg, is also presented by Li et al. [40]. However, it can
be shown that these algorithms do not satisfy PRF. In fact, for given $k$,
these algorithms may fail to output $k$ candidate locations.555To see this,
let $k=3$ and let $\boldsymbol{x}=(0,0,1)$. Chen et al.’s Greedy Capture
algorithm and Li et al.’s ALGg will select candidate locations 0 and 1, but
will not output a 3rd location. Of course, this issue could be rectified by
arbitrarily choosing a 3rd candidate location—but then there is no guarantee
that the set of locations would satisfy PRF.

We consider two natural and stronger notions of PRF in the discrete setting
(that also apply to the continuous setting). We will show that the versions
that we consider do not guarantee the existence of a fair outcome in all
settings.

The PRF concept can be increasingly strengthened in the following ways by
making the requirements on the outcome stronger.

######  Definition 6 (Proportionally Representative Fairness (PRF)-II for
Discrete Clustering).

For any set of agents $S\subseteq{\mathscr{N}}$ of size at least $|S|\geq\ell
n/k$, if there are $\ell^{\prime}\leq\ell$ candidates from ${\mathscr{M}}$
that are at distance at most $y$ from all agents in $S$, the following holds:
there exists some $i\in S$ such that $|c\in X\mathbin{:}d(i,c)\leq
y|\geq\ell^{\prime}$.

######  Definition 7 (Proportionally Representative Fairness (PRF)-III for
Discrete Clustering).

For any set of agents $S\subseteq{\mathscr{N}}$ of size at least $|S|\geq\ell
n/k$, if there are $\ell^{\prime}\leq\ell$ candidates from ${\mathscr{M}}$
that are at distance at most $y$ from all agents in $S$, the following holds:
$|c\in X\mathbin{:}d(i,c)\leq y\text{ for all }i\in S|\geq\ell^{\prime}$.

The following example shows that an outcome satisfying PRF-II may not exist
(and hence also PRF-III may not exist).

######  Example 6.

Take $n=4,k=2$ with the following location profile on a unit interval $[0,1]$:
$\boldsymbol{x}=(0,0,1,1).$ There are 4 candidate locations at
${\mathscr{M}}=(0,0.5,0.5,1)$. It is immediate that the 2 groups of agents at
$0$ and $1$ must have a facility at $0$ and $1$. But this violates PRF-II. The
set of agents $N$ (size 4) have 2 candidate locations with a distance of $0.5$
of all agents; however, no agent in $N$ has 2 facility locations within a
distance of 0.5 of them.

##  6 Experiment

| MSD to $1$ | MSD to $k/2$ | MSD to $k$
---|---|---|---
|  $k$++ | Alg 1 | $ALG_{g}$ |  $k$++ | Alg 1 | $ALG_{g}$ |  $k$++ | Alg 1 | $ALG_{g}$
|  | Difference in MSD | Difference in MSD |  | Difference in MSD | Difference in MSD |  | Difference in MSD | Difference in MSD
Dataset | Average MSD | relative to $k$++ | relative to $k$++ | Average MSD | relative to $k$++ | relative to $k$++ | Average MSD | relative to $k$++ | relative to $k$++
Wholesale | 34,977,392.00 | 664% | 112% | 11,668,107,198.00 | -10% | -12% | 100,307,739,343.00 | -63% | -55%
HCV | 811.60 | 519% | 429% | 582,360.00 | -4% | -6% | 4,858,449.00 | -70% | -62%
Buddy | 782.20 | 8% | 5% | 181,700.00 | -8% | -7% | 784,360.00 | -13% | -9%
Seeds | 0.54 | 23% | 8% | 228.68 | -1% | -1% | 1,449.94 | -4% | -1%

Table 1: Performance of clustering algorithms with respect to MSD to 1, k/2,
and k centroids.

Figure 4: HVC dataset: MSD to closest 1, k/2, and k centroids.

We now apply Algorithm 1 to four real-world datasets. We consider the discrete
domain in which ${\mathscr{M}}={\mathscr{N}}$ as most clustering data sets
only have the data points. Algorithm 1 is guaranteed to satisfy PRF;
therefore, we are interested in analyzing the performance of the algorithm
with respect to other objectives. A prominent objective for clustering
algorithms is to minimize the _Mean Squared Distance (MSD) to the closest
center_ : the average distance between each datapoint and its closest center.
We consider this performance measure as the number of centers ranges from
$k=1$ to $100$.

In addition, to MSD to the closest center, we analyze two other related
measures. MSD to the closest $k/2$ centers and MSD to the closest $k$ centers.
Intuitively, MSD to the closest $k/2$ centers is the average distance between
each datapoint and its $k/2$-closest centers (MSD to the closest $k$ centers
is similar). These measures capture—to varying extents—the idea that it may be
desirable to have datapoints located close to more than just one center; this
idea is at the core of the proportional representation concept. To benchmark
Algorithm 1’s performance, we also implement two other algorithms: the well-
known $k$-means++ algorithm666I.e., Lloyd’s algorithm for $k$-means
minimization objective with a particular initialization. Given our focus on
the discrete domain, we use a $k$-means++ algorithms that only chooses centers
from among the data points.  of Arthur and Vassilvitskii [6] and ALGg of Li et
al. [40]. For all of our MSD measures, a smaller value is more desirable.

### Datasets.

The four datasets that we analyze are from the UCI Machine Learning Repository
[26]. We summarize these below.777 The datasets are licensed under a Creative
Commons Attribution 4.0 International License (CC BY 4.0); for details, please
refer to https://archive-beta.ics.uci.edu/ml/donation-policy.

HCV dataset contains information about patients with Hepatitis C and blood
donors.

Seeds dataset describes measurements of geometrical properties of kernels
belonging to three different varieties of wheat. The data consists of 7 real-
valued variables: area, perimeter, compactness, length and width of kernel, an
asymmetry coefficient, and length of kernel groove.

Buddy-move dataset consists of user information extracted from user reviews
published in www.holidayiq.com about point of interests in South India. The
attributes are integer-valued consisting of the number of reviews for: sports
complexes, religious institutions, natural and cultural areas, shopping areas,
and parks and picnic spots.

Wholesale dataset consists of client information for a wholesale distributor.
It includes the annual spending on various product categories, e.g., fresh
foods, milk, groceries, frozen foods, detergents and paper products,
delicatessen, retail, and location.

### Results

We summarize our results in Table 1 and illustrate our analysis in the
subsequent figures. Across all the datasets, Algorithm 1’s performance
relative to $k$-means improves when moving from MSD to closest center to MSD
to closest $k/2$ centers and MSD to closest $k$ centers. A similar pattern is
observed for $ALG_{g}$, which may be expected and is reassuring since—like
Algorithm 1—$ALG_{g}$ is motivated by the idea of proportional fairness. For
two of the datasets (Wholesale and HCV), Algorithm 1 offers substantially
better performance compared to $k$-means with respect to MSD to closest $k$
centers. In these cases, Algorithm 1 also outperforms $ALG_{g}$. For MSD to
the closest $k/2$ centers, $ALG_{g}$ and Algorithm 1 either outperform or
perform similar to $k$-means. In contrast, and as expected, the $k$-means
outperforms both algorithms with respect to the MSD to closest center. With
this measure, $ALG_{g}$ typically outperforms Algorithm 1. The experiments
illustrate that other well-known algorithms produce different outcomes
compared to our Algorithm 1, and this difference can be quantified via an
intuitive PRF-related metric, i.e., minimizing the MSD to multiple centers.

Figure 5: Buddy dataset: MSD to closest 1, k/2, and k centroids.

Figure 6: Seeds dataset: MSD to closest 1, k/2, and k centroids.

Figure 7: Wholesale dataset: MSD to closest 1, k/2, and k centroids.

##  7 Discussion and conclusion

We revisited a classical AI problem with a novel solution concept that is
based on ideas from the theory of social choice and fair division. We proposed
a natural fairness concept called proportionally representative fairness (PRF)
for clustering in both the unconstrained and discrete settings. PRF is
guaranteed to exist and has desirable features: it implies unanimous
proportionality, does not require the specification of protected groups, and
is robust to outliers and multiplicative scaling. A natural next step is to
identify and analyze stronger versions of the PRF axiom that still guarantees
existence.

It will be interesting to consider more refined versions of the PRF algorithm
that make more clever choices while selecting candidates with sufficient
weighted support. Another direction for future research is the understanding
how much impact the constraint of PRF imposes on standard optimization
objectives such as for $k$-means, $k$-median, or $k$-center. For specific
applications domains where clustering is performed, there may be a possibility
to use additional features of the application and a clearer interpretation of
the data to formalize more nuanced versions of fairness [25] and perhaps also
find natural proportional fairness axioms that are incentive compatible.

## References

  * Abbasi et al. [2021] Abbasi, M., Bhaskara, A., Venkatasubramanian, S., 2021. Fair clustering via equitable group representations. In: Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency. FAccT ’21. Association for Computing Machinery, New York, NY, USA, pp. 504–514.
  * Ahmadian et al. [2019] Ahmadian, S., Epasto, A., Kumar, R., Mahdian, M., 2019. Clustering without over-representation. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM, pp. 267–275.
  * AI-Committee [2019] AI-Committee, 2019. The national artificial intelligence research and development strategic plan: 2019 update. Tech. rep., National Science and Technology Council, Washington, D.C.
  * Airiau et al. [2019] Airiau, S., Aziz, H., Caragiannis, I., Kruger, J., Lang, J., Peters, D., 2019. Portioning using ordinal preferences: Fairness and efficiency. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI). IJCAI.
  * Aloise et al. [2009] Aloise, D., Deshpande, A., Hansen, P., Popat, P., 2009. Np-hardness of euclidean sum-of-squares clustering. Machine Learning 75 (2), 245–248.
  * Arthur and Vassilvitskii [2007] Arthur, D., Vassilvitskii, S., 2007. k-means++: the advantages of careful seeding. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007\. SIAM, pp. 1027–1035.
  * Aziz et al. [2019] Aziz, H., Bogomolnaia, A., Moulin, H., 2019. Fair mixing: the case of dichotomous preferences. In: Proceedings of the 20th ACM Conference on Electronic Commerce (ACM-EC). pp. 753–781.
  * Aziz and Lee [2020] Aziz, H., Lee, B., 2020. The expanding approvals rule: Improving proportional representation and monotonicity. Social Choice and Welfare 54 (1), 1–45.
  * Aziz and Lee [2021] Aziz, H., Lee, B. E., 2021. Proportionally representative participatory budgeting with ordinal preferences. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI).
  * Aziz et al. [2018] Aziz, H., Luo, P., Rizkallah, C., 2018. Rank maximal equal contribution: a probabilistic social choice function. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI).
  * Aziz and Rey [2020] Aziz, H., Rey, S., 2020. Almost group envy-free allocation of indivisible goods and chores. In: Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI). pp. 39–45.
  * Backurs et al. [2019] Backurs, A., Indyk, P., Onak, K., Schieber, B., Vakilian, A., Wagner, T., 2019. Scalable fair clustering. In: Proceedings of the 36th International Conference on Machine Learning, ICML. Vol. 97 of Proceedings of Machine Learning Research. PMLR, pp. 405–413.
  * Bera et al. [2019] Bera, S. K., Chakrabarty, D., Flores, N., Negahbani, M., 2019. Fair algorithms for clustering. In: Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019,. pp. 4955–4966.
  * Berliant et al. [1992] Berliant, M., Thomson, W., Dunz, K., 1992. On the fair division of a heterogeneous commodity. Journal of Mathematical Economics 21 (3), 201–216.
  * Brill et al. [2020] Brill, M., Gölz, P., Peters, D., Schmidt-Kraepelin, U., Wilker, K., 2020. Approval-based apportionment. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI).
  * Brubach et al. [2020] Brubach, B., Chakrabarti, D., Dickerson, J. P., Khuller, S., Srinivasan, A., Tsepenekas, L., 2020. A pairwise fair and community-preserving approach to k-center clustering. In: Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event. Vol. 119 of Proceedings of Machine Learning Research. PMLR, pp. 1178–1189.
  * Chakrabarty and Negahbani [2021] Chakrabarty, D., Negahbani, M., 2021. Better algorithms for individually fair k-clustering. CoRR abs/2106.12150.
  * Chan et al. [2021] Chan, H., Filos-Ratsikas, A., Li, B., Li, M., Wang, C., 2021. Mechanism design for facility location problems: A survey. In: Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI).
  * Chen et al. [2019] Chen, X., Fain, B., Lyu, L., Munagala, K., 2019. Proportionally fair clustering. In: Proceedings of the 36th International Conference on Machine Learning, ICML. Vol. 97 of Proceedings of Machine Learning Research. PMLR, pp. 1032–1041.
  * Chierichetti et al. [2017] Chierichetti, F., Kumar, R., Lattanzi, S., Vassilvitskii, S., 2017. Fair clustering through fairlets. In: Proceedings of the 31st Annual Conference on Neural Information Processing Systems (NeurIPS). pp. 5029–5037.
  * Chiplunkar et al. [2020] Chiplunkar, A., Kale, S., Ramamoorthy, S. N., 2020. How to solve fair k-center in massive data models. In: Proceedings of the 37th International Conference on Machine Learning, ICML 2020. Vol. 119. PMLR, pp. 1877–1886.
  * Chouldechova and Roth [2020] Chouldechova, A., Roth, A., 2020. A snapshot of the frontiers of fairness in machine learning. Communications of the ACM 63 (5), 82–89.
  * Congressional-Research-Service [2021] Congressional-Research-Service, 2021. Artificial intelligence: Background, selected issues, and policy considerations. Tech. rep., Congressional Research Service Reports.
  * Conitzer et al. [2019] Conitzer, V., Freeman, R., Shah, N., Vaughan, J. W., 2019. Group fairness for the allocation of indivisible goods. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI).
  * Deepak [2020] Deepak, P., 2020. Whither fair clustering? In: AI for Social Good Workshop.
  * Dua and Graff [2017] Dua, D., Graff, C., 2017. UCI machine learning repository. _University of California, Irvine, School of Information and Computer Sciences_.
URL http://archive.ics.uci.edu/ml

  * Dummett [1984] Dummett, M., 1984. Voting Procedures. Oxford University Press.
  * Dummett [1997] Dummett, M., 1997. Principles of Electoral Reform. Oxford University Press.
  * Dwork et al. [2012] Dwork, C., Hardt, M., Pitassi, T., Reingold, O., Zemel, R. S., 2012. Fairness through awareness. In: Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012. ACM, pp. 214–226.
  * Esmaeili et al. [2021] Esmaeili, S. A., Brubach, B., Srinivasan, A., Dickerson, J. P., 2021. Fair clustering under a bounded cost. In: Proceedings of the 35th Annual Conference on Neural Information Processing Systems (NeurIPS).
  * Esmaeili et al. [2020] Esmaeili, S. A., Brubach, B., Tsepenekas, L., Dickerson, J., 2020. Probabilistic fair clustering. In: Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual.
  * European Commission [2020] European Commission, Feb. 2020. White paper on artificial intelligence: a european approach to excellence and trust. White Paper COM(2020) 65 final, European Commission, Brussels.
  * Everitt et al. [2009] Everitt, B. S., Landau, S., Leese, M., 2009. Cluster Analysis, 4th Edition. Wiley Publishing.
  * Faliszewski et al. [2017] Faliszewski, P., Skowron, P., Slinko, A., Talmon, N., 2017. Multiwinner voting: A new challenge for social choice theory. In: Endriss, U. (Ed.), Trends in Computational Social Choice. Ch. 2.
  * Faliszewski et al. [2018] Faliszewski, P., Slinko, A., Stahl, K., Talmon, N., 2018. Achieving fully proportional representation by clustering voters. Journal of Heuristics 24 (5), 725–756.
  * Farahani and Hekmatfar [2009] Farahani, R. Z., Hekmatfar, M., 2009. Facility location: concepts, models, algorithms and case studies. Springer Science & Business Media.
  * Friedman and Nissenbaum [1996] Friedman, B., Nissenbaum, H., Jul. 1996. Bias in computer systems. ACM Trans. Inf. Syst. 14 (3), 330–347.
  * Jung et al. [2020] Jung, C., Kannan, S., Lutz, N., 2020. Service in your neighborhood: Fairness in center location. In: 1st Symposium on Foundations of Responsible Computing, FORC 2020, June 1-3, 2020, Harvard University, Cambridge, MA, USA (virtual conference). Vol. 156 of LIPIcs. pp. 5:1–5:15.
  * Kleindessner et al. [2019] Kleindessner, M., Samadi, S., Awasthi, P., Morgenstern, J., 2019. Guarantees for spectral clustering with fairness constraints. In: Proceedings of the 36th International Conference on Machine Learning (ICML). Vol. 97. PMLR, pp. 3458–3467.
  * Li et al. [2021] Li, B., Li, L., Sun, A., Wang, C., Wang, Y., 2021. Approximate group fairness for clustering. In: Proceedings of the 38th International Conference on Machine Learning. Vol. 139 of Proceedings of Machine Learning Research. PMLR, pp. 6381–6391.
  * Megiddo and Supowit [1984] Megiddo, N., Supowit, K. J., 1984. On the complexity of some common geometric location problems. SIAM Journal on Computing 13 (1), 182–196.
  * Mehrabi et al. [2021] Mehrabi, N., Morstatter, F., Saxena, N., Lerman, K., Galstyan, A., 2021. A survey on bias and fairness in machine learning. ACM Computing Surveys 54 (6).
  * Micha and Shah [2020] Micha, E., Shah, N., 2020. Proportionally fair clustering revisited. In: 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020\. Vol. 168. pp. 85:1–85:16.
  * Moulin [2003] Moulin, H., 2003. Fair Division and Collective Welfare. The MIT Press.
  * O’Neil [2016] O’Neil, C., 2016. Weapons of Math Destruction: How Big Data Increases Inequality and Threatens Democracy. Crown Publishing Group, USA.
  * Pierczynski and Skowron [2021] Pierczynski, G., Skowron, P., 2021. Core-stable committees under restricted domains. CoRR.
  * Pukelsheim [2014] Pukelsheim, F., 2014. Proportional Representation: Apportionment Methods and Their Applications. Springer.
  * Sánchez-Fernández et al. [2017] Sánchez-Fernández, L., Elkind, E., Lackner, M., Fernández, N., Fisteus, J. A., Basanta Val, P., Skowron, P., 2017. Proportional justified representation. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI). AAAI Press.
  * Vakilian and Yalçiner [2021] Vakilian, A., Yalçiner, M., 2021. Improved approximation algorithms for individually fair clustering. CoRR abs/2106.14043.