Nawal Benabbou
email: benabbou@comp.nus.edu.sg

Mithun Chakraborty

Xuan-Vinh Ho

Jakub Sliwinski
email: jsliwinski@ethz.ch

Yair Zick

Diversity Constraints in Public Housing Allocation

Keywords: Optimal Assignment, Type Constraints, Diversity

The state of Singapore operates a national public housing program, accounting for over 70% of its residential real estate. Singapore uses its housing allocation program to promote ethnic diversity in its neighborhoods; it does so by imposing ethnic quotas: every ethnic group must not own more than a certain percentage in a housing project, thus ensuring that every neighborhood contains members from each ethnic group. However, imposing diversity constraints naturally results in some welfare loss. Our work studies the tradeoff between diversity and (utilitarian) social welfare from the perspective of computational economics. We model the problem as an extension of the classic assignment problem, with additional diversity constraints. While the classic assignment program is polytime computable, we show that adding diversity constraints makes the problem computationally intractable; however, we identify a 1 2approximation algorithm, as well as reasonable agent utility models which admit poly-time algorithms. In addition, we study the price of diversity: this is the loss in welfare incurred by imposing diversity constraints; we provide upper bounds on the price of diversity as functions of natural problem parameters. Finally, we use recent, public demographic and real-estate data from Singapore to create a simulated framework testing the welfare loss due to diversity constraints in realistic large-scale scenarios.

INTRODUCTION

More than 80% of Singapore citizens and permanent residents live in public housing projects [26]; these apartments are sold in a largescale public market centrally managed by a government body called the Housing and Development Board (HDB). In addition to providing a public good -affordable apartments in a small country with little real estate -HDB estates serve a role in the social integration of Singapore's diverse ethnic groups (Chinese, Malay and Indian/Others). As per the Ethnic Integration Policy introduced in 1989 [START_REF]Better racial mix in HDB housing estates[END_REF], every public housing development must hold a certain percentage of every major ethnic group, which is somewhat proportional to the true percentages of these groups in the general Singaporean population; for example, since 5 March 2010, every HDB housing block is required to hold no more than 87% Chinese, 25% Malay, and 15% Indian/Others [START_REF] Deng | The story of Singapore's public housing: From a nation of home-seekers to a nation of homeowners[END_REF][START_REF]Policy changes to support an inclusive and cohesive home[END_REF]. Ethnic quotas ensure a diverse population composition at the block-level, preventing the de-facto formation of segregated ethnic communities in public housing estates. HDB uses a lottery mechanism to allocate new developments: all applicants who apply for a particular development pick their flats in a random order; however, these ethnicity constraints introduce some peculiarities. For example, consider an applicant i of Chinese ethnicity applying for an apartment block with 100 flats, up to 87 of which may be assigned to ethnically Chinese applicants, and at most 25 of which can be assigned to ethnically Malay applicants. Assume that i is 90th in line to select an apartment. If at least 87 Chinese applicants were allowed to choose a flat before i, the Chinese ethnic quota for the block will have been filled and applicant i will no longer be eligible for the block. On the other hand, suppose that i is 105th in line to select an apartment; if 40 Malay applicants end up before i in the lottery, then 15 of them will be rejected, and i will have a spot 1 .

As the example above shows, ethnic quotas add another layer of complexity to what is, at its foundation, a straightforward allocation problem. Indeed, the allocation of public housing is an economic problem similar to the classic assignment problem: a central planner (HDB) wishes to allocate goods (apartments) to agents (residents) in a manner satisfying certain economic criteria. Diversity, on the other hand, is a social goal external to the underlying economic domain; imposing it may result in reduced social welfare.

Our Contributions

We study the interplay between diversity and social welfare in the public housing market; we model this as an assignment problem with additional type-block constraints: agents are of multiple types and goods are divided into blocks. A limited number of goods in each block can be allocated to agents of each type; we call these upper bounds type-block capacities. These restrictions result in several interesting outcomes. While the optimal assignment problem is well-known to be poly-time solvable [START_REF] Kuhn | The Hungarian method for the assignment problem[END_REF], we show that imposing type-block constraints makes it computationally intractable (Section 3). However, we identify a 1 2 -approximation algorithm (Section 3.1), as well as some agent utility models for which one can find optimal assignments with type-block constraints in polynomial time (Section 3.2). Next, we show that the potential utility loss from imposing type-block constraints -which we term the price of diversity as in [START_REF] Ahmed | Diverse Weighted Bipartite b-Matching[END_REF]-can be bounded by natural problem parameters (Section 4). Finally, we analyze the empirical price of diversity on simulated instances generated from real HDB data (Section 5).

Related work

One can think of public housing allocation as a bipartite matching problem [START_REF] Lovász | Matching theory[END_REF] where an edge from an agent i to an apartment j is weighted with the utility the agent will receive if she is allocated the apartment. There is a rich literature on weighted bipartite matching problems (also known as assignment problems [START_REF] Munkres | Algorithms for the assignment and transportation problems[END_REF]), and polynomial-time algorithms for the unconstrained version have long been known (e.g. [START_REF] Kuhn | The Hungarian method for the assignment problem[END_REF]). Several generalizations and/or constrained versions have been studied, e.g. recent work by Lian et al.

[2018] who allow each agent (resp. item) to be matched to multiple items (resp. agents) but within upper and lower capacities. The assignment problem with subset constraints studied by [START_REF] Bauer | Assignment Problem with Constraints[END_REF] can be thought of as a special case of our problem, with a single block or a single type. If all agents of each type have identical utilities for all apartments in each block, and each type-block capacity is smaller than both the corresponding type and block sizes, then our problem reduces to a special case of the polynomial-time solvable capacitated b-matching on a bipartite graph [START_REF] Kook | Near linear time schemes for uncapacitated and capacitated b-matching problems in nonbipartite graphs[END_REF].

Singapore's public housing is our primary motivating domain but type-block constraints can naturally arise in many other settings [START_REF] Hylland | The efficient allocation of individuals to positions[END_REF][START_REF] Zhou | On a conjecture by Gale about one-sided matching problems[END_REF]. For example, consider the course allocation problem analyzed by [START_REF] Budish | The multi-unit assignment problem: Theory and evidence from course allocation at Harvard[END_REF]; one might require that each course has students from different departments and impose maximal quotas to ensure this. In public school allocation [START_REF] Abdulkadiroğlu | Strategyproofness versus efficiency in matching with indifferences: Redesigning the NYC high school match[END_REF][START_REF] Abdulkadiroğlu | School choice: A mechanism design approach[END_REF][START_REF] Parag | School admissions reform in Chicago and England: Comparing mechanisms by their vulnerability to manipulation[END_REF], one might require that certain schools admit students from diverse neighborhoods to prevent de-facto segregation. Other examples include matching medical interns or residents to hospitals [START_REF] Roth | The evolution of the labor market for medical interns and residents: a case study in game theory[END_REF], allocating subsidized on-campus housing to students [START_REF] Abdulkadiroğlu | Random serial dictatorship and the core from random endowments in house allocation problems[END_REF], appointing teachers at public schools in different regions as done by some nonprofit organizations [START_REF] Featherstone | Rank efficiency: Investigating a widespread ordinal welfare criterion[END_REF], or assigning first year business school students to overseas programs [START_REF] Featherstone | Rank efficiency: Investigating a widespread ordinal welfare criterion[END_REF]. This line of work mainly explores the interaction between individual selfish-rational behavior and allocative efficiency (e.g. Pareto-optimality) of matching mechanisms, under either ordinal preferences or cardinal utilities, one-sided or two-sided (see, e.g. [START_REF] Anshelevich | Anarchy, Stability, and Utopia: Creating Better Matchings[END_REF][START_REF] Bade | Random serial dictatorship: the one and only[END_REF][START_REF] Bhalgat | Social welfare in one-sided matching markets without money[END_REF][START_REF] Bogomolnaia | A new solution to the random assignment problem[END_REF] and references therein); we, on the other hand, focus on the impact of type-block constraints on welfare loss, when agents' utilities are known to a central planner.

A relevant body of work is that on the fair allocation of indivisible goods (see, e.g., [START_REF] Barman | Finding Fair and Efficient Allocations[END_REF][START_REF] Barman | Approximation Algorithms for Maximin Fair Division[END_REF][START_REF] Caragiannis | The unreasonable fairness of maximum Nash welfare[END_REF][START_REF] Kurokawa | When can the maximin share guarantee be guaranteed?[END_REF][START_REF] Procaccia | Fair enough: Guaranteeing approximate maximin shares[END_REF]): here, fairness is quantified in terms of agents' realized utilities or preferences whereas we deal with the proportionate representation of groups in the allocation with respect to an attribute different from utility. Some recent literature [START_REF] Bredereck | Multiwinner Elections with Diversity Constraints[END_REF][START_REF] Lang | Multi-Attribute Proportional Representation[END_REF] addresses diversity in a subset selection setting; [START_REF] Ahmed | Diverse Weighted Bipartite b-Matching[END_REF] "treat[] diversity as an objective, not a constraint" in a b-matching context and use a 'soft' approach towards encouraging diversity, whereas we enforce diversity through hard constraints. Immorlica et al. [2017] study the efficiency of lottery mechanisms such as the ones used by HDB to allocate apartments; however, their work does not account for ethnicity-block constraints which, as we show here, have a significant effect on allocative efficiency.

The Singapore Public Housing Allocation System

The Singapore public housing system, managed by the ). Estates take between 3 to 5 years to complete, during which HDB publicly advertises calls to ballot for an apartment in the new estate. A household (say, a newly married couple looking for a new house) usually ballots for a few estates (balloting is cheap: only S$10 per application [START_REF]Costs and Fees[END_REF]). HDB allocates apartments using a lottery: all applicants to a certain estate choose their flat in some random order; they are only allowed to select an apartment in a block such that their ethnic quota is not reached. There are a few complications here: first-time applicants and low-income families usually receive priority numbers in the lottery scheme; moreover, the same estate may have several balloting rounds in order to ensure that all apartments are allocated by the time of completion. However, the focus of this work is on the welfare effects of using ethnic quotas rather than the specific intricacies of the HDB lottery mechanism. We must mention here the existing literature on the documentation of Singapore's residential desegregation policies [START_REF] Chua | Race relations and public housing policy in Singapore[END_REF][START_REF] Deng | The story of Singapore's public housing: From a nation of home-seekers to a nation of homeowners[END_REF][START_REF] Sock | Singapore's Housing Policies: 1960-2013[END_REF] and the empirical evaluation of their impact on various socioeconomic factors [START_REF] Loo | Public housing and ethnic integration in Singapore[END_REF][START_REF] Wong | Estimating the distortionary effects of ethnic quotas in Singapore using housing transactions[END_REF]; to the best of our knowledge, ours is the first formal approach towards this problem.

PRELIMINARIES

We first describe a formal model for the housing allocation problem with ethnicity quotas. Throughout the paper, given s ∈ N, we let [s] denote the set {1, 2, . . . , s}.

Definition 2.1 (AssignTC). An instance of the Assignment with Type Constraints (AssignTC) problem is given by: (i) a set N of n agents partitioned into k types N 1 , . . . , N k , (ii) a set M of m items/goods partitioned into l blocks M 1 , . . . , M l , (iii) a utility u(i, j) ∈ R + for each agent i ∈ N and each item j ∈ M, (iv) a capacity λ pq ∈ N for all (p, q) ∈ [k]×[l], indicating the upper bound on the number of agents of type N p allowed in M q .

We assume here that the inequality λ pq ≤ |M q | holds for all typeblock pairs (p, q) ∈ [k] × [l] without loss of generality since it is not possible to assign more than |M q | agents of type N p to items in block M q , by definition. In the Singapore public allocation problem, tenant households are the agents and apartments are the items; types correspond to ethnic groups (Chinese, Malay, Indian/Others) and blocks to actual apartment blocks in a sales launch. In general, such partitions could be based on any criterion such as gender, profession, geographical location, or suchlike. For our theoretical analysis, we consider the idealized scenario where we have a central planner who has access to the utilities of each agent for all items, and determines an assignment that maximizes social welfare under type-block constraints.

An assignment of items to agents can be represented by a (0, 1)matrix X = (x i j ) n×m where x i j = 1 if and only if item j is assigned to agent i; a feasible solution is an assignment in which each item is allocated to at most one agent, and each agent receives at most one item, respecting the type-block capacities defined in (iv). We define the objective value as the utilitarian social welfare (or total utility), i.e. the sum of the utilities of all agents in an assignment u(X ) i ∈N j ∈M x i j u(i, j). Clearly, this optimization problem can be formulated as the following integer linear program:

max i ∈N j ∈M x i j u(i, j) (1) s.t.
i ∈N p j ∈M q

x i j ≤ λ pq ∀p ∈ [k], ∀q ∈ [l] (2)
j ∈M

x i j ≤ 1 ∀i ∈ N (3)
i ∈N

x i j ≤ 1 ∀j ∈ M (4)
x i j ∈ {0, 1} ∀i ∈ N , ∀j ∈ M (5)
where constraints [START_REF] Abdulkadiroğlu | School choice: A mechanism design approach[END_REF][START_REF] Ahmed | Diverse Weighted Bipartite b-Matching[END_REF][START_REF] Kook | Near linear time schemes for uncapacitated and capacitated b-matching problems in nonbipartite graphs[END_REF] jointly ensure that X is a matching of items to agents, and inequalities (2) embody our type-block constraints.

Finally, an instance of the decision version of AssignTC consists of ingredients (i) to (iv) in Definition 2.1, as well as a positive value U : it is a 'yes'-instance iff there exists a feasible assignment, satisfying constraints (2-5), whose objective value is at least U .

THE COMPLEXITY OF THE ASSIGNMENT PROBLEM WITH TYPE CONSTRAINTS

Our first main result is that the decision problem we introduce in Section 2 is NP-complete. We prove this by describing a polynomialtime reduction from the NP-complete Bounded Color Matching problem [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF], defined as follows:

Definition 3.1 (BCMatching). An instance of the Bounded Color Matching (BCMatching) problem is given by (i) a bipartite graph G = (A ∪ B, E), where the set of edges E is partitioned into r subsets E 1 , . . . , E r representing r different edge colors, (ii) a capacity w t ∈ N for each color t ∈ [r ], (iii) a profit π e ∈ Q + for each edge e ∈ E, and (iv) a positive integer P. It is a 'yes'-instance iff there exists a matching (i.e. a collection of pairwise non-adjacent edges) E ′ ⊆ E such that the sum of the profits of all edges in the matching is at least P, and there are at most w t edges of color t in the matching, i.e. e ∈E ′ π e ≥ P and

|E ′ ∩ E t | ≤ w t for all t ∈ [r ]. Theorem 3.2. The AssignTC problem is NP-complete.
Proof. That the problem is in NP is immediate: given an assignment, one can verify in poly-time that it satisfies the problem constraints and compute the social welfare. Given an instance ⟨G; ì w; ì π ; P⟩ of BCMatching, we construct an instance of the As-signTC problem as follows (see Example 3.3 for an illustration).

Each edge e ∈ E is an agent, whose type is its color. Items in our construction are partitioned into two blocks: M

u(e, j) =          π e if j = j b , Φ if j = j s a for some s ∈ [deg(a) -1], 0 otherwise.
Here, Φ is an arbitrarily large constant, e.g., Φ = 1 + e ∈E π e . Finally, let U = P + Φ(|E| -|A|). We begin by showing that if the BCMatching instance is a 'yes' instance, then so is our constructed AssignTC instance. Let E ′ ⊆ E be a matching whose value is at least P; let us construct an assignment of items to agents via E ′ as follows. Observe some node a . We now show that it is a valid assignment satisfying the type-block constraints.

∈ A; if (a, b) ∈ E ′ then
First, by construction, every agent (a, b) is assigned at most one item. Moreover, since E ′ is a matching, every item j b ∈ M 1 is assigned to at most one agent of the form (a, b); hence, every item in M 2 is assigned to at most one agent by construction.

Let E ′ p = E p ∩ E ′ be the edges of color p in E ′ . Since matching E ′ satisfies the capacity constraints of the BCMatching instance, we have |E ′ p | ≤ w p for all p ∈ [k]; in particular, the number of items in M 1 assigned to agents of type p is no more than w p = λ p1 . Thus, the type-block constraints for M 1 are satisfied. Moreover, the type-block constraints for M 2 are trivially satisfied. Hence our constructed assignment is valid and satisfies the type-block constraints.

Finally, we want to show that the social welfare exceeds U , the prescribed bound. Let us fix a node a ∈ A. By our construction, if the edge e = (a, b) is in the matching E ′ , then agent e is assigned the item j b for a utility of π e . Thus the total utility of agents in E ′ equals e ∈E ′ π e , which is at least P by choice of E ′ . In addition, for every a ∈ A, there are exactly deg(a) -1 agents assigned to items in M 2 for a total utility of Φ(deg(a) -1). Summing over all a ∈ A, we have that the total utility derived by agents in

E \ E ′ is a ∈A Φ(deg(a) -1) = Φ a ∈A deg(a) - a ∈A 1 = Φ(|E| -|A|).
Putting it all together, we conclude that the total utility obtained by our assignment is at least

P + Φ(|E| -|A|) = U .
Next, we assume that our constructed AssignTC instance is a 'yes' instance, and show that the original BCMatching instance must also be a 'yes' instance. Let X be a constrained assignment whose social welfare is at least U = P + Φ(|E| -|A|). Let E ′ be the set of edges correponding to agents (a, b) assigned to items in M 1 ; we show that E ′ is a valid matching whose value is at least P.

First, for any b ∈ B, X must assign the item j b to at most one agent e ∈ E ′ . Next, since Φ is greater than the total utility obtainable from assigning all items in M 1 , it must be the case that X assigns all items j 1 a , . . . , j

deg(a)-1 a
to deg(a) -1 agents of the form (a, b), with b ∈ B, for every node a ∈ A; thus, there can be one edge in E ′ that is incident on a for every a ∈ A. Next, since X satisfies the type-block constraints, we know that for every p ∈ [k], there are at most λ p1 = w p agents from E p that are assigned items in M 1 ; thus, E ′ satisfies the capacity constraints. Finally, the utility extracted from the agents assigned to items in M 2 is exactly Φ(|E| -|A|); the total utility of the matching X is at least U = P + Φ(|E| -|A|), thus E ′ has a total profit of at least P in the BCMatching instance.

Example 3.3. In Figure 1, the graph

G = (A ∪ B, E 1 ∪ E 2 ), with A = {a 1 , a 2 }, B = {b 1 , b 2 , b 3 }, E 1 = {(a 1 , b 1 ), (a 2 , b 2 )} and E 2 = {(a 1 , b 2 ), (a 2 , b 1 ), (a 2 , b 3 )},
is an instance of the BCMatching problem; edge labels are profits. The associated instance of the As-signTC problem is defined by

N = N 1 ∪ N 2 and M = M 1 ∪ M 2 , where N 1 = {(a 1 , b 1 ), (a 2 , b 2 )}, N 2 = {(a 1 , b 2 ), (a 2 , b 1 ), (a 2 , b 3 )}, M 1 = {j b 1 , j b 2 , j b 3 } and M 2 = {j 1 a 1 , j 1 a 2 , j 2 a 2 }
; the utility of an agent for an item is equal to 0 if there is no edge between them, to Φ if the edge is dashed, and to the edge label otherwise.

a 1 a 2 b 1 b 2 b 3 2 6 3 1 4 j b 1 j b 2 j b 3 (a 1 , b 1 ) (a 1 , b 2 ) (a 2 , b 1 ) (a 2 , b 2 ) (a 2 , b 3 ) j 1 a 1 j 1 a 2 j 2 a 2 2 3 6 1 4
Figure 1: A reduction from BCMatching to AssignTC.

A Polynomial-Time Constant Factor Approximation Algorithm

Having established that the AssignTC problem is computationally intractable in general, we next present an efficient constantfactor approximation algorithm: we construct an approximationpreserving reduction [START_REF] Orponen | On approximation preserving reductions: Complete problems and robust measures[END_REF] -in fact, an S-reduction [START_REF] Crescenzi | A short guide to approximation preserving reductions[END_REF] -from this problem to the BCMatching problem (Definition 3.1), for which a polynomial-time approximation algorithm is known.

Theorem 3.4. There exists a poly-time 1 2 -approximation algorithm for the AssignTC problem.

Proof. Given an instance of the AssignTC problem, we define a complete bipartite graph whose nodes correspond to the sets of agents N and items M, and give the edge joining agent-node i to item-node j a profit equal to the utility u(i, j) for all i ∈ N , j ∈ M. We also give all edges joining agents of one type to items in one block the same color, so that there are kl colors indexed lexicographically by pairs (p, q) ∈ [k]×[l]; let the capacity for color (p, q) be λ pq . This produces, in O(mn) time, an instance of BCMatching; the size of this instance is obviously polynomial in that of the original, and, by construction, there is a one-to-one correspondence between the sets of feasible solutions of the original and reduced instances with each corresponding pair having the same objective value (sum of edgeprofits/utilities), so that the optimal values of the instances are also equal. We can now apply the polynomial-time 1 2 -approximation algorithm introduced by [START_REF] Stamoulis | Approximation algorithms for bounded color matchings via convex decompositions[END_REF] for BCMatching on general weighted graphs. Theorem 3.4 offers a 1 2 -approximation to the AssignTC problem; whether a better poly-time approximation algorithm exists is left for future work.

Uniformity Breeds Simplicity:

Polynomial-Time Special Cases

Our results thus far make no assumptions on agent utilities; as we now show, the AssignTC problem admits a poly-time algorithm under some assumptions on the utility model.

Definition 3.5 (Type-uniformity and Block-uniformity).

A utility model u is called type-uniform if all agents of the same type have the same utility for an item, i.e. for all p ∈ [k] and for all j ∈ M, there exists U p j ∈ R + such that u(i, j) = U p j for all i ∈ N p . A utility model u is called block-uniform if all items in the same block offer the same utility to an agent; that is, for all q ∈ [l] and for all i ∈ N , there exists U iq ∈ R + such that u(i, j) = U iq for all j ∈ M q .

Type-uniformity assumes a strong correlation between agents' type and utility; in the context of the HDB allocation problem, this implies that Singaporeans of the same ethnicity share the same preferences over apartments (perhaps due to cultural or socioeconomic factors). Cases that deal with uniform goods satisfy the blockuniformity assumption: e.g. students applying for spots in public schools or job applicants applying for multiple (identical) positions; in the HDB domain, block-uniformity captures purely locationbased preferences, i.e. a tenant does not care which apartment she gets as long as it is in a specific block close to her workplace, family, or favorite public space. Theorem 3.6. The AssignTC problem can be solved in poly(n, m) time under either a type-uniform or a block-uniform utility model.

We prove the result for a type-uniform utility model; the result for block-uniform utilities can be similarly derived. We propose a polynomial time algorithm based on the Minimum-Cost Flow problem which is known to be solvable in polynomial time. Recall that a flow network is a directed graph G = (V , E) with a source node s ∈ V and a sink node t ∈ V , where each arc (a, b) ∈ E The value v(f ) of a flow f is defined by v

(f ) = a ∈V f (s, a) = a ∈V f (a, t) and its cost γ (f ) is equal to (a,b)∈E f (a, b)γ (a, b).
The optimization problem can be formulated as follows. Given a value F , find a flow f that minimizes the cost γ (f ) subject to v(f ) = F . This problem that takes as input the graph G, the matrices Γ and Ψ, and the value F , will be denoted by MinCostFlow hereafter; given an instance ⟨G; Γ; Ψ; F ⟩ of the MinCostFlow problem, we let γ (G, Γ, Ψ, F ) be the cost of the optimal flow for that instance.

Given an instance I of AssignTC, we construct a flow network G I (V , E) and matrices Γ I and Ψ I as follows (see Figure 2 for an illustration). The node set V is partitioned into layers:

V = {s} ∪ A ∪ B ∪ C ∪ {t }.
A is the agent type layer: there is one node a p ∈ A for each agent type N p , p ∈ [k]. B is the type-block layer: it has a node b pq ∈ B for every type-block pair (p, q) ∈ [k] × [l]. Finally, C is the item layer: there is one node c j ∈ C for all items j ∈ M. The arcs in E are as follows: for every a p in A, there is an arc from s to a p whose capacity ψ (s,

a p ) is |N p |. Fixing p ∈ [k],
there is an arc from a p ∈ A to every b pq ∈ B, where the capacity of (a p , b pq ) is the capacity for type N p in block M q , i.e. ψ (a p , b pq ) = λ pq . Finally, given q ∈ [l], there is an arc from b pq to c j iff j ∈ M q ; in this case, we have ψ (b pq , c j ) = 1. The costs associated with arcs from B to C (i.e. arcs of the form (b pq , c j ) where j ∈ M q ) are -U p j ; recall that U p j is the utility that every agent of type N p assigns to item j. All other arc costs are set to 0. We begin by proving a few technical lemmas on the above network.

Given a positive integer F , there exists an optimal flow that is integer-valued since ⟨G I ; Γ I ; Ψ I ; F ⟩ is integer-valued as well. Let f * be an integer-valued optimal flow, taken over all possible values of F , that is:

f * ∈ argmin F ∈[n] γ (G I , Γ I , Ψ I , F ) (6)
Finding the flow f * involves solving n instances of MinCostFlow by definition; thus, one can find f * in polynomial time. Given f * as defined in ( 6), let X * = (x * i j ) n×m be defined as follows: for every item j ∈ M q , if f * (b pq , c j ) = 1 for some p ∈ [k], then we choose an arbitrary unassigned agent i ∈ N p and set x * i j = 1.

Lemma 3.7. X * is a feasible solution of the AssignTC instance I.

Proof. First, we assign at most one item to every agent by construction; next, let us show that each item j ∈ M q is assigned to at most one agent. Since f * is a flow, we have k p=1 f * (b pq , c j ) = f * (c j , t) due to flow conservation; note that the capacity of the arc (c j , t) is 1, thus at most one arc (b pq , c j ) has f * (b pq , c j ) = 1. Finally, since item j is assigned to an agent in N p iff f * (b pq , c j ) = 1, we conclude that item j is assigned to at most one of the agents in N . Next, let us prove that assignment X * satisfies the type-block constraints; in other words, we need to show that:

i ∈N p j ∈M q x * i j ≤ λ pq , ∀p ∈ [k], ∀q ∈ [l] (7)
Since f * is a flow, we have f * (a p , b pq ) = j ∈M q f * (b pq , c j ) for every pair (p, q) ∈ [k] × [l] due to flow conservation; moreover, we have f * (a p , b pq ) ≤ ψ (b pq , c j ) = λ pq by construction. Therefore, we necessarily have j ∈M q f * (b pq , c j ) ≤ λ pq for all p ∈ [k]. Since an item j ∈ M q is matched with some agent i ∈ N p if and only if we have f * (b pq , c j ) = 1, we conclude that (7) indeed holds. Now, let us establish a relation between the cost of f * and the utility of the feasible assignment X * . Lemma 3.8. The cost of the flow f * satisfies γ (f * ) = -u(X * ).

Proof. By construction, the cost of f * can only be induced by arcs from nodes in B to nodes in C, where the cost of all arcs of the form (b pq , c j ), with j ∈ M q , is equal to -U p j (the negative of the uniform utility derived from item j by members of N p ). In other words, the cost of f * can be written as follows:

γ (f * ) = - k p=1 l q=1 j ∈M q f * (b pq , c j )U p j
As previously argued, we have that f * (b pq , c j ) ∈ {0, 1} for all arcs (b pq , c j ); moreover, f * (b pq , c j ) = 1 iff item j is assigned to some agent in N p . Therefore, we obtain:

γ (f * ) = - k p=1 i ∈N p j ∈M x * i j U p j = - i ∈N j ∈M x * i j u(i, j) = -u(X * )
where the second equality holds since all agents in N p have the same utility by assumption.

Finally, we show that for every feasible solution to the AssignTC instance I, there exists a flow with a matching cost. Lemma 3.9. Let X be a feasible assignment for the AssignTC instance I; there exists some feasible flow f such that γ (f ) = -u(X ). Moreover, we have v(f ) = |{i ∈ N : j ∈M x i j = 1}|.

Proof. Given a feasible assignment X = (x i j ) n×m , we define f : V × V → R + as follows:

                   f (s, a p ) = i ∈N p j ∈M x i j ∀a p ∈ A f (a p , b pq ) = i ∈N p j ∈M q x i j ∀(a p , b pq ) ∈ E f (b pq , c j ) = i ∈N p x i j ∀(b pq , c j ) ∈ E f (c j , t) = i ∈N x i j ∀c j ∈ C f (a, b) = -f (b, a) ∀(a, b) ∈ E f (a, b) = 0 ∀(a, b) E
The function f is indeed a flow: f trivially satisfies the skew symmetry condition by construction; next, we show that f satisfies flow conservation. For all a p ∈ A, the incoming flow to node a p from node s is f (s, a p ) = i ∈N p j ∈M x i j , and the outgoing flow to

every b pq is l q=1 f (a p , b pq ) = i ∈N p j ∈M x i j since M is parti- tioned into M 1 , .
. . , M l ; hence flow is conserved. For a node b pq ∈ B, the incoming flow equals f (a p , b pq ) = i ∈N p j ∈M q x i j and an amount of f (b pq , c j ) = i ∈N p x i j flows to every node c j such that j ∈ M q , thus flow is conserved. For a node c j ∈ C such that j ∈ M q , its incoming flow equals f (b pq , c j ) = i ∈N p x i j from every b pq , for a total flow of k p=1 i ∈N p x i j , which equals its outgoing flow to t. To conclude, f satisfies flow conservation. Now let us prove that f satisfies the capacity constraints (i.e. f (a, b) ≤ ψ (a, b) for all arcs (a, b) ∈ E). For all (s, a p ) ∈ E, we have f (s, a p ) = i ∈N p j ∈M x i j ≤ |N p | = ψ (s, a p ) since every agent i ∈ N p is matched with at most one item. For all (a p , b pq ) ∈ E, we have f (a p , b pq ) = i ∈N p j ∈M l x i j ≤ λ pq = ψ (a p , b pq ) since X satisfies the type-block constraints. For all arcs (b pq , c j ) ∈ E, we have f (b pq , c j ) = i ∈N p x i j ≤ 1 = ψ (b pq , c j ) since item j is matched with at most one of the agents in N p . For all (c j , t) ∈ E, we have f (c j , t) = i ∈N x i j ≤ 1 = ψ (c j , t) since item j is matched with at most one of the agents in N . Hence, f satisfies the capacity constraints and is a valid flow. Note that we have:

v(f ) = a ∈V f (s, a) = k p=1 f (s, a p ) = k p=1 i ∈N p j ∈M x i j = i ∈N j ∈M x i j .
Then, since X is a feasible assignment of the AssignTC instance I, we conclude that we have v(f ) = |{i ∈ N : j ∈M x i j = 1}|. We just need to prove that we have γ (f ) = -u(X ), and we are done. By definition of the flow network, only arcs of the form (b pq , c j ) contribute to the cost γ (f ) and we have γ (b pq , c j ) = -U p j ; therefore,

γ (f ) = -(b pq ,c j )∈E f (b pq , c j )U p j . Since f (b pq , c j ) = i ∈N p x i j
(by definition of f ) and u(i, j) = U p j for all agents i ∈ N p (by hypothesis), we finally obtain γ

(f ) = -j ∈M k p=1 i ∈N p x i j u(i, j) = -j ∈M i ∈N x i j u(i, j) = -u(X ).
We are now ready to prove Theorem 3.6.

Proof of Theorem 3.6. We begin by observing the flow f * as defined in [START_REF] Anshelevich | Anarchy, Stability, and Utopia: Creating Better Matchings[END_REF], and the assignment X * derived from it. First, X * is a feasible assignment of the AssignTC instance I (by Lemma 3.7) and we have u(X * ) = -γ (f * ) (by Lemma 3.8). Then, for any valid assignment X of the AssignTC instance I, there exists a flow f

such that γ (f ) = -u(X ); since v(f ) = |{i ∈ N : j ∈M x i j = 1}| ∈ [n], flow f is a feasible solution of the MinCostFlow instance ⟨G I ; Γ I ; Ψ I ; F ⟩ for some F ∈ [n]
. Therefore, we have:

u(X ) = -γ (f ) ≤ -γ (G I , Γ I , Ψ I , v(f )) ≤ -γ (f * ) = u(X * )
Thus, X * is an optimal solution of the AssignTC instance I; since X * can be computed in poly-time, this completes the proof.

THE PRICE OF DIVERSITY

We now turn to the allocative efficiency of the constrained assignment. As before, an instance of the AssignTC problem is given by a set of n agents N partitioned into types N 1 , . . . , N k , a set of m items M partitioned into M 1 , . . . , M l , a list of capacity values (λ pq ) k ×l , and agent utilities for items given by u = (u(i, j)) n×m . We denote the set of all assignments X of items to agents satisfying only the matching constraints (3-5) of Section 2 by X, and that of all assignments additionally satisfying the type-block constraints (2) by X C ; the corresponding optimal social welfares for any given utility matrix (u(i, j)) n×m are:

OPT (u) max

X ∈X u(X ); OPT C (u) max X ∈X C u(X ).
Clearly, OPT C (u) ≤ OPT (u) since X C ⊆ X; we define the following natural measure of this welfare loss that lies in [1, ∞]: The main result of this section is to establish an upper bound on PoD(u) that is independent of the utility model. Denote the ratio of a type-block capacity to the size of the corresponding block by: α pq λ pq /|M q |. Theorem 4.2. For any instance of AssignTC, the tight upper bound (independent of utilities) on PoD(u) is 1/min (p,q)∈[k ]×[l ] α pq .

In general, the bound in Theorem 4.2 grows linearly in m (e.g. if the capacities λ pq are fixed constants). However, type-block capacities are determined by a central planner in our model; a natural way of setting them is to fix the proportional capacities or quotas α pq in advance, and then compute λ pq = α pq × |M q | when block sizes become available: by committing to a fixed minimum type-block quota α * (i.e. α pq ≥ α * for all (p, q) ∈ [k] × [l]), the planner can ensure a PoD(u) of at most 1/α * , regardless of the problem size and utility function. Higher values of α * reduce the upper bound on PoD(u) but also increase the capacity of a block for every ethnicity, potentially affecting the diversity objective adversely: it thus functions as a tunable tradeoff parameter between ethnic integration and worst-case welfare loss. In fact, in the Singapore allocation problem, the Ethnic Integration Policy fixes a universal percentage cap for each of the three ethnicities in all blocks; these percentages are set somewhat higher than the actual respective population proportions: the current block quotas α pq are 0.87 for Chinese, 0.25 for Malays and 0.15 for Indian/Others [START_REF] Deng | The story of Singapore's public housing: From a nation of home-seekers to a nation of homeowners[END_REF]; plugging in these to the bound in Theorem 4.2, we have that the Singapore housing system has PoD(u) ≤ 6.67. This bound makes no assumptions on agent utilities; in other words, it holds under any utility model.

The proof relies on the following lemma. Given an assignment X ∈ X, let u p (X ) denote the total utility of agents in N p under X :

u p (X )
i ∈N p j ∈M x i j u(i, j).

Lemma 4.3. For any instance of AssignTC and any optimal unconstrained assignment X * ∈ X, we have:

PoD(u) ≤ u(X * )/ p ∈[k ] u p (X * ) min q ∈[l ] α pq .
Proof sketch. Based on the optimal assignment X * , we can construct an assignment X ∈ X C satisfying the type-block constraints, by 'revoking' items in M q from the agents with the smallest realized utilities in N p whenever the type-block constraint is violated for (p, q). We thus ensure that at least α pq proportion of the utility remains under X for (p, q). Summing over blocks, we obtain:

u p (X ) ≥ u p (X * ) min q ∈[l ] α pq ∀p ∈ [k]. (8)
Hence, since X ∈ X C , we have PoD(u) ≤ u(X * )/u(X ) where u(X ) = p ∈[k] u p (X ). Combining this with inequality [START_REF] Barman | Finding Fair and Efficient Allocations[END_REF] gives is the required result.

We can now complete the proof of the theorem.

Proof of Theorem 4.2. Since we have min

(p,q)∈[k ]×[l ] α pq ≤ min q ∈[l ] α p ′ q for all p ′ ∈ [k], Lemma 4.3 immediately implies that PoD(u) ≤ 1/min (p,q)∈[k ]×[l ] α pq .
Depending on the utility matrix u, this upper bound can be tight whenever |N p 0 | ≥ |M q 0 | for some type-block pair (p 0 , q 0 ) in the set argmin (p,q)∈[k ]×[l ] α pq . We identify a utility matrix for which the bound holds with equality: u(i, j) = 1 if i ∈ N p 0 and j ∈ M q 0 , 0 otherwise.

The optimal assignment without type-block constraints fully allocates the items in block M q 0 to agents in N p 0 for a total utility of |M q 0 |; furthermore, we know that any optimal constrained assignment allocates exactly λ p 0 q 0 items in M q 0 to agents in N p 0 for a total utility of λ p 0 q 0 . Since λ p 0 q 0 = α p 0 q 0 × |M q 0 |, we have:

PoD(u) = |M q 0 |/λ p 0 q 0 = 1/α p 0 q 0 = 1/min (p,q)∈[k ]×[l ] α pq .

The Impact of Ethnic Disparity

Theorem 4.2 offers a worst-case tight bound on the price of diversity, making no assumptions on agent utilities. However, its proof suggests that this upper bound is attained when social welfare is solely extracted from a single agent type and a single block. Intuitively, we can obtain a better bound on the price of diversity if a less 'disparate' optimal assignment exists. To formalize this notion, we introduce a new parameter: Definition 4.4. For an optimal unconstrained assignment X * ∈ X, denote by β p (X * ) the ratio of the average utility of agents in N p to the average utility of all agents, under X * . The inter-type disparity parameter β(X * ) is defined as:

β(X * ) min p ∈[k ] β p (X * ) = min p ∈[k ] u p (X * )/ |N p | u(X * )/n .
Notice that β(X * ) ∈ (0, 1] can be computed in polynomial time and is fully independent of the type-block capacities. The closer β(X * ) is to 1, the lower the disparity between average agents of different types under X * . Theorem 4.5. For any AssignTC instance and any unconstrained optimal assignment X * ∈ X, we have:

PoD(u) ≤ 1/ β(X * ) p ∈[k ] |N p | n min q ∈[l ] α pq .
Proof. By definition of β(X * ), we have, for every p ∈ [k], u p (X * ) ≥ β(X * ) |N p | n u(X * ). Substituting this in Lemma 4.3, we obtain the desired bound.

Let us now apply the result to the Singapore public housing domain; we use the ethnic proportions reported in the 2010 census report [START_REF]Census: Key Indicators of the Resident Population[END_REF] to obtain |N 1 |/n = 0.741 (Chinese), |N 2 |/n = 0.134 (Malay), and |N 3 |/n = 0.125 (Indian/Others). Using the same block quotas α pq as before and assuming β(X * ) = 1, we have PoD(u) ≤ 1.43. In general, by Theorems 4.2 and 4.5, if we plot the PoD(u) against the disparity parameter β(X * ), the point corresponding to any AssignTC instance with above block quotas and ethnic proportions must lie in the shaded region of Figure 3.

β (X * ) PoD(u) 0 | 1 - 6.67 - 1 1.43/β (X * )

EXPERIMENTAL ANALYSIS

We simulate instances of the AssignTC problem using recent Singaporean demographic and housing allocation statistics. We compare the welfare of three assignment mechanisms: the optimal unconstrained mechanism, the optimal constrained mechanism, and the lottery-based mechanism used by HDB.

Data Collection

In order to create realistic instances of the AssignTC problem within the Singaporean context, we collect data on the location and number of flats in recent HDB housing development projects advertised over the second and third quarters of 20172 . Each of these developments corresponds to a block in our setup, for a total of m = 1350 flats partitioned into l = 9 blocks (a detailed map is given in Figure 4). We consider a pool of n = 1350 applicants whose ethnic composition follows the 2010 Singapore census report [START_REF]Census: Key Indicators of the Resident Population[END_REF]: we have |N 1 | = 1000 (≈ 74.1% Chinese), |N 2 | = 180 (≈ 13.4% Malay) and |N 3 | = 170 (≈ 12.5% Indian/Others). Finally, we use a uniform block capacity using the latest HDB block quotas [START_REF] Deng | The story of Singapore's public housing: From a nation of home-seekers to a nation of homeowners[END_REF]: for every block M q , we have α 1q = 0.87, α 2q = 0.25 and α 3q = 0.15.

Utility Models

All parameters used to generate AssignTC instances in our simulations are based on real data, except for agent utilities over apartments. Conducting large-scale surveys that elicit user preferences over apartments is beyond the scope of this work; thus, we base our agent utility models on simulated utilities. We examine two types of utility models: distance-based (Dist(σ 2 )) and ethnicity-based (Ethn(σ 2 )). In distance-based utilities, each agent i ∈ N has a preferred geographic location ì a i ∈ R 2 (chosen uniformly at random within the physical landmass of Singapore) that she would like to live as close as possible to (say, the location of her parents' apartment, workplace or preferred school). For every block M q , the utility agent i derives from apartments j ∈ M q is generated according to a normal distribution N (1/d(ì a i , loc(M q )), σ 2 ); here, loc(M q ) is the geographical location of block M q , and d(•) is the Euclidean distance between ì a i and loc(M q ). For the ethnicity-based utility model, we assume that all agents of the same ethnicity have the same preferred location (i.e. ∀p ∈

[k], ∀i, i ′ ∈ N p , ì a i = ì a i ′ ).

Evaluation

For both utility models, we vary σ 2 in {1, 5, 10}; the results reported in Figure 5 are on the average performance over 100 randomly generated instances. For each treatment, we report PoD(u) the price of diversity (green), the theoretical upper bound on PoD(u) as per Theorem 4.5 (blue), and the relative loss of the HDB lottery mechanism averaged over 50 runs (red). We first observe that Dist(σ 2 ) exhibits virtually no utility loss due to the imposition of type-block constraints. This is due to the fact that utilities generated according to the Dist(σ 2 ) model are independent of ethnicities, resulting in a very low value for the inter-type disparity parameter (the blue column) -in fact, for any utility model where utilities are independent of ethnicities, the expected value of the disparity parameter should be 1. For utilities generated based on the Ethn(σ 2 ) model, the disparity parameter is somewhat higher (utilities do strongly depend on ethnicity), resulting in a higher PoD(u). Despite making no attempt to optimize social welfare under type-block constraints, the HDB lottery mechanism does surprisingly well, extracting approximately 85% of the optimal unconstrained welfare under the Dist(σ 2 ) utility model, and at least 79% of the social welfare under the Ethn(σ 2 ) model.

CONCLUSIONS AND FUTURE WORK

Our work constitutes a first step towards a better understanding of the effect that diversity constraints have on social welfare. We offer computational insights, providing a general hardness result, sufficient conditions for tractability, and a 1 2 -approximation algorithm for AssignTC. Our S-reduction essentially shows that AssignTC is a special (still NP-complete) case of BCMatching and, although the question of a better approximation remains open, also implies some easy generalizations of our results. For example, there is a PTAS for BCMatching if one allows (1 + ε)-violations of the color constraints [START_REF] Fabrizio Grandoni | Iterative rounding for multiobjective optimization problems[END_REF]; this immediately implies a PTAS for AssignTC where one allows (1 + ε)-violations of the type-block constraints.

We derive two upper bounds on the price of diversity defined as the ratio of the optimal welfare achievable with and without type-block constraints: the first is in terms of block quotas only, independent of the utility model, hence under the planner's control; the second is parametrized in terms of inter-type disparity, which shows that when the disparity is low, the welfare loss is much closer to its ideal value of 1 than the first bound would suggest.

We analyze our model's behavior in simulation: the fundamental experimental framework is based on Singapore census and HDB sales data. Simulating agent utilities is still a major challenge: ideally, one would elicit applicants' utilities directly via large-scale national surveys. Our simulations tested two 'extreme' cases: one where there is no correlation between ethnicity and utility, and one where utility is artificially correlated to ethnicity. The truth is likely somewhere in between. Ethnic groups in Singapore most likely do have some correlation between their utility models; this can be due to socioeconomic factors (there is some correlation between ethnicity and socioeconomic status), the location of cultural or religious centers, or other unknown factors. Developing a more refined utility model is an interesting direction for future work.

Obviously, the HDB lottery mechanism cannot offer a better welfare than the allocation based on constrained optimization under known utilities; but, in our experiments, it does not perform significantly worse for the utility models we considered.

While our motivating problem is important in its own right, it is by no means an exclusive case where diversity constraints can have an effect on social welfare. Two immediate application domains are course allocation (with student capacity constraints), and public school allocation (with neighborhood location constraints).

Finally, our results describe an inevitable tradeoff between diversity and social welfare; however, we would like to strongly emphasize that this does not constitute a moral judgment on the authors' part. Economic considerations are certainly important, but they are by no means an exclusive nor a first order consideration. That said, understanding the impact of diversity constraints on social welfare is key if one is to justify their implementation.

  1 and M 2 . The items in block M 1 correspond to the vertices in B: there is one item j b for each node b ∈ B. For every a ∈ A, we add deg(a) -1 items j 1 a , . . . , j deg(a)-1 a to M 2 , for a total of |E| -|A| items. Thus, there is a total of m = |B| + |E| -|A| items. Block M 1 accepts at most w p agents of type N p , whereas block M 2 has unlimited capacity; in other words, λ p1 = w p and λ p2 = min{|N p |, |M 2 |} for all p ∈ [k]. Given e = (a, b), we define the utility function of agent e as follows:

  we assign the item j b ∈ M 1 to the agent (a, b); the remaining deg(a) -1 agents of the form (a, b ′ ), b ′ ∈ B, are arbitrarily assigned the items j 1 a , . . . , j deg(a)-1 a ∈ M 2 . If E ′ contains no edges incident on a, then we arbitrarily choose deg(a) -1 edges incident on a and assign the corresponding agents to the items j 1 a , . . . , j deg(a)-1 a

  has a cost γ (a, b) ∈ R and a capacity ψ (a, b) > 0 representing the maximum amount that can flow on the arc; for convenience, we set γ (a, b) = 0 and ψ (a, b) = 0 for all a, b ∈ V such that (a, b) E. Let us denote by Γ and Ψ the matrices of costs and capacities respectively defined by Γ = (γ (a, b)) |V |× |V | and Ψ = (ψ (a, b)) |V |× |V | . A flow in the network is a function f : V × V → R + satisfying: (i) f (a, b) ≤ ψ (a, b) for all a, b ∈ V (capacity constraints), (ii) f (a, b) = -f (b, a) for all a, b ∈ V (skew symmetry), and (iii) b ∈V f (a, b) = 0 for all a ∈ V \{s, t } (flow conservation).

5 -U 11 , 1 -U 12 , 1 -U 21 , 1 -U 22 , 1 -U 13 , 1 -U 14 , 1 -U 15 , 1 -Figure 2 :

 51111212112211311411512 Figure 2: Network flow constructed for the proof of Theorem 3.6; in this case, we have 2 types and 2 blocks: M 1 = {1, 2} and M 2 = {3, 4, 5}. Arc capacities are given in red. All arcs have a cost of 0, except those between b pq ∈ B and c j ∈ C whose cost equals -U p j .

Definition 4 . 1 .

 41 For any instance of the AssignTC problem, we define the Price of Diversity as follows, along the lines of Ahmed et al. [2017] and Bredereck et al. [2018]: PoD(u) OPT (u)/OPT C (u).

Figure 3 :

 3 Figure 3: PoD vs disparity parameter for the HDB problem.

3 M 9 M 8 • M 1 :

 3981 Sky Vista (128 flats) • M 2 : West Scape (162 flats) • M 3 : Rivervale Shores (156 flats) • M 4 : Marsiling Grove (249 flats) • M 5 : Woodlands Spring (108 flats) • M 6 : Forest Spring (94 flats) • M 7 : Woodleigh Hillside (104 flats) • M 8 : Dakota Breeze (190 flats) • M 9 : Pine Vista (159 flats)

Figure 4 :

 4 Figure 4: Block locations and number of flats.

Figure 5 :

 5 Figure 5: Utility losses for Dist(σ 2 ) (left) and Ethn(σ 2 ) (right).

  HDB, provides low-cost apartments to Singapore citizens and permanent residents. Public housing is a dominant force in Singapore: as of 2017, approximately 73.3% of apartments in Singapore are HDB flats[20]. New HDB flats are purchased directly from the government, which offers them at a heavily subsidized rate. New apartments are typically released at quarterly sales launches: these normally consist of plans for several estates at various locations around Singapore, an estate comprising four or five blocks (each apartment block has approximately 100 apartments) sharing some communal facilities (e.g. a playground, a food court, a few shops etc.

While this example is, of course, stylized, the effects it describes are quite real: one often hears stories of young couples who arrive at the HDB office to select a flat, only to be notified that their ethnic quota has just been filled.

http://www.hdb.gov.sg/cs/infoweb/residential/buying-a-flat/new/bto-sbf

ACKNOWLEDGMENTS

This research has been funded by an MOE Grant (no. R-252-000-625-133) and an NRF Research Fellowship (no. R-252-000-750-733).


D Mandache

E Dalimier

Durkin

C Boccara

J.-C Olivo-Marin

V Meas-Yedid

BASAL CELL CARCINOMA DETECTION IN FULL FIELD OCT IMAGES USING CONVOLUTIONAL NEURAL NETWORKS

Keywords: convolutional neural networks, nonmelanoma skin cancer, digital pathology, full field optical coherence tomography

In this paper we introduce a new application that exploits the emerging imaging modality of full field optical coherence tomography (FFOCT) as a means of optical biopsy. The objective is to build a computer-aided diagnosis (CAD) tool that can speed up the detection of tumoral areas in skin excisions resulting from Mohs surgery. Since there is little prior knowledge about the appearance of cancer cell morphology in this type of imagery, deep learning techniques are applied. Using convolutional neural networks (CNN), we train a feature extractor able to find representative characteristics for FFOCT data and a classifier that learns a generalized distribution of the data. With a dataset of 40 high-resolution images, we obtained a classification accuracy of 95.93%.

INTRODUCTION

Skin cancer is the most common human malignancy, predominantly represented by non-melanoma types with 5.4 million cases per year, 80% of which are Basal Cell Carcinomas (BCC) with the majority the remaining being Squamous Cell Carcinomas (SCC) [START_REF]Cancer facts & figures 2016[END_REF]. The gold standard procedure for treating non-melanoma skin cancer in high risk areas is Mohs Surgery [START_REF] Aasi | Atlas of Practical Mohs Histopathology[END_REF]. The technique involves the consecutive removal of thin layers of skin, followed by histological preparation and microscopical examination for tumor clearance. This process can take up to an hour and guides further tissue extraction. We investigate the feasibility of using a non-invasive optical slicing modality, together with an automated diagnosis of the cancerous areas, which would lead to speeding up the procedure, consequently, improving patient comfort and physician throughput.

Histology slides are 3 µm thick, performed at any desired depth in the resection, and observed with high resolution microscopes. So only thin optical slicing systems which ensure cellular-level resolution and enough penetration depth can compete with this standard. The technologies generally employed in this domain are optical coherence tomography (OCT) and confocal microscopy, while the first favors penetration depth (1 mm) with a low axial resolution (10 µm), the other has a better resolution (0.8 µm) and insufficient penetration (100 µm). FFOCT relies on the same principle as classical OCT, light interferometry, but produces "en face" slices, instead of cross-sections. This allows for an intra-cellular resolution (1 µm) and sub-surface penetration (200 µm-1 mm, depending on the numerical aperture and optical properties of the tissue). Given its specifications and resemblance with transverse histological slices, FFOCT proves to be a powerful technique for optical pathology [START_REF] Dalimier | Full-field optical coherence tomography: a new technology for 3d high-resolution skin imaging[END_REF].

There is a growing tendency for medical diagnosis applications to rely on deep learning [START_REF] Litjens | A survey on deep learning in medical image analysis[END_REF], especially convolutional neural networks (CNN) which are most suitable for image inputs. Their efficiency is proven by the fact that CNN architectures are winning the grand challenges in the domain: TU-PAC16 (MICCAI), CAMELYON16-17 (ISBI), however, all their datasets consist of bright-field whole-slide images. In OCT imaging, deep learning is mostly used for segmentation of the retinal layers [START_REF] Venhuizen | Robust total retina thickness segmentation in optical coherence tomography images using convolutional neural networks[END_REF]. Recently, neural networks conquered the field of dermatology, with [START_REF] Esteva | Dermatologist-level classification of skin cancer with deep neural networks[END_REF], which classifies cancerous lesions from macro images of the skin surface. Still, to our knowledge, there is almost no research in automatic diagnosing for the FFOCT modality, including using deep learning methods. In this work we propose exploiting FFOCT images, as exposed in Section 2, which will be used to train a CNN, as detailed in Section 3. The results obtained are presented in Section 4 and the concluding remarks in Section 5.

DATA

Data Acquisition

Our data set consists of 40 FFOCT images of tissue excisions obtained from Mohs surgery, biopsies and conventional excisions, which were then imaged using the Light-CT TM scanner developed by LLTech, France. The samples did not undergo any preparation. The scanner has a resolution of 1 µm 3 and a penetration depth of 200 µm, which means reaching the level of the dermis. Each image is a 2D transverse slice of a unique tissue sample imaged at 20 µm below the surface. Samples measure between 2-2.5cm 2 which gives high-resolution images of around 200 Megapixels. The speed of acquisition is 1 cm 2 per minute.

Data Annotation

As shown in Fig. 1 the images were manually segmented and diagnosed by a dermatopathologist with experience with this modality and who could access the gold standard H&E frozen sections of the specimen for validation. The data was gathered and annotated using the Cytomine [START_REF] Marée | Collaborative analysis of multi-gigapixel imaging data using cytomine[END_REF] platform. 26% of the total imaged area was segmented, the rest (unlabeled areas) being background or abnormal tissue (it sometimes surrounds the tumors but its appearance is not relevant for either class, it should be treated separately). The images are preponderantly annotated with the normal label and only 10 images present some cancerous areas, annotated as BCC, more precisely, only 9.5% of the annotated data is pathological. Therefore, as it is the case of most of the medical applications, we face the class imbalance problem, which we try to solve by oversampling the minority class.

Data Sampling & Preprocessing

The scanner produces 16-bit DICOM images, but only 10 to 12 bits are actually used; they were converted to 8-bit JPEG for convenience, so they can be tested with out of the box pre-trained architectures that only accept this depth.

Speckle noise is strongly present in FFOCT images, but proper denoising algorithms are too computationally costly (of the order of hours) therefore, since one of the requirements of our application is speed, we applied a 3 × 3 Gaussian filter to provide some smoothing while preserving the structures (e.g. cancerous cell nuclei appear as dark blobs with 10 pixels in diameter).

A constraint imposed by the computational power needed to train artificial neural networks is its number of parameters. This is a function of the depth (number of filters, layers) and width (input size of the layers) of the network. To satisfy this constraint while capturing enough context to discern normal skin structures from the cancerous cell organization, we split the images in patches of 256 × 256 pixels. With the aim of augmenting and also balancing the data set, we oversampled the patches with different step values for the two classes: 170px for the normal class, while BCC patches overlap more, with a stride of 40px. This produces 108 082 patches: 59 112 normal and 48 970 BCC; 80% of which serve as a training set and the rest is used for measuring the performance.

Among the popular practices in deep learning is data standardization (zero centering + normalization) which translates into imposing the data to follow a normal distribution. This influences the robustness of the algorithm to variations in the images caused by the acquisition conditions, for example, and it also ensures a better convergence of the learning process. Data standardization is done by subtracting the mean intensity value over the training set and dividing by their standard deviation. Note that the same preprocessing has to be applied on the test data for consistency. Furthermore, some basic data augmentation was performed, which led to doubling the training set, by adding synthetically generated images obtained through horizontal and vertical flipping, slight rotations and shifts.

METHOD

Using some popular architectures like VGG-16 [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF] or Incep-tionV3 [START_REF] Szegedy | Rethinking the inception architecture for computer vision[END_REF], pre-trained on ImageNet database, we obtained an accuracy of 89.30% and 90.79%, respectively. Moreover, the overfitting phenomenon (i.e. "memorizing" training data, rather than learning to generalize) was quite important and was fast to appear. We inferred that those architectures were too deep and complex for our data distribution, therefore, data over specification caused overfitting. However further investigation is intended. Moreover, using pre-trained networks or even fine-tuning (i.e. continuing training) them seems inappropriate for our problem, since we are dealing with a new modality and one of our objectives is to discover relevant features that characterize FFOCT images. We build and train from scratch, a CNN that is able to learn a generalized distribution of our data, with respect to our two classes, normal and BCC.

The proposed architecture follows the classical construction of a multi-layer CNN while having a smaller number of parameters than state of the art architectures. Nevertheless, it takes advantage of the ideas employed by VGG, like: 1) convolutional blocks: consecutive convolutional layers to capture larger input with a spare of parameters; 2) dropout layer: a fraction of neurons is randomly removed to avoid overfitting; 3) rectified linear unit (ReLU): activation function used to speed up the computations.

We trained a 10 layer CNN (see Fig. 2) including the feature extraction part, composed of 4 convolutional blocks (with two convolutional layers each) followed by max-pooling and 25% dropout and a classifier consisting of two fullyconnected layers of 512 and 64 neurons, respectively, each followed by 50% dropout, lastly, there is one output neuron whose firing signals the classification of the input patch as BCC or normal otherwise. The layers from the first blocks have 32 filters and the rest have 64 filters each, the receptive fields of the convolutions vary from 7 × 7 and 5 × 5 to 3 × 3 as we go deeper into the network.

The network has in total 8 654 369 parameters to train, most of them corresponding to the classifier part (i.e. fully connected layers), while 232 417 represent the filters encoding the features, meaning 60× less than VGG-16. The weights are initialized using the Glorot method [START_REF] Glorot | Understanding the difficulty of training deep feedforward neural networks[END_REF] which is based on the idea that the gradients of each layer should follow more or less the same distribution at the beginning of training and it is proven to converge faster and towards a "better" minimum. The training process consists in minimizing the binary cross entropy loss. When computing it, class weighting applies a higher penalization for misclassifying cancerous class with respect to the under representation of the minority class: 1 ÷ 1.2 (there is 1 normal sample for 1.2 cancerous samples). Learning is possible using a gradient decent optimization algorithm, for our application Adaptive Moment Estimation (Adam) [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF] worked best. Adam is one of the adaptive methods of gradient descent whose particularity is that they adapt the learning rate (i.e. step of the descent) to the parameters, performing larger updates for infrequent parameters (i.e. the ones which were rarely updated) and smaller updates for frequent ones. Adam also multiplies the learning rate by the momentum (i.e. average of the previous gradients) providing accelerated optimization. The mini-batch gradient descent approach is a trade-off between computational accuracy and convergence time, so between batch (entire dataset) and stochastic (one example at a time) gradient descent. We chose a mini-batch of 40 samples as it was the biggest size that respected the memory constraints.

The proposed network was implemented using Keras [START_REF] Chollet | [END_REF] with Tensorflow [START_REF] Abadi | Tensorflow: Large-scale machine learning on heterogeneous systems[END_REF]

RESULTS

We obtained a classification accuracy of 95.93%, corresponding to a sensitivity of 95.2% and 96.54% in specificity. Fig. 3 shows a comparison between the ground truth labeling and the patches classified with our method. We notice that the cancerous regions are coarsely detected and, interestingly, the abnormal tissue that was unlabeled (so unknown to the network during training) is classified as BCC. Note that background removal was not performed when testing, however, the method doesn't detect any abnormality outside the sample. There are a few misclassified solitary patches which inspired us to impose some neighborhood relationship constraints in the future work. The results are still raw but they clearly represents a promising step towards an automated segmentation of FFOCT images.

However, caution should be taken with the statistical results which can be misleading in interpreting the overall efficiency of the method and its behavior with different data. Since artificial neural networks are black-box models, gaining an intuition about the reasoning performed by the network is not straightforward. To do that we visualize what the network is learning. This is possible by viewing the weights of the neurons which correspond to the convolutional filters, but since they are very small, the textures encoded are not easily deductible. Still, to get the texture that a filter is responsive to, we can visualize the simulated input that would maximize the activation of its corresponding neurons. This is achieved by performing gradient ascent in the input space with respect to the filter activation loss. In Fig. 4 are plotted the patterns learned by the 3 rd convolutional filter. Without any clinical feedback from a pathologist, we deduce that they could encode different distributions of cells and orientations of collagen fibers, but this matter is still open for discussion.

CONCLUSION

In this work we trained a convolutional neural network in the purpose of discriminating basal cell carcinoma from normal skin. We show preliminary results that open a promising re-search direction, which is analyzing FFOCT images with the powerful methods of deep learning. Developing computeraided diagnosis tools could ease the integration of this novel optical biopsy technology in the clinical environment by assisting pathologists in their familiarization with the new modality and, ultimately, it could reduce the costs and duration of certain medical procedures, like Mohs surgery.

To improve our results we will firstly need a more consistent data set and also a better understanding of the decision flow of the pathologists in diagnosing the samples. This would allow us to translate the knowledge of an expert to artificial neural networks. Additionally, we will include a 3 rd class for the unlabeled areas. For future work we also intend to adopt a multi-scale approach, inspired by MIMO-Net [START_REF] Raza | Mimo-net: A multi-input multi-output convolutional neural network for cell segmentation in fluorescence microscopy images[END_REF], for capturing a larger context and extracting specific information at different levels of zooming.

Another idea is that, in order to accurately assess the efficiency of such a model, we need to understand the reasoning learned by the machine. Therefore, we are ambitiously aiming towards demystifying artificial neural networks in the hope of also gaining knowledge about the data set.

  (a) Annotated sample (green: normal, red: BCC) (b) Normal patches: collagen, hair follicles, glands (c) BCC patches: aggregates of cancer cells, retraction artifacts

Fig. 1 .

 1 Fig. 1. An example of image (11808 × 8352) annotated in Cytomine and some patches (256 × 256) extracted from it.

Fig. 2 .

 2 Fig. 2. Proposed CNN architecture.

  backend. Training time was about a day (25 hours and 17 minutes) on 4 Nvidia Tesla P100 GPUs for 2000 epochs (45 seconds per epoch); an epoch represents one forward and one backward pass over all the training examples. However, testing a full-size image patch by patch takes up to a few seconds and is possible on any kind of basic system configuration.

Fig. 3 .

 3 Fig. 3. Ground truth labeling (left) and predictions (from left to right): proposed method, InceptionV3 pre-trained, VGG16 pre-trained, VGG16 fine-tuned (green: normal, red: BCC).

Fig. 4 .

 4 Fig. 4. Textures maximizing activations for Conv 3 layer.