Adaptive Mechanism Design using Multi-Agent Revealed Preferences
Luke Snow Vikram Krishnamurthy





















Adaptive Mechanism Design using Multi-Agent Revealed Preferences
    Luke Snow,  Vikram Krishnamurthy
This research was supported in part by the National Science Foundation grants CCF-2112457 and CCF-2312198, Army Research Office grant W911NF-19-1-0365, and Air Force Office of Scientific Research grant FA9550-22-1-0016
Luke Snow las474@cornell.edu, and Vikram Krishnamurthy vikramk@cornell.edu are  with the School of Electrical and Computer Engineering, Cornell University, Ithaca, NY 14853, USA
        

    April 29, 2024
===========================================================================================================================================================================================================================================================================================================================================================================================================================================================




This paper constructs an algorithmic framework for adaptively achieving the mechanism design objective, finding a mechanism inducing socially optimal Nash equilibria, without knowledge of the utility functions of the agents. We consider a probing scheme where the designer can iteratively enact mechanisms and observe Nash equilibria responses. We first derive necessary and sufficient conditions, taking the form of linear program feasibility, for the existence of utility functions under which the empirical Nash equilibria responses are socially optimal. Then, we utilize this to construct a loss function with respect to the mechanism, and show that its global minimization occurs at mechanisms under which Nash equilibria system responses are also socially optimal. We develop a simulated annealing-based gradient algorithm, and prove that it converges in probability to this set of global minima, thus achieving adaptive mechanism design.






§ INTRODUCTION


Consider the standard non-cooperative game-theoretic setting. Several agents act in their own self-interest, aiming to maximize their individual utility functions which are dependent on the actions of the entire set of agents. The classical concept of Nash equilibria represents the stable joint-action states of the entire group, representing those states in which no agent has any incentive to unilaterally deviate given the actions of all other agents. In many instances, this non-cooperative interaction degrades the overall utility achieved by the group; that is, there may be other joint-actions not arising from the Nash stability criteria under which the entire group of agents does better.
We term those joint-actions which maximize the sum of agent utilities as 'socially optimal'. The goal of mechanism design is to fashion the game structure, specifically the mapping from joint-action space to agent utilities ("mechanism"), such that non-cooperative behavior gives rise to socially optimal solutions. 

Literature and Main Result.  Mechanism design arises in electronic market design <cit.>, economic policy delegation <cit.> and dynamic spectrum sharing <cit.>. Standard solutions, whether analytical <cit.> or automated <cit.>, pre-suppose knowledge of the agent utility functions in order to devise mechanisms inducing socially optimal Nash equilibria. This paper contributes to the field of algorithmic mechanism design by constructing a framework for attaining socially optimal Nash equilibria without knowledge of the utility functions of the agents. This is relevant to problems where the designer does not have a-priori knowledge of each agent's preferences and goals.

We consider a designer who does not know the agent utilities but can repeatedly interact with the system and adapt its mechanism based on the system's Nash equilibrium behavior.  We employ microeconomic revealed preference theory to develop an algorithmic formulation which converges to a mechanism inducing socially optimal Nash equilibria behavior. Specifically, our main contributions are:

We accomplish this by employing tools from microeconomic revealed preference theory, and developing an iterative scheme for "probing" the multi-agent system and adapting the mechanism given its Nash equilibrium responses.


    
  - We generalize the influential result of Forges and Minelli <cit.> in revealed preferences to the multi-agent regime. Revealed preferences are a branch of microeconomics that  give necessary and sufficient conditions under which it is possible to identify utility maximization behavior from empirical data of a decision maker. Our generalization formulates  necessary and sufficient conditions, in the form of linear program feasibility, for the existence of utility functions under which empirically observed Nash equilibrium responses are socially optimal.
    
  - We exploit this linear program feasibility to construct a loss function which captures the distance between Nash equilibria to social optima. We show that the global minimizers of this loss function coincide with the socially optimal Nash equilibria. We then prove that this loss function can be globally minimized by iteratively observing Nash equilibrium responses of the system and updating the mechanism according to a simulated annealing-based gradient algorithm. 
 
Thus, we provide a novel algorithmic framework for attaining mechanism design in an adaptive fashion without explicit knowledge of the utility functions of the agents.


Section <ref> discusses background on mechanism design, revealed preference theory, and presents our first main result (Theorem <ref>). Section <ref> exploits Theorem <ref> to derive an algorithm for achieving adaptive mechanism design. It contains our second main result, Theorem <ref>,  which proves the algorithm's global convergence in probability. Section <ref> presents an illustrative numerical example in a non-cooperative game setting.  



§ PRELIMINARIES


In this section we first introduce the non-cooperative game-theoretic setting and the mechanism design problem. We then introduce microeconomic revealed preferences theory, and prove a key result which will allow us to achieve adaptive mechanism design. 



 §.§ Mechanism Design


For the mechanism design framework we suppose a parametrized finite-player static non-cooperative game, structured by the tuple G = (,{f^i}_i∈[], ,Θ, O)
where 

    
  -  is the number of participating agents.
    
  -  is the joint action space. Specifically, each agent i takes an action a_i ∈_i ⊆^k, where _i is the space of actions available to agent i. Letting = [a_1,…,a_]' denote the joint-action (sometimes called joint-strategy) taken by all agents, ⊆^k is then the space of joint actions, given by the cartesian product = ⊗_i _i.
    
  - Θ is the mechanism parameter space, and O is the outcome space. Specifically, a mechanism o_θ: → O, parametrized by θ∈Θ, is a mapping from joint action  to outcome o_θ() ∈ O.
    
  - f^i: O → is the utility function of agent i, assigning to each outcome a real-valued utility.


There exist  agents. Agent i∈ [] can takes an action a_i ∈_i, where _i is the space of actions available to agent i. The joint action taken by all agents is given by a = [a_1,…,a_]', and we denote the space of joint actions by the Cartesian product = ⊗_i_i. A mechanism is a mapping from  into an outcome space O, so that the joint action a induces an outcome o(a) ∈ O according to the mechanism o. We can parameterize the mechanism by parameter θ as o_θ, such that we can alter the mapping o_θ by varying the parameter θ∈Θ, where Θ is some parameter space. Each agent has an individual utility function f_i: O → mapping from outcome space to a real-valued utility. Each agent i acts in self-interest by aiming to maximize its own utility f_i. 

The real-valued utility gained for agent i, given mechanism o_θ (with parameter θ) and joint action , is f^i(o_θ()). For notational simplicity we denote f^i_θ() = f^i(o_θ()), so that the emphasis is on the mapping from joint action  to utility f^i, with the mechanism o_θ acting as an intermediary such that θ parametrizes this mapping.




Figure <ref> illustrates the information flow in this setup. The mechanism is defined as a parameter which modulates the mapping from joint-action space  to outcome space O; it thus modulates each agent i's utility gained from joint-actions ∈. [It is defined in this way, rather than directly parametrizing the utility functions, because oftentimes in practice the mapping from joint-actions to outcomes can be completely specified, while the influence on utility functions may be unknown.]


The mechanism design problem begins by assuming that each agent i acts in its own self-interest, aiming to maximize its utility function f^i. The standard solution concept for this non-cooperative interaction is the Nash equilibrium:

   Joint strategy  is a Nash equilibrium of the game G under mechanism o_θ if 
    
    a_i ∈max_a∈_if_θ^i(a,a_-i)  ∀ i∈[]

    where a_-i = \ a_i is the set of actions without a_i, so that (a_i,a_-i) =.


Observe that the Nash equilibrium solutions (<ref>) are dependent on the mechanism parameter θ. The mechanism design problem is that of designing the mechanism o_θ(·), through parameter θ, such that a joint action  at Nash equilibrium also satisfies certain global welfare conditions.  A standard global condition, known as the utilitarian condition <cit.>, is to maximize the 'social welfare' which is simply the sum of agent utility functions 

    A joint-strategy  is socially optimal for the game G and mechanism o_θ if it maximizes the sum of agent utilities:
    
    ∈max_a∈∑_i=1^ f^i_θ(a)


Then the mechanism design problem is to find a mechanism o_θ, through parameter θ, such that the Nash equilibrium solution  arising from the conditions (<ref>) simultaneously maximizes the social welfare, i.e.,
 The mechanism design problem is to find θ∈Θ such that 

    satisfies  a_i ∈max_a∈_if_θ^i(a,a_-i)  ∀ i∈[] 
       ⇒∈max_a∈∑_i=1^ f^i_θ(a)



Conceptually, this definition provides a formalization of designing a system such that even when individual agents act in pure self-interest, they produce outputs which benefit the entire group. [Note that the social welfare condition is a special case of Pareto-optimality; a more broad treatment could fully treat the range of Pareto-optimality solutions. In fact our results easily generalize, but we stick with 'social welfare' in this paper for simplicity and relevance to the mechanism design literature.]

Notice that social optimality (<ref>) is a special case of Pareto-optimality. In fact, the results presented in this work can easily be extended to the case where general Pareto-optimal solutions are considered. We exclude presentation and discussion of this generalization for brevity.

The mechanism design problem has been well-studied <cit.>, <cit.>, <cit.> in the case where the agent utility functions {f^i_θ(·)}_i=1^ are known or can be designed. We consider the case when the utility functions are unknown to the designer. In many realistic scenarios, the designer may need to design the system without explicit knowledge of the preferences and goals of its constituent members. We achieve this by utilizing the methodology of revealed preferences to formulate a simulated annealing-based gradient algorithm which converges to a mechanism parameter θ inducing the relation (<ref>). 




 §.§ Multi-Agent Revealed Preferences


The microeconomic field of revealed preferences dates back to the seminal work <cit.>, and establishes conditions under which it is possible to detect utility maximization behavior from empirical consumer data. In particular, Afriat <cit.> initialized the study of nonparametric utility estimation from microeonomic consumer budget-expenditure data. Specifically, <cit.> provides necessary and sufficient conditions under which budget-expenditure data is consistent with linearly-constrained utility maximization. <cit.> extended this work to incorporate non-linear budget constraints, and in this work we generalize <cit.> to the multi-agent regime. Specifically, we provide necessary and sufficient conditions for the existence of utility functions under which nonlinearly-constrained joint-actions are socially optimal (<ref>). 

The setting is as follows. We consider a multi-agent setting consisting of  agents. The designer observes the multi-agent system over T time-steps. At each time-step t, agent i's action a_t^i ∈^k is constrained by 

    g_t^i(a_t^i) ≤ 0

where g_t^i : ^k → is a continuous and increasing constraint function. The system then produces joint action _t = [a_t^1,…,a_t^] ∈^k, and the designer observes the dataset {{g_t^i(·)}_i=1^,, t∈[T]}, where [x] denotes the set {1,2,…,x}.  

Notice the black-box nature of these observations: the designer does not have any a-priori knowledge of how the actions  are produced. Still, the designer aims to determine if the group responses _t are consistent with social-optimality. Specifically, he aims to determine if there exist utility functions {f^i(·): ^k→}_i=1^ such that for all t∈[T],

    _t ∈max_a∑_i=1^f^i(a)    s.t.    g_t^i(a^i)≤ 0   ∀ i∈[]

where a = [a^1,…,a^] denotes the joint-action optimization variable.
Our first main result generalizes the work of <cit.>, providing necessary and sufficient conditions for this existence in the form of linear program feasibility.




 §.§ Multi-Objective Optimization

Here we introduce the constrained multi-objective optimization framework. For discrete time , subject to increasing and continuous nonlinear functions g_t^i: ^→ and utility functions f^i(·): ^n →, i= [M] := {1,…,}, the constrained multi-objective optimization problem is given as: 


    max _{f^1(),…,f^()}
        s.t.  a_i ∈_t^i := {a : g_t^i(a) ≤ 0} ∀ i∈ []

The constraint function g_t^i governs the actions _t^i available to agent i at time t. Then let us denote 

    _t = ⊗_i∈[]_t^i

as the joint action space at time t.
 In single-objective optimization, the goal is to find the best feasible argument which maximizes the objective. However, in multi-objective optimization there will seldom exist an argument  which simultaneously maximizes all objectives, i.e. there will be tradeoffs between objectives for varying argument . Thus, the solution concept for the multi-objective optimization problem (<ref>) is that of efficiency:


 For fixed {f^i(·), g_t^i}_i=1^ and a joint-action ^*∈, let 

    Z^t(^*) = {∈_t : f^i() ≥ f^i(^*)  ∀ i ∈ [] 
       Y^t(^*) = {∈_t : ∃ k : f^k() > f^k(^*) }

The vector ^* is said to be efficient if 

    Z^t(^*) ∩ Y^t(^*) = ∅

i.e., there does not exist another vector in the feasible set _t which increases the value of some objective f^i(·) without simultaneously decreasing the value of some other objective f^j(·), i,j∈ [].

We then denote the set of all efficient solutions to the problem (<ref>) as 

    ({f^i, g_t^i}_i=1^M) := {^* ∈_t : (<ref>) is satisfied}

and we say that ^* solves (<ref>) if and only if ^* is efficient, i.e.

    ^* ∈{max_{f^1(),…,f^()} s.t.  ∈}
       ⟺ ^* ∈({f^i, g_t^i}_i=1^M)



Denoting () = (f^1(),…,f^())^T, we can use the following problem of weighted sum (PWS) <cit.> to obtain an efficient solution:

    max ^T()  s.t.  ∈

where = (^1,…,^)^T ∈^_+. The set of weights  is restricted to the unit simplex, denoted as := {∈^_+ : 1^T = 1}. Then we can denote the set of optimal solutions for (<ref>) as

    = max_{^T() : ∈}

Then, letting = {∈^_++ : 1^T = 1} denote the unit simplex with each weight ^i strictly positive, we have <cit.>:


    ⋃_∈⊆({f^i}_i=1^M, ) ⊆⋃_w ∈







    Consider a dataset of observed system constraints and responses = {^i(·),, t ∈ [T]}, with ^i(a_t^i) = 0   ∀ t ∈ [T],i∈[][This condition is known as 'satiation' of constraint functions, and is widely assumed in the revealed preference literature <cit.>. Indeed, we will eventually assume concavity of utility functions f^i, which when considered with increasing constraint functions naturally necessitates satiation in utility-maximizing systems]. The following are equivalent:
    
        
  - There exists a set of concave, locally non-satiated utility  functions {f^i: ^k→}_i=1^M such that the actions {, t∈ [T]} are socially optimal, i.e, (<ref>) holds for all t∈[T].
        
  - For each i ∈ M, with _t = [a_t^1,…,a_t^], there exist constants u_t^i∈, λ_t^i >0 such that the following set of inequalities have a feasible solution 
        
    u_s^i - u_t^i - λ_t^i^i(a_s^i) ≤ 0   ∀ t,s ∈ [T]

    



    See Appendix <ref>


In the following section we provide the adaptive mechanism design setting, which merges the two frameworks discusses in this section and employs Theorem <ref> to develop an algorithmic solution. The condition (<ref>) will serve as the key tool in formulating our approach. 





Given constants u_t^i, λ_t^i, t∈[T],i∈[M], explicit monotone and continuous utility functions that rationalize the dataset {g_t^i, } are given by

    Û^i(γ) = min_s ∈ [T][u_s^i + λ_s^i[g_s^i(γ)] ]

Specifically, (<ref>) holds with U^i = Û^i. 



Suppose the linear program (<ref>) has a feasible solution. Then the responses {, t∈[T]} are consistent with play from a Pareto-optimal Nash equilibrium: there exist concave increasing utility functions
{U^i: ^n →}_i=1^ such that 

    ∀ t ∈ [T],∀ i ∈ []:    a_t^i ∈max_a U^i(a, ^-i)

in addition to Pareto-optimality (<ref>).





§ ADAPTIVE MECHANISM DESIGN


In this section we first outline the interaction dynamics between the designer and the multi-agent system, combining the frameworks of sections <ref> and <ref>. We utilize Theorem <ref> to construct a loss function with respect to mechanism parameter θ, which has global minima corresponding to those mechanisms inducing socially optimal Nash equilibria. In section <ref> we provide a simultaneous perturbation stochastic approximation (SPSA) algorithm operating on this loss function, and in section <ref> we prove the global convergence of this algorithm under several basic assumptions. 



 §.§ Algorithm Derivation



Here we describe the high-level strategy and motivation for our adaptive mechanism design algorithm.

Interaction Procedure: First we outline the interaction procedure between the designer and the system constituents.
As in the revealed preference framework, we treat the multi-agent system as a black box. The designer can provide a mechanism o_θ and constraints {g_t^i(·)}_i=1^. It subsequently observes the Nash equilibrium response _t(θ) (<ref>) of the group in game G with mechanism parameter θ and with _i = {a∈^k : g_t^i(a)≤0}. Here t denotes a time-index as in the setting of Theorem <ref>, and we denote (θ) a function of θ to emphasize the dependence of Nash equilibria on the mechanism o_θ. The assumption that the response (θ) is a Nash equilibrium is standard in the mechanism design literature, and is readily achieved from non-cooperative best-response interactions among the agents <cit.>. Figure <ref> displays this interaction procedure.



Suppose the designer now provides T sets of constraint functions {g_t^i(·), t∈[T]}_i=1^M and receives T corresponding Nash equilibrium responses _t(θ) under mechanism parameter θ. We denote this dataset as 
    _θ = {{g_t^i(·)}_i=1^, _t(θ), t∈[T]}

 We translate the mechanism design goal to this empirical setting: to find a mechanism parameter θ such that empirical Nash equilibrium responses (θ̂) are consistent with social optimality, i.e., (1) of Theorem  <ref> holds. 

Recall that the designer can directly test whether the dataset _θ is consistent with social optimality by testing the feasibility of linear program (<ref>). That is, if (<ref>) is feasible, then the goal is achieved. Our adaptive mechanism design solution is then to iteratively modify the parameter θ until (<ref>) is feasible for dataset _θ. We will next formulate a loss function L(θ) which is minimized at some θ̂ which induces feasibility of (<ref>).

Formulating the Loss Function: Suppose the LP (<ref>) does not have a feasible solution for the dataset 𝒟_θ. How can we quantify the proximity of θ to a mechanism θ̂ which induces feasibility of (<ref>)? First notice that we can augment the linear program (<ref>) as:

    L(θ) = min_r∈ : ∃{u_t^i,λ_t^i, t∈[T], i∈[]} :
          u_s^i - u_t^i - λ_t^i^i((θ)) ≤ r   ∀ t,s∈[T],i∈[]

i.e., L(θ) is the minimum value of r such that the specified linear program has a feasible solution for the dataset of Nash equilibrium responses {_s(θ),s∈[T]}. 
Thus, the optimization variable r can be treated as a metric capturing the proximity of the dataset 𝒟_θ to being feasible in (<ref>): if r≤ 0, then (<ref>) is feasible, else lower r indicates _θ being "closer" to feasible. 

Thus, we can adopt the augmented linear program solution L(θ) as an objective function taking parameter θ and outputting a value r representing the proximity of the empirical dataset _θ to feasibility (social optimality). The adaptive mechanism design problem can then be re-stated as 

    Find θ̂∈Θ  s.t.  θ̂∈min_θ L(θ)


There are several technical questions that then arise in determining whether this approach is well-posed: 

    
  - Is this minimum necessarily less than or equal to zero? If not, a mechanism θ which induces a socially optimal Nash equilibria does not exist for the set {f^i_θ(·)}, by Theorem <ref>.
    
  - How can this minimum be achieved? The objective function L(θ) may very well be highly unstructured and nonconvex with respect to θ. 


We address these questions in the Section <ref>, where we introduce assumptions under which (<ref>) can be achieved.  


We next introduce a simultaneous perturbation stochastic approximation (SPSA) algorithm, and then prove that it converges in probability to the global minima of L(θ) under basic assumptions that make the problem well-posed. The proposed SPSA algorithm iteratively adjusts the mechanism parameter θ by observing batch datasets _θ, evaluating L(θ), and moving θ in the direction of decreasing L(θ) by forming a stochastic gradient approximation, until a minima θ̂ making L(θ̂) ≤ 0 is obtained.  Thus, the SPSA algorithm achieves adaptive mechanism design by adaptively finding a mechanism that induces social optimality for Nash equilibrium responses without knowledge of agent utility functions.




 §.§ Simultaneous Perturbation Stochastic Approximation




Simultaneous perturbation stochastic approximation (SPSA) algorithms are a well-studied class of optimization algorithms that operate without direct access to objective function gradient evaluations. 

We use the SPSA algorithm with injected noise, as presented in <cit.> to globally optimize deterministic non-convex functions. With objective function L: ^p →, this algorithm iterates via the recursion

    θ_k+1 = θ_k - a_k G_k(θ_k) + q_k w_k

where w_k i.i.d.∼(0,I) is purposefully injected Gaussian noise, a_k = a/k, q_k^2 = q/kloglog(k), a>0, q>0, and G_k is a term approximating the function gradient, 

    G_k = L(θ_k + c_kΔ_k) - L(θ_k - c_kΔ_k)/2c_kΔ_k

Here c_k is a scalar, and Δ_k = [Δ_k1,…,Δ_kp]'∈^p is a p-dimensional Rademacher random variable, i.e., for each i∈[p], Δ_ki is an independent Bernoulli(1/2) random variable. 



Observe that this algorithm only evaluates the objective function itself and does not rely on access to its gradients. This is appealing for use with our objective function (<ref>) since it is not immediately obvious how one could access or compute the gradient of (<ref>). 

Also notice that the algorithm (<ref>) injects Gaussian noise and thus imitates a simulated annealing <cit.> or stochastic gradient Langevin dynamics <cit.> procedure. It turns out that this allows the algorithm to converge to global minima of potentially nonconvex functions by escaping local minima <cit.>.
Indeed, we will provide a result guaranteeing the convergence of our algorithm to the global minima of L(θ). 

Implementation: The full implementation of the SPSA algorithm within our adaptive mechanism design framework can be seen in Algorithm <ref>. In this implementation, the objective function L(θ) is evaluated by obtaining the empirical dataset _θ and solving the linear program (<ref>). Recall the empirical dataset _θ is obtained by "probing" the multi-agent system with constraint functions {g_t^i(·)}_i=1^ over T time points, and observing the Nash equilibrium responses {_t(θ),t∈[T]} for mechanism o_θ. There are several subtleties that should be pointed out to fully specify Algorithm <ref>:


  - In order to make this "probing" specification precise, we define for each i∈[] a parametrized family of constraint functions {g^i(·,γ)}, where γ is a parameter lying in some space Γ. Then, taking T parameters {γ_t, t∈[T]}, e.g., as instantiations of random variables with distributions on Γ, we form the constraints g_t^i(·) = g^i(·,γ_t). This probing interaction can be seen on lines 14-15 of Algorithm <ref>. 
  - We assume that the mechanism parameters are taken from a compact space Θ⊂^p, and so whenever an iterate θ_k+1 leaves this space, we project it back onto the boundary of Θ by the function 

    Proj_Θ(θ) = min_γ∈Θγ-θ


Apart from these specifications, the operation of Algorithm <ref> follows the recursion (<ref>) exactly, and terminates when a parameter θ̂ for which L(θ̂)≤0 is found.




 §.§ Convergence



Here we demonstrate the efficacy of Algorithm <ref>, by showing its convergence to the global minima of the loss function (<ref>). Before doing so, we must first characterize the conditions under which our problem is well-posed. Recall we assume, as is standard in the mechanism design literature, that for each "probe" constraint set {g_t^i(·)}_i=1^ and mechanism o_θ, the system outputs a Nash equilibrium response _t(θ) that satisfies (<ref>). Therefore, we must ensure the existence of a Nash equilibrium for every mechanism parameter θ∈Θ. Then, for a given mechanism parameter set Θ, we must be sure that there exists some θ̂∈Θ for which a Nash equilibrium solution is socially optimal, otherwise the Algorithm <ref> will never terminate. 

    that is, the conditions on the game form G such that 
 

  i. There exists at least one pure-strategy Nash equilibrium for every mechanism parameter θ∈Θ.

  ii. There exists a mechanism parameter θ∈Θ such that the utility functions f^i(·,o_θ) and joint action set  admit a pure-strategy Pareto-optimal Nash equilibrium. 

  iii. Algorithm <ref> converges to a mechanism parameter corresponding to a Pareto-optimal Nash equilibrium



In order to address these criteria, we must introduce the concept of 'potential modifiability':



    A pure-strategy Nash equilibrium exists in every concave n-person game <cit.>


A game form G that is potential modifiable satisfies (ii.)



A game form G is potential modifiable if there exists some mechanism parameter θ such that the utility functions {f^i_θ(·)} admit a 'potential' function Φ(·) such that for any i∈[],   = (a_i,a_-i)∈, a_i'∈_i, 

    f^i(a_i',a_-i) - f^i(a_i, a_-i) = Φ(a_i',a_-i) - Φ(a_i, a_-i)



A potential modifiable game form G is one for which at least one mechanism parameter exists under which G is a potential game. 

Remark: A necessary and sufficient condition for a game G to be a potential game is that each utility function f^i_θ() can be decomposed as a common function Φ() and a term depending only on actions a_-i. <cit.> 

Now we introduce two assumptions on the game form G which enforce the well-posedness of our problem, and are also sufficient for global convergence of Algorithm <ref>. 



The utility functions {f^i_θ()}_i=1^ are each concave and increasing with respect to a_i, thrice continuously differentiable with bounded n-th order derivatives (n=1,2,3) with respect to both a_i and θ, and potential modifiable. 




The constraint functions g_t^i: _i → are increasing and thrice continuously differentiable for all t and i. 


Discussion of Assumptions: By <cit.>, concavity of utility functions {f^i_θ(·))}_i=1^ and convexity of the constraint regions defined by {g_t^i(·)}_i=1^ is sufficient to ensure existence of a Nash equilibrium solution. Concavity (or quasi-concavity) of utility functions is also widely assumed in the microeconomic and game theory literature <cit.>. Also observe that in a potential game a Nash equilibrium solution is automatically socially optimal by concavity of the potential function  Φ. Therefore, there exists at least one mechanism parameter θ̂ which induces socially optimal Nash equilibrium, namely that parameter under which the game is a potential game. [While potential modifiability is a sufficient condition for existence of a socially optimal Nash equilibrium, it is not necessary. Indeed, we will show in our numerical simulations that a socially optimal Nash equilibrium is found for mechanism parameters not inducing a potential game. Still, potential modifiability is a simple and convenient assumption guaranteeing at least one socially optimal Nash equilibrium. A full characterization of the existence of socially optimal Nash equilibria in game structures is an interesting point for future research.]

The additional differentiability structure imposed by Assumptions <ref> and <ref> is sufficient to guarantee convergence of Algorithm <ref> to the set of global minima of L(θ). This is our second main result, and is stated as follows. 




    Let Θ̂ = {θ∈Θ: L(θ) ≤ 0} and · denote L^2 norm. Under Assumptions <ref> and <ref>, we have 
    
    ∀ϵ>0, lim_k→∞(θ_k - Θ̂ > ϵ) = 0, 
            where   θ_k - Θ̂ = min_θ̂∈Θ̂θ_k-θ̂

    i.e., Algorithm 1 converges in probability to the set of global minimizers of L(θ)



    See Appendix <ref>



Theorem <ref> guarantees that Algorithm <ref> converges to a parameter θ̂ such that mechanism o_θ̂ induces an empirical dataset _θ̂ which is consistent with social optimality, i.e., satisfies (1) of Theorem <ref>. 

Thus, Algorithm <ref> provides a methodology for achieving adaptive mechanism design under basic assumptions on the game form G. In the following section, we implement Algorithm <ref> numerically and verify its efficacy in converging to the global minima of L(θ).
This follows since, by Theorem <ref>, L(θ̂)=0 is a necessary and sufficient condition for the existence of utility functions f^i(·,o_θ̂) under which the empirically observed responses _t(θ̂), t∈[T] are Pareto-optimal Nash equilibria.  




§ NUMERICAL IMPLEMENTATION


Here we numerically verify the efficacy of Algorithm <ref>. We implement the following 'river pollution game', as presented in <cit.>.  Three agents i=1,2,3 are located along a river. Each agent i is engaged in an economic activity that produces pollution as a level x_i, and the players must meet environmental conditions set by a local authority. Pollutants are expelled into a river, where they disperse. There are two monitoring stations l=1,2 along the river, at which the local authority has set the maximum pollutant concentration levels. The revenue for agent i is 

    R_i(x) = [d_1√(x_i) - d_2√(x_1+x_2+x_3)]
 where d_1,d_2 are parameters that determine an inverse demand law <cit.>. Agent i has expenditure 

    F_i(x) = (c_1i√(x_i) + c_2i x_i)

and thus has total profit 

    f^i(x) = [d_1√(x_i) - d_2√(x_1 + x_2 + x_3) - c_1i√(x_i) - c_2i x_i]


The local authority imposes the constraint on total polution levels at each monitoring site as 

    q_l(x_1,x_2,x_3) = ∑_i=1^3δ_ile_ix_i ≤ 100,    l=1,2

Parameters δ_il are transportation-decay coefficients from player i to location l, and e_i is the emission coefficient of player i. 

We take the perspective of the designer (local authority), who does not know the agent utility functions (<ref>), but can enforce the constraints (<ref>) and can modify the parameters d_2,c_1i,c_2i. Observe that the parameter vector [d_2, c_11,c_12,c_1,3,c_21,c_22,c_23] ∈^7 can be treated as a mechanism, since it modifies the agent utility functions and can be controlled by the designer. Also, the parameter vector [e_1,e_2,e_3] ∈^3 can be used to modify the constraint functions, and "probe" the system, as discussed in Section <ref>. 

Furthermore, observe that the utility functions (<ref>) and constraints (<ref>) satisfy assumptions <ref> and <ref>. The utility functions (<ref>) are potential modifiable, as setting d_1=c_1i=c_2i=0 yields a trivial potential game. We emphasize that this potential modifiability condition is a sufficient condition for the existence of a mechanism inducing socially optimal Nash equilibria. However, in practice it is unlikely that this is also a necessary condition; we verify numerically that the algorithm converges to a non-trivial mechanism which does not correspond to a potential game. 

We implement Algorithm <ref> in Matlab. The non-cooperative game-enactment in steps 14-15 is achieved by the NIRA-3 Matlab package <cit.>, which employs the relaxation algorithm and Nikaido-Isoda function to compute Nash equilibrium solutions. We then utilize the standard Matlab linear program solver to compute the optimization in lines 17-18. We set the lower bound on L(θ) to 0, so that the Nash equilibria are consistent with social optimality if and only if L(θ)=0. We take the constraint functions (<ref>) as generated by random parameters γ_t = [e_1,e_2,e_3] ∼ U[0,1]^3 for each t∈[T], i.e., each e_i is uniformly distributed on [0,1]. The remainder of the algorithm is implemented with ease: we take p=7,c=a=0.5,η=1/4, q=0.001, T=10.  

As mentioned, we take mechanism parameter θ = [d_2, c_11,c_12,c_1,3,c_21,c_22,c_23] and Θ = [0,1]^7, that is, each element of θ is restricted to the unit interval [0,1]. We initialize θ_1 as a 7-dimensional uniform random variable in [0,0.5], and iterate Algorithm <ref> until L(θ)=0. Figure <ref> illustrates the iterative value of r (<ref>), corresponding to L(θ_n), as a function of n.





Figure <ref> demonstrates that Algorithm <ref> converges to a parameter θ_59 at iteration n=59 such that the empirical dataset _θ_59 produces L(θ)=0, and is thus consistent with social optimality in the sense of Theorem <ref>. Table <ref> contains the parameter θ_n values for n=1 and n=59. It can be observed that θ_59 does not induce a potential game, and thus the social optimality convergence is non-trivial. 




§ CONCLUSION


We have provided a novel methodology for achieving mechanism design when the agent utility functions are unknown to the designer. We first generalized a seminal result in microeconomic revealed preferences, giving necessary and sufficient conditions for Nash equilibria behavior to be consistent with social optimality. Then, we utilized this to construct a loss function which has global minima corresponding to mechanisms inducing socially optimal Nash equilibria. We proved that a simulated annealing-based gradient algorithm will converge in probability to the set of global minima of this loss function, and thus will allow us to achieve adaptive mechanism design. We also demonstrated the algorithm's efficacy numerically in a standard non-cooperative game setting. 



IEEEtran







§ APPENDIX



A dataset {α_t∈^n, ∈^n} satisfied GARP if there exist relations  and  such that:

    
  - if (α_s^i)'≥ (α_s^i)', then 
    
  -if x_u, x_u  x_v, …, x_z for some (possibly empty) sequence (u,v,…,z), then 
    
  - if , then (α_t^i)'≤ (α_t^i)'



Nonlinear GARP <cit.>




 §.§ Proof of Theorem <ref>



    (1 ⇒ 2): Assume (<ref>) holds. We have that  solves:
    
    max_∑_i=1^^i()  s.t  ^i() ≤ 0    ∀ i∈[]

    By concavity, the functions ^i(·) are subdifferentiable, and thus the sum ∑_i=1^(·) is subdifferentiable. Then, letting ^i be the Lagrange multiplier associated with budget constraint g_t^i(·), an optimal solution  to the maximization problem (<ref>) must satisfy
    ∑_i=1^ = ∑_i=1^^i
    where  and  are subgradients of  and  evaluated at . Let 
    
    λ_t^i    := (∑_i=1^^i_∞ + ∑_j≠ i∇f̂^j()_∞)/min_k∈[n]|()_k|
    _t^i    :=

    and observe that for each i ∈ [], 
    
    ≤λ_t^i _t^i

    Next, concavity of the functions ^i implies for each i
    
    ^i() - ^i() ≤'( - )

    Substituting inequality (<ref>) into (<ref>), and setting v_s^i = ^i(),  v_t^i = ^i(), we obtain v_s^i - v_t^i ≤λ_t^i(_t^i)' ( - )
   
    
    
    Thus the set {_t^i, , t ∈[T] } satisfies the linear 'Generalizes Axiom of revealed preference' (GARP) <cit.> for each i ∈. We will show that this implies the dataset {^i,, t ∈ [T]} satisfies nonlinear GARP <cit.>. First, assume g_t^i() < 0. Since g_t^i() = 0 we have g_t^i() < g_t^i(), and thus '( - ) ≤ 0 by monotonicity of g_t^i. So (_t^i)'  < (_t^i)'. Then by inverting this implication, we obtain _t^i ≥_t^i ⇒ g_t^i() ≥ 0.
    
    Since the linear GARP is satisfied for all i∈[] we have the relation
    
    R ⇒_t^i≤_t^i⇒ g_t^i() ≥ 0

    and thus {g_t^i, , t ∈ [T]} satisfies nonlinear GARP for all i∈[]. So, by <cit.> we have that there for each i ∈ [M], there exist u_t^i ∈, λ_t^i > 0 such that (<ref>) holds. 


    (2 ⇒ 1): Assume (<ref>) holds, take γ such that g_t^i(γ) ≤ g_t^i() = 0  ∀ i ∈ [M] and define
    
    U^i(γ) = min_s ∈ [T][u_s^i + λ_s^i[g_s^i(γ)] ]

    In <cit.> it is shown that we can set u_t^i = U^i(). Then we have that
    
    ∑_i=1^ U^i(γ) ≤∑_i=1^[u_t^i + λ_t^i g_t^i(γ) ] ≤∑_i=1^M U^i().

    
    Without losing generality, take ^i = 1/λ_t^i, we obtain 
    
    ∑_i=1^^i U^i(γ) ≤∑_i=1^M ^i u_t^i + ∑_i=1^ g_t^i(γ)

    and thus we have
    
    ∑_i=1^^i U^i(γ) ≤∑_i=1^M u_t^i = ∑_i=1^^i U^i()

    and so  solves the optimization problem 
    
    max_γ∑_i=1^^i U^i(γ)    :    g_t^i(γ) ≤ 0

    and so from relation (<ref>) we know that {} satisfies (<ref>).
    




 §.§ Proof of Theorem <ref>



Having the constraint sets generated via parameters {γ_t}_t=1^T, where each γ_t is a random variable from set Γ, the loss function becomes:

    L(θ) =    min_r    s.t.   ∃ {u_t^i,λ_t^i}: 
       u_s^i - u_t^i - λ_t^i g_t^i(_s(θ), γ_t) ≤ r   ∀ t,s,i

where _s(θ) is a Nash equilibrium solution for the game with mechanism o_θ and feasible sets _i = {a: g_s^i(a, γ_t) ≤ 0}. 

We show that the loss function L(θ) and algorithm iterates satisfy assumptions H1-H8 of <cit.>. 

H1: Δ_n is distributed according to the p-dimensional Rademacher distribution, and thus the conditions are satisfied. 

H2: We do not have random measurement noise in this framework. Thus the conditions are satisfied. 

H3: 
Let θ = [θ_1,…,θ_p]. By Faá de Bruni's formula, the third derivative of L(θ) with respect to θ_k, k∈[p] can be decomposed as the combinatorial form:

    ^3 L(θ)/θ_k^3
       =∑_t,i∑_π∈Π^|π|L(g_t^i(_s(θ),γ_t))/ g_t^i(_s(θ),γ_t) ^|π|·∏_B∈π^|B|g_t^i(_s(θ),γ_t))/θ_k^|B|

where π iterates through the set of partitions Π of the set {1,2,3}, B∈π is an element of partition π, and |π|, |B| indicate the cardinality of said partitions and elements, respectively. We need to show that (<ref>) exists and is continuous for all k∈ [p]. 

Now, for notational simplicity re-write g_t^i(_s(θ),γ_t)) as g_t,s,i and consider the term
^nL(g_t,s,i)/ g_t,s,i^n for some n∈[3]. This expresses the n-th order derivative of the solution to the linear program (<ref>) with respect to real number g_t,s,i. Fortunately we can obtain a useful bound on this value by the methodology in <cit.>. Specifically, we can re-write the linear program (<ref>) as 

    maximize  L(g_t,s,i) = c· x   s.t.   Ax = 0,    x ≥ 0

where x = [c,u_1^1,…,u_T^M,λ_1^1,…,λ_T^M]^T ∈^2TM+1, c = [-1,0,…,0] ∈^2TM+1 and A is a matrix of coefficients that produces the equalities
u_s^i - u_t^i - λ_t^i g_t,s,i - r = 0     ∀ s,t,i.


    x = [c,u_1^1,…,u_T^M,λ_1^1,…,λ_T^M]^T ∈^2TM+1
       c = [-1,0,…,0] ∈^2TM+1





Then, letting β⊂ [2TM+1], denote A_β as the submatrix of A with columns corresponding to elements of β, such that A_β is nonsingular. Form x̂_β be the basic primal solution to (<ref>) with the i'th element of x̂_β equal to zero for i∈[2TM+1]\β. Also let G_β be the matrix A_β with all elements apart from g_t,s,i replaced by zero. Then by Theorem 1 of <cit.>, we have that for n∈[3], L(g_t,s,i) is n-times differentiable, with derivatives given by
^n L(g_t,s,i)/ g_t,s,i^n = (n!)c(-A_β^-1G_β)^nx̂_β
and for g∈ sufficiently close to g_t,s,i,
^n L(g)/ g^n = ∑_i=n^∞i!/(i-n)!c(g-g_t.s,i)^(i-n)(-B^-1G_β)^ix̂_β

This reveals that the L(g_t,s,i) is n-times continuously differentiable for n∈[3]. 

Now, with {â_1,s(θ),…,â_,s(θ)} = _s(θ) expressing the full vector of actions making up the Nash equilibrium _s(θ), consider the term 
^ng_t^i(_s(θ),γ_t))/θ_k^n = ^ng_t^i(â_i,s(θ),γ_t))/θ_k^n for n∈[3], where the equality holds since the constraint function g_t^i(·) only depends on action a_i. This term can again be decomposed using Faá de Bruni's formula as = ^ng_t^i(â_i,s(θ),γ_t))/θ_k^n=∑_π∈Π∑_j^|π|g_t^i(â_i,j,s(θ),γ_t)/â_i,j,s(θ_k)^|π|·∏_B∈π^|B|â_i,j,s(θ)/θ_k^|B| 


    ^ng_t^i(â_i,s(θ),γ_t))/θ_k^n
             =∑_π∈Π∑_j^|π|g_t^i(â_i,j,s(θ),γ_t)/â_i,j,s(θ_k)^|π|·∏_B∈π^|B|â_i,j,s(θ)/θ_k^|B|


with Π being the partitions of [n] here. The constraint function derivatives are bounded by assumption <ref>. The term 
^|B|â_i,j,s(θ)/θ_k^|B|expresses the sensitivity of a Nash equilibrium solution to changes in the underlying utility function parameters. 

Let (θ) = {a_i} be a Nash equilibrium solution for the game [G], where a_i = {a_i,1,…,a_i,k}∈^k is the action of player i. Let us begin by decomposing
^n f^i_θ((θ))/θ_k^n = ∑_π∈Π^|π|f_θ^i((θ))/(θ)^|π|·∏_B∈π^|B|(θ)/θ_k^|B|
where again Π is the set of partitions of [n]. Begin with the base case n=1. Then, 
f_θ^i(a_i,j(θ))/θ_k =  f_θ^i(a_i,j(θ))/ a_i,j(θ) a_i,j(θ)/θ_k
and

    a_i,j(θ)/θ_k =  f_θ^i(a_i,j(θ))/θ_k( f_θ^i(a_i,j(θ))/ a_i,j(θ))^-1

and thus by assumption <ref>, (<ref>) is continuous. Now, assume ^n_i,j(θ)/θ_k^n is continuous for some n. Then, by decomposition 
^n+1 f^i_θ(a_i,j(θ))/θ_k^n+1 = ∑_π∈Π^|π|f_θ^i(a_i,j(θ))/ a_i,j(θ)^|π|·∏_B∈π^|B|a_i,j(θ)/θ_k^|B|
we have that ^n+1_i,j(θ)/θ_k^n+1 can be isolated and expressed as a polynomial in terms ^m f^i_θ(a_i,j(θ)/ a_i,j(θ)^m, m∈ [n], ^m a_i,j(θ)/θ_k ^m, m∈[n-1], and thus by the assumption <ref>, and the induction base, this term is also continuous. 

Furthermore, observe that the n-th order derivatives are all bounded by their expressions in the previous derivations and assumption <ref>.


H4: The algorithm parameters are taken to satisfy these conditions

H5: Our algorithm is isolated to the compact set Θ, eliminating the necessity of asymptotic objective function structure such as this requirement. 

H6: This is satisfied.

H7: Let P_η be a parametrized probability measure over the parameter space Θ, defined by the Radon-Nikodym derivative 
dP_η(θ)/dθ = exp(-2L(θ)/η^2)/Z_η
where η>0 and Z_η = ∫_Θexp(-2L(θ)/η^2)dθ < ∞ is a normalizing term. Then the unique weak limit P = lim_η→ 0P_η is given by an indicator on points in the set Θ̂ := {θ : L(θ) = 0}, i.e.,
P(θ) = χ_θ∈Θ̂ / Z_0
with χ the indicator function and Z_0 = ∫_Θχ_θ∈Θ̂dθ.


H8: The sequence is trivially tight, since P(θ_k ∈Θ) = 1  ∀ k∈

