betaFeedback

WorksComputer Science

Learning Global Equilibria in Non-Concave Prospect Theoretic Games

Abstract

Human agents in non cooperative games often exhibit non rational behaviour. Prospect theory provides a behavioural framework to capture how agents perceive gains and losses under risk, but, its incorporation into games typically leads to non concave and non convex utility functions, making equilibrium computation challenging. In such cases, it is difficult to obtain algorithms that have global convergence behaviour. This paper proposes a learning algorithm which uses minorization-maximization (MM). Under a proximal Polyak-Lojasiewicz (PL) condition on the potential function, we establish global convergence of the algorithm to a potential-maximizing Nash equilibrium. We further show how the structure of the MM minorizer can be used to enable a distributed implementation of the algorithm. With additional noise injection, the individual updates of the agents can be obscured, while still ensuring global convergence.

Introduction

Non cooperative games have been used successfully to model various problems that arise in areas such as engineering and economics. The classical framework of expected utility maximization has been used predominantly in these works. Usually, these generally assume fully rational agents. However, human agents exhibit a number of non rational behaviours, which reflect in their game play and decision making. Consequently, there have been a number of different approaches that sought to incorporate bounded rational behaviour of human agents in games. Prospect theory (PT) emerged as a framework for capturing systematic departures from expected utility maximization in human decision-making under risk.

A number of papers have used PT in game theory. However, the utility model under PT tends to be in general non-concave and non-smooth. This makes it difficult to directly apply a number of existing game theoretic tools and learning algorithms. In this paper, we consider a non cooperative game model, with agents taking actions from continuous, compact sets. The game is a potential game, and the utility is assumed to be continuously differentiable. However, no assumption is made on the concavity (or convexity) of the utility function (and consequently, the potential function). A learning approach based on minorization-maximization (MM) is proposed. It is shown that the minorization functions can be chosen such that the MM learning approach converges to a potential maximizing Nash equilibrium. The result hinges on the potential function obeying a proximal Polyak-Łojasiewicz (PŁ) inequality, which ensures that stationary points over the strategy set are maximizers of the potential.

In many applications, agents may be reluctant to share information about their personal preferences with other agents. Prospect-theoretic value functions encode such preferences by capturing how agents perceive and evaluate outcomes under risk. In this paper, we provide an MM algorithm, that can be implemented in a distributed fashion, with noise injected to limit the disclosure of their private preferences. Thus, in non-concave games, it is possible to develop learning algorithms that are distributed and still have global convergence guarantees.

Literature Review

Prospect theory [1] and its cumulative version [2] have been incorporated in non-cooperative games in several ways. Equilibrium notions for agents with PT and CPT preferences, and their existence and properties, have been studied in [3, 4, 5], which show that probability weighting can substantially change the structure of the equilibrium set. Learning in repeated games with CPT agents was considered in [6], where calibrated learning is shown to converge to a set of CPT correlated equilibria. PT has also been used in engineering applications, for instance to model prosumers in smart grid energy management [7]. These works mostly consider finite action sets or specific game structures; in contrast, we consider continuous action sets and study learning dynamics with global convergence guarantees to Nash equilibria.

In continuous games, convergence of learning dynamics is typically established under concavity or monotonicity of the utilities [8, 9]. Without such assumptions, gradient-based learning may fail to converge, or may avoid some Nash equilibria [10]. In [11], the authors propose the use of local Nash equilibria to study non-concave, non-smooth games. Potential games [12] have the useful property that learning in the game can be related to the optimization of the potential function [13]; however, when the potential is non-concave, only convergence to stationary points can be expected in general. The Polyak-Łojasiewicz (PŁ) inequality [14] provides a way of obtaining global convergence without concavity, with linear rates for gradient and proximal-gradient methods under its proximal version [15]. In games, a two-sided PŁ condition has been used to obtain global convergence of gradient methods in non convex-non concave minimax problems [16]. Here, we use the proximal PŁ inequality on the potential function of a game with PT utilities.

MM algorithms [17, 18] successively optimize surrogate functions that bound the objective and are tight at the current iterate. For non convex problems, their convergence to stationary points has been established under general conditions [19, 20]. In multi-agent problems, surrogates obtained by partially linearizing the objective lead to decompositions that can be solved in parallel by the agents [21]. Our minorizer follows a similar idea: the coupling term is kept exact, while the individual PT terms, which encode private preferences, are linearized.

Distributed algorithms for computing Nash equilibria based on the alternating direction method of multipliers (ADMM) have been proposed in [22]. When the agents’ objectives are private, a common approach is to perturb the exchanged messages with noise, which leads to a trade-off between privacy and accuracy [23]; for such message perturbation schemes, exact convergence and privacy guarantees cannot be achieved simultaneously [24]. In this paper, the noisy ADMM is analyzed as an inexact maximization step within the MM scheme, which yields convergence guarantees when the noise variance decreases.

The main contributions of this paper are as follows.

  1. We propose an MM learning scheme for non-cooperative potential games with prospect theoretic, non concave potentials. We show that, when the potential satisfies a proximal PL inequality, the scheme converges at a linear rate to a potential maximizing Nash equilibrium.

  1. We construct a separable minorizer that allows the maximization step to be carried out in a distributed fashion using ADMM, in which each agent’s preferences enter only its own local update.

  1. We analyze MM with an inexact maximization step, and apply this analysis to a noisy ADMM in which agents perturb their updates to obscure their preferences. We show that the iterates converge when the noise variance decreases, up to an error that decays exponentially in the number of ADMM iterations.

Overview of Prospect Theory

We now present a high level overview of Prospect theory [1, 25]. Under the expected utility paradigm, a user evaluates their prospects based on expected utility. A prospect PP involves outcomes (x1,x2,…,xM)(x_1, x_2, \ldots, x_M) with a distribution (q1,…,qM)(q_1, \ldots, q_M), where the outcomes are ordered in increasing order of attractiveness. The expected utility is

E(P)≜∑m=1Mqmxm.(1)E(P) \triangleq\sum_{m=1}^{M} q_m x_m. \tag*{(1)}

Comparing PP to another prospect P~\widetilde{P} having outcomes (x~1,…,x~M)(\widetilde{x}_1, \ldots, \widetilde{x}_M) with distribution (q~1,…,q~M)(\widetilde{q}_1, \ldots, \widetilde{q}_M), involves a comparison between E(P)E(P) and E(P~)E(\widetilde{P}), and choosing the higher one.

Under PT, the perception of outcomes changes with respect to a reference point. Outcomes above this reference are seen as gains, and those below as losses. When faced with gains, agents will behave in a risk averse manner, and when faced with losses, agents tend to be risk seeking or risk neutral. This perception is captured by an outcome to value map vv, which, in order to model the above (and other) aspects of bounded rational behaviour, is assumed in general to be convex below a threshold, concave above it. One such function is depicted in Figure 1. Here the agents are risk averse for gains and risk seeking for losses, with the zero being the reference point that demarcates gains from losses.

Example of a prospect theoretic value function

Figure 1. Example of a prospect theoretic value function vv that maps outcomes to values.

In addition to the notion of value relative to risk, the weight accorded to outcomes is modified as well. The modified value of the prospect is

V(P)≜∑m=1Mσmv(xm),V(P) \triangleq\sum_{m=1}^{M} \sigma_m v(x_m),

where vv is a function similar to the one in Figure 1, and σm\sigma_m are the weights for the distorted outcomes, given by [25],

σ1=π(q1),σj=π(∑m=1jqm)−π(∑m=1j−1qm),j>1,(2)\sigma_1 = \pi(q_1),\quad\sigma_j = \pi\left(\sum_{m=1}^{j}q_m\right)-\pi\left(\sum_{m=1}^{j-1}q_m\right),\quad j>1, \tag*{(2)}

for an appropriate weighting function π\pi, which is monotone increasing and bounded between 0 and 1. This models the overweighting of small probabilities, and the under-weighting of large probabilities, for large outcomes. Faced with a choice between two prospects PP and P~\widetilde{P}, the agent will make a decision comparing their PT modified values V(P)V(P) and V(P~)V(\widetilde{P}), and choosing the better option. It is clear that these decisions are likely to be very different from those predicted by expected utility theory.

Game Model

We consider a game with N+1N+1 agents, of which NN play the game, while agent N+1N+1 acts as a coordinator between the agents. Let N≜{1,…,N}\mathcal{N} \triangleq\{1,\ldots,N\} denote the set of agents that participate in the game. Agent i∈Ni \in\mathcal{N} chooses its strategy xix_i from a convex and compact set Xi⊆R\mathcal{X}_i \subseteq\mathbb{R}. Let x≜(xi)i∈N\mathbf{x} \triangleq(x_i)_{i\in\mathcal{N}} denote the joint strategy vector, which is an element of X≜∏j=1NXj\mathcal{X} \triangleq\prod_{j=1}^{N}\mathcal{X}_j. The randomness in outcomes is modelled by a real valued random variable ξ\xi taking values over the set Ξ≜{ξ1,…,ξM}1\Xi\triangleq\{\xi_1,\ldots,\xi_M\}^{1} where 0<ξ1<⋯<ξM0<\xi_1<\cdots<\xi_M, with probability distribution q=(q1,…,qM)\mathbf{q}=(q_1,\ldots,q_M). Let Vi:R→RV_i:\mathbb{R}\to\mathbb{R}, i=1,…,Ni=1,\ldots,N and π:[0,1]→[0,1]\pi:[0,1]\to[0,1] be monotone increasing. The utility for user ii under the strategy x=(xi,x−i)\mathbf{x}=(x_i,\mathbf{x}_{-i}) where x−i≜(x1,…,xi−1,xi+1,…,xN)\mathbf{x}_{-i}\triangleq(x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_N), is given by

Ji(xi,x−i)≜aiJ(x)+Eσ[Vi∘Ri(xi,ξ)],(3)J_i(x_i,\mathbf{x}_{-i}) \triangleq a_i\mathcal{J}(\mathbf{x})+\mathbb{E}_{\sigma}[V_i\circ\mathcal{R}_i(x_i,\xi)], \tag*{(3)}

where 0<aN≤aN−1≤⋯≤a10<a_N\leq a_{N-1}\leq\cdots\leq a_1, and σ\sigma is the distribution generated from q\mathbf{q} by (2) using π\pi. This form of the utility function includes the following terms:

  1. A collective usage benefit J(x):X→R\mathcal{J}(\mathbf{x}):\mathcal{X}\to\mathbb{R}, which is a collective utility common to all agents.

  1. An individual random reward Ri(xi,ξ):Xi×Ξ→R\mathcal{R}_i(x_i,\xi):\mathcal{X}_i\times\Xi\to\mathbb{R}. This reward is random due to its dependence on ξ\xi, and is viewed subjectively through the PT value function ViV_i.

We assume that the functions J\mathcal{J}, ViV_i and Ri\mathcal{R}_i are continuous and smooth, for each ii.

Definition 1. We define the game G\mathcal{G} as the tuple (N,{Xj}j=1N,{Jj}j=1N,{Vj}j=1N,σ)(\mathcal{N},\{\mathcal{X}_j\}_{j=1}^{N},\{\mathcal{J}_j\}_{j=1}^{N},\{V_j\}_{j=1}^{N},\sigma).

Definition 2. A Nash equilibrium for G\mathcal{G} is any x∗≜(xi∗,x−i∗)=(x1∗,…,xN∗)∈X\mathbf{x}^{*}\triangleq(x_i^{*},\mathbf{x}_{-i}^{*})=(x_1^{*},\ldots,x_N^{*})\in\mathcal{X} such that for all i=1,…,Ni=1,\ldots,N,

Ji(xi∗,x−i∗)≥Ji(x,x−i∗),∀x∈Xi.(4)J_i(x_i^{*},\mathbf{x}_{-i}^{*})\geq J_i(x,\mathbf{x}_{-i}^{*}),\quad\forall x\in\mathcal{X}_i. \tag*{(4)}

Potential Structure

The game G\mathcal{G} is a weighted potential game [12], with weights aia_i and potential function

Φ(x)≜J(x)+∑j=1N1ajEσ[Vj∘Rj(xj,ξ)],(5)\Phi(\mathbf{x})\triangleq\mathcal{J}(\mathbf{x})+\sum_{j=1}^{N}\frac{1}{a_j}\mathbb{E}_{\sigma}[V_j\circ\mathcal{R}_j(x_j,\xi)], \tag*{(5)}

that is, Ji(xi,x−i)−Ji(x~i,x−i)=ai(Φ(xi,x−i)−Φ(x~i,x−i))J_i(x_i,\mathbf{x}_{-i})-J_i(\widetilde{x}_i,\mathbf{x}_{-i})=a_i(\Phi(x_i,\mathbf{x}_{-i})-\Phi(\widetilde{x}_i,\mathbf{x}_{-i})) for all ii, x∈X\mathbf{x}\in\mathcal{X} and x~i∈Xi\widetilde{x}_i\in\mathcal{X}_i. Since Φ\Phi is continuous and X\mathcal{X} is compact, the set of maxima

M≜arg max⁡x∈XΦ(x)(6)\mathcal{M}\triangleq\operatorname*{arg\,max}_{\mathbf{x}\in\mathcal{X}}\Phi(\mathbf{x}) \tag*{(6)}

is non empty, and every element of M\mathcal{M} is a Nash equilibrium [12]; we call such points potential optimal equilibria. Define the maximum value of the potential function and the optimality gap,

Φ∗=Φ(x) for some x∈M,g(x)≜Φ∗−Φ(x).(7)\Phi^* = \Phi(\mathbf{x}) \text{ for some } \mathbf{x} \in\mathcal{M}, \qquad g(\mathbf{x}) \triangleq\Phi^* - \Phi(\mathbf{x}). \tag*{(7)}

We make the following assumption.

Assumption 1 (Proximal PL Inequality). There exist μ>0\mu> 0 and Lˉ>0\bar{L} > 0 such that the potential function satisfies, for all x∈X\mathbf{x} \in\mathcal{X},

12DLˉ(x)≥μg(x),(8)\frac{1}{2}D_{\bar{L}}(\mathbf{x}) \geq\mu g(\mathbf{x}), \tag*{(8)}

where, for L>0L > 0,

DL(x)≜2Lmax⁡y∈X(⟨∇Φ(x),y−x⟩−L2∥y−x∥2).(9)D_L(\mathbf{x}) \triangleq2L \max_{\mathbf{y} \in\mathcal{X}} \left( \langle\nabla\Phi(\mathbf{x}), \mathbf{y} - \mathbf{x} \rangle- \frac{L}{2} \lVert\mathbf{y} - \mathbf{x} \rVert^2 \right). \tag*{(9)}

Assumption 1 is a generalization of the PL inequality to constrained problems [15]. The maximum in (9) is attained at y=ΠX(x+1L∇Φ(x))\mathbf{y} = \Pi_{\mathcal{X}}\left(\mathbf{x} + \frac{1}{L}\nabla\Phi(\mathbf{x})\right), where ΠX\Pi_{\mathcal{X}} denotes projection to the set X\mathcal{X}. The function DL(x)D_L(\mathbf{x}) satisfies DL(x)≥0D_L(\mathbf{x}) \geq0, with equality if and only if x\mathbf{x} is a stationary point of Φ\Phi over X\mathcal{X}, i.e., ⟨∇Φ(x),y−x⟩≤0\langle\nabla\Phi(\mathbf{x}), \mathbf{y} - \mathbf{x} \rangle\leq0 for all y∈X\mathbf{y} \in\mathcal{X}. Whenever the gradient step x+1L∇Φ(x)\mathbf{x} + \frac{1}{L}\nabla\Phi(\mathbf{x}) lies in X\mathcal{X} (in particular, if the constraints were absent), DL(x)=∥∇Φ(x)∥2D_L(\mathbf{x}) = \lVert\nabla\Phi(\mathbf{x}) \rVert^2, and (8) reduces to the classical PL inequality 12∥∇Φ(x)∥2≥μg(x)\frac{1}{2}\lVert\nabla\Phi(\mathbf{x}) \rVert^2 \geq\mu g(\mathbf{x}). The classical PL inequality ensures that all points with zero gradient are optimal points for unconstrained optimization. The proximal PL assumption ensures that every stationary point of Φ\Phi over X\mathcal{X}, including stationary points on the boundary of X\mathcal{X}, is also a maximizer. Thus, learning algorithms that move towards a stationary point are assured of reaching an optimum.

The following property of the function DLD_L will be used in subsequent results.

Lemma 1. For L1≥L2>0L_1 \geq L_2 > 0 and all x∈X\mathbf{x} \in\mathcal{X},

DL1(x)≥DL2(x).(10)D_{L_1}(\mathbf{x}) \geq D_{L_2}(\mathbf{x}). \tag*{(10)}

Proof.

DL(x)=max⁡y∈X(2L⟨∇Φ(x),y−x⟩−L2∥y−x∥2),(11)D_L(\mathbf{x}) = \max_{\mathbf{y} \in\mathcal{X}} \left(2L\langle\nabla\Phi(\mathbf{x}), \mathbf{y} - \mathbf{x}\rangle- L^2\lVert\mathbf{y} - \mathbf{x}\rVert^2\right), \tag*{(11)}
=max⁡z∈L(X−x)(2⟨∇Φ(x),z⟩−∥z∥2).(12)= \max_{\mathbf{z} \in L(\mathcal{X}-\mathbf{x})} \left(2\langle\nabla\Phi(\mathbf{x}), \mathbf{z}\rangle- \lVert\mathbf{z}\rVert^2\right). \tag*{(12)}

The result follows by observing that any element in the set L2(X−x)L_2(\mathcal{X}-\mathbf{x}) is contained in the set L1(X−x)L_1(\mathcal{X}-\mathbf{x}).

Convergence under the Proximal PŁ Condition

Definition 3 (MM Learning). Consider the sequence of joint strategies (x(k),k≥0)(x(k), k \ge0), where

x(k+1)=arg⁡x∈Xmax⁡ϕ(x∣x(k)),(13)x(k+1)=\arg_{x\in\mathcal{X}}\max\phi(x\mid x(k)), \tag*{(13)}

where ϕ(⋅∣x(k))\phi(\cdot\mid x(k)) is the minorizing function at iteration kk, which is any function that satisfies,

  1. ϕ(x∣x(k))≤Φ(x), ∀x∈X,\phi(x\mid x(k))\le\Phi(x),\ \forall x\in\mathcal{X},

  2. ϕ(x(k)∣x(k))=Φ(x(k))\phi(x(k)\mid x(k))=\Phi(x(k)).

The initial point x(0)∈Xx(0)\in\mathcal{X}.

For a non concave function, this MM algorithm converges to a stationary point [20]. Convergence to global maximum can be ensured under further assumptions.

Assumption 2. The minorizer ϕ(x∣y)\phi(x\mid y) is differentiable and strongly concave in xx, with modulus β>0\beta>0, and its gradient ∇ϕ(⋅∣y)\nabla\phi(\cdot\mid y) is BB-Lipschitz, uniformly over yy. Moreover, for every y∈Xy\in\mathcal{X}, the minorizer is tangent to the potential at yy, i.e., ∇ϕ(y∣y)=∇Φ(y)\nabla\phi(y\mid y)=\nabla\Phi(y).

Theorem 2. Under Assumptions 1 and 2, the MM learning scheme converges to a potential maximizing Nash equilibrium. Moreover, with L~≜max⁡(B,Lˉ)\tilde{L}\triangleq\max(B,\bar{L}), the optimality gap

g(x(k))≤(1−μL~)kg(x(0)).(14)g(x(k))\le\left(1-\frac{\mu}{\tilde{L}}\right)^k g(x(0)). \tag*{(14)}

Proof. Since the minorizer is strongly concave with modulus β\beta, we have, for every u,w\mathbf{u},\mathbf{w},

ϕ(u∣y)−ϕ(w∣y)≤⟨u−w,∇ϕ(w∣y)⟩−β2∥u−w∥2.(15)\phi(\mathbf{u}\mid\mathbf{y})-\phi(\mathbf{w}\mid\mathbf{y})\le\langle\mathbf{u}-\mathbf{w},\nabla\phi(\mathbf{w}\mid\mathbf{y})\rangle-\frac{\beta}{2}\lVert\mathbf{u}-\mathbf{w}\rVert^2. \tag*{(15)}

Since x(k+1)x(k+1) maximizes the concave function ϕ(⋅∣x(k))\phi(\cdot\mid x(k)) over the convex set X\mathcal{X}, it satisfies the first order optimality condition ⟨u−x(k+1),∇ϕ(x(k+1)∣x(k))⟩≤0\langle\mathbf{u}-x(k+1),\nabla\phi(x(k+1)\mid x(k))\rangle\le0 for all u∈X\mathbf{u}\in\mathcal{X}. Using (15) with u=x(k)\mathbf{u}=x(k), w=x(k+1)\mathbf{w}=x(k+1) and y=x(k)\mathbf{y}=x(k), we obtain

ϕ(x(k)∣x(k))+β2∥x(k)−x(k+1)∥2≤ϕ(x(k+1)∣x(k)).\phi(x(k)\mid x(k))+\frac{\beta}{2}\lVert x(k)-x(k+1)\rVert^2\le\phi(x(k+1)\mid x(k)).

This implies,

Φ(x(k+1))≥ϕ(x(k+1)∣x(k)),≥ϕ(x(k)∣x(k))+β2∥x(k)−x(k+1)∥2,=Φ(x(k))+β2∥x(k)−x(k+1)∥2.\begin{aligned} \Phi(x(k+1))&\ge\phi(x(k+1)\mid x(k)),\\ &\ge\phi(x(k)\mid x(k))+\frac{\beta}{2}\lVert x(k)-x(k+1)\rVert^2,\\ &=\Phi(x(k))+\frac{\beta}{2}\lVert x(k)-x(k+1)\rVert^2. \end{aligned}

Hence,

g(x(k))−g(x(k+1))≥β2∥x(k+1)−x(k)∥2.(16)g(\mathbf{x}(k)) - g(\mathbf{x}(k+1)) \ge\frac{\beta}{2}\lVert\mathbf{x}(k+1)-\mathbf{x}(k)\rVert^2. \tag*{(16)}

Following the argument of [15 Theorem 5], fix y∈X\mathbf{y} \in\mathcal{X}. Then,

ϕ(x∣y)≥ϕ(y∣y)+⟨∇ϕ(y∣y),x−y⟩−B2∥x−y∥2,(17)\phi(\mathbf{x}|\mathbf{y}) \ge\phi(\mathbf{y}|\mathbf{y}) + \langle\nabla\phi(\mathbf{y}|\mathbf{y}),\mathbf{x}-\mathbf{y}\rangle- \frac{B}{2}\lVert\mathbf{x}-\mathbf{y}\rVert^2, \tag*{(17)}
≥Φ(y)+⟨∇Φ(y),x−y⟩−L~2∥x−y∥2(18)\ge\Phi(\mathbf{y}) + \langle\nabla\Phi(\mathbf{y}),\mathbf{x}-\mathbf{y}\rangle- \frac{\widetilde{L}}{2}\lVert\mathbf{x}-\mathbf{y}\rVert^2 \tag*{(18)}

where we used ϕ(y∣y)=Φ(y)\phi(\mathbf{y}|\mathbf{y}) = \Phi(\mathbf{y}) and Assumption 2. Taking y=x(k)\mathbf{y} = \mathbf{x}(k) and maximizing both sides over x∈X\mathbf{x} \in\mathcal{X}, we obtain, using the definition (9),

Φ(x(k+1))≥ϕ(x(k+1)∣x(k))=max⁡x∈Xϕ(x∣x(k)),(19)\Phi(\mathbf{x}(k+1)) \ge\phi(\mathbf{x}(k+1)|\mathbf{x}(k)) = \max_{\mathbf{x}\in\mathcal{X}}\phi(\mathbf{x}|\mathbf{x}(k)), \tag*{(19)}
≥Φ(x(k))+12L~DL~(x(k)).(20)\ge\Phi(\mathbf{x}(k)) + \frac{1}{2\widetilde{L}}\mathcal{D}_{\widetilde{L}}(\mathbf{x}(k)). \tag*{(20)}

Using Lemma 1 and Assumption 1, we get

g(x(k))−g(x(k+1))=Φ(x(k+1))−Φ(x(k)),(21)g(\mathbf{x}(k)) - g(\mathbf{x}(k+1)) = \Phi(\mathbf{x}(k+1)) - \Phi(\mathbf{x}(k)), \tag*{(21)}
≥μL~g(x(k)).(22)\ge\frac{\mu}{\widetilde{L}}g(\mathbf{x}(k)). \tag*{(22)}

This yields g(x(k+1))≤(1−μL~)g(x(k))g(\mathbf{x}(k+1)) \le\left(1-\frac{\mu}{\widetilde{L}}\right)g(\mathbf{x}(k)), where μ≤L~\mu\le\widetilde{L} since g≥0g \ge0, and therefore

g(x(k))≤(1−μL~)kg(x(0)).(23)g(\mathbf{x}(k)) \le\left(1-\frac{\mu}{\widetilde{L}}\right)^k g(\mathbf{x}(0)). \tag*{(23)}

As k→∞k \to\infty, g(x(k))→0g(\mathbf{x}(k)) \to0, and hence, Φ(x(k))→Φ∗\Phi(\mathbf{x}(k)) \to\Phi^*. From (16) and using the fact that g(x(k))g(\mathbf{x}(k)) is non negative and decreasing, we can write

∥x(k+1)−x(k)∥≤2βg(x(k)),(24)\lVert\mathbf{x}(k+1)-\mathbf{x}(k)\rVert\le\sqrt{\frac{2}{\beta}g(\mathbf{x}(k))}, \tag*{(24)}
≤2g(x(0))β(1−μL~)k2.(25)\le\sqrt{\frac{2g(\mathbf{x}(0))}{\beta}}\left(1-\frac{\mu}{\widetilde{L}}\right)^{\frac{k}{2}}. \tag*{(25)}

Thus (x(k))k≥0(\mathbf{x}(k))_{k\geq0} is Cauchy, and converges to some x^\hat{\mathbf{x}}. Since Φ(x(k))\Phi(\mathbf{x}(k)) converges to Φ∗\Phi^*, it follows that x^\hat{\mathbf{x}} is a maximizer of the potential function Φ(x)\Phi(\mathbf{x}).

Privacy Aware MM

While the minorizer ϕ\phi has to be designed keeping the requirements of Theorem 2 in mind, maximization of the minorizer (which is to be done in every iteration of the MM algorithm), can itself be implemented in a partially distributed fashion. The need for a distributed implementation stems from the fact that agents’ individual reward functions encode information about their personal preferences through their prospect-theoretic value functions, which they may be reluctant to disclose to other agents.

A minorizer that enables distributed optimization at each iteration, while limiting the disclosure of agents’ preference information to one another, is obtained by keeping the collective term J\mathcal{J} exact and linearizing only the individual terms. Write the potential as

Φ(x)=J(x)+∑i=1Nfi(xi),(26)\Phi(\mathbf{x}) = \mathcal{J}(\mathbf{x}) + \sum_{i=1}^{N} f_i(x_i), \tag*{(26)}

with fi(xi)≜1aiEσ[Vi∘Ri(xi,ξ)]f_i(x_i) \triangleq\frac{1}{a_i}\mathbb{E}_{\sigma}[V_i \circ R_i(x_i,\xi)], and consider

ϕ(x∣y)=J(x)+∑i=1Nhi(xi,yi),(27)\phi(\mathbf{x}|\mathbf{y}) = \mathcal{J}(\mathbf{x}) + \sum_{i=1}^{N} h_i(x_i,y_i), \tag*{(27)}

where

hi(xi,yi)=fi(yi)+fi′(yi)(xi−yi)−α2(xi−yi)2.(28)h_i(x_i,y_i) = f_i(y_i) + f_i^{\prime}(y_i)(x_i-y_i) - \frac{\alpha}{2}(x_i-y_i)^2. \tag*{(28)}

If each fi′f_i^{\prime} is α\alpha-Lipschitz, the descent lemma [26 Lemma 1.2.3] gives hi(xi,yi)≤fi(xi)h_i(x_i,y_i) \leq f_i(x_i), with equality at xi=yix_i = y_i, so that (27) is a minorizer of Φ\Phi. Since ∇ϕ(y∣y)=∇J(y)+(f1′(y1),…,fN′(yN))=∇Φ(y)\nabla\phi(\mathbf{y}|\mathbf{y}) = \nabla\mathcal{J}(\mathbf{y}) + (f_1^{\prime}(y_1),\ldots,f_N^{\prime}(y_N)) = \nabla\Phi(\mathbf{y}), it is tangent to Φ\Phi, and if J\mathcal{J} is concave with LJL_{\mathcal{J}}-Lipschitz gradient, it satisfies Assumption 2 with β≥α\beta\geq\alpha and B=α+LJB = \alpha+ L_{\mathcal{J}}. Thus, there is a separable structure in the minorizer: the collective term J\mathcal{J} couples the agents, while each hih_i depends only on the strategy and on the PT preferences of agent ii. If J\mathcal{J} is a separable function, then the optimization becomes completely separable, and can be solved in a distributed manner. Linearizing the whole potential instead would make the MM step a projected gradient step [15], but would not preserve this separable structure.

Noisy Alternating Direction Method of Multipliers (ADMM) Method

An ADMM based approach can be used to maximize (27) if the functions J\mathcal{J} and hih_i are concave. To limit the information revealed to other agents, each agent can inject noise into its individual updates, thereby making its state variables less directly observable. For a concave function ff, define the proximal operator,

prox⁡λf(u)=arg⁡max⁡x(f(x)−12λ∥x−u∥2).(29)\operatorname{prox}_{\lambda f}(\mathbf{u}) = \underset{\mathbf{x}}{\arg\max}\left(f(\mathbf{x}) - \frac{1}{2\lambda}\lVert\mathbf{x} - \mathbf{u} \rVert^2\right). \tag*{(29)}

The ADMM algorithm [27] is

xt+1=prox⁡λJ(zt−vt),(30)\mathbf{x}^{t+1} = \operatorname{prox}_{\lambda\mathcal{J}}(\mathbf{z}^{t} - \mathbf{v}^{t}), \tag*{(30)}
zit+1=prox⁡λhi(xit+1+vit)+ηit+1,i=1,…,N,(31)z_i^{t+1} = \operatorname{prox}_{\lambda h_i}(x_i^{t+1} + v_i^{t}) + \eta_i^{t+1},\quad i = 1,\ldots,N, \tag*{(31)}
vt+1=vt+xt+1−zt+1.(32)\mathbf{v}^{t+1} = \mathbf{v}^{t} + \mathbf{x}^{t+1} - \mathbf{z}^{t+1}. \tag*{(32)}

The first step is generally centralized (unless J\mathcal{J} is separable) and is performed by agent N+1N+1. The other two steps can be carried out by the agents in a distributed fashion. Importantly, the individual prospect-theoretic value functions fif_i encode agents’ personal preferences, through parameters that characterize how they evaluate outcomes under risk. Their derivatives fi′(yi)f_i'(y_i), which enter the individual updates, may therefore reveal information about these preferences. To limit such disclosure, agents inject noise ηi\eta_i into their updates, so that the messages sent to the coordinator do not reveal the exact values of fi′(yi)f_i'(y_i). As shown in § 5, convergence to Φ∗\Phi^* requires the variance of this noise to decrease over the MM iterations.

Convergence with an Inexact MM Step

The noisy ADMM of § 4 can be considered an MM scheme where the optimization in the MM step returns an answer with error. We first show that MM can tolerate certain errors and then show that the noisy ADMM produces errors of the required kind, under assumptions on the collective benefit J\mathcal{J}.

Throughout, L~=max⁡(B,Lˉ)\widetilde{L}=\max(B,\bar{L}), and

ζ(y)≜arg⁡x∈Xmax⁡ϕ(x∣y)(33)\zeta(y) \triangleq\arg_{x\in\mathcal{X}} \max\phi(x\mid y) \tag*{(33)}

denotes the exact maximization step in the MM algorithm. From Assumption 2, it follows that this is unique.

MM maximization with error

The error of the inexact MM step is

ek≜x(k+1)−ζ(x(k)).(34)e_k \triangleq x(k+1)-\zeta(x(k)). \tag*{(34)}

Let Fk\mathcal{F}_k denote the history of the algorithm up to x(k)x(k). We also define

G≜sup⁡y∈X∥∇ϕ(ζ(y)∣y)∥.(35)G \triangleq\sup_{y\in\mathcal{X}}\|\nabla\phi(\zeta(y)\mid y)\|. \tag*{(35)}

By the BB-Lipschitz gradient and the tangency of ϕ\phi (Assumption 2), ∥∇ϕ(ζ(y)∣y)∥≤∥∇Φ(y)∥+B∥ζ(y)−y∥\|\nabla\phi(\zeta(y)\mid y)\|\leq\|\nabla\Phi(y)\|+B\|\zeta(y)-y\|, so that G≤sup⁡x∈X∥∇Φ(x)∥+Bdiam⁡(X)<∞G\leq\sup_{x\in\mathcal{X}}\|\nabla\Phi(x)\|+B\operatorname{diam}(\mathcal{X})<\infty. Moreover, G=0G=0 when ζ(y)\zeta(y) lies in the interior of X\mathcal{X} for every yy, since ∇ϕ(ζ(y)∣y)=0\nabla\phi(\zeta(y)\mid y)=0 at an interior maximizer.

Theorem 3 (MM with error). Let Assumptions 1 and 2 hold, let ρ≜1−μLˉ\rho\triangleq1-\frac{\mu}{\bar{L}}, and suppose that (E[∥ek∥2∣Fk])1/2≤εk\left(\mathbb{E}\left[\|e_k\|^2\mid\mathcal{F}_k\right]\right)^{1/2}\leq\varepsilon_k for a deterministic sequence (εk)(\varepsilon_k). Then

E g(x(k))≤ρkg(x(0))+∑j=0k−1ρk−1−j(Gεj+B2εj2).(36)\mathbb{E}\,g(x(k))\leq\rho^k g(x(0))+\sum_{j=0}^{k-1}\rho^{k-1-j}\left(G\varepsilon_j+\frac{B}{2}\varepsilon_j^2\right). \tag*{(36)}

and, with εˉ≜lim sup⁡kεk\bar{\varepsilon} \triangleq\limsup_{k} \varepsilon_k,

lim sup⁡k→∞E g(x(k))≤L~μ(Gεˉ+B2εˉ2).(37)\limsup_{k \to\infty} \mathbb{E}\,g(\mathbf{x}(k)) \le\frac{\tilde{L}}{\mu}\left(G\bar{\varepsilon}+\frac{B}{2}\bar{\varepsilon}^{2}\right). \tag*{(37)}

In particular, E g(x(k))→0\mathbb{E}\,g(\mathbf{x}(k)) \to0 if εk→0\varepsilon_k \to0.

Proof. Fix kk, and write y=x(k)\mathbf{y}=\mathbf{x}(k) and x^=ζ(y)\hat{\mathbf{x}}=\zeta(\mathbf{y}), so that x(k+1)=x^+ek\mathbf{x}(k+1)=\hat{\mathbf{x}}+\mathbf{e}_k. By the minorization property and the BB-Lipschitz gradient of ϕ(⋅∣y)\phi(\cdot\mid\mathbf{y}) (Assumption 2),

Φ(x(k+1))≥ϕ(x(k+1)∣y)≥ϕ(x^∣y)+⟨∇ϕ(x^∣y),ek⟩−B2∥ek∥2≥ϕ(x^∣y)−G∥ek∥−B2∥ek∥2.\begin{aligned} \Phi(\mathbf{x}(k+1)) &\ge\phi(\mathbf{x}(k+1)\mid\mathbf{y})\\ &\ge\phi(\hat{\mathbf{x}}\mid\mathbf{y})+\langle\nabla\phi(\hat{\mathbf{x}}\mid\mathbf{y}),\mathbf{e}_k\rangle-\frac{B}{2}\lVert\mathbf{e}_k\rVert^2\\ &\ge\phi(\hat{\mathbf{x}}\mid\mathbf{y})-G\lVert\mathbf{e}_k\rVert-\frac{B}{2}\lVert\mathbf{e}_k\rVert^2. \end{aligned}

As in (20), by Lemma 1 and Assumption 1, ϕ(x^∣y)≥Φ(y)+μL~g(y)\phi(\hat{\mathbf{x}}\mid\mathbf{y})\ge\Phi(\mathbf{y})+\frac{\mu}{\tilde{L}}g(\mathbf{y}), and subtracting both sides from Φ∗\Phi^* gives

g(x(k+1))≤ρg(x(k))+G∥ek∥+B2∥ek∥2.(38)g(\mathbf{x}(k+1))\le\rho g(\mathbf{x}(k))+G\lVert\mathbf{e}_k\rVert+\frac{B}{2}\lVert\mathbf{e}_k\rVert^2. \tag*{(38)}

Taking conditional expectations, with E[∥ek∥∣Fk]≤εk\mathbb{E}[\lVert\mathbf{e}_k\rVert\mid\mathcal{F}_k]\le\varepsilon_k by Jensen’s inequality, and unrolling the recursion gives (36). Finally, the weights ρk−1−j\rho^{k-1-j} in (36) sum to at most 1/(1−ρ)=L~/μ1/(1-\rho)=\tilde{L}/\mu, which gives (37).

Theorem 3 makes no assumption on how the MM step is solved: the errors need not be zero-mean or independent, and only their conditional second moments are used. The errors enter (36) through two terms. The linear term is present only when ζ(y)\zeta(\mathbf{y}) lies on the boundary of X\mathcal{X}. When ζ(y)\zeta(\mathbf{y}) is interior for all y\mathbf{y}, G=0G=0 and the errors have a quadratic effect, so that the asymptotic gap scales with the variance of the error. Finally, since Φ\Phi is continuous on the compact set X\mathcal{X}, g(x(k))→0g(\mathbf{x}(k))\to0 implies that the distance from x(k)\mathbf{x}(k) to the set of maximizers M\mathcal{M} tends to zero; when Φ\Phi has a unique maximizer x∗\mathbf{x}^*, x(k)→x∗\mathbf{x}(k)\to\mathbf{x}^*.

Noisy ADMM with finite iterations

We now consider the case where the MM step is solved by the noisy ADMM of § 4. At MM step kk, with y=x(k)\mathbf{y}=\mathbf{x}(k), the algorithm runs TT iterations of (30)–(32), with hi=hi(⋅,yi)h_i=h_i(\cdot,y_i), from z0=y\mathbf{z}^0=\mathbf{y} and v0=0\mathbf{v}^0=0, and sets x(k+1)=ΠX(xT)\mathbf{x}(k+1)=\Pi_{\mathcal{X}}(\mathbf{x}^T), the projection of the last iterate onto X\mathcal{X}. With the state w=(z,v)\mathbf{w}=(\mathbf{z},\mathbf{v}), the noiseless iteration (η≡0\eta\equiv0) is a map wt+1=Fy(wt)\mathbf{w}^{t+1}=F_{\mathbf{y}}(\mathbf{w}^t), and the noisy one reads

wt+1=Fy(wt)+(ηt+1,−ηt+1),(39)\mathbf{w}^{t+1}=F_{\mathbf{y}}(\mathbf{w}^t)+(\boldsymbol{\eta}^{t+1},-\boldsymbol{\eta}^{t+1}), \tag*{(39)}

since the noise added to zt+1\mathbf{z}^{t+1} is subtracted in the update of vt+1\mathbf{v}^{t+1}.

Lemma 4 (Error of noisy ADMM). Let the minorizer be (27), with α>0\alpha> 0 and J(x)=−12xTQx+pTx\mathcal{J}(x) = -\frac{1}{2}x^{\mathsf{T}}Qx + p^{\mathsf{T}}x for some Q⪰0Q \succeq0 and p∈RNp \in\mathbb{R}^{N}, and suppose that, for every y∈Xy \in\mathcal{X}, the maximizer of ϕ(⋅∣y)\phi(\cdot|y) over RN\mathbb{R}^{N} lies in X\mathcal{X}. If E[∥ηkt∥2∣Fk]≤Nνk\mathbb{E}\left[\lVert\eta_{k}^{t}\rVert^{2}\mid\mathcal{F}_{k}\right]\leq N\nu_{k} for t=1,…,Tt=1,\ldots,T, then there are constants ρˉ∈(0,1)\bar{\rho}\in(0,1) and CC, independent of kk, such that

(E[∥ek∥2∣Fk])1/2≤ϵk≜C(ρˉT+Nνk).(40)\left(\mathbb{E}\left[\lVert e_{k}\rVert^{2}\mid\mathcal{F}_{k}\right]\right)^{1/2}\leq\epsilon_{k}\triangleq C\left(\bar{\rho}^{T}+\sqrt{N\nu_{k}}\right). \tag*{(40)}

Proof. Since J\mathcal{J} and hi(⋅,yi)h_i(\cdot,y_i) are quadratic, the noiseless iteration is affine, Fy(w)=Mw+byF_y(\mathbf{w})=M\mathbf{w}+\mathbf{b}_y: the linear parts of the proximal operators, (I+λQ)−1(I+\lambda Q)^{-1} and (1+λα)−1(1+\lambda\alpha)^{-1}, do not depend on yy, while by\mathbf{b}_y depends continuously on yy through fi′(yi)f_i'(y_i) and yiy_i. As the noiseless ADMM converges linearly to the maximizer ζ(y)\zeta(y) of ϕ(⋅∣y)\phi(\cdot|y) [28, 29], ∥Mt∥≤CMρˉt\lVert M^t\rVert\leq C_M\bar{\rho}^{t} for some ρˉ<1\bar{\rho}<1, and FyF_y has a unique fixed point wy⋆=(zy⋆,vy⋆)\mathbf{w}_y^\star=(\mathbf{z}_y^\star,\mathbf{v}_y^\star), with zy⋆=prox⁡λJ(zy⋆−vy⋆)=ζ(y)\mathbf{z}_y^\star=\operatorname{prox}_{\lambda\mathcal{J}}(\mathbf{z}_y^\star-\mathbf{v}_y^\star)=\zeta(y). Unrolling (39),

wT−1−wy⋆=MT−1(w0−wy⋆)+∑s=1T−1MT−1−s(ηs,−ηs).\mathbf{w}^{T-1}-\mathbf{w}_y^\star=M^{T-1}(\mathbf{w}^{0}-\mathbf{w}_y^\star)+\sum_{s=1}^{T-1}M^{T-1-s}(\eta^s,-\eta^s).

Since the proximal operator and the projection onto X\mathcal{X} are nonexpansive, ∥ek∥≤2∥wT−1−wy⋆∥\lVert e_k\rVert\leq\sqrt{2}\lVert\mathbf{w}^{T-1}-\mathbf{w}_y^\star\rVert. By Minkowski’s inequality, using E[∥(ηs,−ηs)∥2∣Fk]≤2Nνk\mathbb{E}\left[\lVert(\eta^s,-\eta^s)\rVert^2\mid\mathcal{F}_k\right]\leq2N\nu_k,

(E[∥ek∥2∣Fk])1/2≤2CM(ρˉT−1∥w0−wy⋆∥+2Nνk1−ρˉ),\left(\mathbb{E}\left[\lVert e_k\rVert^2\mid\mathcal{F}_k\right]\right)^{1/2}\leq\sqrt{2}C_M\left(\bar{\rho}^{T-1}\lVert\mathbf{w}^{0}-\mathbf{w}_y^\star\rVert+\frac{\sqrt{2N\nu_k}}{1-\bar{\rho}}\right),

which gives (40), since ∥w0−wy⋆∥\lVert\mathbf{w}^{0}-\mathbf{w}_y^\star\rVert is bounded over the compact set X\mathcal{X}.

After TT inner iterations, the initial error has shrunk as ρˉT\bar{\rho}^{T}, while the accumulated noise remains of order Nνk\sqrt{N\nu_k}. The interior assumption is needed because the ADMM of § 4 does not take the constraints into account. Otherwise, each agent can project its update onto Xi\mathcal{X}_i, and a similar bound follows from the contraction property of Douglas–Rachford splitting [28].

Corollary 5 (MM with noisy ADMM). Under the assumptions of Theorem 3 and Lemma 4, the bound (36) holds with ϵk\epsilon_k given by (40). In particular, if νk→0\nu_k\to0,

lim sup⁡k→∞E[g(x(k))]≤L~μ(Gϵˉ+B2ϵˉ2),(41)\limsup_{k\to\infty}\mathbb{E}[g(x(k))]\leq\frac{\widetilde{L}}{\mu}\left(G\bar{\epsilon}+\frac{B}{2}\bar{\epsilon}^{2}\right), \tag*{(41)}

where ϵˉ≜CρˉT\bar{\epsilon}\triangleq C\bar{\rho}^{T}.

Proof. By Lemma 4, Theorem 3 applies with ϵk\epsilon_k given by (40). If νk→0\nu_k\to0, then ϵk→ϵˉ\epsilon_k\to\bar{\epsilon}, and (37) gives (41).

The bound of Corollary 5 separates three effects: the initial gap is forgotten at the rate ρ\rho of Theorem 2; the noise contributes through νk\sqrt{\nu_k} and vanishes only if its variance decreases to zero, independent and identically distributed noise leaving an asymptotic gap; and the finite number TT of inner iterations leaves the floor (41), which decreases exponentially in TT and vanishes if TT grows with kk.

The injected noise only obscures the agents’ individual updates. Since its variance must decrease for the iterates to converge, the level of obfuscation it provides also diminishes over time. This highlights a trade-off between convergence accuracy and privacy protection in noise-based mechanisms: for schemes that perturb the exchanged messages, exact convergence and differential privacy cannot be achieved simultaneously [24]. Larger noise levels may provide stronger obfuscation of individual preference information, but can also increase the error in the MM updates and slow down convergence. Conversely, reducing the noise improves solution accuracy and convergence, but progressively weakens the protection of individual information.

Numerical Example

We illustrate our results on an example which captures the key features of our analysis: agents with smooth S-shaped value functions that make the potential non-concave while satisfying our assumptions; a collective benefit that couples the players; a game small enough for the optimum to be computed exactly. We consider N=3N = 3 agents and a coordinator (agent N+1N + 1). Agent ii chooses xi∈Xi=[0,x‾]x_i \in\mathcal{X}_i = [0,\overline{x}], interpreted as a quantity sold at a random price ξ∈{0.5,1,2}\xi\in\{0.5, 1, 2\} with probabilities q=(0.3,0.5,0.2)\mathbf{q} = (0.3, 0.5, 0.2). The reward of agent ii is Ri(xi,ξ)=ξxi−biR_i(x_i,\xi) = \xi x_i-b_i, where bi>0b_i > 0 is a reference level. Outcomes are evaluated through the smooth prospect-theoretic value function

Vi(r)={θi+tanh⁡(r/θi+),r≥0,θi−tanh⁡(r/θi−),r<0,(42)V_i(r) = \begin{cases} \theta_i^+ \tanh(r/\theta_i^+), & r \ge0,\\ \theta_i^- \tanh(r/\theta_i^-), & r < 0, \end{cases} \tag*{(42)}

which is increasing, concave on gains and convex on losses (Figure 2).

Figure 2. Prospect-theoretic value functions ViV_i used in the example: concave on gains (r>0r > 0) with saturation level θi+\theta_i^+, convex on losses (r<0r < 0) with saturation level −θi−-\theta_i^-, where θi−>θi+\theta_i^- > \theta_i^+.

The weights σ\boldsymbol{\sigma} are obtained from q\mathbf{q} via (2) with π(p)=pδ(pδ+(1−p)δ)1/δ\pi(p) = \frac{p^\delta}{\left(p^\delta+ (1-p)^\delta\right)^{1/\delta}}, δ=0.65\delta= 0.65, giving σ=(0.324,0.316,0.360)\boldsymbol{\sigma} = (0.324, 0.316, 0.360). The collective benefit is

J(x)=−κ2∑i=1N(xi−d)2−γ2∑i<j(xi−xj)2.(43)\mathcal{J}(\mathbf{x}) = -\frac{\kappa}{2}\sum_{i=1}^{N}(x_i-d)^2-\frac{\gamma}{2}\sum_{i<j}(x_i-x_j)^2. \tag*{(43)}

Its first part penalizes, quadratically, the deviation of each agent from its share dd of a collective target (as in tracking or imbalance penalties), while the second part penalizes disparities between agents and thus favours an equitable distribution of effort. It can also be written as

J(x)=−12(x−d1)TQ(x−d1),(44)\mathcal{J}(\mathbf{x}) = -\frac{1}{2}(\mathbf{x}-d\mathbf{1})^{\mathsf{T}}\mathbf{Q}(\mathbf{x}-d\mathbf{1}), \tag*{(44)}

with Q=κI+γΛQ = \kappa I + \gamma\Lambda, where Λ\Lambda is the Laplacian of the complete graph. This form is also chosen for tractability of the coordinator’s proximal step in the ADMM. The utilities are Ji(x)=aiJ(x)+Eσ[Vi∘Ri(xi,ξ)]J_i(\mathbf{x}) = a_i\mathcal{J}(\mathbf{x}) + \mathbb{E}_{\sigma}[V_i \circ R_i(x_i,\xi)]. The different parameters are listed in Table 1.

Agent 1Agent 2Agent 3
aia_i1.00.80.5
bib_i2.01.52.5
θi+\theta_i^+1.01.50.8
θi−\theta_i^-1.52.01.2
κ=0.2, γ=0.1, d=5, xˉ=17.58\kappa= 0.2,\ \gamma= 0.1,\ d = 5,\ \bar{x} = 17.58

Table 1. Parameters of the numerical example.

When ξ1d≥max⁡ibi\xi_1 d \ge\max_i b_i, one can show that the potential Φ\Phi has a unique critical point, which is its global maximizer x∗=(5.617,5.651,5.913)\mathbf{x}^* = (5.617, 5.651, 5.913), lying in the interior of X\mathcal{X}, and that Φ\Phi satisfies Assumption 1 (numerically, μ≈0.18\mu\approx0.18 for any Lˉ≥1\bar{L} \ge1). Nevertheless, Φ\Phi and each JiJ_i are non-concave: ∂2Φ/∂xi2>0\partial^2\Phi/\partial x_i^2 > 0 near xi=0x_i = 0.

Algorithm settings At each MM step the minorizer (27) of § 4, ϕ(x∣y)=J(x)+∑ihi(xi,yi)\phi(\mathbf{x}|\mathbf{y}) = \mathcal{J}(\mathbf{x}) + \sum_i h_i(x_i,y_i), with

hi(xi,yi)=fi(yi)+fi′(yi)(xi−yi)−α2(xi−yi)2(45)h_i(x_i,y_i) = f_i(y_i) + f_i'(y_i)(x_i-y_i) - \frac{\alpha}{2}(x_i-y_i)^2 \tag*{(45)}

and fi(xi)=ai−1Eσ[Vi∘Ri(xi,ξ)]f_i(x_i) = a_i^{-1}\mathbb{E}_{\sigma}[V_i \circ R_i(x_i,\xi)], is maximized by 30 iterations of noisy ADMM with λ=1\lambda= 1. Note that ϕ\phi is a minorizer of Φ\Phi whenever α≥sup⁡x∣fi′′(x)∣\alpha\ge\sup_x |f_i''(x)| for all ii. We take α\alpha equal to the closed-form bound obtained from ∣Vi′′∣≤4/(33θ)|V_i''| \le4/(3\sqrt{3}\theta) with θ=min⁡(θi+,θi−)\theta= \min(\theta_i^+,\theta_i^-),

α=max⁡i1ai∑mσmξm2433min⁡(θi+,θi−)=3.535,(46)\alpha= \max_i \frac{1}{a_i}\sum_m \sigma_m \xi_m^2 \frac{4}{3\sqrt{3}\min(\theta_i^+,\theta_i^-)} = 3.535, \tag*{(46)}

which guarantees minorization and can be computed without any numerical search. At MM step kk, agents add independent noise ηi∼Laplace⁡(0,sk)\eta_i \sim\operatorname{Laplace}(0,s_k) with sk=s0(0.95)ks_k = s_0(0.95)^k, for initial variances Var⁡(η0)=2s02∈{0,0.01,0.1,1,5}\operatorname{Var}(\eta_0) = 2s_0^2 \in\{0, 0.01, 0.1, 1, 5\}. Each configuration is run 20 times from x(0)=0x(0) = 0 for 150 MM steps, and the reported curves are averages over runs.

Results Figure 3 shows the potential Φ(x(k))\Phi(x(k)) along the MM iterates, and Figure 4 the optimality gap Φ∗−Φ(x(k))\Phi^* - \Phi(x(k)) on a logarithmic scale. For every noise level the iterates converge to the potential maximizing equilibrium x∗x^*. A larger initial variance slows the early iterations, where the noise is largest, but since sk→0s_k \to0 it does not leave a residual gap: after 150 MM steps the mean gap ranges from 6×10−106 \times10^{-10} without noise to 1.3×10−51.3 \times10^{-5} for Var⁡(η0)=5\operatorname{Var}(\eta_0) = 5. With noise, the gap decays geometrically at a rate governed by the noise decay 0.95k0.95^k rather than by the MM contraction alone. This is the behaviour predicted by Corollary 5: in this example the exact MM step is interior, so that G=0G = 0, and since the noise variance decays to zero, the only remaining floor is due to the finite number of ADMM iterations, which is negligible for T=30T = 30.

Potential $\Phi(x(k))$ along the MM iterates for different initial noise variances

Figure 3. Potential Φ(x(k))\Phi(x(k)) along the MM iterates for different initial noise variances, averaged over 20 runs; shaded regions show the 10–90% range across runs. The dashed line is Φ∗\Phi^*.

Optimality gap $\Phi^{*}-\Phi(x(k))$ on a log scale for different initial noise variances

Figure 4. Optimality gap Φ∗−Φ(x(k))\Phi^{*}-\Phi(x(k)) (log scale) for different initial noise variances, averaged over 20 runs; shaded regions show the 10–90% range across runs.

Impact of prospect theory If we consider the same game with expected-utility players, i.e., Vi(r)=rV_i(r)=r and σ=q\sigma=q, the potential is a concave quadratic, and the equilibrium is xEU=(11.56,12.09,13.66)x_{\mathrm{EU}}=(11.56,12.09,13.66), roughly twice the PT equilibrium x∗=(5.62,5.65,5.91)x^{*}=(5.62,5.65,5.91). The difference is driven by the value function: at equilibrium all outcomes are gains, where ViV_i is concave and saturates, so the PT players, being risk averse in gains, sell much smaller quantities. Probability weighting alone has the opposite effect: using σ\sigma with Vi(r)=rV_i(r)=r gives (12.49,13.09,14.88)(12.49,13.09,14.88). This is because the weighting overweights the rare high price (σ3=0.36\sigma_3=0.36 against q3=0.2q_3=0.2), which raises the perceived expected price (Eσ[ξ]=1.20\mathbb{E}_{\sigma}[\xi]=1.20 against Eq[ξ]=1.05\mathbb{E}_{q}[\xi]=1.05). Also note that PT is also what makes the problem non-concave: the non-concavity of Φ\Phi comes from the convex loss region of ViV_i, and is absent under expected utility, where standard methods apply.

Effect of the minorizer curvature The bound α=3.535\alpha=3.535 used above is conservative. For the minorizer (27), the condition of § 4 (fi′f_i' α\alpha-Lipschitz) holds for α≥max⁡isup⁡x∈Xi∣fi′′(x)∣=2.34\alpha\ge\max_i\sup_{x\in\mathcal{X}_i}|f_i''(x)|=2.34, which here coincides with αmin⁡≔max⁡isup⁡x∈Xi(−fi′′(x))\alpha_{\min}\coloneqq\max_i\sup_{x\in\mathcal{X}_i}(-f_i''(x)), the smallest α\alpha for which ϕ\phi is a minorizer; for α<αmin⁡\alpha<\alpha_{\min} the minorization is imperfect. To study the effect of α\alpha, we run the full algorithm for a fixed budget of K=50K=50 MM steps, for 21 values of α∈[0,14]\alpha\in[0,14] and the same decaying noise as above (20 runs per configuration, 150 ADMM iterations per MM step). Figure 5 shows the resulting value Φ(x(K))\Phi(x(K)), with the dotted line marking α=αmin⁡\alpha=\alpha_{\min}.

Plot of potential versus curvature parameter for different initial noise variances

Figure 5. Potential Φ(x(K))\Phi(\mathbf{x}(K)) after K=50K = 50 MM steps versus the curvature parameter α\alpha, for different initial noise variances, averaged over 20 runs; shaded regions show the 10–90% range across runs. The dotted line marks α=αmin⁡\alpha= \alpha_{\min}, and the dashed line is Φ∗\Phi^*. The horizontal axis is logarithmic in α\alpha plus a small constant (0.2), so that α=0\alpha= 0 can be shown.

To the right of αmin⁡\alpha_{\min}, a larger α\alpha makes ϕ\phi more curved and each MM step shorter, so after KK steps the iterates are further from the optimum: at α=14\alpha=14 the mean of Φ(x(K))\Phi(x(K)) is about 2.3 without noise and about 0 for Var⁡(η0)=5\operatorname{Var}(\eta_0)=5, against Φ∗=3.76\Phi^{*}=3.76, and the noise also widens the spread across runs. To the left of αmin⁡\alpha_{\min}, where ϕ\phi is no longer a minorizer and Theorem 2 does not apply, the curves stay close to Φ∗\Phi^{*}: in all runs the algorithm still converged to x∗x^{*}. In this region the remaining gap is set by the noise rather than by α\alpha; it is below 10−510^{-5} without noise and at most 3×10−33 \times10^{-3}, 3×10−23 \times10^{-2} and 0.13 for Var⁡(η0)=0.1\operatorname{Var}(\eta_0) = 0.1, 1 and 5. Choosing α\alpha above αmin⁡\alpha_{\min} thus slows convergence, while values below αmin⁡\alpha_{\min} can be faster but are not covered by Theorem 2.

Conclusion

We studied learning in non-cooperative potential games with prospect theoretic non concave utilities. If the potential satisfies a proximal PL inequality, an MM learning algorithm can be constructed, which converges linearly to a potential maximizing Nash equilibrium. The minorizer for this algorithm can be designed to enable distributed implementation using a noisy ADMM. The noise prevents the agents from revealing their preferences exactly. Convergence of the noisy MM algorithm is shown under assumptions of the noise variance. In particular, we demonstrate a trade off between algorithm convergence and privacy for agent preferences: noise levels that do not decay in time ensure better hiding of agent preferences, whereas decaying noise levels lead to convergence to equilibrium. Numerical results illustrate the performance of the proposed algorithm. A formal characterization of the privacy guarantee will be undertaken in a follow-up work.

Declaration of Generative AI and AI-Assisted Technologies

The authors used Claude (Opus 5.5, Anthropic) to assist in checking and deriving intermediate algebraic steps and formatting mathematical derivations in Sections 4 and 6, for designing the numerical simulations in Section 7, and for formatting and editing the paper. The authors have independently re-derived and verified all the content of the paper, and take full responsibility for the mathematical accuracy and content of the publication.

References

  1. [1]D. Kahneman and A. Tversky, “Prospect theory: An analysis of decision under risk,” Econometrica, vol. 47, no. 2, pp. 363–391, 1979.
  2. [2]A. Tversky and D. Kahneman, “Advances in prospect theory: Cumulative representation of uncertainty,” Journal of Risk and Uncertainty, vol. 5, no. 4, pp. 297–323, 1992.
  3. [3]K. Keskin, “Equilibrium notions for agents with cumulative prospect theory preferences,” Decision Analysis, vol. 13, no. 3, pp. 192–208, 2016.DOI
  4. [4]L. P. Metzger and M. O. Rieger, “Non-cooperative games with prospect theory players and dominated strategies,” Games and Economic Behavior, vol. 115, pp. 396–409, 2019.DOI
  5. [5]S. R. Phade and V. Anantharam, “On the geometry of Nash and correlated equilibria with cumulative prospect theoretic preferences,” Decision Analysis, vol. 16, no. 2, pp. 142–156, 2019.
  6. [6]S. R. Phade and V. Anantharam, “Learning in games with cumulative prospect theoretic preferences,” Dynamic Games and Applications, vol. 13, no. 1, pp. 265–306, 2023.
  7. [7]S. R. Etesami, W. Saad, N. B. Mandayam, and H. V. Poor, “Stochastic games for the smart grid energy management with prospect prosumers,” IEEE Transactions on Automatic Control, vol. 63, no. 8, pp. 2327–2342, 2018.
  8. [8]A. Krishnan K.S., H. Le Cadre, and A. Bušić, “How irrationality shapes Nash equilibria: A prospect-theoretic perspective,” in 2025 IEEE 64th Conference on Decision and Control (CDC), pp. 4428–4433, IEEE, 2025.
  9. [9]A. Krishnan K.S., H. Le Cadre, and A. Bušić, “Achieving a Collective Target through Incentives,” in International Conference on Network Games, Artificial Intelligence, Control and Optimization, pp. 57–67, Springer, 2025.
  10. [10]E. Mazumdar, L. J. Ratliff, and S. S. Sastry, “On gradient-based learning in continuous games,” SIAM Journal on Mathematics of Data Science, vol. 2, no. 1, pp. 103–131, 2020.DOI
  11. [11]M. Fochesato, F. Pokou, H. Le Cadre, and J. Lygeros, “Noncooperative games with prospect theoretic preferences,” IEEE Control Systems Letters, 2025.DOI
  12. [12]D. Monderer and L. S. Shapley, “Potential games,” Games and economic behavior, vol. 14, no. 1, pp. 124–143, 1996.
  13. [13]J. R. Mardeen, G. Arslan, and J. S. Shamma, “Cooperative control and potential games,” IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 39, no. 6, pp. 1393–1407, 2009.
  14. [14]B. T. Polyak, “Gradient methods for minimizing functionals,” USSR Computational Mathematics and Mathematical Physics, vol. 3, no. 4, pp. 864–878, 1963.
  15. [15]H. Karimi, J. Nutini, and M. Schmidt, “Linear convergence of gradient and proximal-gradient methods under the Polyak-Lojasiewicz condition.” arXiv:1608.04636, 2016.arxiv.org/abs/1608.04636
  16. [16]J. Yang, N. Kiyavash, and N. He, “Global convergence and variance reduction for a class of nonconvex-nonconcave minimax problems,” in Advances in Neural Information Processing Systems, vol. 33, 2020.
  17. [17]D. R. Hunter and K. Lange, “A tutorial on MM algorithms,” The American Statistician, vol. 58, no. 1, pp. 30–37, 2004.DOI
  18. [18]Y. Sun, P. Babu, and D. P. Palomar, “Majorization-minimization algorithms in signal processing, communications, and machine learning,” IEEE Transactions on Signal Processing, vol. 65, no. 3, pp. 794–816, 2017.DOI
  19. [19]M. Razaviyayn, M. Hong, and Z.-Q. Luo, “A unified convergence analysis of block successive minimization methods for nonsmooth optimization,” SIAM Journal on Optimization, vol. 23, no. 2, pp. 1126–1153, 2013.arxiv.org/abs/1209.2385
  20. [20]J. Bolte and E. Pauwels, “Majorization-minimization procedures and convergence of sqp methods for semi-algebraic and tame programs,” Mathematics of Operations Research, vol. 41, no. 2, pp. 442–465, 2016.DOI
  21. [21]G. Scutari, F. Facchinei, P. Song, D. P. Palomar, and J.-S. Pang, “Decomposition by partial linearization: Parallel optimization of multi-agent systems,” IEEE Transactions on Signal Processing, vol. 62, no. 3, pp. 641–656, 2014.DOI
  22. [22]F. Salehisadaghiani, W. Shi, and L. Pavel, “Distributed Nash equilibrium seeking under partial-decision information via the alternating direction method of multipliers,” Automatica, vol. 103, pp. 27–35, 2019.DOI
  23. [23]Z. Huang, S. Mitra, and N. Vaidya, “Differentially private distributed optimization,” in Proceedings of the International Conference on Distributed Computing and Networking (ICDCN), pp. 4:1–4:10, ACM, 2015.arxiv.org/abs/1401.2596
  24. [24]E. Nozari, P. Tallapragada, and J. Cortés, “Differentially private distributed convex optimization via functional perturbation,” IEEE Transactions on Control of Network Systems, vol. 5, no. 1, pp. 395–408, 2018.
  25. [25]H. P. Stott, “Cumulative prospect theory’s functional menagerie,” Journal of Risk and uncertainty, vol. 32, pp. 101–130, 2006.DOI
  26. [26]Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, vol. 87 of Applied Optimization. Boston, MA: Kluwer Academic Publishers, 2004.
  27. [27]N. Parikh and S. Boyd, “Proximal algorithms,” Foundations and Trends in optimization, vol. 1, no. 3, pp. 127–239, 2014.DOI
  28. [28]P. Giselsson and S. Boyd, “Linear convergence and metric selection for douglas-rachford splitting and admm,” IEEE Transactions on Automatic Control, vol. 62, no. 2, pp. 532–544, 2016.arxiv.org/abs/1410.8479
  29. [29]W. Deng and W. Yin, “On the global and linear convergence of the generalized alternating direction method of multipliers,” Journal of Scientific Computing, vol. 66, no. 3, pp. 889–916, 2016.

Paper details

vlnc:W_xhwtjsp7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude

View statement
Looking for related papers…
Contents