A Neural Network Auction For Group Decision Making Over a Continuous Space

1 Introduction

We consider multiple agents, which must agree on a location in a continuous space, such as a point in Rn , and who each have private preferences over the possible locations.

Motivating examples: As an example, consider multiple people who must agree on a single place to locate a certain joint facility, such a school, a factory or a stadium in a city. Denote the set of possible locations as D. Each person knows how much value she associates with each possible location x ∈ D. For instance, one person might want the factory to be located close to them as they work there, whereas another person would want the factory away from them as the noise disturbs them. Similarly a person might want the school close to them, as this saves them money on fuel for their car when driving their kids to school. In this case, each possible location x for the facility has monetary consequences for a participant, and the preferences of a participant i can be captured as a function vi : D → R mapping each possible location x ∈ D to the utility participant i derives from having the facility being placed in location x. We refer to the function vi as a "heatmap", since when locations are points in the plane, it can be visualized as a plot where the color indicates the degree of preference to that location (see example in Figure 1).

Another example is multiple managers who need to decide on the composition of a fund holding a portfolio of k underlying assets. A composition can be captured as x = (p1, . . . , pk) where each 0 ≤ pi ≤ 1 is the proportion of the funds allocated to the i'th underlying asset (so ∑ki=1 pi = 1, and x is a point on the unit simplex). We denote the set of possible compositions as D. Each manager i may have a different prediction regarding how each asset composition x would do, in terms of expected profit and the risk, and hence has a monetary preference for each alternative. This may again be captured as a function vi : D → R. In both examples, a participant i knows its own function vi, but does not the preferences of other participants. How can we select an outcome, such as the facility's location or asset composition, so as the maximize the utility of all participants?

Mechanism design explores how institutions can achieve desirable economic outcomes when self-interested agents interact. Such institutions are essential to ensuring collaboration in human societies, and have the potential of enable cooperation between artificial intelligence agents as well [Dash et al., 2003; Boella et al., 2006; Lopes et al., 2008; Fatima et al., 2014; Rahwan et al., 2019; Dafoe et al., 2020]. Consider agents who must jointly agree on an alternative a from a set A of possible alternatives, with each agent i having a valuation function vi : A → R mapping any alternative a ∈ A to the value of the alternative a to agent i. These valuations are private information, with agent i knowing only their own valuation vi (but not those of the other agents). A central optimizer can select the alternative maximizing social welfare a∗ = argmaxa∈A ∑i vi(a), but this requires knowing all the valuation functions vi. The central optimizer can request agents to report their valuations vi, but then agents may have an incentive to misreport their valuations so as to manipulate the optimizer to choose an alternative they prefer.

The Vickrey-Clarke-Groves (VCG) mechanism [Vickrey, 1961; Clarke, 1971; Groves, 1973] is a key mechanism design success, prescribing an auction framework for charging agents prices based on reported valuations, that disincentivizes such manipulations and enables choosing the alternative maximizing the social welfare. 1

Our contribution: Existing VCG applications typically deal with a discrete (finite) set A of alternatives, so agents can report the utility function ui as a table, listing ui(a) for each a ∈ A. When A is finite but large, earlier research also investigated representation languages for concisely communicating utilities [Boutilier and Hoos, 2001; Lahaie et al., 2008; Nisan, 2000; 2006; Nisan and Ronen, 2001].

We propose a framework to enable applying the VCG mechanism in a continuous domain D, such as participants having valuation over locations in a subset of the 2D plane (D ⊂ R2 ) or higher dimensional space (D ⊂ Rm), where participants cannot communicate their preferences to the central optimizer as a simple table (with a finite number of rows).

Our framework operates by querying each participant i for their valuations in randomly sampled locations, approximating their valuation function vi : D → R by training a deep neural network. The parameters of these neural networks are communicated to the central optimizer, which executes the VCG mechanism to compute the chosen location and calculate prices to be paid. We show how the VCG formula can be computed (approximately) using gradient ascent, as neural networks are differentiable models. 2

2 Expressing and Aggregating Preferences on Continuous Spaces

A continuous preferences domain consists of a continuous domain D (e.g. D ⊂ R2 ), and n agents who must agree on a single chosen location r ∈ D; Each agent i has a valuation function vi : D → R mapping each element p ∈ D to a real value vi(p) indicating the utility agent i derives from having the agreed location be x. When considering a bounded part of the plane, e.g. D = [0, 1] × [0, 1] (i.e. coordinates (x, y) in the plane where 0 ≤ x ≤ 1 and 0 ≤ y ≤ 1), one can visualize the function vi as a heatmap, but we emphasize our framework works for the general case D = Rm.

1 A key application of VCG or similar auctions is for sponsored search and display advertising [Edelman et al., 2007; Lahaie et al., 2008; Bachrach et al., 2014; Jin et al., 2018], where the alternative set is discrete. In contrast, we focus on continuous alternative sets.

2 Our approach is related to other neural auctions [Feng et al., 2018; Tacchetti et al., 2019; Shen et al., 2019], but rather than using neural networks to learn the rules of the auction, we use them as a language enabling agents to express preferences. Our method is akin to neural methods for aggregating responses [Gaunt et al., 2016; Li'ang Yin et al., 2017; Atarashi et al., 2018], but we focus on strategic agents that may misreport preferences, and examine the VCG auction. Other methods learn user preferences [Gal et al., 2004; Coehoorn and Jennings, 2004; Albrecht and Stone, 2018], but neural networks are differentiable and offer universal function approximation so are well-suited for our use-case.

The central optimizer requires each agent to report their valuations {vi}ni=1 (where each is a function vi : D → R). We refer to this report representing an agent's valuation as the agent's "type" θ ∈ Θ (where Θ denotes the set of all possible such types). A representation method is an encoder e, a reversible function converting an agent's valuation vi to an encoding e(vi), which can be transmitted to the central optimizer. 3 The decoder is e-1 , the inverse function of an encoder, mapping a representation θ back into a function vθ : D → R. We say an agent i with valuation vi is truthful if it transmits θ = e(vi), though agents may transmit any valid representation θ′ ∈ Θ, representing some function vθ′ , where vθ′ may be very different from vi. 4

We denote the reported representations of agent i as θ′i . The center takes the valuation reports θ′1 , . . . , θ′n and decodes them to obtain vθ′i = e-1 (θ′i ): given i's report θ′i , it determines i's value of location k as vi(k, θ′i ) = vθ′i (k). The mechanism used by the center is specified by two functions f, t, both taking the reports θ′1 , . . . , θ′n , where f : Θn → D specifies how to choose the final location k ∈ D and t : Θn → Rn specifies the payments t1, . . . , tn to extract (ti is the amount paid by i under the reports θ′1 , . . . , θ′n ).

A Neural Network Variant of the VCG Mechanism: We use the VCG mechanism [Vickrey, 1961; Clarke, 1971; Groves, 1973], which guarantees that participants are incentivized to be truthful, and report a valuation function vθ′i that matches their true valuation function vi.

For brevity we denote θ′ = (θ′1 , . . . , θ′n ), and denote θ′-i = (θ′1 , . . . , θ′i-1 , θ′i+1 , . . . , θ′n ). The VCG framework uses an outcome choice function f aimed at maximizing the sum of the agent utilities according to the submitted reports:

We denote this optimal location according to the agent reports θ′ as d∗ (θ′ ) = f(θ′ ). The Groves family of mechanisms sets the payments to be:

Here, hi(θ′-i ) relates to any function hi : Θn-1 →Rwhich only takes into account the reports of agents other than i (i.e. this function does not depend on the report θ′i of agent i).

The VCG mechanism is a special case of the Groves family, which sets hi as follows: hi(θ′i-) =

3 Standard VCG implementations for discrete domains [Groves, 1973; Nisan and Ronen, 2001] deal with a finite set of alternatives A, so the encoding may be a list of |A| numbers, consisting of vi(a) for each a ∈ A. Clearly, this is intractable for continuous domains.

4 The encoding and decoding functions are public information.

∑j̸=i vθ′j (d∗-i (θ′-i )). Here, d∗-i (θ′-i ) relates the the (welfare-maximizing) outcome that would have been chosen based solely on the reports of participants other than i, i,e: d∗-i = argmaxd∈D ∑j̸=i vθ′j (d). In discrete domains D is a finite set of alternatives; each agent i can transmit its valuation function vi as a table of |D| values, and the center computes argmaxd∈D ∑ni=1 vi(d) by iterating over all elements d ∈ D. Neither is directly feasible where D is a continuous space, which is where our approach comes in.

2.1 Using Neural Networks as a Representation Language for Preferences

Our approach is based on executing the VCG mechanism by using neural networks a the representation language for the preferences of agents. More precisely, we propose using the parameters of a neural network to express the function vi : D → R of each participant. Neural networks are universal function approximators [Cs´aji and others, 2001; Hornik et al., 1989], i.e. given a large enough number of parameters, neural networks can approximate arbitrarily complex functions. Hence, we can use neural networks as a language for representing participant preferences vi without needing to impose any restriction on these valuations.

Our framework operates as follows.

1. For every participant i, we randomly sample B elements in the domain D, denoted as d1, . . . , dB.
2. We train a neural network to approximate vi given these samples, obtaining the neural network parameters θ′i . There are many possible choices for the neural network architecture, the loss used for the training, or the optimization hyperparameters such as the learning rate. A simple implementation can use a feedforward neural network, and an L2 loss L = (fθ′ (d) - vi(d))2 . However, many other choices are also valid, and may yield better results, depending on the domain.
3. Each participant i transmits the trained parameters θ′i to the center. Note that participants may attempt to manipulate by making a false report i.e. θ′ ̸= θ, but the VCG pricing rule computed in the next step disincentives such dishonest behavior.
4. The center computes the chosen outcome d∗ (θ′ ) = argmaxd∈D ∑ni=1 vθ′i (d). As s = ∑ni=1 vθ′i (d) is a sum of the functions vθ′i (and similarly to each vθ′i , the sum s is also a function s : D → R); as each vθ′i is captured by a neural network, it is a differentiable model, so as a result s is also differentiable. Given a differentiable model s, one can optimize for argmaxd∈D s(d) using any method for finding a local maximum of a differentiable function, and we suggest applying the commonly used Gradient Ascent [Sra et al., 2012; Ruder, 2016].
5. The center computes the VCG prices ti. Similarly to the previous step, to perform the optimization d∗-i = argmaxd∈D ∑j̸=i vθ′j (d), we note that the partial sum s-i = ∑j̸=i vθ′j is a sum of differentiable models vθ′j , and is a differentiable function, so one can optimize for argmaxd∈Ds-i(d) using Gradient Ascent.

A limitation of this method is that the VCG formula requires computing global optima argmaxd∈D ∑ni=1 vθ′i (d), but Gradient Ascent may converge on a local rather than global optimum. One may ameliorate this by starting off from many random locations when applying Gradient Ascent (and selecting the optimal location across these runs), or consider placing a restriction on the form that the function vi can take and using a representation form that allows for an optimization algorithmwith better guarantees. 5

3 Conclusion

Our approach enables users to agree on a location or parameter configuration in a continuous space, taking a form of a VCG auction, executed using neural networks for expressing the preferences of participants. Users may express valuations through a graphical interface, providing data to train neural networks to capture and represent their preferences, and finally compute the VCG outcome and prices. One could also use a programmatic interface, where users provide valuation functions as code, with the system then querying this code to train the neural network. The VCG pricing rule we use desincentivizes tricking the system into selecting a location that improves their individual utility at the expense of others.

Several questions remain open. First, how can we improve the optimization procedure so as to obtain a global rather than local optima? Second, can the neural network architecture be better tailored to specific domains? Finally, could neural network based representations of user preferences be used in other settings, such as voting and social choice?