Deep Learning for Multi-Facility Location Mechanism Design

1 Introduction

In many multi-agent systems, the use of payments is either not possible or unethical, for example in deciding about a public good, or in organizational settings where norms preclude payments. Moreover, mechanism design without money is essentially impossible outside of structured domains: by the Gibbard-Sattherwaite theorem [Gibbard, 1973; Satterthwaite, 1975], any strategy-proof mechanism that chooses between two or more outcomes and for which agents can have all possible strict preferences must be dictatorial.

The most studied domain for which there are positive results is that of single-peaked preferences. Given a space Ω ⊆ Rd of locations, consider the problem of locating one or more facilities at one of these locations. An agent i has single-peaked preferences if she has one location, τi ∈ Ω (the peak), where she most prefers a facility to be located, and if her preference decreases as the location of the closest facility moves farther away from her peak. The facility location problem can occur in many real-world scenarios. For instance, if Ω ⊆ R2 , it could represent the problem of deciding where to place a public facility, such as a swimming pool, in a town.

We have a complete understanding of this problem when only one facility must be chosen. If the outcome space is 1dimensional (e.g. Ω = [0, 1]) it has long been known [Black,

1948] that choosing the median of the agents' peaks is the strategy-proof mechanism that minimizes the sum of the agents' distances to the outcome. Moulin [1980] developed a complete characterization of all strategy-proof social choice rules in the 1-dimensional, 1-facility setup, which was later generalized to multi-dimensional outcome spaces [Border and Jordan, 1983; Barber`a et al., 1993].

The design problem for the multi-facility setting is both less well understood, and has negative approximation results. For n agents and 2-facilities, Procaccia and Tenneholz [2013] give a lower-bound of 3/2 - O(1/n) and an upper-bound of n-1, for deterministic, strategy-proof mechanisms. Amongst follow-on work [Lu et al., 2010; Wang and Lu, 2009; Alon et al., 2010; Fotakis and Tzamos, 2014; Sui et al., 2013], of particular note is a proof that tightens the result of Procaccia and Tenneholz to show that the best approximation ratio is exactly n - 2 [Fotakis and Tzamos, 2014]. Moreover, for K > 2 facilities and anonymous strategy-proof mechanisms, the approximation ratio becomes unbounded [Fotakis and Tzamos, 2014].

In light of these negative, worst-case approximation results, we adopt the goal of minimizing expected social cost, both unweighted and weighted. We assume that there is a joint distribution D over the agents' single-peaked utility functions (u1, . . . , un). As with most works in the multifacility literature, we take Ω to be a subset of the real line.

Our solution approach uses the framework of machine learning to find optimal mechanisms. While there have been previous works that have used machine learning for the design of mechanisms without money [Narasimhan et al., 2016; Narasimhan and Parkes, 2016], none of them present a practical, flexible approach for designing general mechanisms.

Building on the recent success of using deep learning for the design of revenue-optimal auctions [D¨utting et al., 2017; Feng et al., 2018], we model a mechanism as a feed-forward network, and optimize its parameters with the social cost as the loss function. The following are our contributions:

• We show that the class of multi-facility generalized median rules is PAC learnable under product distributions (Section 3). This result leverages the characterization result of Moulin [1980] as well as the recent framework of Cai and Daskalakis [2017] to take advantage of the independence of agents' reports.

• We develop a neural network, MoulinNet, for learning from the class of generalized median rules (Section 4). This is analogous to characterization-based approach of D¨utting et al. However, unlike their networks, we need to deal with an exponential blow-up in parameters, requiring new tricks to make the training tractable. For a single facility problem, our network can represent to an arbitrary accuracy any strategy-proof mechanism. This is however not the case for K > 1 facilities.
• For K > 1, we provide a more general approach that does not rely on characterization results and learns mechanisms that yield very low ex-post regret (Section 5). We model a mechanism as a fully-connected network, the RegretNet-nm, and impose explicit constraints for strategy-proofness on the training problem. Our approach builds on the agnostic framework of D¨utting et al. and is the first to successfully apply deep learning for the design of mechanisms without money.
• In our experiments (Section 6), RegretNet-nm learns mechanisms that are essentially strategy-proof, with social costs comparable to or lower than the best percentile and dictatorial rules. The RegretNet-nm mechanisms are often better than the ones learned by MoulinNet. The generality of RegretNet-nm is particularly beneficial when the design objective is the weighted social cost, or when the utility distribution is non-independent. These are settings where the less flexible mechanisms in the literature do not perform as well.

1.1 RelatedWork

Conitzer and Sandholm [2002] introduced the paradigm of automated mechanism design (AMD). In this work, design was achieved through integer linear programming techniques, with explicit, enumerative representation of functions and incentive constraints. This made their approach difficult to scale. Since then, several papers have adopted machine learning for economic design problems.

Procaccia et al. [2009] showed learnability of specific classes of voting rules, but without requiring strategyproofness. Xia [2013] introduced specific axiomatic properties still without incentive considerations. The first paper to use learning in the context of design under incentive constraints is D¨utting et al. [2015], who use support vector machines (SVMs) to learn payment rules that are maximally strategy-proof with respect to a given outcome function.

Our paper builds on the framework of D¨utting et al. [2017], extending it for the design of mechanisms without money. In regard to facility location, Narasimhan et al. [2016] have previously adopted an SVM-based approach to automated design without money, but specialize to a specific family of rules, and to single facility only. We search over a richer space of mechanisms and handle multiple facilities.

Recent work has also studied the sample complexity of learning revenue-optimal auctions [Cai and Daskalakis, 2017; Morgenstern and Roughgarden, 2016], and assignment mechanisms with and without money [Narasimhan and Parkes, 2016]. To the best of our knowledge, we provide the first sample complexity results for the facility location problem.

2 Preliminaries

There are a set of agents N = {1, . . . , n} and a set of locations Ω. In this paper, we work with Ω = [0, 1]. We are interested in the problem of locating K facilities among locations in Ω. Each agent i has a preference over Ω for where a facility needs to be located, represented by a utility function ui : Ω → R that associates a real value with each location. Let Ui be the set of permissible utility functions. Let u = (u1, . . . , un) denote a profile of utilities, and denote the set of all such tuples by U = ∏ni=1 Ui. Further, let u-i = (u1, . . . , ui-1, ui+1, . . . , un) denote all utility functions other than ui, and U-i = ∏nj̸=i Uj .

Each agent cares about the location of its closest facility. As such, an agent's utility function induces a utility for an outcome, o = (o1, . . . , oK), which specifies a location for each facility. By a slight abuse of notation, we write ui(o) = maxk∈{1,...,K} ui(ok). We require single peaked preferences.

Definition 1 (Single-peaked preferences). For locations Ω ⊆ R, a function ui : Ω → R≥0 is single-peaked if and only if there exists a unique point a ∈ Ω (the peak of u), denoted by a = τ(ui), such that for all x, y ∈ Ω, if either y > x > a or y < x < a, then ui(y) < ui(x) < ui(a).

As one moves away from the peak τ(ui) of utility function ui, the location becomes less preferred. Following from Procaccia and Tennenholtz [2013] and subsequent work, we assume u(x) = -|x - a|, where a = τ (u) is the peak.

A mechanism for facility location f : U → ΩK takes reports of agent utilities as inputs, and outputs the locations in Ω for the K facilities. We use fk(u) to denote the location of the k-th facility for input u. A mechanism is strategyproof if agent i cannot strictly increase her utility by misreporting her utility, whatever the inputs from others, i.e. for all i ∈ N, u ∈ U, u′i ∈ Ui, we have ui(f(u′i , u-i)) ≤ ui(f(u)).

We denote by Msp ⊆ M the space of all strategy-proof mechanisms for the facility location problem (leaving K implicit). We assume that the agent utilities are sampled from a joint distribution D over U, with full support on U. We will sometimes assume that D is a product distribution, i.e. D = ∏ni=1 Di for independent distributions Di on Ui.

The design objective is to find the strategy-proof mechanism f ∈ Msp that minimizes expected social cost (or a weighted variant): gsc(f ; D) = -Eu∼D [ 1n ∑ni=1 ui(f (u))]. We do not have direct access to D, but are provided a sample of profiles S = {u(1) , . . . , u(R) } drawn i.i.d. from D.

3 Learnability of GeneralizedMedian Rules

As a first step, we ask if known classes of strategy-proof mechanisms in the literature are learnable. Moulin provided a characterization of unanimous strategy-proof mechanisms for a single facility, later generalized by Border and Jordan:

Theorem 1 (1-facility generalized median rules [Moulin, 1980; Border and Jordan, 1983]). A unanimous mechanism f : U → Ω is strategy-proof if and only if it is a generalized median rule, i.e. for each S ⊆ {1, . . . , n}, there exists some aS ∈ Ω s.t. for all (u1, . . . , un) ∈ U,

There is no complete characterization of strategy-proof mechanisms for multi-facility location. 1 Still, we can leverage Moulin's result and consider a rich (if incomplete) family, by combining single-facility mechanisms in the natural way.

Definition 2 (Multi-facility generalized median rules). Let MGM denote the class of multi-facility generalized median rules given by f = (f1, . . . , fK), where each fk is a 1-facility generalized median rule for parameters akS ∈ Ω, S ⊆ N.

The set of multi-facility generalized median rules is a strict superset of the set of multi-facility percentile rules considered in [Sui et al., 2013]; all multi-facility percentile rules are anonymous, but this is not true of all rules inMGM. It is immediate that MGM is strategy-proof for all K ≥ 1. To see this, suppose an agent i can improve her cost by misreporting her utility. Let fk(u) and fk′ ((u′i , u-i)) be the closest facility to the agent under a truthful report and the misreport. Clearly, fk′ ((u′i , u-i)) also yields lower cost to the agent than fk′ (u), which is a contradiction to the strategy-proofness of fk′ .

Definition 3 (PAC learnability). A class of mechanisms M on U is probably approximately correct (PAC) learnable over product distributions if there exists an algorithmA, such that for any product distribution D over U, any ϵ > 0, and any δ ∈ (0, 1), running A on an i.i.d. sample from D of size poly(1/ϵ, 1/δ) gives a function ̂ f ∈ F s.t. gsc( ̂ f;D) ≤ inff∈M gsc(f ; D)+ϵ, with probability 1-δ over the sample.

Despite there being an exponential number of parameters akS in defining a mechanism in class MGM, we have:

Proof Sketch. Consider the class of social cost functions {u ↦→ ∑ni=1 min1≤k≤K |τ(ui) - fk(u)| : f ∈M} from mechanisms in M. The proof involves establishing a uniform convergence sample complexity bound for this class. Specifically, we use the recent framework of Cai and Daskalakis [2017] to exploit the product structure of D and break down the overall analysis into an analysis of the following projected functions from the class for each i, j ∈ [n]: Hi,j = {uj ↦→min1≤k≤K |τ(ui) - fk(uj, u-j)| : f ∈M, u-i ∈ U-i}

Each function in Hi,j captures the effect agent j's reports have on agent i's social cost, fixing the reports of agents other than j. It can be shown that the functions in Hi,j are piece-wise linear with O(K) pieces if i = j and O(1) pieces if i ̸= j, and correspondingly have a pseudo-dimension 2 O(K logK) if i = j and O(1) if i ̸= j. Standard results [Anthony and Bartlett, 2009] allow us to derive a uniform convergence bound for each Hi,j. An application of the result of Cai and Daskalakis then completes the proof.

1 Ehlers and Gordon [2011] and Heo [2013] provide characterizations for the special case K = 2 under different assumptions.

2 The pseudo dimension of a class F of functions f : X → R is the VC-dimension of the class {(x, y) ↦→ sign(f(x)-y) : f ∈ F}.

4 MoulinNet for GeneralizedMedian Rules

Equipped with the above learnability result, we now develop a computational procedure for learning from the class of generalized median rules, by modeling these rules using neural networks. We start with the case of a single facility.

Recall that a generalized median rule depends only on the agent peaks τ(ui). For the single facility location on [0, 1] it is w.l.o.g. to only consider mechanisms that operate on agent peaks [Border and Jordan, 1983]. It is also w.l.o.g. to assume that the parameters aS are monotone, i.e. aS ≥ aT , ∀S ⊂ T .

One computational approach would search direclty over the space of parameters {aS}S⊆N. But this does not scale because there are exponentially many parameters. Instead we parametrize each aS using a monotone feed-forward neural network. For this, we use a neural network h : {-1, 1}n → R that maps a n-dimensional binary representation of set S to a real value. Any S ⊆ N can be represented as a binary vector x ∈ {-1, 1}n , with xi = 1 if and only if i ∈ S. We use ν(S) to denote the binary encoding of S, and define aS = h(ν(S)). With this, the parameters to optimize are those that parametrize neural network h.

We say h is monotonically decreasing if ∀x, x′ ∈ {-1, 1}n , i ∈ [n], (xi ≥ x′i ) ∧ (x-i = x′-i ) =⇒ h(x) ≤ h(x′ ). If h is monotone then the resulting {aS}S⊆N are also monotone. We appeal to a characterization of Sill [1998] to construct monotone neural networks. Sill shows that any bounded, monotone function h : {-1, 1}n → R can be approximated to arbitrary precision using the following parameterization, for suitable choice of positive integers L, J, parameters wlj ∈ Rn-, blj ∈ R, l ∈ [L], j ∈ [J]:

Figure 1 contains a representation of this function as a feedforward network, taking ν(S) as input and outputting aS.

Thus for any choice of wlj ∈ Rn-, blj ∈ R, j ∈ [J], l ∈ [L], L, J ∈ N, the following single-facility mechanism is strategy-proof:

By choosing parameters L and J to tune the complexity of the function class, (3) gives us a way to parametrize all 1-facility generalized median rules.

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

The method in (3) still involves a minimum over |S| = 2n functions of wlj, blj. We can compute (3) efficiently by exploiting the fact that the aS values are monotone. In particular, let π denote a permutation of the reported peaks in sorted order, i.e. τ(uπ(1)) ≤ · · · ≤ · · · ≤ τ(uπ(n)). For 1 ≤ i ≤ n, we let Sπ,i = {π(1), . . . , π(i)}. We can show that:

Theorem 3. (3) can be computed in time O(z · n+n logn), where z is the time taken for a single invocation of hw,b .

The proof is omitted due to lack of space. The resulting mechanism for a single facility is given by a feed-forward neural network that takes peaks τ(u1), . . . , τ(un) as inputs and outputs the location of the facility. This architecture, referred to as MoulinNet, is shown in Figure 2. When there are K ≥ 2 facilities, we use K replicas of the network, with K parameter sets, each deciding the location of a facility. We know that this K-facility generalized median rule is strategyproof. We optimize the network parameters with the social cost as the loss function, which is estimated from sample S.

5 RegretNet-nm for General Mechanisms

We now develop a general approach that is not limited by existing characterization results, and which learns mechanisms that have low ex-post regret. For this, we extend the agnostic framework of D¨utting et al. [2017]. We model a mechanism as a feed-forward neural network, which may not be strategyproof for all parameter assignments. We optimize the network parameters to minimize a given cost objective, while seeking to achieve strategy-proofness. The search space can be controlled by varying the depth and width of the neural network.

To measure the deviation of a mechanism f from strategyproof, we adapt the notion of regret to facility location mechanisms [D¨utting et al., 2015; 2017]. We define the expected ex post regret from a mechanism f to an agent i as the (expected) maximum gain in utility that the agent can get by misreporting her preferences:

The network architecture for a mechanism is described in Figure 3. The network is fully-connected, has L hidden layers, takes n agent peaks τ(u1), . . . , τ(un) as input and outputs the locations of the K facilities z1, . . . , zK. Specifically,

where τ(u) = (τ(u1), . . . , τ(un)), wi ∈ RHi×Hi-1 , with H0 = n,HL+1 = K, are the parameters of the network, H1, . . . ,HL are the number of units in each hidden layer of the network, and σ : R → R is a nonlinear activation function, and ¯σ(A) applies σ to every entry of a real matrix A. We use the ReLU activation function σ(x) = max{0, x}.

Let w ∈ Rd denote all the network parameters. The loss function L(w) is the expected social cost or a weighted variant. Our goal is to minimize the loss subject to the expected ex post regret being zero for all agents. Since D has full support on U, this implies that the network is strategy-proof (except for events with zero measure):

Following D¨utting et al. [2017], one way to estimate the regret from a sample u(1) , . . . , u(R) is to search over a subset of misreport peaks in [0, 1] for agent i, say at a certain granularity 1/M; we denote the average of this quantity over the sample by ˆ rgti (f w). While training, searching over M misreports can be expensive, so we adopt a new, pairwise estimate for training that makes better use of each utility calculation:

where β1, . . . , βM′ ∼ [0, 1] are sampled independently and uniformly. For each example j, (5) computes the maximum utility agent i could gain if her true peak was one of β1, . . . , βM′ and she chose to misreport it as one of β1, . . . , βM′ . To include T misreports per agent, the standard definition requires us to perform R(T +1) utility evaluations, whereas (5) requires at most R√T + 1 utility evaluations.

During training, we adopt the augmented Lagrangian solver in D¨utting et al. [2017]. We minimize the empirical loss ˆ L(w) = - 1 Rn ∑Rj=1 ∑ni=1 u(j) i (f w(u(j) )), while seeking to satisfy the constraints ˆ prgti (f) = 0 for each i. The following is the Lagrangian for the above optimization problem, augmented with a quadratic penalty term:

where ρ > 0 controls the weight on the quadratic term.

The solver alternates between updates on the parameter λt : λt+1 = λt +ρ ·maxi∈N ˆ prgti (f w), and using stochastic gradient descent (SGD) to optimize the network parameters w to minimize the Lagrangian. The SGD involves multiple updates on w, each computing the gradient of (6) w.r.t. w.

Since the optimization problem (5) is non-convex, and the solver works with estimates of the loss and regret from a sample, the learned mechanism may have a small, residual regret. 3 In our experiments, we find that the mechanisms learned by RegretNet-nm have a non-zero regret on the test sample, but the regret is often negligibly small, indicating that the mechanisms are essentially strategy-proof.

6 Experimental Results

We describe the results of our experiments on learning mechanisms for multi-facility location problems using MoulinNet and RegretNet-nm. MoulinNet serves as as a benchmark for the best that can be achieved with characterization results.

We implement RegretNet-nm with L = 4 hidden layers, each with 40 units. In the augmented Lagrangian solver, we performed 1000 updates on λ and 50 gradient updates on w for every one update on λ. We implement MoulinNet with L = K = 3. In both cases we make use of the Tensorflow library. We use the Adam algorithm for optimizing w (with mini-batches of size 500). 4 We repeat training with 5 random initializations, and choose the network from the run with smallest regret (based only on the training data).

We train RegretNet with M ′ = 5 by generating new instances and misreports for each mini-batch. We train MoulinNet with multiple passes through a single batch of 1000 examples. Both networks take less than half hour to train on a Tesla K20Xm GPU. Both networks are evaluated based on their social cost on a held-out test set of 2000 examples. For RegretNet, we also report its empirical regret: maxi ˆ rgti , where ˆ rgti is computed using 50 misreports from [0, 1].

We compare our approach against standard mechanisms from the literature: the best percentile rule [Sui et al., 2013], the best dictatorial rule, and the best constant rule, all found by a brute-force search, which is quick for these rules. 5

3 See Nocedal and Wright [1999] for convergence properties of the augmented Lagrangian method on non-convex problems.

4 The learning rate in Adam was initialized to 0.005 for RegretNet-nm (and decayed by a factor 0.99 every 100 updates) and to 0.1 in MoulinNet. Weights were initialized as i.i.d. draws from N(0, 0.01). The offsets in RegretNet-nm were initialized to 0.1.

5 A percentile rule locates each facility at a fixed percentile of the

Unweighted Social Cost

We begin with social cost as the design objective. We consider n = 5 agents, whose peaks are distributed i.i.d. uniformly on [0, 1]. We focus primarily on K = 2, 3 and 4 facilities; for K = 1 both MoulinNet and RegretNet-nm nearly always place the facility very close to the median of the agents' peaks.

Table 1 shows the social cost on the test set for the mechanisms learned by RegretNet-nm, MoulinNet and the other baselines. We also report the social cost for the optimal (non-strategy-proof) mechanism. Both kinds of networks yield similar performance as the best percentile rule. The RegretNet-nmmechanisms have negligible regret, indicating that they are essentially strategy-proof.

Figure 4 plots the average social cost and empirical regret for RegretNet-nm on the test set as a function of running time. With increasing number of solver updates, the regret can be seen to approach zero. The plot also includes the approach of [D¨utting et al., 2017], which uses the standard regret definition ˆ rgt in the Lagrangian formulation (6). This method was trained with 20 misreports per agent, which is effectively the number of misreports per agent RegretNet-nm obtains with

reported peaks. A dictatorial rule locates each facility at the peak of

a fixed agent. A constant rule locates each facility at a fixed point.

MoulinNet

Figure 6: n = 5,K = 3, unweighted social cost. Plots of mechanism outputs as a function of report of a single agent i ∈ {1, 2, 3}, keeping the reports of other agents fixed. The location of each facility is shown in a different color. (a)-(c): Plots for RegretNet-nm on instances where ˆ prgti , i = 1, 2, 3 are respectively maximum (in a sample of size 40). (d)-(f): Plots for RegretNet-nm on instances where ˆ prgti , i = 1, 2, 3 are in the 75-th percentile of the regret values. (g)-(i): Plots for MoulinNet (strategy-proof) on a random instance.

M ′ = 5, Clearly, by using the pairwise regret ˆ prgt in (6), RegretNet-nm achieves a notable speed-up.

We next take a closer look at the learned mechanism. Figure 5 shows the histograms of the percentiles of the facilities chosen by the RegretNet-nm and MoulinNet mechanisms for the test set examples for K = 2, 3, 4. 6 The peaks on percentiles 0, 1/(K - 1), 2/(K - 1), . . . , 1 indicate that the networks use the percentiles of agent reports to make decisions. For K = 2, 3, the mechanisms learned by RegretNetnm approximate the best percentile rules. For K = 4, the percentiles at which RegretNet-nm and MoulinNet place facilities are not the same for all instances.

To understand the inputs on which the RegretNet-nm mechanisms incur a small regret, we visualize the misreports that are useful for agents, for K = 3. Figure 6 plots the locations of the 3 facilities as a function of the report of a single agent i, holding the reports u-i of all other agents fixed.

For fixed u-i, let Ru-i denote the set of all locations where a facility is placed by a mechanism f for some report ui of agent i. Then f is strategy-proof iff for every ui, f(ui, u-i) places one facility at the location in Ru-i closest to τ(ui).

In other words, strategy-proof rules have facilities along the line y = x, and y = const elsewhere. The plots in row

6 If p1, . . . , pn are the agent peaks in sorted order, then a facility at location x has percentile 0 if x ≤ p1, has percentile 1 if x ≥ pn, and has percentile i-1 n-1 + x-pi (n-1)(pi+1-pi) if pi ≤ x < pi+1.

1 (inputs with max. regret in RegretNet) do not satisfy this property. Suppose in (c), agent 3's true peak is at 0.06. Then there is a value in [0.4, 0.6] that she can deviate to and have one of the facilities (orange) placed at her peak. In row 3 (strategy-proof MoulinNet), all the plots satisfy this property.

Weighted Social Cost

In order to demonstrate the flexibility of our framework, we also consider weighted social cost as the design objective: -Eu∼D [ 1 ∑ni=1 γi · ∑ni=1 γiui(f(u))], where γi is a weight on agent i and may correspond to the importance of agent i to society. In this setup, there are n = 9 agents, and all valuations are i.i.d. uniform on [0, 1]. Agents 1 and 2 are assigned a weight of 5, while the remaining agents are assigned a weight of 1. As shown in Table 2 (first row), RegretNet-nm and MoulinNet yield significantly smaller social cost than the baseline mechanisms.

Non-Independent Valuations

Finally, we show that our approach can be used to find optimal mechanisms for non-product distributions. Let n = 4,K = 3. We consider two distributions D1 dep and D2 dep , where it is not immediately clear what the optimal strategyproof mechanism is. In both, the peak X1 for agent 1 is drawn from U([0, 1]), and the peak for each agent i = 2, 3, 4 is set to one of the following piece-wise linear functions: X1 + σi, f1(X1)+σi, f2(X1)+σi, where σi ∼ N(0, 0.01). 7 In D1 dep , the agent chooses one of the 3 functions with equal probability, independent of the others. In D2 dep , the selection is made uniformly over all possibilities where each function is chosen by exactly one agent. The results are shown in Table 2 (rows 2-3). The flexibility of RegretNet-nm allows it to outperform all the benchmarks. For D2 dep , the dictatorial rule that places the facilities at the peaks of agents 2, 3, 4 performs well since each of the functions X1, f1(X1), f2(X1) is chosen by exactly one agent.

7 Conclusion

We have shown that neural networks can be successfully applied to design near-optimal, low ex-post regret mechanisms for the multi-facility location problem. This opens the door for using deep learning to design mechanisms for other settings without money such as matching and allocation problems. In the future, it would be interesting to consider cost functions that are general functions of distance to nearest facility, to study generalization properties of the ex post regret, to develop networks that are invariant to the number of agents, and to allow for randomized mechanisms.

7 f1(x) = 2/3 · 1[0 ≤ x < 1/3] + 1/4 · 1[1/3 ≤ x < 2/3], and f2(x) = 1/3 + 2/3 · 1[0 ≤ x < 1/3] + 5/12 · 1[1/3 ≤ x < 2/3].

Acknowledgments

We thank Dimitris Fotakis for a useful discussion, Zhe Feng for helpful suggestions, and the anonymous reviewers for their comments. The first author is grateful for funding from the Harvard College Research Program.