Deep Contract Design via Discontinuous Networks
Authors: Tonghan Wang
Paul Duetting
Dmitry Ivanov
Inbal Talgam-Cohen
David C. Parkes
Venue: NeurIPS 2023 poster (2023)
Keywords: Automated contract design
discontinuous neural networks
TL;DR: We initiate the study of deep learning for the automated design of optimal contracts by introducing discontinuity into fully-connected networks with ReLU activation to better model the contractual agreements between the principal and the agent.

Abstract: Contract design involves a principal who establishes contractual agreements about payments for outcomes that arise from the actions of an agent. In this paper, we initiate the study of deep learning for the automated design of optimal contracts. We introduce a novel representation: the Discontinuous ReLU (DeLU) network, which models the principal's utility as a discontinuous piecewise affine function of the design of a contract where each piece corresponds to the agent taking a particular action. DeLU networks implicitly learn closed-form expressions for the incentive compatibility constraints of the agent and the utility maximization objective of the principal, and support parallel inference on each piece through linear programming or interior-point methods that solve for optimal contracts. We provide empirical results that demonstrate success in approximating the principal's utility function with a small number of training samples and scaling to find approximately optimal contracts on problems with a large number of actions and outcomes.

Deep Contract Design via Discontinuous Networks
Tonghan Wang
Paul Dütting Google Switzerland duetting&googl com
Dmitry Ivanov
Harvard University
Israel Institute Technology di divanov@campus. technien..eee ac. ac. il
twang10g harvard.
Inbal Talgam-Cohen
David C. Parkes
Israel Institute of Technology italgamècs technion. ac.
Harvard University"
parkesβeecs. harvard. edu
Abstract
Contract design involves a principal who establishes contractual agreements about payments for outcomes that arise from the actions of an agent. In this paper, we initiate the study of deep learning for the automated design of optimal contracts. We introduce novel representation: the Discontinuous ReLU (DeLU) network, which models the principal's 's utility as a discontinuous piecewise affine function of the design of contract where each piece corresponds to the agent taking a particular action. DeLU networks implicitly learn closed-fomt expressions for the incentive compatibility constraints of the agent and the utility maximization objective of the principal, and support parallel inference on each piece through linear programming interior-poin methods that solve for optimal contracts. We provide empirical results that demonstrate success in approximating the principal's utility function with a small number of training samples and scaling to find approximately optimal contracts on problems with large number of actions and outcomes.
Introduction
Contract theory studies the setting where principal seeks to design contract for rewarding an agent on the basis the uncertain outcomes caused by the agent's private actions 8 45 Typical examples include landlord who enters into summer rental with contract that includes penalties in the case of damage; homeowner who engages firm to complete a kitchen renovation with contract that conditions payments on timely completion or functioning appliances; or individual who employs freelancer to do some design work with a contract that includes bonuses for completing the job.
A contract specifies payments the agent, conditioned outcomes. The principal is self-interested, with value for each outcome and a cost for making payments. The agent is also self-interested, and responds to a contract by choosing action that maximizes its expected utility (expected payment minus the cost of an action). The problem is to find a contract that maximizes the principal's 's utility (expected value minus expected payment), given that the agent will best respond the contract. In economics, this is referred to as problem of moral hazard, in that the agent is willing to privately act in its best interest given the contract (the "hazard" is that the behavior the agent may be the detriment of the principal).
The importance of contract design is evidenced by the 2016 Nobel Prize awarded O. Hart and B. Holmström [51] and its broad application to real-world problems. Contract design one of the three fundamental problems in the realm of economics involving asymmetric information and incen- tives, along with mechanism design and signalling (Bayesian persuasion) [41]. However, while
Also DeepMind, London UK
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Del.U
ReLU Opt.
(a) uP function
(b) ReLU approximation (baseline)
(c) DeL. approximation
Figure I: DeLU and ReLU approximation on randomly generated contract design instance with 1,000 actions and 2 outcomes (see Sec. S.3. The x- and y-coordinates are the payments for each of the two outcomes, and the z-coordinate the utility of the principal. (a) The exact surface of the principal's utility function u². Different colors represent the action selected by the agent upon receiving the contract. (b) A learned ReLU network cannot model the discontinuity of the u² function and yields an incorrect contract shown in (a). Colors in (b) and (c) represent different activation patterns (linear regions) of the networks. (c) A learned DeLU network represents a discontinuous function and can well-approximate w", yiclding the optimal contract shown in (a).
both mechanism design [10 from a computational perspective, the contract design problem has only recently received attention and presented distinct computational challenges. For many combinatorial contract settings [6], the conventional approach based on linear programming becomes computationally infcasible and the problem of finding or even approximating the optimal contract becomes intractable [33 28 29).
36 and signalling 26
27 18 have been studied extensively
In addition, learning-theorett results give worst-case exponential sample complexity bounds for learning approximately-optime contract 40 55 As a result, there is growing demand for scalable, general purpose, and beyond- woost case approach for computing (near- (near-)optimal contracts.
We are thus motivated to initiate the study of deep learning for optimal contract design (deep contract design). This falls within the broader framework of differentiable economics, which seeks to leverage parameterized representations of differentiable functions for the purpose of optimal economic design [30]. In regard to learning contracts, recent work [40, 21, 55, considers the distinct setting of online learning for contract design with bandit feedback, characterizing regret bounds without appeal to deep learning.
A first innovation of this paper is to introduce a neural network architecture that can well-approximate the principal's 's utility function.
close examination of the geometry of the principal's utility function (Sec. 3 reveals its similarity to fully-connecterd feed-forward neural networks with ReLU activations II: both of them are piecewise affine functions [22]. However, whereas a ReLU network models continuous function, the principal's 's utility function is discontinuous at the boundary of linear regions, where the best response of the agent changes. Accurate approximation in the vicinity of boundaries is critical because an optimal contract is always located on the boundary (Lemma 3 in Sec. B but this is exactly where ReLU approximation error can be large. To handle this, we introduce the Discontinuous ReLU (DeLU) network, which recognizes that the linear regions of ReLU network are decided by activation patterns (the status of all activation units in the network), and conditions piecewise bias these activation patterns. In this way, each linear region has different bias parameter and can be discontinuous at the boundaries. Fig. Iillustratee the DeLU and its use to represent the principal's utility function, contrasting this with continuous ReLU function.
second innovation in this paper is to introduce a scalable inference technique that can find the contract that maximizes the network output (i.e., the principal's 's utility). We show that linear regions (pieces) of DeLU networks implicitly learn closed-form expressions for the incentive constraints of the agent and the utility maximization objective of the principal, so that we can use linear programming (LP) on each piece to find the global optimum. However, the time efficiency of this LP method is impeded by the overhead of solving individual LPs, and worsens with problem size in the absence of suitable parallel computing resources. To increase the computational efficiency, we develop a gradient-basse based inference algorithm based on the interior poritt method [49] that only requires few forward and backward passes of the DeLU network to find the contract that maximizes the network output. This method scales well large-scale problems and can be readily in parallel on GPUs.
The effectiveness of introducing piecewise discontinuity into neural networks demonstrated by our experimental results. The DeLU network well-approximates the principal's 's utility function even with

---

small number of training samples, and the inference method remains accurate and efficient as the problem size grows. By synergistically harnessing these two innovations, our method consistently finds near-optimal solutions on a wide range of contract design problems, significantly surpassing the capability of conventional continuous networks.
Related work. A longstanding challenge in the deep learning community has been to approximate discontinuous functions with neural networks. While the Universal Approximation Theorem guaran- lees the approximation of continuous functions, many problems involve discontinuity, including solar flare imaging [46] and problems coming from mathematics 24 However, establishing a network to represent discontinuous functions is not an easy task. Discontinuities were considered as early as in the 1950s, when Rosenblatt [50] introduced the perceptron model and its single-layer of step activation functions. Following this work, others modeled discontinuity through the use of different discontinuous activation functions 34
However, training these models is more challenging than the more typical models that make use of continuous activation functions [24], and this has hindered their application. To the best of our knowledge, this paper presents the first discontinuous network architecture with continuous activation functions and stable optimization performance.
There is vast and still-growing economies literature on contracts [see, e.g., 52 [5]
which the computational lens has recently been applied. In classic settings, computing the optimal contract is tractable by solving one LP per agent's is action, and taking the overall best solution [see, e.g., 32). However, LP becomes computationally infeasible for combinatorial contracts, including settings with exponentially-man -ann outcomes [33, actions (28] or agent combinations (29] Another issue with the L.- approach is that it requires complete information in regard to the problem facing the agent (its type). If the agent has a hidden type, this makes the optimal contract hard to compute [16 38 17). or otherwise complex [4. One way to deal with these complexities is to focus on simple contracts, in particular linear contracts (commission-
which are popular in practice [e.g.. 13 14.
A distinct but related approach combines contract design with learning, where efforts have con- centrated on online learning theory 440 21 55 3T.. These works show exponential lower bounds on the achievable regret for general contracts in worst-case settings, and sublinear regret bounds for linear contracts. Additionally, contracts have been studied from the perspective of agget reinforcement learning [48] 19 25]. The problem of strategic classification has also established a formal connection between strategy-aware classifiers and contracts 43
42 There is also interest
in the application of contract theory to the Al alignment problem 39 However, the use of learning methods for solving optimal contracts, as opposed to auctions 33 remains largely unexplored. This
gap in the literature can be partly attributed to the inherent complexity of finding optimal contracts, as the principal utility depends on the agent's s action, which must conform to incentive compatibility (IC) constraints that are not observable by the principal.
2 Preliminaries
Offline contract learning problem. The contract design problem is defined with elements C = (A, O,F.F. c. p. v), and involves single principal and single agent. The agent selects an action in the finite action space A. |A|=n. Action a leads to distribution p(-la) over the outcomes in O [O]=m, and incurs cost c(a) E T2 to the agent. The valuation of each outcome oj E O for the principal is decided by the value function v: O + Rzo. The principal sets up contract, f E F c 200 which influences the action selected by the agent. A contract f = f2, ... fm.) specifies the payment fy 2 0 made to the agent by the principal in the event of outcome oy. On receiving a contract f. the agent selects the action a (f) maximizing its utility 2a (f:
Eomp(-la) [f.] - -(a). For given action of the agent, the principal gets utility uP of(f:)) a) = Eo-p(-la) 1% fol. which is the principal's 's expected value minus payment. In the case that the induced action is the best response of the agent given the contract, we write uP uP()) = Ee-p(-la' ())) [to fo]. The goal in optimal contract design is to find the contract that maximizes the principal's utility without access to p(-la) and the action taken by the agent:
fd arg max uP (f) arg max Eorp(-la [vo fo].
f
ReLU piecewise-affing networks and activation patterns. A fully-connected neural network with piecewise linear activation function (e.g., ReLU and leaky ReI.U) and a linear output layer represents continuous piecewise affine function 55] 23 A piecewise affine function is defined as follows.
3

---

Definition 1 [Piecewise affine function]. A fimction g R + R is piecewise affine if there exists finite set of polytopes (D: such that - D; R. D. Dj Ø, and g is linear function Di D; + R when restricted to D. We call P; linear piece of g-
We now follow [22] and introduce some local properties of the piecewise affine function that is represented by ReLU network. Suppose there are L hidden layers in a network g. with sizes [ni, mi.,.... ,.p]. W
-u and b()) I are the weights and biases of layer I. Let vi = dd denote the input space dimension. We consider a ReLU network with one-dimensional outputs, and the output layer has weights W(++1) E Rlxa xaL and bias b(L+1) E R. With input a E IRd, we have the pre- and post-activation output of layer I: (x)) = ( + 6 and (x)) = a (x)). where a : + R is an activation function. In this paper, we consider ReLU activation (ax) = max(z, 0} B3 54]. but the proposed method can be extended other piecewise linear activation functions (e.g.. LeakyReI.U and PReLU [54]). For each hidden unit, the ReL.U activation status has two values, defined as when pre-activation h is positive and when is strictly negative. The activation pattern of the entire network is defined as follows.
Definition 2 [Activation Pattern].An An activation pattern of a ReLU network g with L hidden layers binary vector r (r(1).... r(]] {0, 1) "t, where r() is a layer activation pattern indicating activation status of each unit in layer L.
The activation pattern depends on the input æ, and we define function r Rd - f0, 13²:. "y that maps the input to the corresponding activation pattern. For a ReLU network, inputs that have the same activation pattern lie in a polytope, and the activation pattern determines the boundaries of this polytope. To see this, we can write the output of layer (x)). as
h (x) (h ((-1)(((((x))))
(wil-1) R (x))
(w (w
+b0011)) b
(2)
where k2()) is diagonal matrix with diagonal elements equal the layer activation pattern (((k) Eq. 2 indicates that, when r is fixed, (2) is a linear function h (z)))) ( + z(), where M
(!) [mE-] R(( (x) w and 2(1) = b + - (IT) w(++1-5) (( ((t), We
thus get Σ/= ny half-spaces, with the half-space corresponding to unit of layer defined as:
Tú, = {u E "
( (M. y + 2(²) 2 o).
where ((0 y + x is the output of unit i at layer L, and A is 1 if h ( (x) is positive, and is -1 otherwise. The input æ is in the polytope that defined by the intersection of these half-spaces: D(x)= = -t=...... O==1... (ei,... Tí,i. When restricted to D(x), the ReLU network is linear function: g(x)) W((+1) ((L) (x)) + (((+1),
(1)
Interior-point method for optimization problems with inequality constraints. For a minimization
problem with objective function q(æ) and incquality constraints p. > 0, = 1,... .M, the interior-point print method (53] introduces a logarithmic barrier function, ((x) log log(p (a))). and finds the minimizer of g(x) / (z(z), for some 0. This new objective function is defined on the set of strictly feasible points {œ)p (x) > 0, = 1,... ......,,, .M), and approximates the original objective as becomes large. Given this, we can solve for a series of optimization problems for increasing values of t. In the k-th round, {(k) is to n- {(k-1), where μ > 1 a constant, g(1)) is an initial value, and the problem is solved (c.g., by Newton initialized at (**-1) to yield (t). Assume that we solve the barrier problem exactly for each iterate, then to achieve a desired accuracy level of > O, we need Tbbariier = log(MM (tt e)) log(u) rounds of optimization.
3 Geometry of Optimal Contracts
In this section, we introduce some properties of the principal's utility function, u" : : R. which will motivate our method in Sec. 4 First, we show that u² is piecewise affine function.
Lemma 1. The principal's 's utility function u" is a piecewise affine function.

---

Proof. The principal utility depends on the agent action. For contracts in the intersection of the following n 1 half spaces that represent incentive compatibility constraints, the agent's 's action is a;:
Fig {f E F (a)p(()a.) [fo] c(a))= 2 Eo-p((aa) [fo] - c{a))} Vj t
(4)
Moreover, when agent action a; remains unchanged, u² changes linearly with f: an (f f:a:)
BuP( (f';a) (+)=== = alRo-p((-aa)) [vo so] + Pp (a.) [mo - [-] = Bompl-laa)) [vo - (afo + 35%)
u (af + 3f';;;;) Therefore, when restricted to the polytope Qi = Oizzi i.j. Vi, u² is linear.
Based Lemmal) I we define linear piece of function uP as μc, Q R. where Q, defines the set of contracts that motivates the agent to take action i. Lemma T can be easily extended to the agent's utility function u and the linear pieces of function w2 and u share the same set of domains (-:)- We define a linear piece of function u as n.f Qi - RR. We next observe:
Lemma 2. The principal's 's utility function u² can be discontinuous on the boundary of linear pieces.
The proof in Appx. Affollows the idea that the agent is indifferent between action a, and aj given a contract ff on the boundary of two neighboring linear pieces jtt and مس (f)= (f). However, the principal's utility equals the expected value minus the cost of an action minus u (f). As the expected value minus the cost can be different in nº₂ and uz wP can be discontinuous at f.
We then define the optimality a contract and analyze the structure of optimal contracts.
Definition 3 [Piecewise and Global Optimal Contracts]. A contract f 2, is piecewise optimal if
(f()) 2 u² (f), E Qi. A contract f is global optimal if u (f*) uf(f) F.
Lemma 3. The global optimal contract is on the boundary of a linear piece.
Lemma 3 can be proved by contradiction (as detailed in Appx. A if global optimal contract not on the boundary, we can always find a solution with greater principal utility. As analyzed in Sec. 4
Lemma B serves as a compelling rationale for introducing our discontinuous networks. Besides discontinuity, there is another network design consideration motivated by the following property.
Lemma 4. The principal's 's utility function uP can be written as a summation of concave function and a piecewise constant function.
The proof in Appx. A commences by establishing the convexity of function u" and subsequently formulating u as a function u". This property motivates us introduce concavity into our network design. In Appx. C we discuss how to achieve this by imposing non-ne negaaiiiyy constrains on network weights and analyze the impact of this design choice on the performance.
4 DeLU Neural Networks
Given the piecewise-affine geometry, the preceding analysis shows a close connection between the principal's utility function wP (Lemma and fully-connected ReLU networks (Sec. 2 However, ReLU functions are continuous and cannot represent the abrupt changes in u² at the boundaries of the lincar pieces. This lack of representational capacity is problematic because the optimal contracts on the boundary (Lemma B which is precisely where the ReLU approximation errors can be large. Consequently, ReLU networks are not well suited to deep contract design. In this section, we introduce the new Discontinuous ReLU (DeLU) network, which provides a discontinuity at boundaries between pieces, making it a suitable function approximator for the u² function.
4.1 Architecture
The DeLU network architecture supports different biases for different linear pieces. Since linear piece can be identified by the corresponding activation pattern, we propose to condition these piecewise biases activation patterns. Specifically, we learn DeLU network E: F RR (Fig. 2) to approximate the principal's 's utility function, mapping a contract to the corresponding utility of the principal. The first part of DeLU network is sub-network similar to a conventional ReLU network. This sub-network n has L fully-comnected hidden layers with ReLU activation and a weight matrix at the output layer, i.e., rj is parameterized as 0,, = (W11), ((1), ... W(L), b(2), W(L+1)), }. which includes weights and biases for L hidden layers and weights for the output ((L + 1))th) layer. The
5

---

XX
Output E
Algorithm 1 Parallel Gradient- Inference
W
Input: X (0) E IR xxm, DeLU network & with trained parameters; e; μ > 1; {(0;; a.
Baas c C
MSE Joss (6)
ReLU activation
Activation Pattern
for k E [1,..., log Loo (N/1 10 do log(R)
((k) = 11 (0);; X (k.0) < x(==1); /*aach round starts with the optimal solution the last round.*/ */ for j = 1, ... do
o a S ( 1
Layer
network
H M ( 2 faGet hidden layer
outputs in a single forward pass. */ T (A.-1)
ReLU activation
En, log A (1) H M"Barier term. */
dX ax (x-1)
W ((++)
R RL H
(k)-1)
100
w (1))
Layer 1
if | < 6 then CConverged at (1))+/
Input contract
( t (k---l) break; (To the next round"/
Dara flow in the
Data Dow
Gradient
else X ( (X (k-j-1 od /*Gradient ascent"/
bias network g
flow
end for end for
Figure 2: The DeLU architecture.
DeLU network is different from a conventional ReLU network at the bias of the output (last) layer (b(L+1)), and we introduce a new method to generate the last-layer biases.
Since there are no activation units at the output layer, given an input contract f. we can obtain the activation pattern r(f) by forward pass of the network up until the last layer. To condition b(4+1) on the activation pattern, we train another sub-network Ç [0, 1|= bias of the output layer. We use two-layer fully-connected network with Tanh activation to represent ( and denote its parameters as lz. In this way, contracts in the same linear piece of the DeLU network share the same bias value, enabling the network to express discontinuity at the boundaries while keeping other properties of network v unchanged. In Appx. B. we discuss why we adopt neural network, instead of a simpler function, to model the bias term.
R, that maps r(f) to the
4.2 Training and inference
The DeLU network &, including sub-networks 1) and Ç. is end-to-end differentiable. For training, we
randomly sample K contracts and the corresponding principal's utilities: Tx = {(fi, u² (f:)))
Feeding a training sample fi as input, we get an approximated principal's utility: E(f:: fyy 0x)
n[fr; f,)) + ((r(f)); fg)), and the network & is trained minimize the following loss function in T epochs (Appx. gives more details on network architecture, infrastructure, and training):
K
CTx (0,, =
1
Σ
IE(f;; 0c) - (
(5)
K
Given a trained DeLU network, E F F R. we have an approximation of the principal's 's utility function. The next step is to find contract that maximizes the learned utility function, that is f === arg max {(f). We call this the inference process. Since the function represented by DeLU network is discontinuous, conventional first- or second-order optimization methods are not applicable, and, formally, we need to develop a suitable optimization approach to solve
E(f") max max pf()) JED.
where A; : D, - R is linear piece of network &. This motivates to first find the piecewise optimal contracts and then get the global optimum by comparing the piecewise optima.
4.2.1 Linear programming based inference
A first approach finds the optimal contract for each piece using linear programming (LP). Contracts in the same linear piece p result in the same activation pattern r, and the DeLU network is linear function the piece. In particular, the optimization problem of finding the piecewise optimum is:
arg max W (1+1) ((4)
M (L) f + 2 20)
A (1) [M f + 2!") 2 o, VI E [4], i E [md],
s.t.

---

where [4] = (1. ,.), [nu] = {1, ... n. ). the objective is the linear function represented by the DeLU network on piece p. and the constraints require that the activation pattern remains The definitions of A,") R(L,, M and (x)) are the same in Sec. 2 but with the activation pattern fixed to r. We omit the last-layer bias in the objective because the activation pattern is fixed for this (a) DeL.U face and contour lines the barrier fianction one piece.
(b) Gradient-based inference
(e) Parallel inferenee
Figure 3: The gradient-based inference method for finding piecewise optima, illustrated the same instance as Fig. |
piece, and thus the bias is constant and does not influence the piecewise optimal solution.
For each LP, there are m decision variables, representing payments for m outcomes, and N = Et ny (the number of neurons) constraints. I.ss for each piece can be solved in polynomial time of m and N, and quickly in practice via the simplex method. However, a challenge is that there are 2 activation patterns For a DeLU network with moderate size, we enumerate all these pieces. For a larger DeLÜ network, we can approximate by collecting random contract samples and solving LPs with the corresponding activation patterns. Parallelizing these LPs may achieve better time efficiency. However, this improvement is limited by the overhead of solving a single LP and the required amount of suitable parallel computational resources. In the next section, introduce a gradient- based method that provides better efficiency in solving single problems and better parallelism through making use of GPUs. We compare these two inference methods in Sec. 5.1
4.2.2 Gradient-based inference
The gradient-based inference method based on the interior-point method (Sec. 2 and finds piecewise optimal solutions via forward and backward passes of the DeLU network. Specifically, each linear piece, P. we adopt the following barrier function:
1. log
(
= Σ
(M. A,00
f f ++x,0]]
1=1 1=1
At the k--th round, the objective function is
(f) = (1(+)) (L))
M f +1]0 + {(k) o(f).
(8)
We use gradient descent initialized at ((k-1), and update f with (gs(k) (f to find the minimizer. forward pass of the DeLU network gives (f) and backward pass is sufficient to calculate (e(()) (f)())())) (f)/Of. Since forward and backward passes are naturally parallelized in modern deep learning frameworks, this method can be parallelized by processing multiple f simultaneously. Alg. ggives the matrix-form expression of this parallel computation. The input X (0) E IR can be the training set or a random sample set, and we discuss the difference of these two settings in Appx.
Inference performance and boundary alignment degree. The performance of the proposed inference algorithms depends the DeLU approximation quality, especially the degree of alignment between the DeLU boundaries and the ground-truth linear piece boundaries. An interesting question is whether to think this is possible comes from observing that the MSE training loss (Eq. (5) is sensitive to misalignment between the DeL.U and true boundaries. In particular, given that the jump of the utility function at boundary points can be arbitrarily large, a slight misalignment between DeLU and true boundaries can lead large increase the MSE loss. Related this, we explore an extension of the gradient-based inference method to make it more robust to possible boundary misalignment. When
training setup can achieve a high boundary alignment degree. A reason
Previous research 20 found some patterns invalid, and there actually NN.
En (m)) pieces.
7

---

DeLU - Best Training Data
ReLU
-... Lincar Programming (Oracle, has access to unobservable informationn)
Outcomes 25
Outcomes
Outcomes 100
42-
80-
Optimality
Optimabity
Optinality
log(!! Actions)
log( Actions)
log(/ Actions)
Optimality (normalized principal utility) of DeLU, ReLU and a direct LP solver (Oracle LP), for problems with increasing sizes.
Figure 4:
annealing the coefficient of the barrier function, we can check whether the principal's utility increases for each (k)) value. A non-increasing utility indicates that we encounter inaccurate boundaries, and we can stop the inference to seek more robustness. We call inference with this "early stop" mechanism the sub-argmax gradient-basee inference method.
In Sec. 5.3 empirically evaluate the boundary alignment degree achieved by DeLU, and demon- strate that optr-optimal contract-design performance is closely associated with high boundary align- ment. We also show that the sub-argmax variation can improve performance of gradient-based inference, especially on tasks where the boundary alignment degree is low.
4.3 Illustrating DeL.Ubased contract design
We first illustrate the DeLU approach on a randomly generated contract design instance, in this case with 2 outcomes and 1,000 actions. In this instance, we sample the values for outcomes and costs for actions uniformly from [0. 10). The outcome distribution for an action is further generated by applying Sof tMax to Gaussian random vector in R In Fig. (a), we show the exact surface of the principal's utility function u² on such randomly generated instance. We observe that wP is discontinuous, piecewise affine function, where each piece corresponds to an action of the agent. In Fig. (b) and (c), we show the u² surface approximated by each ReLU and a DeLU network trained with 40K samples. These two networks have similar architecture, with single hidden layer of 8 ReLU units. The difference is the additional, last-layer biases of the DeLU network, which are dependent on activation patterns. Whereas the ReLU network cannot represent the discontinuity of w", and thus gives an incorrect optimal contract, the DeLU network replicates the u² surface, and gives accurate optimal contract (Fig- (a)). Another interesting observation is that the DeLU network may use multiple pieces to represent an original linear region (Fig. (c)). In Fig. 3 we further illustrate the inference process of the gradient-based method on this instance.
5 Empirical Evaluation
In this section, we design experiments to study the following aspects of DeL.U contract design: (1) Optimality (Sec. (.Ic. Can DeLU networks give solutions close to the optimal contracts? How do the solutions compare against those generated by continuous neural networks? (2) Sample efficiency (Sec. 5.T.: How many training samples are required for accurate DeLU approximation? Is the proposed method applicable to large-scale problems? (3) Time efficiency (Sec. (.2)): How does the computation overhead required for DeLU learning and inference compare those of other solvers? (4) Inference (Sec. (.2c. Does the gradient- inference method provide a good tradeoff between accuracy and time efficiency? (5) Boundary alignment degree (Sec. 5.3): How does the boundary alignment degree affect optimality?
Problem generation. Experiments are carried out on random synthetic examples. The outcome distributions p(-la) are generated by applying Sof tMax on a Gaussian random vector in IRm The outcome value vo is uniform on [0, 10). The action cost is mixture, c(a) (1 - B, c.-(a)) (a) + (a). where c, = axpllEo--((11l)) [v%] for scaling factor ap > is a correlated cost that is proportional to the expected value of the action, 6; (a) an independent cost and uniform on [0, 1]. and 9 controls the weight of the independent cost. We test different problem sizes by changing the number of outcomes m and actions n. For each problem size, we test various combinations of (app 3p) to consider the influence of correlation costs. Different methods compared on the same set of problems.

---

Time Efficiency
Opt. va. Best Iminn Data %
Largo-Scale Problems
(c) Limited Training Data
1130
LP Infor
Grad. Infer
200
res-
DeLU
Oncle
Optimality %
Time (5)
158-
42-
(n.m)
100
RoL.
48-
(5.
230
22-
(50, 52)
(168.128)
(199C
(100100)
logti Actions)
Problem size (9 outicomee, actions)
.Taining sumples
Figure 5: (a) DeLU training and inference time compared against Oracle LP. (b) DeLU performance on large-scale problems. (c) DeLU performance with small number of training samples.
DeLU (LP-B Inference)
DeLU Srradient-Based Inference)
DeLUU (Sub-argmax StrdieentBBsse Inference)
Outcomes 25
Oulcomes 50
Outcommes 100
100
Optimaling %
Optimality
Optimality
log(# Actions)
log(# Actions)
log(# Actions)
Figure 6: Comparing the optimality of the two inference methods for solving the global optimum given a learned DeLU network, considering increasing problem sizes.
5.1 Optimality and efficiency.
In Fig. we compare DeLU against ReLU networks as well as a baseline linear programming (LP) solver (Oracle e LP). Oracle LP refers to the use LP for directly solving the contract design problem, not for inference on trained DeLU network. It solves n LP problems, one for each action where the objective is maximize u" with the incentive compatibility (IC) constraints associated with the action a. The best of these n solutions becomes the optimal contract. Oracle LP has access to the outcome distributions (a) (to construct the IC constraints) that unobservable to the DeLU and ReIUU learners, but gives a benchmark for the optimality of the proposed method.
We test different problem sizes in Fig. Specifically, we set the number of outcomes to 25 (1st column), 50 (2nd column), and 100 (3 column) and increase the number of actions n from 2 to 28. For each problem size, 12 combinations of ap and 8p are tested, with (ap, Bp) E {0.5, 0.7, 0.9) x {0, 0.3, 0.6, 0.9]. The median performance as well as the first and third quartile (shaped area) of these 12 combinations are shown. When reporting optimality, achieved by DeLU/ReLU LP-based inference via dividing them by the value returned by Oracle LP. To ensure fair comparison, DeLU and ReLU networks have the same architecture, with one hidden layer of 32 hidden units. They are trained for 100 epochs with 50K random samples.
normalize the principal's 's utility
DeL.U consistently achieves better optimality than ReLU networks 2..2%% and the best contract in the training set (+23.84%) across all problem sizes. The performance gap is partieularly large for large-scale problems. For example, when the number of outcomes is larger than 1, 000 (Fig. 1gg.5pro (b)). the ReLU networks return solutions much worse (< 20%) than training samples, while DeLU can obtain solution at least 1.7 times better than the best training data. As for sample efficiency, as shown in Fig. (c), DeLU achieves near-optimality even with a very small training set.
5.2
Comparing the two DeLU inference methods.
In Fig. 6 we fix to 25, 50, 100 and increase from 2 to 2 to compare the optimality of the proposed inference methods. We again test the same 12 combinations of (ap,,3)). The median performance and the first and third quartile are shown for each problem size. Gradient-based inference is parallelized for 50K training samples on GPUs, while LP inference is parallelized for 5 linear pieces CPUs. We can see that LP inference consistently provides better solution, as the optimality of gradient- braddeent-based inference (-7.5%%) is limited by the number of gradient descent steps.
The advantage of gradient-based inference is its time efficiency. In Fig. 5 (a), we compare the inference time for different problem sizes (with m fixed to 25). Gradient-based inference saves around 50-90% overhead compared to LP inference. We also note that the DeLU training and

---

Opt. (LP intérence) %
Opt. (grad. infevence) %
Imppro iuprovementt ceneeneentt by sub aor--argmux
80
80
40
0,5
Boundary alignment degree %
Boundary alignment degree
Boundary alignment degree %
Figure 7: Correlation between boundary alignment degree (x-axis) and DeLU optimality (y-axis; left: LP-based inference; middle: gradient-based inference); also, the improvement achieved by sub-argmax inference compared to gradient-based inference (right). Trend lines (linear regression) shown. Point sizes (m)) indicate the corresponding problem size.
inference costs do not increase with the problem size. By comparison, the overhead of the direct LP solver grows quickly with the problem scale.
5.3 Boundary alignment degree and its influence on DeLU optimality
In Fig. we study the relationship between DeLU performance and the degree of boundary alignment.
For each contract design problem, we first calculate the boundary alignment degree achieved by the DeLU network. For this, we test large number (50K) of contracts, and check whether they are simultancously on the DeLU model and true utility boundary. Specifically, for each contract we randomly sample 10K directions and assess linearity of the DeLU utility model and the true utility function each direction. The principal's utility function is piecewise linear in the proximity of an interior point. Conversely, when point lies on a boundary, there is jump in utility within its proximity, rendering the utility unable to pass linearity test some direction. function is non-linear in >20% of random directions,
particular, if mark the contract sample as being boundary (we use the exact same approach to check for boundaries of the DeLU utility function and the principal's 'ss true utility function). The boundary alignment degree is calculated as the percentage of overlapped boundary points (# contract samples on both DeL.U and true boundaries # contract samples true boundaries).
Each point in Fig. represents a contract design problem, and use the same of problems as in the previous experiments. The x-axis is the DeLU boundary alignment degree, and the y-axis is the optimality of DeLU with LP-based inference (Fig. left) and gradient- based inference (Fig. middle). The right plot gives the optimality improvement achieved by the sub-argmax inference method compared standard gradient- based inference. From Fig. left, we observe that DeLU achieves good boundary alignment degrees (>80%) for most contract design problems, and that strong positive correlation exists between the boundary alignment degree and the optimality of LP- based inference. This result indicates that the alignment degree between DeL.U and true boundaries is important in supporting good performance of LP-besed inference. A similar observation can be made for gradient-based inference. Fig. riight shows that as the boundary alignment degree increases, the optimality improvement from the sub-argmax inference compared to standard gradient-based inference becomes less significant. This confirms that the sub- argmax inference is especially helpful for contract design problems where the DeLU boundaries are less accurate.
6 Closing Remarks
This paper initiates the investigation of contract design from deep learning perspective, introducing a family of piecewise discontinuous networks and inference techniques that are tailored for deep contract learning. In future work, it will be interesting to take this framework to real-world settings, provide theory in regard to the expressiveness of the function class comprising these piecewise discontinuous functions, and extend to the setting of online learning. We expect that our exploration of discontinuous networks can also draw attention to other economics problems involving discontinuity and thereby contribute to advancing Al progress in computational economics.
10

---

7 Acknowledgements
This work received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement: 101077862, project name ALGO- CONTRACT). We extend our heartfelt appreciation to the anonymous NeurIPS reviewers for their insightful questions and constructive interactions during the review process, which has inspired us to delve deeper into critical inquiries, such as the boundary alignment issue. Their feedback has been important in shaping the quality and depth of our work.
References
[1] Abien Fred Agarap. Deep learning using rectified linear units (ReI.U). arXiv preprini 2018.
[2] Marat Akhmet and Enes Yilmaz. Neural networks with discontinnnons/impaet activations. Springer, 2014.
[3] Tal Alon, Magdalen Dobson, Ariel D. Procaccia, Inbal Talgam-Cohen, and Jamie Tucker-Foltz. Multiagent evaluation mechanisms. AAAI 2020, pages 1774-1781, 2020.
[4] Tal Alon, Paul Dütting, Yingkai Li, and Inbal Talgam-Cohen. Bayesian analysis of linear contracts. EC 23, page 66. ACM, 2023.
[5] Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In ICLR 2018, 2018.
[6] Moshe Babaioff, Michal Feldman, Noam Nisan, and Eyal Winter. Combinatorial agency. Journal of Economic Theory, 147(3):99--1333 2012.
[7] Moshe Babaioff, Nicole Immorlica, Brendan Lucier, and S Matthew Weinberg. A simple and approximately optimal mechanism for an additive buyer. Journal of the ACM, 67(4):1-40, 2020.
[8] Patrick Bolton and Mathias Dewatripont. Contract theory. MIT press, 2004.
[9] Tilman Börgers, An introduction to the theory of mechanism design. Oxford University Press, USA, 2015.
[10] Yang Cai, Constantinos Daskalakis, and S Matthew Weinberg. An algorithmic characterization of multi-dimensional mechanisms. STOC 2012, pages 459-478, 2012.
[11) Yang Cai, Constantinos Daskalakis, and S Matthew Weinberg. Optimal multi-dimmensonal mechanism design: Reducing revenue welfare maximization. In FOCS 20/2, pages 130-139, 2012.
[12] Yang Cai, Nikhil Devanur, and Matthew Weinberg. A duality based unified approach to Bayesian mechanism design. In STOC 2016, pages 939-939, 2016.
[13] Gabriel Carroll. Robustness and linear contracts. American Economic Review, 105(2):536-63, 2015.
[14] Gabriel Carroll. Robustness in mechanism design and contracting. Annual Review of Economics, 11:139-166, 2019.
[15] Gabriel Carroll. Contract theory. In Federico Echenique, Nicole Immorlica, and Vijay V. Vazirani, editors, Online and Matching-Basel Market Design. Cambridge University Press, 2022. To appear.
[16] Mattco Castiglioni, Alberto Marchesi, and Nicola Gatti. Bayesian agency: Linear versus tractable contracts. Artificial Intelligence, 307: 307:103684, 2022.
[17] Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Designing menus of contracts effi- ciently: The power of randomization. In EC 2022, pages 705-735, 2022.

---

[18] Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Ehsan Emamjomeh-Zadee Zadeh, Li Han, and Shang- Hua Teng. Mixture selection, mechanism design, and signaling. In FOCS 2015, pages 1426-144 1445, 2015.
[19] Phillip J.K. Christoffersen, Andreas A. Haupt, and Dylan Hadeilld-Menell. Get it in writing: Formal contracts mitigate social dilemmas in multi-agent RL. In AAMAS 2023, page 448-456, 2023.
[20] Lingyang Chu, Xia Hu, Juhua Hu, Lanjun Wang, and Jian Pei. Exact and consistent inter- pretation for piecewise linear neural networks: closed form solution. In KDD 2018, pages 1244 1253, 2018.
[21] Alon Cohen, Argyrios Deligkas, and Moran Koren. Learning approximately optimal contracts. In SAGT 2022, pages 331-346, 2022.
[22] Francesco Croce, Maksym Andriushchenko, and Matthias Hein. Provable robustness of ReL.U
networks via maximization of linear regions. In AISTATS 20/9, pages 2057-2066, 2019.
[23] Francesco Croce and Matthias Hein. A randomized gradient-free attack on ReLU networks. In GCPR 2019, pages 215-227, 2019.
[24] Francesco Della Santa and Sandra Pieraccini. Discontinuous neural networks and discontinuity learning. Journal of Computational and Applied Mathematics, 419:1 14678, 2023.
[25] Heng Dong, Tonghan Wang. Jiayuan Liu, Chi Han, and Chongjie Zhang. Birds of feather flock together: A close look at cooperation emergence via multi-agent rl. arXiv preprint arXiv:21044 1455, 2021.
[26] Shaddin Dughmi. On the hardness of signaling. In FOCS 2014, pages 354-363, 2014.
[27] Shaddin Dughmi and Haifeng Xu. Algorithmic Bayesian persuasion. STOC 2016, pages $12-425, 2016.
[28) Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Combinatorial contracts.
In FOCS 2021, pages 815-826, 2022.
[29] Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Multi-agent contracts. In STOC 2023, pages 1311-1322 2023.
[30] Paul Dütting, Zhe Feng, Harikrishna Narasimhan, David C. Parkes, and Sai Srivatsa Ravin- dranath. Optimal auctions through deep learning: Advances in differentiable economics. Journal of the ACM, Forthcoming 2023. First version, ICML 2019, pages 1706-1715. PMLR, 2019.
[31] Paul Dütting, Guru Guruganesh, Jon Schneider, and Joshua Ruizhi Wang. Optimal no-regret learning for one-sided Lipschitz functions. JCML 2023, volume 202, pages 8836- PMLR, 2023.
[32] Paul Dütting, Tim Roughgarden, and Inbal "Talgam-Cohen. Simple versus optimal contracts. In EC 2019, pages 369-387, 2019,
[33] Paul Dütting, Tim Roughgarden, and Inbal Talgam-Cohen. The complexity of contracts. SIAM Journal on Computing, 50(1):21 1-254, 2021.
[34] Mauro Forti and Paolo Nistri. Global convergence of neural networks with discontinuous neuron activations. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications. 50(11):1421-1433 2003.
[35] Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep sparse rectifier neural networks, In AISTATS 20 pages 315-323, 2011.
[36] Yannai A Gonczarowski. Bounding the menu-size of approximately optimal auctions via optimal-transpont duality. STOC 2018, pages 123-131, 2018.
[37] Yannai Gonezarowski and Matthew Weinberg. The sample complexity of up-to-s multi- dimensional revenue maximization. Journal of the ACM, 68(3):1-28, 2021.
12

---

[38] Guru Guruganesh, Jon Schneider, and Joshua R Wang. Contracts under moral hazard and adverse selection. In EC 2021, pages 563-582, 2021.
[39] Dylan Hadfield-Menell and Gillian K. Hadfield. Incomplete contracting and Al alignment. In ATES 2023, pages 417-422, 2019.
[40] Chien-Ju Ho, Aleksandrs Slivkins, and Jennifer Wortman Vaughan. Adaptive contract design for crowdsourcing markets: Bandit algorithms for repeated principal-agem problems. Journal of Artificial Intelligence Research, 55:317-359, 2016.
[41] Emir Kamenica and Matthew Gentzkow. Bayesian persuasion. American Economic Review, 101(6):550-26115, 2011.
[42] Jon Kleinberg and Manish Raghavan. Algorithmic classification and strategic effort. ACM SIGecom Exchanges, 18(2):55-52, 2020.
[43] Jon M. Kleinberg and Manish Raghavan. How do classifiers induce agents to invest effort strategically? ACM Transactions Economics and Computation, 8(4):19:1-19:23, 2020.
[44] Xiaoyang Liu and Jinde Cao. Robust state estimation for neural networks with discontinuous activations. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 40(6):1425-1444 2010.
[45] David Martimort and Jean-Jacques Laffont. The theory of incentives: The principal-agent model. Princeton University Press, 2009.
[46] Paolo Massa, Sara Garbarino, and Federico Benvenuto. Approximation of discontinuous inverse operators with neural networks. Inverse Problems, 38(10)100001, 2022.
[47] Stuart Mitchell, Michael OSullivan, and lain Dunning. Pulp: linear programming toolkit for python. The University Auckland, Auckland, New Zealand, 65, 2011.
[48] Tong Mu, Stephan Zheng, and Alexander Trott. Solving dynamic principal- agent problems with a rationally inattentive principal. arXiv preprint arXiv:2202.01691, 2022.
[49] Florian A Potra and Stephen Wright. Interior-point methods. Journal of Computational and Applied Mathematics, 124(1-2):28 1--022 2000.
[50] Frank Rosenblatt. The perceptron: probabilistic model for information storage and organiza- tion in the brain. Psychological review, 65(6):386, 1958.
[51] Royal Swedish Academy of Sciences. Scientific background on the 2016 Nobel Prize in Economic Sciences, 2016.
[52] Bernard Salanie. The Economics of Contracts: Primer. MIT press, 2017.
[53] Stephen J Wright. On the convergence of the Newton/log-baris method. Mathematical Programming, 90:71-100, 2001.
[54] Bing Xu, Naiyan Wang, Tianqi Chen, and Mu Li. Empirical evaluation of rectified activations in convolutional network. arXiv preprint arXiv: arXiv: 11.55.000553. 2015.
[55] Banghua Zhu, Stephen Bates, Zhuoran Yang, Yixin Wang, Jiantao Jiao, and Michael I. Jordan. The sample complexity of online contract design. EC 23, page 1188. ACM, 2023.
13

---

A Proofs of Lemma 2/4
In Sec. 3] we study the geometric structure of optimal contracts by establishing four lemmas. While some of them have been stated and proved for linear contracts [2]. and the first two lemmas, at least, are not surprising, we give formal proofs of these properties of the principal's 's utility and optimal
contracts in the general case. An important property of the principal's 's utility function u that we state in Lemma iis that u² can be discontinuous function.
Lemma 2. The principal's 's utility function uP can be discontinuous on the boundary of linear pieces.
Proof. For a contract f on the boundary of two neighboring linear pieces nb and 1' the agent is indifferent between action a; and aj given f: (f) = (f). The principal's utility
(f)
Bo [22 E 1o)p((le))(oo)
(9)
Buwp(-la [b0 - c(a,) (Bo-p(las c((a))
(10)
Buwp(-)as) Hol - c(as) (f)
(11)
Bomp(tHas) [Mo] - d(as) (f)
(12)
=1g(f) Bo-p(-a))) [vo] - c(as) (Bowp((ay))oo) - c(az)). -((a)))
(13)
is possible that
Ea-((la) [vo] - c(ai) # Ea -(a)).
(14)
Function wl is discontinuous in this case.
Another property of the principal's utility function w² that motivates our discontinuous neural networks is Lemma 3
Lemma 3. The global optimal contract is on the boundury of a linear piece.
Proof. Suppose that the global optimal f is not on a boundary but is an interior point of linear piece Qi (contracts in Q encourage the agent to take action a:.):
f" E Q - -Q..
(15)
where
Q Nigil ii
(16)
Tij {s F FFIBoopplaa [Sa] - -daa)= 2 Eo-p(laa [so] caa))) Vij ii.
(17)
It follows that
f E Bo-n( (as) [fo] - c(as) > Eo-p( (ay) [fol - -((a)), vj # where the inequality strict. Let It holds that e,, > 0, 0, # i.
(18)
Cjj Bo-n(-las) las) 1fo] c(ai) - (osp(( + cca,))
(19)
Now consider the contract f = - for some small 8 > 0. For any aj # a, we have
wd az) u af';
-Eor 1550 8p(o) c(a,) Bomp(-lay) lay) Ifo Sp(ola:)] + c(a,)
(20)
SE BBap(())) [p(o|a:)] S.app()))) [p[ola:)].
=E,
When
0 <<b 8 < min
(21)
3 Eamp(-la.) [p(ola:)] E Bomp(-lay) [p(o|a,)]
(where note the denominator is 0), we have
" af): - u (f':aj))> > 0. +i,
(22)
14

---

which means f' incentivizes the agent to take action Therefore, for in this range, the principal's utility given f' is:
up uf(')) = 1oo) [vo fo + óp(ola;)
Bo [Vo fol + Bowp()aas) [ōp(ola,)]
(23)
= -f(")) + Σ (ola;)
> (f()))
We thus find contract f' that induces greater utility for the principal, contradicting with the fact that S is the global optimal contract. This finishes the proof.
Note that here consider the boundary resulting from changes in the agent's 's best responses. We can extend the proof to cover another type of boundary, which pertains to the requirement that contracts non-negative, by defining Q, be 2i (flf 0} n
2 114+ n....
Lemma 4 claimms another property that may influence the design of DeLU networks.
Lemma 4. The principal's 's utility function u" can be written as a summation of a concave function and a piecewise constant function.
Proof. We first prove the agent's 's utility function (f) a convex function.
need prove that, for any two contracts (() E F and f E F, holds that (A + (1
S 22)
(f)( + (1 (f(2)) AA [0, 1]. Denote d f(2) f()), It suffices to prove
that the derivative of w² (f( + öd) with respect to ö non-decreasing function for d E [0, 1].
We have
06 n" (f()) + 5d)
Bomp(-las) + 5do] - c(as)] a5
(24)
where as is the agent's 's action given the contract (() 5d.
Case 1: When as does not change,
08 u (f(1) + od) Bowpttlaa)
(25)
a constant, which non-decreasing function.
Case 2: When changes. Suppose that there exists d1 E [0, 1] such that f()) + d,d is on the boundary of linear piece Q; and 2j. Let
8t = 81 +
8 = 81
(26)
where e is a small number and
(() + 87 d Qn, ( + 5 d E 2j-
(27)
Because the agent is self-interested, it follows that aj is the best response when the contract is f()) + 6, d:
a ((()))) + 8+td (1(( o7 d: > u u(((() + 5 d;a))
(28)
It follows that
(1() + 8 d) ua (f(1) + ,,d)
u (f(1) + dd)
lim c00
(29)
06
6=6
lim (1 + 8t di as) - n ( + 6
(30)
15

---

We now look at the two terms in the numerator of Eq. 30
u (f()()) + d: a,) = (x-p(-(a,) 1/ + 87 do) d(a)
(31)
(owp(-la.) [8 + (òi + e)do] - c(ai)
(32)
Boup(-tai) (f0 6 c(ai) + + eBBonp(-aa)
(33)
w² (((())) (jdd + < p.pl (dob,
(34)
and
u'( + +jjd) El a, (5( t caa))
(35)
(a)p() (5( + (6] + e)dol - c(a:)
(36)
Bo-p(-le.) (6(0)) 07 do] c(a;) + e eBooo(((aa)
(37)
u² (f(())) + oj d) + cBoop((la))
(38)
Therefore,
0
u² (f(((1) 87 a;) - +
u (f(l)) 8d)
> lim c1+
06
6=6
e
ut (f(())) + +did) (f(()) + 0. 0
lim +
(39)
u (f + od)
a8
6==
This finishes the proof that u" is convex function. Furthermore, we have that
v (f) - (f) (f)
c(aa (f))
(1))
(40)
where (f) is a concave function and aa (f)) + la (f) is piecewise constant function with the value -c(a;) + (omp((le)) when f Q
B Why we use another network to generate the last-layer bias?
To model model the dependency of the last-layer bias the activation pattern, network, rather than simpler, linear, and learnable function. The reason that the bias does not always depend linearly the activation pattern. Here is example to illustrate this. There are two outcomes with values v = [20, 1]. four actions with costs c = [1.0, 2.1, 2.3, 4.7], and the action-outcome transition kernel is
neural
00.211
0.7897
0.398
0.602
P
0.430
0.570
0.684
0.316
Suppose we consider linear contracts, where av, > different contracts is:
Then the principal's utility function for
5a
0.2 < 0.3
8.57a + 8.57
0.3 < a < 0.4
ua(a)
9.17a 9.17
0.4 0.5
14a 14
a>0.5
Suppose that we have a a 2-dimensional activation pattern, and the linear function converting activation patterns the bias has parameters [b2, b2]. Then the bias for each the four pieces would 0, b, 62- and b + by, respectively. The difference between each piece's 's bias needs to model the discontinuity contract parameter
0.3, 0.4, 0.5, but this is impossible with this linear model. To see this, first assume that the piece 0.2 < a < 0.3 has bias 0. Then the differences of biases of the other pieces would need to be 2.5, 2.86, and 5.28, which cannot achieved with b,, b2, and by + b2. can be easily verified that the cases where other pieces have bias of 0 are similar, demonstrating that a linear bias function cannot express the discontinuity. By contrast, appealing second network allows for non-ling lonelr dependency activation, and can handle this problem.
16

---

Linear Prggammiin
Delli Inference Time Actions
Cancave DeUU Inference Time
Actions 50
Outcomes a
Outcomes
100
100
100
100
Optimlity
Optmmalty
50
50
50
30
laggl
logd
Outcomes
Time On secondo
200
Time Sec0nd0
1500
limal Un saccesda
2000
Time Cif SociaIAk
1000
100
2000
500
1ag2le Outcomes)
log OuEcomee)
Augu Actions]
1ogg Actions)
Figure 8: Optimality (normalized principal utility, divided by the result obtained by the direct LP solver Oracle LP) and inference time of Del.U, Concave DeLU, and Oracle LP on increasing problem sizes.
C Introducing Concavity into the DeLU Network
From Lemma the principal's utility function w² is a summation of concave function and piecewise constant function. Further, our DeL.U network, which is used to approximate the function w², can be written as
E(1;; + ((r(f)):
(41)
In particular, ((r(f:); 0c) is piecewise constant function, because given an activation pattern r r(f.). Ç constant. However, the first term in Eq. [4]] function. This raises the question as to whether it is useful to further restrict the network architecture, constraining the sub-network 7) to be concave function. In this section, discuss how introduce concavity into n, and how this restriction affects the performance of DeLU-based contract design.
general DeLU network, an arbitrary
C.1 Concave DeLU architecture
We can make 17 a concave function by (1) enforcing its weights (for all but the first layer) to be non-negative, and (2) taking the negation of its output. The first modification will make a convex function because 17 uses ReLU activation, which is a convex and non-decreasing function. When the weights after a ReLU activation are non-negative, 1) becomes a composition of several convex, non-decreasing functions, which still a convex function. Since the negation of convex function is a concave function, the second modification will make 77 concave.
Formally, in Concave DeLU, the sub-netwond 77 calculates
h (4) (z))) (() R (-. ( (W (W() (x) (w + (w())+ + +b(1)....) b(4)
7(x)) ((+1)) R(U
(42)
where (²() is diagonal matrix with diagonal elements equal to the layer activation pattern (+)) The other components, as well as the training process, of Concave DeLU are the same as DeLU network. In the next sub-section, evaluate the performance of Concave DeLU.
C.2 Experiments on Concave DeLU networks
In Fig. we compare Concave DeLU against DeLU and the direct LP solver (Oracle LP). For this, we fix DeLU and Concave DeLU to have the same size, and both use the LP inference algorithm. We test different problem sizes. the first and second column, we set the number of actions respectively, and increase the number of outcomes from 2 to 28, In the third and fourth column, we set the number of outcomes m to 5 and 50, respectively, and increase the number of actions n from 2 to 28, For each problem size, the same 12 combinations of a, and 3, tested. The median
5 and 50,
17

---

performance as well as the first and third quartile (shaped area) of these 12 combinations are shown. The first row compares optimality, while the second row compares inference time efficiency. We again report normalized principal utilities when it comes to optimality.
surprising result is that for most problem sizes, DeLU achieves better optimality than Concave DeLU. Although the function class represented by Concave DeLU is a better fit with w², it seems that the larger function class of DeLU aids optimization and leads better performance. At the same time, it is somewhat surprising that Concave DeLU can reduce inference time substantially. Unlike DeLU, the inference time of Concave DeLU remains relatively stable when the problem size increases. We conjecture that this behavior can be attributed to the non-negativity constraint on network weights, which reduces the number of valid activation patterns and speeds up LP inference.
D Experimental Setups
D.1 Network architecture and training
We use simple architecture for the DeLU network. In all experiments, the sub-network v) has one hidden layer with 32 hidden units and ReLU activations. We deliberately restrict the size of this sub- network to limit the number of valid activation patterns and speedup LP-based inference. However, this restriction may reduce the representational capacity of DeLU networks: it is in contrast to the common practice of overparameterization which has contributed the success of deep learning. To alleviate this concern, we employ a relatively larger network for the bias network Ç. In our experiments, has a hidden layer with 512 (Tanh-activated) neurons.
The two sub-networks and are trained in an end-to-end manner by the MSE loss (Eq. 5). The optimization is conducted using RMSprop with learning rate of 1 x 10-3, of 0.99, and with no momentum or weight decay. For the DeLU and the baseline ReLU networks, training samples are randomly shuffled in each of the training epochs.
D.2 Infrastructure
Across all experiments, DeLU, and the baseline ReLU networks are trained on a NVIDIA A100 GPU. Gradient-based inference is also parallelized on the A100 GPU. The direct LP solver (Oracle LP) and the LP-baaed inference algorithm are based on the linear programming toolkit PuLP [7]. and we parallelize five LP solvers CPUs.
E More Experiments
In this section, we carry out experiments to study (1) using random samples to initialize gradient- based inference (Appx. E. and (2) the influence of cost correlation the optimality of DeLU learners (Appx.
E.1
inference initialized with random samples
In Sec. 4.2.2. we introduce a gradient-based inference algorithm, and Alg. ggiees the matrix-form expression its parallel implementation. There a choice in using Alg. I as whether the input ("probe points") (0) E I Kxm is taken from the training set or different, random sample set. In this section, we report the results of experiments to empirically compare these two setups.
We start from the same trained DeLU networks on small (n and large (n = 50, m = 128) problem sizes, where n is the number of actions and m is the number of outcomes. For each problem size, consider 12 different combinations of (ap,
16), middle (n 32, m 50),
in other experiments and report the mean and variance of the performance. We run Alg. [ with two different inputs ((); Training Set uses 50K training samples while Random Set uses 50K randomly generated contracts. In Table. [ present the normalized principal utility (divided by the result obtained by Oracle LP) of these two setups.
We can observe that the optimality of these two setups are very close, especially when the problem size is large. We thus recommend running Alg. Minitialized with the training set reduce the possible time and memory overhead of generating new random sample set.
18

---

Table Optimality (normalized principal utility %) of two setups of gradient- based inference: using the training set (Training Set) a random sample set (Random Set) input X of Alg. Mean and variance over 12 different combinations of (ap, Sp) are shown. In this table, the problem size is defined by (n, m), where is the number of actions and m is the number of outcomes.
Problem size (n, m)
Training Set
Random Set
(5, 16)
95.29 + 0.20
95.33 + 0.19
(32, 50)
88.43 + 0.97
88.46 0.98
(50, 128)
94.28 + 0.02
94.28 + 0.02
Table 2: Optimality (normalized principal utilities %) of DeLU networks under different combinations of (Op, Sp). Mean and variance over 32 problem sizes shown.
Op = 0.5
Qp 0.7
Ap 0.9
8, 0.0
88.79
87.20=11.97 19.67
3, = 0.3
11.94=11.16
93.28
83.44=13:45
S. = 0.6
95.22+7.93
95.08=18.78
91.97=10.32
P = 0.9
6..23+6.62
90.69
96.43+7.45
E.2 Influence of correlated costs
Across our experiments, we test 12 different combinations of Opp and 3p. where (pp.8p) E (0.5, 0.7, 0.9) x {0, 0.3, 0.6, 0.9}. Recall that greater 3p value means put weights on the independent cost, and greater ap value indicates that the correlated cost more close to the expected value of the action. It is interesting investigate the influence of these two parameters on the performance of DeLU contract designers.
In Table we show the optimality of DeLU learners (using the LP inference algorithm) under different ap and 3, values. For each (ap. 3p) combination, we test 24 different problem sizes: (m.n) {25, 50, 100} x {2, 8, 16, 32, 64, 128, 256}. We give the median and standard deviation of these 24 instances. We observe that 3p exerts influence on the performance of DeLU networks: optimality of the learned contracts generally increases for greater values of 3p,, whatever the value of 0g. and we see that DeLU seems better suited to handle problems in which the costs of actions relatively independent of the expected values of actions. This claim is also supported by the results regarding Opp, where the optimality under ap 0.5 is typically better than those under other Op values for most 3, values. will be interesting future work further study this phenomenon, and to see whether suitable modifications can be made to the DeLU architecture to further improve optimality in regimes with higher cost correlation.
19


Reviews:
[{"review_id": "J5JKWrj78s", "reviewer": "Reviewer_z4Vn", "summary": "This paper introduces an automated optimal contract design method from offline data using deep learning. In this setting, a principle deigns a contract establishing an agreement of payments the principle will undertake for the outcomes arising from the actions of an agent. Given a contract, the agent privately selects an action to maximize its expected utility under an action-outcome transition kernel. The principle, unaware of the agent's actions and the transition kernel, aims to maximize its own expected utility. The authors propose the use of neural network function approximation to learn the principle's utility function from offline samples. Due to piecewise discontinuous nature of the principle's utility function and the continuous nature of existing neural network (eg. ReLU), the authors propose the Discontinuous ReLU (DeLU) network to model the the principle's utility function as a discontinuous piecewise affine function, where each piece represents a particular action taken by the agent. Moreover, the authors present a computationally efficient inference method for contract designing based on interior-point method. Finally, the paper empirically evaluates the validity and the performance of the methods presented here on synthetic data. ", "questions": "I have some question to the authors out of curiosity.\n1) How easy is it to extend your method to contract with mixed payment-penalty structure (ie. negative values for f)?\n2) Is there a sequential version of contract design problem with cumulative utility maximization? I am thinking of a case where the principle also is deemed responsible of its actions in the contract design and there is a dynamics interaction between the agent and the principle.\n3) Is there a specific reason to pick a mother neural network to models the bias term? It'd be more straightforward to write the bias term  as a linear function of activation pattern $ b^{L+1}(\\mathbf{f}) = \\sum_{l=1}^{L} \\mathbf{r_l(\\mathbf {f})}^T \\mathbf{b}_l $.\n4) What are some real world applications where the the offline learning with previously collected data could be feasible and reasonable? Are these type of data readily available in practice?\n5) Does it require a significantly new treatment to extend this to multi-agent (single principle) case?", "limitations": "Limitations, societal considerations and future works are all discussed.", "rating": 9, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1) Originality:\nNoting that I am not quite familiar with this field, this is the first ever use of neural network learning of utility functions for contract design based on the author's claims. The authors not only combine two existing ideas, but also innovate a new neural network architecture as the existing models are not capable of capturing the critical discontinuities in the utility function. Moreover, they propose an efficient implementation of the inference computations by utilizing highly parallelized existing deep learning frameworks. They also propose an alternative concave neural network architecture. \n\n2) Quality\nThe claims made here were supported by sound theoretical and empirical evidence. \n\n3) Clarity \nEven though I am out of the field, it was very easy to follow the paper. The problem and its motivation are explained very clearly. The theory and the experimental results are stated neatly and discussed properly. It was a pleasure to read this paper.\n\n4) Significance\nAgain, since this is outside my expertise, it is less obvious to me why this problem should be studied. The examples provided by the authors as well as a quick Google search were helpful to clarify this. Aside from the real-world significance, the proposed DeLU network and its concave counterpart are novel and worthy of studying further. \n\n", "weaknesses": "I don't have much to say here. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the thought-provoking review, which prompts us to think deeper about the applicability and extension of our work.\n\n> (Q1) _`How easy is it to extend your method to contracts with mixed payment-penalty structure?`_\n\nFor this, we can consider the case $\\mathbf{f}\\ge-c$, for a positive constant $c$  (with no limitation on how much the agent can pay the principal, there is a trivial optimal solution, charging the agent the entire expected social welfare). Everything then goes through immediately, with contracts sampled $\\mathbf{f}\\ge-c$, and the non-negativity constraints in the inference replaced with $\\mathbf{f}\\ge-c$.\n\n&nbsp;\n> (Q2) _`Is there a sequential version of the contract design problem with cumulative utility maximization?`_\n\nThis is an interesting direction, and sequential versions of the contract design problem are a classic topic in the economics literature; e.g., the seminal paper [1], see also [2]. Studying these models from a computational direction is an interesting direction for future work.\n\nIn the future, if (deep) (multi-agent) reinforcement learning is explored to study more comprehensive or larger scale sequential problems, we believe the proposed DeLU architecture can contribute by approximating the Q function to estimate the long-term value the principal can expect with a contract. Such a Q function is discontinuous, with the agent's response a sequence of discrete actions.\n\n[1] Holmstrom, B. and Milgrom, P., 1987. Aggregation and linearity in the provision of intertemporal incentives. Econometrica, pp.303-328.\n\n[2] Zhang, H. and Zenios, S., 2008. A dynamic principal-agent model with hidden information: Sequential optimality through truthful state revelation. Operations Research, 56(3), pp.681-696.\n\n&nbsp;\n> (Q3) `Is there a specific reason to pick a mother neural network, instead of a linear function, to model the bias term?`\n\nThe reason for using a second network is that the bias does not always depend linearly on the activation pattern. Here is an example to illustrate this. There are two outcomes with values $\\mathbf{v}=[20,1]$,  four actions with costs $\\mathbf{c}=[1.0,2.1,2.3,4.7]$, and the action-outcome transition kernel is$$P=\\begin{bmatrix}0.211&0.789\\\\\\\\0.398&0.602\\\\\\\\0.430&0.570\\\\\\\\0.684&0.316\\end{bmatrix}.$$\nSuppose we consider linear contracts, where $\\mathbf{f}=\\alpha\\mathbf{v},\\alpha>0$. Then the principal's utility function for different contracts is$$u^p(\\alpha)=\\begin{cases}-5\\alpha+5&0.2<\\alpha<0.3\\\\\\\\-8.57\\alpha+8.57&0.3<\\alpha<0.4\\\\\\\\-9.17\\alpha+9.17&0.4<\\alpha<0.5\\\\\\\\-14\\alpha+14&\\alpha>0.5\\\\\\\\ \\end{cases}.$$Suppose that we have a 2-dimensional activation pattern, and the linear function converting activation patterns to the bias has parameters $[b_1,b_2]$. Then the bias for each of the four pieces would be $0$, $b_1$, $b_2$, and $b_1+b_2$, respectively. The difference between each piece's bias needs to model the discontinuity at contract parameter $\\alpha=0.3,0.4,0.5$, but this is impossible with this linear model. To see this, we first assume that the piece $0.2<\\alpha<0.3$ has bias 0. Then the differences of biases of the other 3 pieces would need to be 2.5, 2.86, and 5.28, which cannot be achieved with $b_1$, $b_2$, and $b_1+b_2$. It can be easily verified that the cases where other pieces have a bias of 0 are similar, demonstrating that a linear bias function cannot express the discontinuity. By contrast, appealing to a second network allows for non-linear dependency on activation, and can handle this problem.\n\n&nbsp;\n> (Q4) _`What are some real world applications where offline learning with previously collected data could be feasible and reasonable? Are these type of data readily available in practice?`_\n\nFirst of all, an application that motivates us is that of developing a tool for theoretical economists to study contract design. In economic theory, one typically assumes a model of a world environment (e.g., actions, technology, costs, rewards, outcomes), and looks to understand the optimal designs. In this setting, offline data is reasonable because we have a model of the world.\n\nIn regard to real-world, practical applications:\n\n(1) One application comes from the _digital economy_, where we can expect to gain access to training sets as we see increasing automation of economic processes (e.g., it doesn't seem too unlikely that we will soon have contracts for LLM-style actors, for example working to plan the details of a vacation for a user with the possibility of contracting on outcomes) [3].\n\n(2) Another application comes from settings where we can expect to have access to a simulator of the behavior of  agents. In particular, a black-box simulator fits perfectly  with our set-up, where we only need access to the induced utility to the principal for different contract designs. These simulations may be for automated agents in the digital economy. Another interesting development is that attention is going these days to generative models as simulators of _human decision making and behavior_ (and in the future, likely firm behavior) [4].\n\nAs these models are developed, methods to optimize on top of them will become important, and we expect our method to be useful in regard to contract design.\n\n[3] Horton, J.J., 2023. Large language models as simulated economic agents: What can we learn from homo silicus? (No. w31122). National Bureau of Economic Research\n\n[4] Park, J.S., O'Brien, J.C., Cai, C.J., Morris, M.R., Liang, P. and Bernstein, M.S., 2023. Generative agents: Interactive simulacra of human behavior. arXiv:2304.03442\n\n&nbsp;\n> (Q5) _`Does it require a significantly new treatment to extend this to multi-agent (single principal) case?`_\n\nNot a significantly new treatment, as long as we have access to the behavior model of the system of agents. This would need to resolve, for example, a question in regard to computing or observing equilibrium behavior, perhaps also involving tie-breaking across multiple possible equilibria."}, {"review_id": "RT6sJe6xwM", "reviewer": "Reviewer_aB6m", "summary": "This paper proposes a deep-learning approach for contract design. The rationale is:\n- the principal's utility function should be learned from the data \n- the problem of approximating accurately the utility function is non-trivial, and the utility function may be discontinuous --- suggesting the development of better models such as those proposed in the paper\n\nIn addition to the model approximation problem, the authors improve the available algorithms for training and inference. Finally, the authors experimentally evaluate their paradigm according to several dimensions.", "questions": "*Technicalities*\n- are the techniques for training and inference provided by the authors important advancements (i.e., non-trivial, non-direct) of the deep learning techniques? if yes, why and how\n\n*Applicability*\n- is correct my understanding that several thousands of samples are necessary for training? if yes, do you believe that making thousands of queries to the principal is reasonable (using $10^6$ in the plot does not help and I would suggest the authors use semi-log plots to show what happens with a small number of samples).\n", "limitations": "Not applicable.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors clearly posed the problem and the presentation is clear. ", "weaknesses": "At the current stage, I have some doubts about the significance of the contributions and I need that the authors help me to understand better that issue. \n\nMy feeling is that the machine-learning contribution is not very strong and that the work is primarily a slight variation of deep-learning tools applied to contract design. That is, from a machine-learning perspective, this paper does not provide substantial advancements. This is not necessarily a critical issue for the acceptance of the paper. Many papers just apply machine learning tools to design important applications.  More importantly for me, the advancement in the contract design perspective is not really strong. Yes, the authors are providing better approximations, but it is not clear to me the applicability of the results, e.g., due to the need for thousands of samples for the training and it is unlikely such data are available.\n\nI agree with the authors that the main works done so far focus on online/bandit approaches and that the authors are providing a completely different perspective. While online/bandit approaches are directed at a small number of samples, deep learning makes the reverse and, in my opinion, could require a too large number of samples for a good approximation. Personally, I believe that something in the middle would be useful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> (Q1: Technicalities) _`Are the techniques for training and inference provided by the authors important advancements of the deep learning techniques?`_\n\nA longstanding challenge in the deep learning community has been approximating discontinuous functions. While the Universal Approximation Theorem only guarantees the approximation of continuous functions, many crucial problems involve discontinuity, such as astronomy (e.g., solar flare imaging [1]) and mathematics (e.g., uncertainty quantification [2]).\n\nHowever, establishing a discontinuous network is not an easy task. Discontinuities were considered as early as in the 1950s when neural networks were first proposed [3] by using step activation functions. Following this work, most models introduced discontinuity through the use of different discontinuous activation functions. However, optimizing these models is typically more challenging than with continuous activation functions [2], hindering the application of discontinuous networks. To the best of our knowledge, this paper presents the first discontinuous network architecture with continuous activation functions and stable optimization performance. As other reviewers stated, _\"the proposed DeLU network and its concave counterpart are novel and worthy of studying further,\"_ and _\"the paper proposes a novel neural network architecture ... is very interesting and useful for many other applications in multi-agent learning.\"_ The proposed inference algorithm also provides a new approach to ReLU maximization. Previous work typically relies on mixed integer linear programming [4], while our method is gradient-based and scales well with the input dimensions and network sizes while matching GPU/TPU architecture.\n\nFor economics, we expect that our exploration of discontinuous networks can draw attention to problems involving discontinuity. For example, discontinuity also arises in mechanism design when agents, in effect, ``chose'' from a menu of options. We hope that research on discontinuous network architectures and optimization will contribute to advancing AI progress in computational economics.\n\n[1] Massa, P., Garbarino, S. and Benvenuto, F., 2022. Approximation of discontinuous inverse operators with neural networks. Inverse Problems, 38(10), p.105001\n\n[2] Della Santa, F. and Pieraccini, S., 2023. Discontinuous neural networks and discontinuity learning. Journal of Computational and Applied Mathematics, 419, p.114678\n\n[3] Rosenblatt, F., 1958. The perceptron: a probabilistic model for information storage and organization in the brain. Psychological review, 65(6), p.386\n\n[4] Tjeng, V., Xiao, K.Y. and Tedrake, R., Evaluating Robustness of Neural Networks with Mixed Integer Programming. ICLR 2018\n\n&nbsp;\n> (Q2.1: Applicability) _`Is correct my understanding that several thousands of samples are necessary for training? (... I would suggest the authors use semi-log plots to show what happens with a small number of samples.)`_\n\nThe number of training samples depends on the problem size. On relatively small problems (16 outcomes, 5 actions), using 100 samples is enough to achieve an optimality of 92.99%. For large problem sizes (50 actions, 32 outcomes), we need 5K samples to get a satisfactory optimality (94.67%). Fig. 2 in the PDF of the general response presents semi-log plots to show in detail how DeLU performance changes with small numbers of training samples. \n\nConsidering learning theory, whereas there are exponential worst-case sample complexity bounds coming from recent work [5] (exponential in the number of samples in order to learn an approximately optimal contract, and thus severe difficulty when the number of outcomes is large), we show empirically that we can get good results with a relatively small number of samples. We see this as a strength of the proposed framework, which is simple to implement, versatile, and general purpose. Getting a better theoretical understanding beyond the worst-case, and in the offline setting of the present paper, is an open problem.\n\n[5] Zhu, B., Bates, S., Yang, Z., Wang, Y., Jiao, J. and Jordan, M.I., 2023. The sample complexity of online contract design. ACM EC 2023\n\n&nbsp;\n> (Q2.2: Applicability) _If yes, do you believe that making thousands of queries to the principal is reasonable?_\n\nWe discuss this in different applications to which our method can be applied.\n\n(1) The first application is as a tool for _theoretical economists_ to study contract design problems. In economic theory, one assumes a model of a world environment (e.g., actions, technology, costs, rewards, outcomes), and looks to understand the optimal designs. In this setting, thousands of queries is reasonable because we have a model of the world. \n\n(2) A second application comes from the _digital economy_, where we can expect to gain access to large training sets as we see increasing automation of economic processes (e.g., it doesn't seem too unlikely that we will soon have contracts for LLM-style actors, for example working to plan vacation details for a user with the possibility of contracting on outcomes) [6].\n\n(3) A third application comes from settings where we can expect to have access to a simulator of the agent behavior. In particular, a black-box simulator fits perfectly with our set-up, where we only need access to the induced utility to the principal for different contract designs. These simulations may be for automated agents in the digital economy. Another interesting development is that attention is going these days to _generative models as simulators of human decision making and behavior_ (and in the future, likely firm behavior) [7].\n\n[6] Horton, J.J., 2023. Large language models as simulated economic agents: What can we learn from homo silicus? (No. w31122). National Bureau of Economic Research\n\n[7] Park, J.S., O'Brien, J.C., Cai, C.J., Morris, M.R., Liang, P. and Bernstein, M.S., 2023. Generative agents: Interactive simulacra of human behavior. arXiv:2304.03442"}, {"review_id": "G1mrOVjw7g", "reviewer": "Reviewer_1ATX", "summary": "This paper considers an offline learning problem of optimal contract through neural network. The authors propose a novel neural network architecture, called Discontinuous ReLU (DeLU) network, which models a piecewise affine function with discontinuous boundaries --- a representation that captures the principal (contract designer)'s utility function with respect to the different contracts. With the neural network to model the principal's utility, the paper showcases two methods to determine the optimal contract, linear programming or the gradient-based interior-point method. The gradient based method is shown to be more efficient in the experiments.", "questions": "Please answer to my concern in the first point of weakness section.", "limitations": "n/a", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The paper is well written and easy to follow. The authors provide a good introduction to the contract design problem and the related literature. The paper is also well organized, with a clear description of the proposed method and the experiments. The figures in this paper are very well designed for readers to intuitively understand the idea.\n2. The paper proposes a novel neural network architecture for training a piecewise affine function with discontinuous boundaries, as well as the gradient based optimization for inference. This architecture is very interesting and useful for many other applications in multi-agent learning. The authors also provide a good explanation of the architecture and the intuition behind it.\n3. The paper provides extensive empirical experiments on simulated data with comparison of different network architecture, inference methods.\n", "weaknesses": "1. One major concern on the proposed method of this paper is the fact that it attempts to approximate the optimal contract simply as the argmax to the approximated principal’s utility. This does not seem to be a reasonable choice, because there may be a constant gap between the expected agent response and the actual agent response. In particular, the argmax contract at some boundary of the piecewise affine function in the approximated principal’s utility (as pointed out in Lemma 3) is not robustified from the small inaccuracies at the boundary --- at least I do not see how the proposed method can ensure an accurate boundary can be learnt. And this necessarily leads to a constant drop in the testing against the actual agent in a large class of problem instances. If this understanding is indeed correct, it is actually surprising that the proposed method can still achieve a good performance in the experiments. The authors should provide some explanation on this issue; I suspect this is due to the special structure in the synthesized data.\n\n\n\n2. The paper in general lacks theoretical analysis.  It would be interesting to see some theoretical analysis on the generalization error/sample complexity of the proposed network architecture. The authors could also provide some theoretical analysis on the convergence of the gradient based optimization method, as well as the convergence of the linear programming method.\n\n3. I also expect the paper to include some discussion on the novelty of neural network architecture. I wonder if similar attempts have been made to design neural architecture for special function structures in the hypothesis class.\n\n> Both the first and second concern are resolved given the additional experiments and details provided by the authors in the rebuttal. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">(Major concern) `One major concern... is that it attempts to approximate the optimal contract as the argmax to the approximated principal’s utility. In particular, the argmax contract at some boundary... is not robustified from the inaccuracies at the boundary.`\n\nThanks for this point, which motivates us to consider additional analyses and experiments to support the following three arguments, which we hope can address your concern.\n\n___The current alignment degree between DeLU and real boundaries can support the good performance of DeLU.___ Although we didn't explicitly discuss this in the paper, we believe the reason for this is that  MSE loss is sensitive to misalignment between real and DeLU boundaries. In particular, the jump of the utility function at boundary points can be  arbitrarily large, and thus, a slight misalignment between DeLU and real boundaries can lead to a large increase in the MSE loss.\n\nWe conduct additional experiments to test this viewpoint. For each contract design problem, we randomly sample a large number (50K) of contracts, and check whether they are simultaneously on the real and the DeLU boundary. Specifically, we randomly sample 10K directions for each contract and assess linearity of the real and DeLU utility function in each direction. If the function is non-linear in some (>20%) directions, we mark the contract as on a boundary. In Table 1, we report the percentage of overlapped boundaries points (# samples on both real and DeLU boundaries / # samples on real boundaries). Here we fix the number of outcomes to 5, and increase the number of actions from $2^2$ to $2^8$. For each problem size, we present the median and s.d. of 12 different $(\\alpha_p,\\beta_p)$ combinations. We observe that DeLU achieves a good degree of boundary alignment.\n\nTable 1. DeLU learns boundaries reasonably aligned with real boundaries, and the performance of DeLU is related to the boundary alignment degree.\n|# Actions|4|8|16|32|64|128|256|\n|-|-|-|-|-|-|-|-|\n|Overlapped boundary points (%)|99.71±12.40|83.09±17.32|74.54±15.20|91.36±10.23|76.44±17.36|98.86±4.41|80.57±12.65|\n|DeLU optimality (%)|95.81|88.54|91.78|91.13|89.30|93.02|88.87|\n\nShown in the second row is the optimality (normalized principal utility) of DeLU contracts. It can be observed that the boundary alignment degree is related to DeLU (argmax) performance.\n\n___Our method can be extended to support \"sub-\"argmax, which slightly improves its performance.___ Following the reviewer's comments, going beyond argmax is also possible with our gradient-based inference. When annealing the coefficient of the barrier function $1/t^{(k)}$, we can check whether the actual principal utility increases for each $t$ value. If the utility decreases, we know that we encounter inaccurate boundaries and can stop the inference to seek more robustness. Tested on 8 different problem sizes, we find that \"early stop\" can increase the optimality by 3.96±0.20% (avg±var). Thanks to the reviewer for inspiring this mechanism, which will be included in our codebase. But we also note that this performance improvement is not very large, in line with DeLU boundaries aligning reasonably with real boundaries.\n\n___DeLU recovers optimal contracts on a range of problems.___ The reviewer asks whether the good performance is due to the special structure in synthesized data. We take DeLU to a nonlinear contract design problem with some real-world economic intuition, presented in STOC 2022 and EC 2019 tutorial ([1], Page 47). DeLU achieves an optimality of 97.83% (2.89/2.95). Furthermore, we consider a wide range of environments in our experiments including correlations of different kinds. The results in Figs 4-6 are presented for 12 different correlation structures. Table 2 (Appendix) gives a breakdown for these structures and shows robust performance.\n\n[1] Duetting, P. and Talgam-Cohen, I., Contract Theory: A New Frontier for AGT\n\n&nbsp;\n> `The novelty of neural network architecture.`\n\nA longstanding challenge in the deep learning community has been approximating discontinuous functions using neural networks. While the Universal Approximation Theorem only guarantees the approximation of continuous functions, many crucial problems involve discontinuity, such as astronomy (e.g., solar flare imaging [2]) and mathematics (e.g., uncertainty quantification [3]).\n\nHowever, establishing a discontinuous network is not an easy task. Discontinuities were considered as early as in the 1950s when neural networks were first proposed [4] by using step activation functions. Following this work, most models introduced discontinuity through the use of different discontinuous activation functions. However, optimizing these models is typically more challenging than with continuous activation functions [3], hindering the application of discontinuous networks. To the best of our knowledge, this paper presents the first discontinuous network architecture with continuous activation functions and stable optimization performance. \n\nFor economics, we expect that our exploration of discontinuous networks can draw attention to problems involving discontinuity, especially in utility functions. For example, this kind of discontinuity also arises in mechanism design when agents, in effect, ``chose'' from a menu of options. For this reason, we are hopeful that further research on discontinuous network architectures and optimization methods can contribute to advancing AI progress in computational economics.\n\n[2] Massa, P., Garbarino, S. and Benvenuto, F., 2022. Approximation of discontinuous inverse operators with neural networks. Inverse Problems, 38(10), p.105001\n\n[3] Della Santa, F. and Pieraccini, S., 2023. Discontinuous neural networks and discontinuity learning. Journal of Computational and Applied Mathematics, 419, p.114678\n\n[4] Rosenblatt, F., 1958. The perceptron: a probabilistic model for information storage and organization in the brain. Psychological review, 65(6), p.386"}, {"review_id": "cBRCy948i7", "reviewer": "Reviewer_GYpK", "summary": "The authors focus on the problem of contract design. In this problem, there is an agent which can take some costly action, each action resulting in a distribution over possible outcomes. A principle gets utility based on outcomes, and incentivizes the agent to take actions which will benefit them by transferring them a payment that depends on the outcome. The agent chooses the action that maximizes their expected received payment minus cost; the principal gets a utility equal to the utility of the outcome minus the required payment.\n\nIn mechanism design for selling goods (e.g. auctions) there is a recent thread of work on “differentiable economics” for learning good mechanisms. The authors to some extent work within this broad area, although the techniques they represent depart from prior work in interesting ways. In particular, rather than using a differentiable neural network to represent the mechanism or the agent’s utility as a function of agent types, they instead represent the principal’s utility as a function of the mechanism (contract) itself. The authors present a new network architecture (DeLU) well-suited to learning to represent principal utilities (which are always piecewise affine, though unlike ReLU network not necessarily continuous). By training these networks in a supervised manner, the authors approximate the utility of a given contract. They then present various techniques to optimize over network inputs to find a high-utility contract, and show that these approaches do in fact give good-performing contracts.", "questions": "Figure 1, although a valuable and informative plot, is unpleasant looking. Now that you are not up against NeurIPS deadline it might make sense to take the time to do it and make it better looking (e.g. change the strange camera perspective, make axes not cut off, etc.)\n\nHow would this approach differ from directly doing gradient-based optimization in the space of contracts, similar to RochetNet/MenuNet for auctions?\n\nIt is possible to embed ReLU networks in a mixed-integer program and globally optimize over their inputs. This approach, along with some preprocessing and pruning, has been shown to work quite well even at relatively large scales (e.g. Tjeng et al., https://arxiv.org/abs/1711.07356), especially since good MIP solvers are so fast these days. Could this technique be used effectively to globally optimize over DeLU networks too?\n", "limitations": "The authors adequately discuss limitations of their work, except for the issue mentioned in \"Weaknesses\". I think better discussion of the size of problem instances in which their approach can be used would be warranted.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The problem of contract design is relevant and interesting, and the authors tackle it in a novel way. The new network architecture and new techniques for optimizing over its input are interesting technical contributions. The experiments are carefully done and support the empirical claims made.", "weaknesses": "A major concern I have is that essentially, the authors take many examples of contracts, use them to supervised-learn an approximate utility function, and then optimize on that utility function. Does this reliably work much better than just taking the best contract observed from the training data, skipping this intermediate step? This general problem also shows up in other mechanism design problems where utility functions are learned via supervised learning -- does learning the utility function and using it significantly improve downstream performance compared to just using the fixed training dataset as a \"pointwise\" utility function?\n\nI don't think this is a trivial issue and if unaddressed it is hard to tell if the paper's contribution serves a purpose or not. This is the main reason for my low score and if it can be addressed and no other problems emerge during the discussion phase, I would significantly raise my score.\n\nAfter author response: this issue is satisfactorily addressed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> (Major concern) _`Does learning the utility function and using it significantly improve downstream performance compared to just using the fixed training dataset as a \"pointwise\" utility function?`_\n\nThanks for this question. We present the results from a new set of experiments to demonstrate that learning and then maximizing utility functions finds significantly better contracts than those in the training samples, especially when the number of outcomes is large.\n\n__Experiments.__ We first compare the utilities of the best contracts in the training datasets and the contracts found by DeLU.\n\nIn Table 2, we fix the number of actions $n$ to 50 and increase the number of outcomes $m$ from $2^5$ to $2^8$. As in other experiments, for each problem size, 12 combinations of $\\alpha_p$ and $\\beta_p$ are tested, and we report the median optimality (normalized principal utility) and standard deviation.\n\n__Table 2. Optimality of the best training sample and DeLU contract.__  The number of actions $n$ is fixed to 50.\n|# Outcomes|32|64|128|256|\n|-|-|-|-|-|\n|Best Training Samples|85.83±2.05%|78.72±2.54%|72.04±2.24%|65.41±2.07%|\n|DeLU|92.62±3.81%|97.22±3.71%|88.64±6.93%|94.14±6.27%|\n\nWhen the number of outcome is 256, the best training sample has an optimality of 65.49%, significantly lower than 94.13% achieved by DeLU. Moreover, the optimality of the best training sample decreases as the number of outcomes increases, while our method scales well with the number of outcomes. DeLU also performs substantially better than the best training sample when we increase the number of actions (Table 3). In Figure 1 of the PDF attached in the general response, we observe similar results of these two methods in more problem sizes.\n\n__Table 3. Optimality of the best training sample and DeLU contract.__ The number of outcomes $m$ is fixed to 50.\n|# Actions|32|64|128|256|\n|-|-|-|-|-|\n|Best Training Samples|73.34±3.41%|77.37±3.20%|73.16±3.19%|70.68±2.29%|\n|DeLU|96.44±5.68%|89.84±9.07%|95.03±5.31%|94.30±3.07%|\n\nThe advantage of supervised learning is more significant in very large scale problems. In Table 4, we can see that in problems with 1M outcomes, the performance of DeLU is about 2x  the performance of the best training sample.\n\n__Table 4. Utility of DeLU contracts / utility of the best contract in the training set in large-scale problems.__\n|(# Outcomes, # Actions)|(1K,1K)|(10K,10K)|(50K,2K)|(100K,1K)|(1M,100)|\n|-|-|-|-|-|-|\n|DeLU Result / Best Training Sample|166.49%|190.54%|194.72%|197.64%|199.18%|\n\n__Why?__ As Lemma 3 shows, the  optimal contract is on the boundary of a linear piece (at an optimal solution, the agent's utility of taking the  actions corresponding to adjacent contracts should be the same). This sub-space in which these optimal contracts reside is of a lower dimension. As the dimension of the contract space grows, the probability of obtaining a random sample in this lower-dimensional sub-space gets closer to 0.\n\n&nbsp;\n> (Q2) _`How would this approach differ from directly doing gradient-based optimization in the space of contracts, similar to RochetNet/MenuNet for auctions?`_\n\nA first difference is that auction design is done against a _distribution_ of agent types, which makes the revenue function in auction design  continuous (with a continuous measure of the type distribution \"peeling off\" and choosing a different menu choice as the specification of the choices change). Here, we optimize against a single agent type, which makes the principal's utility function discontinuous. For this reason, direct gradient-based optimization would not be expected to converge to even locally-optimal contracts because the gradients at the boundary are not well defined.\n\nA second difference in applying RochetNet/MenuNet is that the choice in the menu would correspond to an action of the agent (it is not choosing from a menu of contracts, but choosing from a menu of actions given a single contract). For this, the actions would need to be explicitly modeled in the network architecture, and this will become infeasible, for example in the case of an number of actions that increases exponentially in some natural domain parameters.  In our framework, the agent's actions are implicit, and it is only the \"contract to utility\" function that is modeled by the network.\n\n&nbsp;\n> (Q3) _`Could this technique (embed ReLU networks in a mixed-integer program and globally optimize over their inputs) be used effectively to globally optimize over DeLU networks too?`_\n\nThanks for this inspiring question. Globally optimizing a DeLU network involves the bias term for the last layer. This piecewise bias is generated by a Tanh-activated multi-layer network, which is challenging to be embedded in a mixed-integer program (MIP). But if we use ReLU as the activation function in this bias network, then it would be in principle possible to test a global MIP method for inference (our intuition is this would scale less well than the current, piece-oriented inference method). \n\n&nbsp;\n> (Limitations) _`I think better discussion of the size of problem instances in which their approach can be used would be warranted.`_\n\nIn Table 4, we test our method empirically on problems with up to 1M outcomes. As the standard LP algorithm becomes intractable, we compare DeLU results to the best training samples, and DeLU shows substantially superior outcomes.\n\nGiven sufficient RAM and GPU RAM (we now use 80G RAM and an A100 GPU with 40G GPU RAM, allowing at most 10K training samples for 1M outcome problems), we anticipate applicability of our method to even larger problems. This is because a problem size depends on actions and outcomes, both of which DeLU well handles: (1) actions impact linear pieces count, and DeLU represents an exponentially large number of linear pieces (e.g., $2^{128}$ pieces by a single ReLU layer with 128 units); and (2) outcomes affect input dimension, and neural networks are known to be good at handling high-dimensional inputs."}, {"review_id": "UUL89uT2nj", "reviewer": "Reviewer_GXTm", "summary": "This paper studies the problem of contract design, focusing on a scenario where a single principal aims to design the reward structure for different outcomes, followed by a self-interest agent. The principal's utility function, which relies on the agent's best response strategy, is a piecewise affine funciton with points of discontinuity at the boundaries. Based on that, the authors introduce a novel approach by using a discontinuous ReLU (DeLU) network to model the principal's utility function. \n\nTo infer the optimal contract using a trained DeLU network, the authors propose two inference methods: a Linear Programming (LP)-based approach and a gradient-based approach. \n\nThe authors provide empirical evidence through various experiments to showcase the optimality, sample complexity, and time efficiency of their DeLU network in comparison to the conventional ReLU network, as well as the effectiveness of their proposed inference techniques.\n", "questions": "1. As I mentioned in 'Weakness', what is the significance of using deep learning in optimal contract design? why do we care about this? \n2. Why model the utility function and infer the optimal contract instead of directly modeling the contract and optimizing it based on the utility function?\n", "limitations": "The authors have discussed the limitations in Section 6.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The idea of representing the principal's utility function using a neural network is novel and insightful. It paves the way for a new research direction in contract design that harnesses the power of neural networks.\n2. The motivation behind the DeLU network is well-founded. The authors thoroughly analyze the piecewise affine linear nature of the principal's utility function, including its discontinuity at boundary points. Subsequently, they construct the DeLU network, which aligns with and preserves these crucial properties.\n3. The paper exhibits excellent organization throughout, seamlessly integrating theoretical analysis, methodology descriptions, and the experimental section. The logical flow makes it easy to follow and comprehend the content.\n", "weaknesses": "From my view, one significant weakness of the paper is the lack of motivation for utilizing deep learning in the context of optimal contract design.  Why is deep learning a relevant and beneficial approach in this domain? To enhance the paper, it would be essential to address this gap and explain the motivation behind incorporating deep learning techniques for contract design.\n\nFor instance, researchers have explored deep learning for optimal auction design because the theoretical research on optimal auctions has encountered bottlenecks. Similarly, it is crucial to identify the motivation for leveraging deep learning in contract design. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> (Q1) _`What is the significance of using deep learning in optimal contract design? Why do we care about this?`_\n\nThe reason, which is similar to the case of auction design, is that previous theoretical and empirical work has encountered bottlenecks.\n\nA particularly interesting angle is the computational one, given that many contracting settings exhibit combinatorial structure, in which case vanilla LP-based approaches fail to be efficient. Indeed, a recent literature in TCS has embarked on designing worst-case poly-time (approximation) algorithms for different combinatorial domains (e.g., [1, 2, 3, 4]). Our approach provides a scalable, general purpose, and beyond-worst case approach for computing (near-)optimal contracts in such settings. \n\nConsidering learning theory, whereas there are exponential worst-case sample complexity bounds coming from recent work [5] (exponential  in the number of samples in order to learn an approximately optimal contract, and thus  severe difficulty when the number of outcomes is large), we show empirically that we can get good results with a relatively small number of samples. We see this as a strength of the proposed framework, which is simple to implement, versatile, and general purpose. Getting a better theoretical understanding beyond the worst-case, and in the offline setting of the present paper, is an open problem.\n\nIn summary, _no previous method can scale well to the general case of contract design_, motivating us to explore deep learning methods. Moreover, _we expect deep contact design to become more important in the near future_, considering both the digital economy and likely near-term application of AI for automating economic decision making (e.g., contracting with an LLM to plan a vacation, with contracts on outcomes, and the application of smart contracts in DeFi, for example for trading and loans). It seems likely that technological approaches can find application to the design contracts in these kinds of settings [6, 7].\n\n[1] M. Babaioff, M. Feldman, N. Nisan. Combinatorial Agency. EC'06\n\n[2] P. Duetting, T. Roughgarden, I. Talgam-Cohen. The Complexity of Contracts. SODA'20\n\n[3] P. Duetting, T. Ezra, T. Kesselheim, M. Feldman. Combinatorial Contracts. FOCS'21\n\n[4] P. Duetting, T. Ezra, T. Kesselheim, M. Feldman. Multi-Agent Contracts. STOC'23\n\n[5] Zhu, B., Bates, S., Yang, Z., Wang, Y., Jiao, J. and Jordan, M.I., 2023. The sample complexity of online contract design. ACM EC 2023\n\n[6] Horton, J.J., 2023. Large language models as simulated economic agents: What can we learn from homo silicus? (No. w31122). National Bureau of Economic Research.\n\n[7] Park, J.S., O'Brien, J.C., Cai, C.J., Morris, M.R., Liang, P. and Bernstein, M.S., 2023. Generative agents: Interactive simulacra of human behavior. arXiv:2304.03442\n\n&nbsp;\n> (Q2) _`Why model the utility function and infer the optimal contract instead of directly modeling the contract and optimizing it based on the utility function?`_\n\n(1) A first reason is to handle a black box model of an agent, rather than explicitly modeling its actions. A direct optimization approach would need to be able to ``push gradients through\" the agent's decision function, along with the effect of this decision (i.e., action) on the world (i.e., outcomes).  For example, if using an approach similar to RochetNet/MenuNet, then the network would model a set of choices for an agent, with each choice corresponding to an action. As a result, the agent's actions would need to be explicitly modeled in the network architecture, which will get infeasible, for example with an exponential number of actions. In our framework, the agent's actions are implicit, and it is only the \"contract to utility\" function that is modeled by the network.\n\n(2) Direct optimization has been used for auction design. However, the difference there is that auction design is done against a _distribution_ of agent types. _This makes the revenue function in auction design continuous_, with a continuous measure of the type distribution \"peeling off\" and choosing a different menu choice as the specification of the choices change. Here, we optimize against a single agent type, which makes the principal's utility function discontinuous. For this reason, conventional gradient-based optimization would not be expected to converge to even locally-optimal contracts because the gradients at the boundary are not well defined."}]

Author rebuttal:
We would like to express our sincere gratitude to the reviewers for providing exceptionally high-quality and insightful reviews. Your thoughtful insights and valuable suggestions have significantly enriched our work. Thank you for your time, effort, and commitment, and we look forward to addressing your further comments during the discussion period.

Here in the general response, we show the following figures in the attached PDF:

- Figure 1. Optimality (normalized principal utility) of (1) _the best sample in the training dataset_, (2) DeLU, (3) ReLU, and (4) a direct LP solver (“Oracle LP"), for contract-design problems with increasing sizes.

- Figure 2: The performance of the DeLU network trained with _different numbers of training samples (log scale)_ on three sizes of problems (# actions, # outcomes). The median performance as well as the first and third quartile (shaded area) of 5 combinations of $(\alpha_p, \beta_p)$ are shown.

Meta-review: This paper provides a new approach for the contract design problem based on (1) supervised learning approach for learning utility, (2) a new DeLU network architecture for better approximating the discontinuous utility, and (3) efficient gradient-based inference to find approximate optimal contract on a learned DeLU network. The approach shows advantages in runtime and solving larger-scale problems over existing methods such as Linear Programming on the exact utility.

The reviewers are unanimously positive about the paper after rebuttal. Therefore, I recommend acceptance.
Decision: Accept (poster)