Fair and Optimal Decision Trees: A Dynamic Programming Approach
Authors: Jacobus G.M. van der Linden
Mathijs Weerdt
Emir Demirović
Venue: NeurIPS 2022 Accept (2022)
Keywords: optimal decision trees
group fairness
dynamic programming

Abstract: Interpretable and fair machine learning models are required for many applications, such as credit assessment and in criminal justice. Decision trees offer this interpretability, especially when they are small. Optimal decision trees are of particular interest because they offer the best performance possible for a given size. However, state-of-the-art algorithms for fair and optimal decision trees have scalability issues, often requiring several hours to find such trees even for small datasets. Previous research has shown that dynamic programming (DP) performs well for optimizing decision trees because it can exploit the tree structure. However, adding a global fairness constraint to a DP approach is not straightforward, because the global constraint violates the condition that subproblems should be independent. We show how such a constraint can be incorporated by introducing upper and lower bounds on final fairness values for partial solutions of subproblems, which enables early comparison and pruning. Our results show that our model can find fair and optimal trees several orders of magnitude faster than previous methods, and now also for larger datasets that were previously beyond reach. Moreover, we show that with this substantial improvement our method can find the full Pareto front in the trade-off between accuracy and fairness.

Fair and Optimal Decision Trees: A Dynamic Programming Approach
Jacobus G.M. van der Linden Mathijs M. de Weerdt Delft University of Technology, Department of Computer Science
Emir Demirović
{J. G.G.MM vanderLinden, M.M. deWerrt,, E. D.Dem
Abstract
Interpretable and fair machine learning models required for many applications, such as credit assessment and in criminal justice. Decision trees offer this inter- pretability, especially when they are small. Optimal decision trees of particular interest because they offer the best performance possible for a given size. However, state-of-the-art algorithms for fair and optimal decision trees have scalability issues, often requiring several hours to find such trees even for small datasets. Previous research has shown that dynamic programming (DP) performs well for optimizing decision trees because it can exploit the tree structure. However, adding a global fairness constraint constraint violates the condition that subproblems should be independent. We show how such constraint can be incorporated by introducing upper and lower bounds on final fairness values for partial solutions of subproblems, which enables early comparison and pruning. Our results show that our model can find fair and optimal trees several orders of magnitude faster than previous methods, and now also for larger datasets that were previously beyond reach. Moreover, we show that with this substantial improvement method can find the full Pareto front in the trade-off between accuracy and fairness.
DP approach not straightforward. because the global
Introduction
As machine learning (ML) is used in more domains that involve discrimination-sensiin decisions, demand for fair, interpretable and accurate models increases. ML, for example, is used in criminal justice [8) credit assessment
(28), and housing appointments [7], each of which requires fair decisions. Simply removing the diseriminatioon-sesiiive attribute from the dataset does necessarily result in less discrimination
[3 Instead, fairness is obtained by adding a constraint on the classifier: often group fairness constraint (see [10 20 for a comparison of the two). The focus this paper is on group fairness. With group fairness, a binary classifier considered fair the probability of receiving the positive outcome the same for all protected groups. This fairness metric is formulated as global constraint over the full dataset.
either individual
To increase confidence and prevent errors in these munsitive-deciion domains, it also important that the ML models are interpretable [39]. Decision trees offer inherent interpretability and do not carry some of the risks of post-hoc attempts explaining black-box models (36). This is especially the case when decision trees are small [4]. On average, optimal decision trees, i.c., trees that for a given size provably maximize objective such as accuracy, provide better out-of-sample performance than trees generated by heuristics when comparing trees of equal size [9] [5]. Therefore small optimal decision trees are ideal when searching for accurate and interpretable models.
There are several approaches for finding fair and optimal decision trees 2. use mixed integer programming (MIP). However, none of these models scale well. If faimess is not considered, small optimal decision trees can be found efficiently by using dynamic programming (DP)
40) all of which
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

methods that exploit the separability present in the tree structure 4 15 23 31]. Demirović and Stuckey [14) also use DP to find the Pareto front of optimal decision trees for biobjective nonlinear metrics.
However, a global fairness constraint cannot trivially he added to these algorithms,, because the fairness constraint breaks the separability assumption by introducing dependency between subproblems. When optimizing for accuracy, for example, left and right subtrees can be solved independently after choosing what feature to branch on in the current decision node. In contrast, when optimizing for fairness, the left and right subtree cannot be optimized independently, since imbalance one part of the tree can be cancelled out in another part of the tree.
Motivated by the success of DP methods for conventional optimal trees, we developed novel DP method that successfully incorporates a global fairness constraint. We solve the subproblem dependency by computing upper and lower bounds the final fairness values of partial solutions, thus enabling early pruning of the search space. Moreover, we present algorithmic improvements in the merging and comparing subproblems, and perform study of scalability. Overall our approach provides orders of magnitude improvements over state-of-the-art MIP methods.
This has several benefits. First, our algorithm can find fair and optimal decision trees for datasets that were previously too large to consider, often even within seconds. Second, it can find deeper and more accurate trees, while still satisfying the fairesss constraint. Last, our algorithm pureto-front in the trade-off between accuracy and fairness. This enables the responsible domain expert make well-informed decision and select policy from the solution set that fits the context and application best.
find the full
As is commonly done in optimal decision tree search, we assume that all features have been binarized in advance [[2]. Similarly, it is assumed that the label of every instance in the dataset is binary: either the positive/preferred outcome or the negative outcome. This is common assumption in fair classification [6] and was also assumed in previous fair and optimal decision tree methods 25
The paper setup is as follows: we first discuss related work and preliminaries, and then we present our method. Finally, we evaluate the performance of the new method on twelve datasets from different application domains and we compare its performance to a leading MIP method from the literature.
2 Related work
This section discusses, in order, the related work of 1) algorithms for finding optimal decision trees, 2) MIP models for finding fair optimal decision trees, and finally 3) other (non-optimal) methods for finding fair decision trees.
Algorithms for Optimal Decision Trees. The search for optimal decision trees is an NP-Hard problem (24]. Therefore decision tree search was traditionally done by means of heuristics such as the much-used CART algorithm [11]. Because of increasing computation power, searching for optimal decision trees has become feasible and Bertsimas and Dunn [ showed that optimal decision trees can offer 1-5% better out-of-sample accuracy scores than previous heuristics. Their MIP model was consecutively improved by several others 41 42
During the same period, custom search and bound- approaches, using techniques such as caching and branching, for finding (binary) classification trees were developed. These methods often outperformed the MIP models in terms of runtime and scalability, sometimes reducing runtimes of several hours to several seconds, by utilizing dynamic programming in depth-first 4 5 [5] or
breadth- approach 23 31.
Of particular interest for this paper is the method presented in 14] which extends on these methods and finds decision trees for biobjective optimisation, minimizing the misclassification score for both classes in binary classification at the same time and returning the Pareto front of nondominated solutions. This method is further discussed in the preliminaries.
Fairness in Optimal Decision Trees. Currently, the only methods for finding fair and optimal decision trees are MIP-based. Verwer and Zhang [40] developed a MIP model with a soft group fairness constraint in the objective. They report how their method can find fair depth- three tree for

---

dataset of 1000 instances in 15 minutes, when the model is given an initial solution from CART. But for the fair tree case they do not report being able to prove optimality within this time limit.
Aghaei et al. (2 present a MIP model that co-optimizes fairness and error for both classification and regression. Apart from group fairness, they also consider a notion of individual faimesss separately. However, they are criticized by Ranzato et al. (35) that their model often provides accuracy not much better than a constant classifier. In 3 and 225 they continue their work and present a MIP model based on a max-flow formulation that results in considerable improvement of the runtime. However, these models still have scalability issues because of the large number of binary variables.
Other methods for Fair Decision Trees. For completeness the following section mentions number of related fair decision tree methods that do not guarantee a globally optimal solution. These can be divided into pre-, in-, and postprocessing methods.
Kamiran and Calders [26] present preprocessing method that changes the labels in the dataset according to a group fairness metric. The updated dataset can then be used to train any regular classifier.
Some of the in-processing methods consider fairness in the classifier itself. Others use a regular classifier, combined with meta- master problem that takes care of the fairness constraint. Pedreschi et al. 33 for example, develop a method for finding fair association rules that can then be used to compile decision trees. Agarwal al. [ iteratively solve number of cost-sensitive classification problems, with the costs determined by the number of violations of the fairness constraint. Grari al. 21 propose gradient tree boosting approach with an adversarial faimess constraint. Detassis et al. use MIP master problem that changes the labels for the next training iteration to satisfy the fairness constraint. There is, however, no guarantee of convergence. Valdivia et al. [8 developed an evolutionary algorithm that returns a Pareto front of decision trees with the multiobjective of both fairness and accuracy.
Kamiran et al. (7 test a CART-hased approach with a split criterion that is a mix of information gain in the label and the sensitive feature. They did not observe significant improvement when using this approach. As an alternative, they suggest a postprocessing relabeling method that uses a greedy knapsack algorithm to decide which leaf nodes relabel improve fairness at a minimum cost of accuracy.
Summary of related work. In summary, the current state-of-the-art has scalable custom methods for finding optimal conventional decision trees, but adding fairness constraints to these methods is non-trivial. MIP-based solutions exist for this problem, but they not scale well. The alternative to use heuristic methods, which result in suboptimal solutions.
3 Preliminaries
This section discusses the preliminaries of our method: an introduction of notation, formal intro- duction of group fairness, a formal problem definition, and a dynamic programming formulation for optimal decision tree search that does not consider fairness.
Notation. A dataset D contains instances (x, a, y). with x the feature vector, a the sensitive attribute and y the label value. The number of instances in the dataset D is N [D]. Let y be the label of instance and a; the value of the protected feature. Let F be the feature set and f E F a feature in the feature set. We use f. to denote the value of this feature for instance i. Since we are only considering binary features and binary classification, we introduce the shorter notation fi and Se to mean respectively that instance i satisfies or does not satisfy feature f. The same idea applies for y and y, and a and a. We use subseript notation to refer to a subgroup of the dataset: for example, Dj refers to all instances dataset D that do not satisfy feature f: NN is the number of instances in the dataset that belong to group a, and N y is the number of instances in the dataset with positive outcome that does not belong group a.
Group Fairness Formalized. The specific group fairness definition considered in this paper is demographic parity, although our method can easily be extended to support other notions of group fairness, such as equality of opportunity. Demographic parity requires that the performance (the
3

---

expected percentage of positive outcomes) per group is the same 20)] More formally, if is the predicted outcome, 1 the positive outcome, and represents a (bmmary) sensitive/protected group. then demographic parity holds iff:
P)==1[a=1)=P6 =
(1)
In binary classification, this constraint can be measured by considering the relative average perfor- mance of the two groups. Let ý be the percentage of instances that receive the positive outcome, so Ps / The difference in the performance between two groups is what we will call the imbalance = Pa - Pa- When the imbalance is limited to some value ò, we say that it satisfies demographic parity up to bias ò:
|1| 10. Pal S
According to the definition of demographic parity, if leaf node n receives label O, the partial imbalance I in that node also Otherwise, the partial imbalance in a leaf node can be expressed as follows:
Nn,a I No
Nn.a
Na
The partial imbalance of branching node is the sum of the imbalance of both sub-nodes.
Problem Definition. The task of learning optimal fair decision tree is to find the feature value tests the branch nodes and the leaf node assignments for a tree of a given maximum size that minimize the number of misclassification in a training data set while observing fairness constraint. The percentage of correctly classified instances is called accuracy. This can be formalized as follows. The task is to find a decision tree classifier I: {0, 131 + {0. 1) of depth d that minimizes the misclassification score for given dataset 'D while observing fairness constraint up to bias d:
min (x.a.y)e
Σ
[xx) yl
(4)
h(x)
h(x)
s.t.
Σ
Σ
S 8
Na
N
(x,
(x,
Alternatively, when searching for the full Pareto front, the parameter 5 is not necessary, and the problem can be written multiobjective problem:
h(x)
h(x)
min h
Σ (X.D
[h(x) yl.
Σ
Σ
(5)
No
Na
(X,..)ED.
(X.
The Pareto front for Eq. consists of all nondominated solutions (M, with M the misclassification score and / the imbalance. A solution is considered dominated if there is another solution that performs better or similar on all objectives. Therefore, we can define the dominance relation (>) for two solutions (M1, I1) and (M2, I2). and the function nondom as follows:
(Mr. 11) (M2, I2) iff M1 S M2 A |1 nondom S) {s1 E - 82 E S, 813
1 A (M1 11) # (22
(6)
$1}
Dynamic Programming Formulation for Decision Trees. The problem of finding accurate decision trees has been formulated as a DP problem before in [15). Of interest to this paper is the formulation for biobjective optimization in [14]. They minimize the misclassification score two classes at the same time and return the Pareto front of nondominated solutions:
{(O, (PP)l.)))))
d = 0 else
ThE (D, = nondom (USer merge (Tii(D,, - 1)) ()..dd-)),,((
(8)
At the leaf node (d 0), the function returns two solutions consisting of values: the misclassifi- cation score per class (e.g., (0, |Dyl) when label ý = 0 is selected, because all instances with y 0 will correctly classified and all instances with y = will cause D,I misclassifications for class 1). At branching node (d > 0), the function should return the merge of two solution sets and retain only the nondominated solutions resulting from that merge. The function merge combines two sets of partial solutions (from the left and right subtree) by clement-wise addition:
merge(S1, S2) {(a + ag b b2) (a1,b1) b1) E S1, (a2, b2) S2)
(9)

---

Method Description
In this section, present method DPF (DP Fair) and show how to deal with global fairness constraint that introduces subproblem dependency. Similar to Eq. [ we define recursive function TF that returns set of all nondominated (partial) solutions, resulting in full Pareto front of fair and optimal decision trees, In order to guarantee that the method returns the full Pareto front we must do an exhaustive search of all combinations of subtrees, pruning only those solutions for which we can prove that they will never be part of an optimal (nondominated) solution.
Dependency. The recursive function 8 introduced in the preliminaries assumes that the left and the right tree can be independently optimized, but this not the case when considering group fairness, which global constraint on the whole tree. When comparing two possible subtrees, one of which discriminates against group A and the other discriminating against group B, it is not clear which one is better, because will depend on what happens in the rest of the tree. Even when both subtrees discriminate against the same group A. it is not immediately clear that the one with lower discrimination score will be better, but again will depend on what happens in the rest of the tree.
More formally, the previous proposed biobjective method requires objectives to be additive and monotonic in order to create independent subproblem. The additive property holds if two partial solutions (a, b) and (a', 1/) can be combined by addition: (a + a', b. B)) The monotonic property holds for biobjective function f(a, if for any two possible different inputs a, b and a' b, the following dominance relation holds:
S aD' f(a.b) > f(a',b')
(10)
However, because fairness is measured by the absolute value of the imbalance, both the additive property and the monotonic property are not satisfied. Our method addresses this problem.
Upper and lower bounds for fairness. The key idea in our method is to compute upper and lower bounds for the imbalance value of partial solutions to enable comparison. When upper and lower bounds In and In are known for the imbalance in the rest (R) of the tree, then the final imbalance value of tree that contains node n will be in the range: [IR + Ins J In]- The lower bound (f) and the upper bound (!) for the final absolute imbalance value can now be computed:
I[In, [I,, Jn]) = 10
0 E [RR + In, I + In]
(11)
min (M/R + 4nb. 1R + 4.) I(In, [RR, IR]) max (I/R In), [R + In)
else
(12)
In Eq. [1]] the lower bound is zero if the permitted range contains zero; otherwise it is the minimum absolute value in that range. Eq. [2] the upper bound is the maximum absolute value in the permitted range.
With these upper and lower bounds on the final absolute imbalance value, we can redefine the dominance relation of Eq.
[
(M,, 41) > (M2, 12)) iff (M1 11) * (M2
M1 S M2
(13)
(I(T, [In, JR)) S I(12, [R), V 1 = =2)
solution is dominated by another solution if 1) the other solution has lower misclassification score; and either has an upper bound the absolute imbalance lower than the lower bound on the absolute imbalance of this solution, or has precisely the same imbalance score.
Finding the Pareto front of optimal fair trees. trees TF (D, d, [R, In]) that optimizes Eq. 5
Now can define new function for finding fair
leaf(DD LR IRl) branch(D, d, [RR, IR])
d=0
Tr(D, d. [R, In]) ={
(14)
else
The functions leaf and branch will be introduced next. Both use the nondom function, which is now based on our new dominance comparison as described in Eq. 13 (but for ease of notation, [Ln, Tn] will often be left out).
5

---

In leaf node the function should return the following (M, I) solutions, with imbalance values based on Eq.
(D, [n. Tn]) = nondom (<11B)).) (), (DD)). Nu.a Nn,a
)})
(15)
No
Na
Eq. returns up to two solutions, each described by two values: first the misclassification score as before, and second the imbalance when assigning the positive outcome.
In a branching node, the data set is split on some feature f. resulting in two subproblems. Each subproblem is solved independently by passing the best known bounds for the other subproblem. Let (D), f. LR,, [n]. d - 1) denote the function that returns these best known bounds. These bounds can be based on dataset inspection, or based on previous (cached) solutions. Bounds from inspecting the dataset can be derived by assigning one label to all instances of one group and the other label to all other instances and vice versa. The results provide the maximum discrimination that could possibly happen. When (cached) partial solutions for the rest of the tree are known, the bounds can be derived by taking the minimum and maximum imbalance values among solutions. With these bounds, the solutions from the two subproblems are then merged as follows:
branch (D, d, [L,, In]) nondom (UreF merge (
T₁ (D 1, U [R. In] 1)), TF d UD HR. IR], d 1))))
(16)
Finding single best tree. It is also possible with this same DP formulation to search for single optimal and fair tree up to bias 8, as defined in Eq. 4 This can be achieved by pruning all (partial) solutions and retaining only those that are possibly fair. Then, in the root node of the search, the tree with minimum misclassification score is selected from the list of solutions. A solution is possibly fair if the lower bound the absolute imbalance value is less than equal 5. For this, introduce the function prune, which should filter a set of solutions S before it is passed to the nondom function.
prune(S, LR IR)) = (MM, 1x) (M,, In) E S, [(I,, LR IR)) S 86
(17)
This section gives the pseudocode for DPF. addition the description above, the pseudocode also considers upper and lower bounds and cache. Therefore, the function Zp receives the current best known upper bound ub on the misclassification score as an extra parameter.
Pseudocode.
The function prune must be redefined to take into account this upper bound on the misclassification score.
prune(S, ub, [In. Tn)) {(Ma, In) (Ma, Ix) E S, I(I,, [In, Tm)) 6, Mn ubb
(18)
For shorter notation, define:
filter(S, ub, [RR, IR)) = nondom (prune (S,ub, [RR, JR]) [RR, JR])
(19)
Also we define the functions M to return the best misclassification score within set of solutions:
( = min {M (M, E S}
(20)
Furthermore, let LB return the best known lower bound on the misclassification score for subprob- lem, or zero if no such lower bound is known.
With these changes, see Algorithm T for the resulting pseudocode of DPF. In this algorithm S is the set of solutions, and 1b and ub are the lower and upper bounds, with subscripts I. and denoting left and right subtrees. For a full Pareto front, the algorithm must be called with fairness cut-off value of 8 1.
Other algorithmic improvements. There are a number of other improvements in DPF for reducing the runtime. reduce the runtime cost the merge function, before merging, the two sets of partial solutions are first pruned based on bounds on the misclassification score and discrimination score derived from the other set. Then the two sets are sorted by misclassification score to enable early termination of the merge if it can be proven that all consecutive combinations of partial solutions will

---

Algorithm 1: Tree search of depth d with fairness on dataset D for feature set F.
(2, d, ub, In. In])
if = then
S + (1D)).))) (iDgl, Nu. No.a
}}
Na
return fS ub, [ TR])
(S. lb, stat) <- cache (D. d, RR, IR]] 2 ub then return 0
stat = optimal then return filter(S, ub, [R,, IR)) S 0
for f E do
lbR
St TF L, IR))
lRR UD (R. IR], d- 1))
, = 0 then continue
lbg - LB(Dy,d-1 [R JR])
SR - (F(D,; d 1, ub - lb,, (D [R,, RR] d 1))
R = 0 then continue
- J prune (merge(Sz, SR, RR IR]), ub, RR Rl)
- nondom(()
if S then
cache[D, d, RR TR]]= t (0, ub, lower bound) return 0
cache|D, d, [R. JR]l (S, (S)) optimal)
return S
exceed the misclassification upper bound. In the root node of the search, the solutions are sorted on the imbalance value to enable faster elimination of non-fair solutions.
The runtime of the nondom function can be reduced by observing that partial solutions with a lower bound imbalance of 0 do need be compared with other solutions because they will always be nondominated. For the sake of brevity, all these have been left out of the method description. See our code repository for full implementation details
Similar to [14 [5] our method also uses a special depth-two solver to increase the runtime perfor- mance. Our source code contains the full details. Appendix (A] presents complexity analysis of DPF. Appendix B shows how our algorithm can easily be modified to also optimize tree sparsity.
Experimental Results
The following section analyzes the performance of DPF. We focus on the analysis of the runtime and scalability of DPF: 1) How does DPF compare to the state-of-the-a impact do our pruning method and merge improvements have on the runtime? 3) What is the runtime cost to find the full Pareto front? 4) What impact do parameters such as number of features, instances, etc. have on the runtime of DPF?
terms of runtime? 2) What
For an out-of-sample analysis, see Appendix D
Experiment setup. We evaluate DPF on all datasets mentioned the survey by Le Quy et al. 30 The data preprocessing and binarization is also done as described in that paper. Categorical variables are encoded through one-hot encoding, except for variables with twenty or more categories, which were removed (this applies the KDD census dataset). The binarized datasets are included in our code repository (if the license permits redistribution). The Diabetes and Law-school dataset are left of the evaluation because the best tree of depth three (almost) identical the trivial solution (assign the majority label to all instances). See Appendix C for more details.

---

The algorithm receives the whole dataset as input and is asked to find a tree with an unfairness limit of 5 1%. In later experiment, we also examine the impact this parameter on the runtime. The values shown are the average of five runs and a time limit of one hour is set for every run. All experiments are run on 2.6Ghz Intel i7 CPU with 8GB RAM using only one thread.
The FairOCT model To our knowledge, the only methods available for finding fair and optimal de- cision trees are MIP models 2 [2 40). Verwer and Zhang 440 limit their model solving problems with less than 1000 instances. In our initial comparison of 2 and 225 the latter outperformed the first by a large margin. Therefore, we compare our method with their FairOCT model. They model the decision tree as a flow graph where all instances must flow from the source (connected to the root node of the tree) to one of the sink nodes (one for each class), to which all nodes are connected. In experiments, the FairOCT model is solved with Gurobi 9.0 using the default parameters.
Runtime comparison. Table I shows runtime comparison between FairOCT and our method DPF. DPF can find optimal trees for d = 2 within one second for all datasets, about four to five orders of magnitude faster than FairOCT. FairOCT is able to find d = trees only for the smallest datasets within hour. It struggles with an increasing number of data instances because every data instance represented by binary variable. Also for d 3, DPF can find optimal trees within one second for several datasets and all problems problem becomes clearly visible. Datasets with both large number of features and instances are no longer solvable within one hour. However, DPF still succeeds in finding the best tree for number of datasets, among which Adult, with over 45000 instances.
solved within a minute. For d = 4, the exponential nature of the
The impact of our novel pruning method and the merge improvements Table 2 shows the runtime results when DPF is run 1) without our novel pruning method (not applying the prune and nondom methods of Eqs. and 2) without improvements the merge method; 3) without our improvement to the nondom method, and 4) to generate full Pareto front.
For several datasets, pruning method decreases the runtime by
more orders of magnitude.
This is specifically the case for depth four, where the subproblem dependency is more significant than for depth three. Our method can find optimal trees for depth four for eight out of twelve datasets within one hour, but without the pruning method, this is possible for only four datasets.
Our improvements to the merge function in some cases significantly reduce the runtime. This is specifically the case for datasets that have high initial bias (the bias of optimal tree fairness would not be considered): Adult, COMPAS recid. and Dutch census have an initial bias of 18%, 16%, and 14% respectively, and for these datasets the merge improvements reduce the runtime by an order of magnitude. The other data sets in Table result only a small reduction of the runtime. The improvements to the nondom function are also essential for the performance of our pruning mechanism.
Table[2have have an initial bias of 1 1-6% and the merge improvements
Table 1: Runtime comparison of DPF and FairOCT, Runtime is in seconds, FairOCT resulted in an of memory for KDD census income, runtime can be reported.
FairOCT
DPF
Dataset
[D]
[F]
2 d d=
d
==
d
= 3
d d= 4
Adult
Gender
45222
17
lh
<1
1012
Bank Marketing Communities & Crime
Married
45211
46
> lh
<1
2
> >1h
Race
1994
97
1h
<1
1261
COMPAS recid.
Race
6172
9
1h
<1
<1
9
COMPAS viol. recid.
Race
4020
1594
<1
<1
<1
Dutch census
Gender
60420
58
> 1h
<1
5
> 1h
German credit
Gender
1000
69
lh
<1
2
741
KDD census income
Race
284556
117
<1
32
> lh
OULAD
Gender
21562
45
lh
<1
3
> lh
Ricci
Race
118
4
<1
<1
<1
<1
Student-Maate Mathematics
Gender
395
55
284
<1
<1
24
Student-Portuguu
Gender
649
55
866
<1
<1
32

---

Table DPF runtimes without the pruning and dominance checks (-P), without the merge improve- ments (-M), without the nondom improvements (-D), for finding the full Pareto-from (Pr), and for comparison the default runtime (Df). Datasets for which DPF has default runtime below one second or over one hour, are left out.
d = 3
=
Dataset
-P
-M
-D
Pr
Df
Dataset
-P
-M
D
Pr
Df
Bank
5
3
319
4
2
Adult
> 1h
1h
1h
> 1h
1012
Com.&Cr.
13
5
19
7
4
Com
> 1h
1329
2473
1939
1261
Dutch
1h
101
1814
510
5
COMP.
> 1h
394
1658
1659
9
German
2
22
2
2
German
> 1h
770
1971
738
741
KDD
144
35
1254
50
32
Stud. Math
144
24
29
412
24
OULAD
4
1448
3
3
Stud. Port.
1834
32
38
259
32
Generating the full Pareto-front Because of the runtime improvements of DPF, it is also able to find a full, fair and optimal decision tree Pareto front. contrast, Valdivia al. 33 find partial and non-optimal Pareto front and the FairOCT model is used to find an optimal, but still partial, Pareto front. Table 2 shows the runtime performance of DPF when tasked to find the full Pareto front. In comparison to FairOCT, DPF is several orders of magnitude faster. For COMPAS recid., for example, DPF found the Pareto front for depth two consisting of 29 solutions in 0.12 + 0.04 seconds. The FairOCT method generates the partial Pareto front by repeatedly solving the problem with a different maximum bias, resulting in a runtime several times higher than the values reported in Table
See Figure $ for number of full Pareto fronts generated by DPF for depth 2-4. These plots confirm the trade-off between accuracy and fairness as reported previous works.
Method evaluation. To provide more insight into our method we evaluate the impact of the number of features, the number of dataset instances, the minimum leaf node size and the maximum allowed bias in the fairness constraint on the runtime of DPF for three datasets when searching for trees of depth three. Figure shows the results. of features is the most important factor, resulting in an exponential increase, which is in line with previous studies 15 3T. One might expect that the method would scale linearly with increasing dataset size, but the experiments show almost no increase in runtime after certain size. The reason for this is that the runtime of the method is mostly dependent on the number of unique partial solutions that need to be merged by Eq. 99] This number of unique solutions is strongly dependent on the number of features and is only weakly related the number of instances.
be observed from these experiments that the number
DPF can easily be changed to limit the minimum leaf node size, by returning an empty set in Eq. 15 when the number of instances does not exceed the required leaf node size. Increasing the minimum leaf node size decreases the amount of unique partial solutions, and consequently we see a significant decrease in the runtime when the minimum leaf node size increased. Adding such a minimum leaf node size often does not have a significant impact on the accuracy score.
Relaxing the faimesss constraint values larger than å 1% causes the runtime increase for the Dutch census dataset. This can be explained because a more relaxed constraint means a larger search space and less strong faimess bounds. However, when the constraint is even more relaxed, the problem
Adult
Communities & Crime
COMP P-rreidd
Student- Portuguese
20
Discrimination
Depth
10
0
75
95
96
55
60
85
90
Accuracy (%)
Accuracy (%)
Accuracy (%)
Accuracy (%)
Figure 1: The full Pareto front of training accuracy and discrimination for four datasets for trees of
depth 2, 3 and 4, generated by DPF.

---

Bank Marketing
Dutch census
OULAD
run time
0.1
20
40
60
25000
50000
500
1000
0.00
0.05
0.10
features
instances
min. leaf node size
max. bias (6)
Figure 2: The impact of the number of features, instances, minimum leaf node size and maximum allowed bias the fairness constraint, d, on the runtime of DPF with 3. The shaded area shows the values within standard deviation. Note the logarithmic scale of the y-axis.
is closer to normal optimal tree search, and the accuracy bounds become stronger, again resulting in shorter runtime. For the Bank marketing and OULAD datasets, the default discrimination when no fairness constraint is in place, is lower: 1.2% and 3.0%, versus Dutch census: 14.1%. This explains why these datasets show almost no difference in runtime when changing the value 5.
Conclusion
We show how dynamic programming be used find fair and optimal decision trees, when considering a global fairness constraint that introduces subproblem dependency. We solve the subproblem dependency by computing upper and lower bounds on the final fairness value and thus enable comparison of partial solutions. The results show that our method DPF can find fair optimal trees several orders of magnitude faster than the state-of-the-art. As result, DPF succeeds in finding fair and optimal decision trees even for large datasets that were previously beyond reach. Moreover, we present the first specialized algorithm for finding fair optimal decision trees that can also find the full Pareto front in terms of accuracy and fairness.
An extension of DPF would be to support other group-based notions of fairness, such equality of opportunity. To better deal with unbalanced datasets, another extension of the presented research would be replace the accuracy objective with objective that can cope better with unbalanced datasets, for example, with the biobjective method presented [4], or by using balanced accuracy. Future work could also investigate the possibility of combining top-down search with bottom-up search. Finally, based on the evaluation results, new heuristic methods could be investigated, for example, by considering not all possibly-fair partial solutions, but only representative subset.
References
Alckh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach. reductions approach to fair classification. In Proceedings of ICML-18, 2018.
[2] Sina Aghaei, Mohammad Javad Azizi, and Phebe Vayanos. Learning Optimal and Fair Decision Trees for Don--isrrimintivee Decision- Decision-Making. In Proceedings of AAAI-19, 2019.
[3] Sina Aghaei, Andrés Gómez, and Phebe Vayanos. Strong Optimal Classification Trees. arXiv preprint 1xXiv:2103.15663 2021.
[4] Gaäl Aglin, Siegfried Nijssen, and Pierre Schaus. Learning Optimal Decision Trees Using Caching Branch-and- -auunnddd--d-ddd---- Search. In Proceedings of AAA1-20, 2020.
[5] Gael Aglin, Siegfried Nijssen, and Pierre Schaus. PyDL8.5: Library for Learning Optimal Decision Trees. In Proceedings of IJCA1-20, 2020.
[6] Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirehner. Machine Bias, May 2016. URL https:// www www.propublica www.eoor//rrrtttteereeeee http://aacccce/accaaeeeeeeee bias risk assessments in- cr aarimiaall-a sentensettnnnnnnnn
[7] Mohammad Javad Azizi, Phebe Vayanos, Bryan Wilder, Eric Rice, and Milind Tambe. Designing Fair, Efficient, and Interpretable Policies for Prioritizing Homeless Youth for Housing Resources. In Proceedings of CPAIOR-JE 18, 2018
10

---

[8] Richard Berk, Hoda Heidari, Shahin Jabbari, Michael Kearns, and Aaron Roth. Fairness in criminal justice risk assessments: The state of the art. Sociological Methods & Research, 50(1):3 2021.
[9] Dimitris Bertsimas and Jack Dunn. Optimal classification trees. Machine Learning, 106(7):1039-1082 2017.
[10] Reuben Binns. On the apparent conflict between individual and group faimesss In Proceedings of FAT* 20, 2020.
[11] Leo Breiman, Jerome H. Friedman, Richard A. Olshen, and Charles J. Stone. Classification and Regression Trees. Wadsworth and Brooks, Monterey, CA, 1984.
[12] Emilio Carrizosa, Cristina Molero- Radero-Riio and Dolores Romero Morales. Mathematical optimization in classification and regression trees. TOP: An Official Journal of Spanish Society of Statistics and Operations Research, 29(1):5 33, 2021.
[13] Paulo Cortez and Alice Maria Gonçalves Silva. Using data mining to predict secondary school student performance. In A. Brito and J. Teixeira, editors, Proceedings of 5th FUture BUsinexs TEChnology Conference, 2008.
[14] Emir Demirović and Peter J. Stuckey, Optimal Decision Trees for Nonlinear Metrics, In Proceedings of AAAI-21, 2021.
[15] Emir Demirović, Anna Lukina, Emmanuel Hebrard, Jeffrey Chan, James Bailey, Christopher Leckie, Kotagiri Ramamohanarao, and Peter J. Stuckey. MurTree: Optimal Classification Trees via Dynamic Programming and Search. Journal of Machine Learning Research, 23(2)), 2022.
[16] Christophe Denis, Romuald Elie, Mohamed Hebiri, and François Hu. Faimess guarantee in multi-class classification. arXiv preprint arXiv:2109. 134442209.11342, 2021.
[17] Fabrizio Detassis, Michele Lombardi, and Michela Milano. Teaching the Old Dog New Tricks: Supervised Learning with Constraints. In Proceedings of AAAI-21, 2021.
[18] Dheeru Dua and Casey Graff. archive. uuw.u.i...uuuu...
UCI Machine Learning Repository, 2017.
URL http://
[19] Dutch Central Bureau for Statistics. Dutch Census 2001 public use files (anonymized 1% samples from the microdata files). DANS, 2001. URL /ttpsst/////aadddaaa knaw ml//a///aaaassts////eaass 2 32357
[20] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel, Fairness Through Awareness. In Proceedings of ICTS '22 2012.
[21] Vincent Grari, Boris Ruf, Sylvain Lamprier, and Marcin Detyniecki. Achieving fairness with decision trees: An adversarial approach. Data Science and Engineering, 5(2):99-110, 2020.
[22] Gurobi Optimization LLC. Gurobi Optimizer Reference Manual, 2022. URL
[23] Xiyang Hu, Cynthia Rudin, and Margo Seltzer. Optimal sparse decision trees. In Advances NeurlPS-19. 2019.
[24] Laurent Hyafil and Ronald Rivest, Constructing optimal binary decision trees NP-complete. Informa- tion processing letters, 5(1):15-17, 1976.
[25] Nathanael Jo, Sina Aghaei, Jack Benson, Andrés Gómez, and Phebe Vayanos. Learning Optimal Fair Classification Trees. arXiv preprini arXiv:2201.00 009932, 2022.
[26] Faisal Kamiran and Toon Calders. Classifying without discriminating. In 2nd International Conference on Computer, Control and Communication, 2009.
[27] Faisal Kamiran, Toon Calders, and Mykola Pechenizkiy. Discrimination Aware Decision Tree Learning. In Proceedings of ICDM-JO, 2010.
[28] Nikita Kozodoi, Johannes Jacob, and Stefan Lessmann. Fairness in credit scoring: Assessment, im- plementation and profit implications. European Journal of Operational Research, 193- 2022.
[29] Jakub Kuzilek, Martin Hlosta, and Zdenek Zdrahal, Open university learning analyties dataset. Scientific data, 4(1), 2017.

---

[30] Tai Le Quy. Arjun Roy, Vasileios Iosifidis, Wenbin Zhang, and Eirini Ntoutsi. A survey datasets for fairness-aware machine learning. Wiley Intendisciplinary Reviews: Data Mining and Knowledge Discovery, page e1452, 2022.
[31] Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, and Margo Seltzer. Generalized and scalable optimal sparse decision trees. In Proceedings of ICMI.-20, 2020.
[32] Sérgio Moro, Paulo Cortez, and Paulo Rita. A data-driven approach to predict the success of bank telemarketing. Decision Support Systems, 62:22-31, 2014.
[33] Dino Pedreschi, Salvatore Ruggieri, and Franco Turini. Discrimination-aware Data Mining, Proceedings of SIGKDD-08. 000 2008.
[34] Rok Piltaver, Mitja Luštrek, Matjaž Gams, and Sandra Martinčić-Ipšíć. What makes classification trees comprehensible? Expert Systems with Applications, 62:333-346, 2016.
[35] Francesco Ranzato, Caterina Urban, and Marco Zanella. Fair Training of Decision Tree Classifiers. arXiv preprint arXiv:2101.00909 2021.
[36] Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and usc interpretable models instead. Nature Machine Intelligence, 1(5):206-22) 215, 2019.
[37] Beata Strack, Jonathan DeShazo, Chris Gennings, Juan I. Olmo, Schastian Ventura, Krzysztof Cios, and John N Clore. Impact of HbAlc measurement on hospital readmission rates: analysis of 70,000 climical database patient records. BioMeed research international, 2014.
[38] Ana Valdivia, Javier Sánchez- Monedero, and Jorge Casillas. How fair can we go in machine learning? Assessing the boundaries of accuracy and fairness. International Journal of Intelligent Systems, 36(4): 1619-16433 2021.
[39] Kush R Varshney and Homa Alemzadeh. On the safety of machine learning: Cyber-physical systems, decision sciences, and data products. Big data, 5(3):246-255, 2017.
[40] Sicco Verwer and Yingqian Zhang, Learning decision trees with flexible constraints and objectives using integer optimization. In Proceedings of CPAIOR-17, 2017.
[41] Sicco Verwer and Yingqian Zhang. Learning optimal classification trees using a binary linear program formulation. In Proceedings of AAAI-19, 19,1-19,20 2019.
[42] Haoran Zhu, Pavankumar Murali, Dzung T. Phan, Lam M. Nguyen, and Jayant R. Kalagnanam. A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees. In Advances in NeurlPS-20, 2020.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] The limitations of the work are as follows: 1) the algorithm only works for binary classification with only binary features; 2) the algorithm can only generate small decision trees; 3) the algorithm's 's runtime performance scales exponentially with increasing number of features. All of these are mentioned in the text.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] This paper uses demographic parity as a fairness metric. Readers are informed that this is just one of the metrics commonly used to determine what is fair. Other papers that further discuss these issues are referenced.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [es]] 1) Datasets are referenced and licenses are included in the repository. 2) This paper focuses on demographic parity as a faimess metric. Relevant papers that discuss the value and limitations this faimness metric are referenced.
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
12

---

3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as a URL)? [Yes] The link the
source code will be made publicly available upon acceptance
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] In the code repository.
(c) Did you include any new assets either in the suppiemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "mnCW8j86YEl", "reviewer": "Reviewer_5CeZ", "summary": "The authors designed a specialized algorithm, DPF(Dynamic Programming Fair?) that can find fair optimal decision trees, i.e., the decision trees with the best performance metrics under a given fairness gap constraint. The algorithm can also return a Pareto front of performance and fairness and use the front to filter out dominated splits at each level. Dynamic programming is used in DPF to find possible splits. The authors show numerical results that DPF is much more efficient to train compared to related works like FairOCT. ", "questions": "1. In some of the other decision tree models, putting samples into different bins help significantly with the split finding and training speed. In this work, when keeping all the non-dominated submodels, is it possible to use this technique? \n2. If the technique in question 1 is possible, what are some of the conditions that guarantee when splitting at the bin boundaries results in two non-dominated submodels, all other splits within this bin are also non-dominated? Is this somehow related to the monotonic condition? \n3. Is it possible to come up with theoretical reasonanings on the efficiency of DPF? Can you specify when, or on what type of dataset DPF can perform much better than the related works and when not?\n4. DPF is compared to other in-process fairness oriented algorithms in the article, so a natural question to ask is can DPF be compared to or combined with pre-process fairness oriented methods or post-process fairness oriented methods?", "limitations": "As discussed in the weaknesses already.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Strong numerical results showing that DPF is much more efficient to train compared to related works like FairOCT\n2. Clear Problem statement\n\nWeaknesses:\n1. No theorem or propositions to show the advantage of DPF theoretically\n2. Pseudo code would be nice to have in the main article than in the appendix to help the readers understand the algorithm", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "d47B1ZlR4Vx", "reviewer": "Reviewer_Vs5A", "summary": "The paper address the problem of finding fair and accurate decision trees. Using demographic parity as the fairness definition, they try to minimize misclassification while at the same time satisfying a fairness constraint. The problem is hence formulated as a multiobjective problem in which both misclassification error and group imbalance are minimized. Having defined a dominating solution as one which is similar or better in both objectives, they search for Pareto fronts of nondominated solutions.\n\nPrevious work have proposed dynamic programming approaches for biobjective optimization in decision trees, and finding the Pareto front  of nondominated solutions in the case where the objectives are additive and monotonic. Since the imbalance part of their objective is not monotonic (contains absolute value), the dynamic programming approach cannot be directly used. As a result, the authors propose a way to calculate the upper and lower bound of the imbalance value, and later on, redefine the dominance relation based on these values. They then propose a dp approach that finds the Pareto frontiers and improve the time complexity of the search by pruning the search space based on the upper and lower bound values of the imbalance.", "questions": "I would like to thank the authors for taking the time to write the paper in a well-organized way. It was my pleasure to review the paper. I have a few questions from the authors: \n\n- How good are the set of Pareto frontiers? Can it be that a solution that is not dominated by any other solution is not really a good one? Assume the accuracy is very high but it is at the cost of very low fairness (in the tuple (M,I), M is very high and I is very low. Then it could happen that no other solution can dominate this one because no solution can beat M, but the solution is very imbalanced. \n\n- In equation 11 and 12, is it not the case that the lower bound is always equal to the lowerbound of the rest + I_n and the upper bound is equal to the upperbound of the rest + I_n? I do not understand why you wrote it with min/max?\n\n- it is not very easy to understand equations 14-17. What is the function U exactly? How exactly does the merge function work? if it works the same as defined in Eq.9, then how is it using the upper/lower bound information? If it is not using that information, why is it input to the function?\n", "limitations": "they have provided the run time of their approach so it gets clear that it gets higher as the dataset or the number of features grows. Maybe they could also talk about space complexity and how much storage they used to store the intermediate solutions, since they use a dp approach. They could also show the performance considering more fairness criteria rather than just demographic parity. Their approach is applicable to binary classification with binary features. It would be nice to mention what happens if the features are not binary and whether the algorithm could scale.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- very well written except for some typos mentioned below\n- they consider a well-motivated problem\n\nWeaknesses\n\n- From section 4 on, the paper does not flow very well. In the end of section 3, it gets clear that due to non-monotonicity of the imbalance function, the dp approach cannot be directly used and the reader is waiting for that problem to be addresses. In the beginning of section 4 you directly mention that you present DPF, without saying what it stands for, and without saying how it tries to overcome the monotonicity problem. Section 4 is hard to follow. Not everything is clearly defined such as the meaning of (R), being the rest of the tree, and how exactly you calculate the upper/lower bounds. I believe the quality of the upper/lower bounds directly affect the quality of the solutions found so I do not find the sentence \"These bounds can be trivial, ...\" in line 202 really convincing. \n\nThere are further presentation issues mentioned below:\n- punctuations before/after equations are completely missing\n- typo in the first line of Eq.8\n- Eq 8 needs some explanation. You copy it from another paper without introducing what it is searching for. For example, it is not clear what (|D|,0) is showing. I had to refer to the cited papers to understand but I think it is better if the paper is self-contained and the reader does not need to search for the meaning of notation elsewhere.\n- lines 176-178 are not well written\n- line 191, \"is\" is missing\n- you never mention what is \"DPF\". You use the abbreviation from the first occurrence.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Rpqwfz76Hs", "reviewer": "Reviewer_NysV", "summary": "The authors studied the optimal and fair decision trees. They proposed a dynamic programming method considering the fairness constraint. Due to the global fairness constraint, the decision tree is not separable. Using upper and lower bounds on the fairness values, the authors decrease the search space and improve the solution time. ", "questions": "Is there a theoretical guarantee that obtaining the \"global\" optimal solution to the posed problem would lead to higher accuracy and/or fairness for the out-of-sample instances?\n\nWhat is the impact of highly imbalanced datasets on the performance of the proposed algorithm?\n\nThe authors have reported only the runtimes for DPF and FairOCT. How about the accuracies and fairness scores? In case of multiple optimal solutions, one would think that the out-of-sample performances may differ. Do these methods obtain exactly same solutions? \n\nHow do the computation times of the proposed method compare against the method of Kamiran? Are the results for Kamiran in Table 3 obtained after tuning the hyperparameters of the method?\n\nThe following recent paper discusses fairness in optimal trees by formulating MIP. Their results seem promising. It would be great if the authors also review this paper and highlight their differences:\n\nJo, N., Aghaei, S., Benson, J., Gómez, A., & Vayanos, P. (2022). Learning Optimal Fair Classification Trees. arXiv preprint arXiv:2201.09932.\n\n", "limitations": "Limitations are discussed in the conclusion section.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "With the use of upper and lower bounds on fairness, the authors set forth a new dominance relation. The same bounds also lead to a new pruning mechanism. Consequently, the authors obtain a method that finds the Pareto front, and it is faster than the other methods proposed in the literature.\n\nThe paper is mainly based on two papers [14, 15] that authors have also cited. Adding only group fairness constraint and pruning the trees through trivial bounds are straightforward extensions. In its current form, the work does not introduce enough novelty to the literature.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MGhYree5Sn0", "reviewer": "Reviewer_Bp3p", "summary": "This paper proposes a dynamic programming (DP) model to construct optimal decision trees subject to fairness constraints, i.e., where the positive classification observes demographic parity. The methodology extends an existing bi-objective recursive reformulation for decision trees and returns the full Pareto frontier in terms of the optimal and fairness criteria. In particular, the authors develop upper and lower bounds on the fairness constraint to ensure all generated solutions are feasible, in addition to pruning techniques to speed up the frontier enumeration. The numerical study evaluates the approach against current (mostly MIP-based) state-of-the-art methods.", "questions": "1. Given the nice performance, is it possible to extend the approach to non-binary trees? It would not be surprising to find cases where the DP would perform well (if the state space is still relatively \"compact\").\n\n2. Could authors discuss the scalability of the approach for datasets beyond the ones presented?\n\n3. Labelling approaches in multiobjective DP optimization can be significantly improved when using bidirectional search, such as the one presented in [1]. That is, the state-space graph of the DP is constructed from top-down and bottom-up separately, and the Pareto frontier is \"merged\" when the two layers meet. This is the key performance in state-of-the-art multiobjective models, such as the ones appearing in shortest-path subproblems for vehicle routing. I wonder how this relates to Algorithm 1, or whether that could help improve the methodology?\n\n[1] Galand L, Ismaili A, Perny P, Spanjaard O (2013) Bidirectional preference-based search for state space graph problems. Proceedings of the Sixth International Symposium on Combinatorial Search", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- Very strong numerical results, significantly outperforming the state of the art\n- Idea is intuitive and easy to implement\n- Paper very well written\n\nWeaknesses\n- I have concerns about the contribution; except for the lower or upper bounds, the methodology itself seems to be derived in a somewhat straightforward way from existing works\n- Scalability and usage could be detailed more thoroughly\n\nMajor comments\n\nOverall, I greatly enjoyed reading the work because the methodology is intuitive, involves interesting bounding procedures associated with the structure of the fairness constraint, and the numerical results are quite strong, outperforming MIP-based models very prominently. However, I have two major concerns after reading the work.\n\n(i) [Novelty.] My (possibly wrong) impression is that the authors essentially implemented the ideas from two existing works (references [14] and [15] of the paper) for this paper. More precisely, they specialized the bi-objective approach to accommodate fairness constraints by considering interval-based labelling to ensure the full Pareto frontier was enumerated correctly. While the effectiveness is apparent and there is some novelty in the upper/lower bounds, this brought me some concerns about whether the results are somewhat incremental to existing literature. I believe this could be addressed in multiple ways. For instance, authors could expand on other constraint classes that could leverage the methodology, or whether there are other fairness definitions that could also be accommodated by the technique.\n\n(ii) [Scalability and Usage.] It is impressive that the authors are enumerating the full Pareto frontier. This shines light into two usual questions that also follow any type of multiobjective work. First, it is unclear how scalable that is; while it worked well for the datasets in the numerical experiments, how large are the problems that actually can be solved by DP in this context? Second, even if the Pareto frontier can be fully enumerated, what would be the guidelines/insights to pick the appropriate tree among such a possibly large set? It would be great if authors could expand further on those concepts.\n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept