# Relationship Design for Socially Desirable Behavior in Static Games

Shenghui Chen, Yigit E. Bayiz, David Fridovich-Keil, Yue Yu, and Ufuk Topcu S.
Chen, Y. E. Bayiz, D. Fridovich-Keil, Y. Yu, and U. Topcu are with Univeristy
of Texas at Austin, TX 78712 USA. E-mails: {shenghui.chen, egebayiz, dfk,
yueyu<EMAIL_ADDRESS>
###### Abstract

Interactions among multiple self-interested agents may not necessarily yield
socially desirable behaviors. While static games offer a pragmatic model for
such interactions, and modifying the utilities of the agents in such games
provides a means toward achieving socially desirable behavior, manipulating
the utilities is hard—if not impossible—after the system is deployed. We
investigate an alternative means where each agent incorporates others’
utilities into its own utility based on a relationship network, which
characterizes how much one agent cares about another and hence the extent of
their utility incorporation. We introduce the notion of a relationship game, a
static game with a set of weighted relationship networks and a social cost
function. The main problem we study is the design of the weight vector on the
relationships such that the Nash equilibrium of the associated game is
socially desirable. We propose an ordering-based exact method and a gradient-
based approximate method to solve this problem. We show theoretically that the
exact solution scales exponentially with the number of players. Empirical
results show both methods are effective and scale exponentially, with the
runtime of gradient-based solution growing slower.

##  I Introduction

In the interaction of multiple autonomous agents, where each agent seeks to
maximize its own objective, socially desirable behavior such as collaboration
is hard to achieve because it requires self-interested agents to sacrifice
part of their individual utility for the greater good [1]. Single-agent
optimization is not enough because the collaborative action of one agent
depends on the actions of the other agents [2].

General-sum static games offer a mathematical formalism that captures such
interaction [3]. In these games, the optimal action for each player is often
characterized by one of many solution concepts, e.g., a Nash equilibrium,
which happens when no player will unilaterally choose to switch its actions.
However, a Nash equilibrium often does not lead to the optimal joint decision
for the group of players.

To evaluate the optimality of decisions for the collective of all players in a
game, we define a notion of social cost function. Consider the running example
illustrated in Fig. 1: three autonomous vehicles are deployed in an area with
a cost-sharing route $A$ and an easily congested route $B$. Here, we take the
social cost function of the game as the sum of all its players’ cost
functions. A game solution is more socially desirable than another if it has a
lower expected social cost, and is called maximally socially desirable when
the social cost is minimized. In the running example, this happens when the
autonomous cars join the cost-sharing route $A$. The challenge is this: can we
enable a group of selfish players to achieve the more socially desirable
decisions?

(a) Running example: 3-player, 2-route traffic

(b) Types of relationships in a 3-player setting

Figure 1: (a) Each of the three players starts at the origin and ends at the
destination through one of two routes: route $A$ is a car-pool route where the
passenger players share a total cost of $5, i.e., $u(l_{A})=5/l_{A}$, where
$l_{A}$ is the number of players entered route $A$; route $B$ is an easily
congested route where the cost for each passenger player increases as more
players enter this route, i.e., $u(l_{B})=1.5\times l_{B}$. (b) individual
relationships which represents one-to-one relations between any two players in
the game, all-people relationships which represents the relations from one
player to all other players, and reciprocity relationships which represents
the reciprocal relations between any two players.

Humans are able to trust each other and behave cooperatively without much
training, achieving higher efficiency because they are guided by certain
ethical principles [4]. One important ethical principle is altruism—acting in
a way that cares about others, but how do people calibrate how much they
should care about different individuals in society? Kleiman-Weiner et al. [5]
propose that this amount of care over specific people should be determined by
abstract relationships. For example, people usually care more about others in
their family than some larger affiliation. We hypothesize that autonomous
agents can similarly achieve socially desirable outcomes by introducing
relationships among them.

While there are many ways for specifying the structure of the relationships
among agents, in this work we consider three relationship types: (a)
individual relationships which allow all players to set weights on another
arbitrarily, (b) all-people relationships which only allow one player to set
equal weights on all other players, and (c) reciprocity relationships which
require players to put equal weights on each other reciprocally. Fig. 1b
illustrates the underlying structure of relationships in a 3-player setting
for the three relationship types. For each relationship type, we have a set of
relationship networks, each represented by a directed graph with players
represented at vertices. In Fig. 1b, a dot represents a player, and an arrow
from one dot to another represents the existence of a relation between the two
players. Bi-directional arrows in the set of reciprocity relationship networks
represent bilateral relations of players setting equal weights on each other.

A static game with a set of relationship networks can be collapsed into a
graphical game [6] if we assign a weight to each element in the set, which
collectively we call a relationship weight vector. A set of relationship
networks abstracts the relations among the player qualitatively, and a
relationship weight vector refines the relations quantitatively. The weights
assigned to elements in a relationship network set tell the players not only
whether to care about the objectives of other specific players, but also how
much to care about them.

We formalize the notion of relationship game as a static game combined with a
social cost function, an ordered set of relationship networks, and a
relationship weight vector. We consider the new problem of designing the
relationship weight vector, as sparse as possible, such that the Nash
equilibrium of the associated game is as socially desirable as possible. Fig.
1 shows an overview of this problem, referred to as relationship weight vector
design.

We propose and implement two solutions to solve the problem. Order-and-Design
is an exact method that designs relationship weight vectors to achieve pure
Nash equilibria in ascending order of social costs by solving a series of
linear programs. Entropy-regularized Nash gradient descent (Entropy-Nash GD)
is a gradient-based approximate method built on a new game solver. This solver
prevents large zero-gradient regions by incorporating an entropy
regularization term for each player. With the new solver, gradients can be
properly defined and amenable to be applied in gradient descent of expected
social cost with respect to changes in a relationship weight vector.
Theoretically, we show Order-and-Design is correct by construction and scales
exponentially with the number of players. Empirical results support this
finding and show that, despite both growing exponentially, the runtime of
Entropy-Nash GD grows at a lower rate. Experiments also demonstrate the
effectiveness of both methods in leading to socially desirable behaviors, with
the caveat of more parameter tuning needed in Entropy-Nash GD.

##  II Related Work

Collaboration is hard to achieve in games because players often need to face
the dilemma where actions to minimize social costs do not coincide with what
is optimal for themselves. This challenge is not a new one, and two general
approaches are employed in prior works. First, the designer of the game can
force players to behave according to a particular game solution concept [7],
yet the choice of an appropriate moral value becomes a dilemma itself and this
work only deals with two-player games. The second approach chooses to alter
the game matrices such that the moral value of an action aligns with the
agents’ rationality [8]. This approach is also our intuition behind game cost
function modification, but [8] only characterizes what a good modified game
is, without a general algorithm to achieve it from the original game.

In economics and game theory, researchers have been thinking about the effect
of selfish behaviors of the players on the game performance. The Price of
Anarchy (PoA) [9] is a concept to measure how the efficiency of a system,
often modeled as a game, degrades due to the selfish behavior of its agents.
However, PoA views the problem as an outsider, measuring the distance from the
game equilibrium to the social optimum without changing the players’
strategies. It is mostly used for evaluation purposes and is not constructive.
On the other end of the spectrum, mechanism design [10] is free to design game
matrices and not subject to any constraints. Our method considers the
realistic game modification through relationships among players, yielding a
constrained problem.

The idea of using relationships among players is inspired by [5], where the
authors discuss how people learn to trade off the interests and welfare of
different individuals in their social groups and the larger society. In game
theory, this idea is closely linked to that of graphical games [11, 6], where
we are given a network connecting the players, and each player’s utility
depends only on the choices of the players in its neighborhood. Here, the
network is the linear combination of a list of given relationship networks,
which further constrains the problem under realistic bounds.

##  III Background: Static games

An $n$-player, static game is a tuple $G=(N,S,u)$. $N=\\{1,\ldots,n\\}$ is a
set of players. The set $S$ of pure strategy profiles is the Cartesian product
of pure strategies for all players, i.e., $S=\prod_{i\in N}S^{i}$ where
$S^{i}$ is the finite set of pure strategies available to player $i$. $u$ is
the tuple of $n$ cost functions $u^{i}$ corresponding to each player $i\in N$
where each $u^{i}$ assigns a cost to the chosen strategy profile across all
players, i.e., $u=(u^{i})_{i\in N}$ where $u^{i}:S\to\mathbb{R}$.

A mixed strategy is a probability distribution over the available pure
strategies of a player, i.e., for player $i$, $x^{i}\in\Delta_{|S^{i}|-1}$ and
$x^{i}(s)$ denotes the probability of player $i$ choosing strategy $s\in
S^{i}$. Without loss of generality, we can assume that the elements in $S^{i}$
are indexed from $1$ to $|S^{i}|$. Then each mixed strategy $x^{i}$ can be
characterized as a vector in $\mathbb{R}^{|S_{i}|}$ where
$\mathbbm{1}^{T}x^{i}=1$. The mixed strategy profile is the tuple of mixed
strategies for all $n$ players, i.e., $\mathbf{x}=(x^{1},\ldots,x^{n})$.

For convenience we introduce the notation $x^{-i}$ to refer to the list of
strategies of all $n-1$ players other than player $i$, i.e.,

$x^{-i}\coloneqq(x^{1},\dots,x^{i-1},x^{i+1},\dots,x^{n}).$

Under the probability distribution given by a mixed strategy $\mathbf{x}$ and
the $i$’th player’s cost function $u^{i}$, the expected cost of player $i$ can
be written as

$\displaystyle J(\textbf{x},u^{i})$
$\displaystyle\coloneqq\mathbb{E}_{s^{1}\sim x^{1},\ldots,s^{n}\sim
x^{n}}[u^{i}(s^{1},\ldots,s^{n})]$ (1) $\displaystyle=\sum_{s^{1}\in
S^{1},\ldots,s^{n}\in S^{n}}x^{1}(s^{1})\ldots
x^{n}(s^{n})u^{i}(s^{1},\ldots,s^{n}).$

Nash equilibria are solutions to the coupled optimization problems, i.e.,
$\textbf{x}=\operatorname*{Nash}(G_{u})$ if and only if for all $i\in N$,

$\displaystyle\min_{x^{i}}$ $\displaystyle J(\textbf{x},u^{i})$ (2) s.t.
$\displaystyle\mathbbm{1}^{T}{x^{i}}=1.$

######  Running Example 1.

We represent the 3-player, 2-route traffic example introduced in Fig. 1 with
$N=\\{1,2,3\\}$, $S^{i}=\\{\text{route }A,\text{route }B\\}\quad\text{for
all}\quad i\in N$. Each player cost function is represented by a tensor in
$\mathbb{R}^{2\times 2\times 2}$. The Nash equilibrium for this game is a
mixed strategy of $\mathbf{x}=[[0.355,0.645],[0.355,0.645],[0.355,0.645]]$,
meaning all players choose route $A$ with a probability of $0.355$ and route
$B$ with a probability of $0.645$.

##  IV Problem: Relationship Game and Weight Design

The existing analyses of static games are often concerned with finding an
equilibrium point given pre-defined cost functions. In contrast, this work is
concerned with the mechanism design problem that aims to find a game structure
that enables players to end up with more socially desirable behaviors. We
achieve this by introducing a relationship structure that allows the players
to make altruistic decisions rather than basing their strategies purely on
their own cost functions. We call a static game coupled with this relationship
structure a relationship game and formally define it as follows.

######  Definition 1 (Relationship Game).

A relationship game is a static game $G_{u}=(N,S,u)$ combined with the
following elements:

  * •

$V:S\to\mathbb{R}$ is a social cost function that assigns real numbers to
strategy profiles.

  * •

$\Phi=(\phi_{i})_{i\in[m]}$ is an ordered set of $m$ relationship networks
where $\phi_{i}\in\mathbb{R}^{n\times n}$ is a directed graph represented by a
$n\times n$ real-valued adjacency matrix.

  * •

$w\in\mathbb{R}^{m}$ is a relationship weight vector where $w_{i}$ is the
weight on relationship network $\phi_{i}$ for $i\leq m$.

The static game $G_{u}$ together with the a set of relationship networks
$\Phi$ and a relationship weight $w$ induces a new game
$G_{\tilde{u}}=(N,S,\tilde{u})$. This associated game is characterized by the
cost functions $\tilde{u}=(\tilde{u}^{i})_{i\in N}$ constructed by a
modification function $M(u,\Phi,w)$, i.e.,

$\displaystyle\tilde{u}=M(u,\Phi,w)\quad\text{if and only if for all }i\in N,$
(3) $\displaystyle\tilde{u}^{i}(s)=u^{i}(s)+\sum_{j\in
N}\bigg{(}\sum_{r=1}^{m}w_{r}\phi_{r}\bigg{)}_{ij}u^{j}(s)\quad\forall s\in
S.$

Given a relationship game defined as above, the design problem aims to find a
relationship weight vector $w$, as sparse as possible, across relationship
networks in $\Phi$ such that the Nash equilibrium of the associated game is
socially desirable. In short, it seeks to answer the question: How should the
players care about each other so that they achieve the socially desirable
outcome?

######  Problem 1 (Relationship Weight Vector Design).

Given a relationship game where we have $G_{u}=(N,S,u)$, a social cost
function $V$, an ordered set of relationships $\Phi$, to design some
$w\in\mathbb{R}^{n}$ so that it leads to a Nash equilibrium—not necessarily
unique—of the associated game with lowest social cost, and is as sparse as
possible, i.e.,

$\displaystyle\min_{w}$ $\displaystyle J(\mathbf{x},V)$ (4) s.t.
$\displaystyle\tilde{u}=M(u,\Phi,w)$
$\displaystyle\mathbf{x}=\operatorname*{Nash}(G_{\tilde{u}})$
$\displaystyle\|w\|_{0}\leq k.$

######  Running Example 2.

The relationship game for the 3-player, 2-route example has a social cost
function $V$ with $(A,A,A)$ of the minimal cost, and relationship networks
$\Phi$ of individual type in Fig. 1b. This relationship type allows each
player to set arbitrary weights on any other players. In this relationship
weight vector design problem, we aim to find $w\in\mathbb{R}^{6}$
corresponding to each element in $\Phi$ so that its resulting game has Nash at
$(A,A,A)$ and it is as sparse as possible.

##  V Exact Solution: Order-and-Design

For problem 1 we want to find the sparsest weight vector $w$ so that the Nash
equilibrium of the modified game minimizes the social cost $V$. Ignoring
sparsity, we need to find a Nash equilibrium for the associated game, and
check if its social cost is the minimum among all possible equilibria.

In Algorithm 1, we first order all possible pure strategy profiles in
ascending order of their social costs, and then design $w$ by solving the
linear program in Problem 2 so that the current strategy profile at hand is
the Nash equilibrium in the modified game, hence the name Order-and-Design.

Algorithm 1 Order-and-Design

Input $G_{u}=(N,S,u),V,\Phi,k$
Output $w$ if found

1: $S^{\prime}=S$

2: while $\exists s\in S^{\prime}$ do

3: $s=\operatorname*{arg\,min}_{s^{\prime}\in S^{\prime}}V(s^{\prime})$

4: found, $w$ = DESIGN($S,u,s,\Phi,k$)

5: if found then

6: Return $w$

7: else

8: $S^{\prime}=S^{\prime}\setminus\\{s\\}$

9: end if

10: end while

11: Return FALSE

######  Problem 2 (DESIGN).

Given $S=(S_{1},\ldots,S_{n}),u,s=(s_{1},\ldots,s_{n}),\Phi,k$, this
subroutine finds a feasible $w$ that solves the optimization problem

$\displaystyle\min_{w}$ $\displaystyle\|w\|_{1}$ (5) s.t.
$\displaystyle\tilde{u}=M(u,\Phi,w)$
$\displaystyle\tilde{u}^{i}({s_{1},\ldots,s_{n}})\leq\tilde{u}^{i}(s_{i}^{\prime},s_{-i})\quad\forall
s_{i}^{\prime}\neq s_{i}\in S_{i},\forall i\in N$ $\displaystyle\|w\|_{1}\leq
k.$

Here, we only consider $S$ in the pure strategy space. We use $L_{1}$-norm in
constraint $\|w\|_{1}\leq k$ to promote the sparsity of the relationship
weight vector $w$ [12].

###  V-A Correctness

The constraint
$\tilde{u}^{i}({s_{1},\ldots,s_{n}})\leq\tilde{u}^{i}(s_{i}^{\prime},s_{-i})$
for all $s_{i}^{\prime}\neq s_{i}\in S_{i},i\in N$ in Problem 2 provides the
necessary and sufficient conditions for the pure strategy $s$ to be a Nash
equilibrium of the modified cost functions $\tilde{u}$. Thus, it trivially
follows that if the $\textrm{DESIGN}(S,u,s,\Phi,k)$ program returns a solution
$w$, then the modified cost function $\tilde{u}=M(u,\Phi,w)$ is guaranteed to
have a pure Nash equilibrium at $s$. Thus, the DESIGN function is correct by
design.

Unfortunately, due to the additional sparsity constraint on the weight vector
$w$, eq. 5 may not be feasible even if there exists a weight assignment that
leads to a pure Nash equilibrium at the desired pure strategy. Furthermore, it
might be impossible to generate modified costs $\tilde{u}$ with a pure Nash
equilibrium using the admissible weight assignments where $\|w\|_{1}\leq k$.
Thus, it is possible for Algorithm 1 to fail completely and return FALSE. Due
to this shortcoming, it is critical to characterize conditions where the
Algorithm 1 will not fail. Lemma 1 provides such characterization of a
sufficient condition for the Algorithm 1 to never fail.

######  Lemma 1.

Suppose that the game $G_{u}$ has a pure Nash equilibrium $s^{*}$ and the
relationship set $\Phi$ is nonempty. Further suppose that the LP solver used
in the design problem is complete and correct then:

  1. 1.

Algorithm 1 is guaranteed to return $w^{\prime}\neq\textrm{FALSE}$.

  2. 2.

For $\tilde{u}=M(u,\Phi,w)$ is guaranteed to have at least one pure Nash
equilibrium at $s^{\prime}$ such that $V(s^{\prime})\leq V(s^{*})$.

###### Proof.

Since $G_{u}$ has a pure Nash equilibrium on strategy profile $s^{*}$ the
design problem 2 has an optimal feasible solution at $w=\mathbf{0}$. Thus, the
Algorithm 1 can never execute $S^{\prime}=S^{\prime}\setminus\\{s^{*}\\}$ at
line 8 since DESIGN($S,u,s^{*},\Phi,k$) is guaranteed to return found = TRUE.
which will immediately break the loop at line 6 and terminate the algorithm.
Therefore at termination we are guaranteed that $s^{*}\in S^{\prime}$, and
consequently we know that that Algorithm 1 returns
$w^{\prime}\neq\textrm{FALSE}$ since at termination we have
$S^{\prime}\neq\emptyset$. Also, we know that the returned weight vector
$w^{\prime}$ is a solution to DESIGN($S,u,s^{\prime},\Phi,k$) for some pure
strategy profile $s^{\prime}$ satisfying
$s^{\prime}=\operatorname*{arg\,min}_{s\in S^{\prime}}V(s)$ at termination.
Then by the first two constraints in LP problem 2 we are guaranteed that
$s^{\prime}$ is a Nash equilibrium of $\tilde{u}=M(u,\Phi,w)$,
$G_{\tilde{u}}$. Furthermore, since $s^{\prime}=\operatorname*{arg\,min}_{s\in
S^{\prime}}V(s)$ and $s^{*}\in S^{\prime}$ we have $V(s^{\prime})\leq
V(s^{*})$. ∎

###  V-B Worst-case complexity

Despite offering a simple formulation and correctness guarantees, Order-and-
Design suffers from a high worst-case computational complexity. Since
Algorithm 1 removes an element from $S^{\prime}$ in each loop iteration, the
number of times Algorithm 1 calls the DESIGN subroutine is at most
$|S|=\prod_{i\in N}S^{i}$. Thus, assuming that all players have access to at
least two strategies, the maximum number of times the DESIGN subroutine is
called scales exponentially with the number of players. Thus the worst-case
time complexity of Algorithm 1 is at least exponential with the number of
players regardless of the LP solver used to implement the DESIGN subroutine.
Even worse, the number of constraints in the DESIGN LP itself is $2+\sum_{i\in
N}(|S^{i}|-1)$, which grows linearly with the number of players in the game.
The worst-case complexity of the DESIGN subroutine also depends on the LP
solver used to implement it. An interior-point based solver yields a
polynomial time complexity for the DESIGN subroutine, resulting in an
exponential worst-case time complexity for Algorithm 1 with respect to the
number of players. In contrast using the simplex method for the DESIGN LP
yields exponential worst-case time complexity for the DESIGN subroutine with
respect to the number of players, in which case the worst-case time complexity
of the entire Algorithm 1 is double-exponential.

Fortunately, the experimental performance of Algorithm 1 is much better than
this worst-case complexity results. In practical applications, the simplex
method attains much better scaling than its worst-case time complexity would
suggest. Also, it is very rare for Algorithm 1 to go through all possible
strategy profiles in $S$, and a solution is often found within the first few
iterations of the loop. Thus, Algorithm 1 remains useful in practice despite
its high worst-case computational complexity.

######  Running Example 3.

Applying Order-and-Design on the 3-player, 2-route example, we get
$w=[0.2,0,0,0.2,0.2,0]$ for the relationship networks of the individual
relationship type. This means player 1 cares about player 2 with a weight of
0.2, player 2 cares 0.2 for player 3, and player 3 cares 0.2 for player 1, in
a cyclic fashion. The associated game results in a new Nash solution of
$\mathbf{x}=[[1.0,0.0],[1.0,0.0],[1.0,0.0]]$, meaning all players choose to
collaborate in joining route $A$.

##  VI Approximate Solution: Entropy-regularized Nash Gradient Descent

Since Order-and-Design only searches for solutions in the pure strategy space,
we can face situations where it cannot find the more socially desirable
strategies in the mixed strategy space. This section presents a method that
operates in mixed strategy space and modifies the Nash equilibrium defined in
equation 2 by including an additive entropy regularization term. We refer to
this equilibrium as a Entropy-Regularized Nash Equilibrium (Entropy-Nash).

We can rewrite problem 1 by transforming the sparsity constraint as a penalty
term, i.e.,

$\displaystyle\min_{w}$ $\displaystyle J(\mathbf{x},V)+\gamma\|w\|_{1}$ (6)
s.t. $\displaystyle\tilde{u}=M(u,\Phi,w)$
$\displaystyle\mathbf{x}=\text{Nash}(G_{\tilde{u}}).$

A gradient-based method requires us to compute

$\frac{\partial J(\mathbf{x},V)}{\partial w}=\frac{\partial
J(\mathbf{x},V)}{\partial\mathbf{x}}\cdot\frac{\partial\mathbf{x}}{\partial\tilde{u}}\cdot\frac{\partial\tilde{u}}{\partial
w}.$ (7)

The key here is to find the second gradient term
$\frac{\partial\mathbf{x}}{\partial\tilde{u}}$ by differentiating through the
Nash solver. However, the Nash solver almost always outputs pure strategies
for each player, yielding regions of zero gradients (see Fig. 2a). This
prevents further improvement of the relationship weight vector $w$. This is
problematic because in practice these regions cover almost the whole space of
$w$. To solve this issue, we include an entropy regularization term that
smoothens the game and prevents large zero-gradient regions.

(a) Nash Heatmap

(b) Entropy-Nash Heatmap

Figure 2: Heatmaps of expected social cost for Prisoner’s dilemma. (a) The
heatmap for Nash equilibrium, darker regions are more socially desirable. (b)
The heatmap for the entropy-regularized Nash solver. The rigid split of
regions is softened and gradients (cyan arrows) can be properly defined on
this smooth region.

###  VI-A Entropy-Nash

Recall the optimality conditions for Nash are for all $i\in N$,

$\displaystyle\min_{x^{i}}$ $\displaystyle J(\textbf{x},u^{i})$ (8) s.t.
$\displaystyle\mathbbm{1}^{T}{x^{i}}=1.$

Entropy-regularized Nash equilibrium ($\operatorname*{Entropy-Nash}$) builds
on top of the optimality conditions for Nash with an additional term of
entropy for each player, i.e., for all $i\in N$,

$\displaystyle\min_{x^{i}}$ $\displaystyle J(\textbf{x},u^{i})-\lambda
H(x^{i})$ (9) s.t. $\displaystyle\mathbbm{1}^{T}{x^{i}}=1.$

After rearranging we get for all $i\in N$,

$\displaystyle\min_{x^{i}}$
$\displaystyle-\left(-\frac{1}{\lambda}J(x^{-i},u^{i})\right)^{T}x^{i}-H(x^{i})$
(10) s.t. $\displaystyle\mathbbm{1}^{T}{x^{i}}=1.$

Based on Theorem 4 in the thesis [13] by Amos, the solution for this
optimization problem is that $\mathbf{x}=\operatorname*{Entropy-Nash}(G_{u})$
if and only if for all $i\in N$,

$\displaystyle x^{i}$
$\displaystyle=\operatorname*{softmax}\left(-\frac{1}{\lambda}J\left(x^{-i},\tilde{u}^{i}\right)\right).$
(11)

The conditions in eq. 11 shows that the Entropy-Nash equilibrium is
essentially a Quantal Response Equilbrium (QRE), which is commonly used to
model players that are prone to decision making errors [14]. However, due to
differences in our problem setting and purpose, we prefer to call this
solution concept entropy-regularized Nash equilibrium instead of QRE.

We can implement entropy-regularized Nash equilibrium by Newton’s method in
Algorithm 2. In line 4 of the pseudocode, we define function

$\displaystyle F(\mathbf{x},w)=\mathbf{x}-\mathbf{s}\;\text{where}\;$ (12)
$\displaystyle
s^{i}(\mathbf{x},w)=\operatorname*{softmax}\left(-\frac{1}{\lambda}J\left(x^{-i},u^{i}\right)\right),$

and compute Jacobian matrix $\mathbb{J}_{F}$ by

$\mathbb{J}_{F}=I-[\mathbb{J}_{s^{j}}(x^{i})]_{ij},$ (13)

where

$\mathbb{J}_{s^{j}}(x^{i})=\begin{cases}0_{A_{i}\times A_{j}}\quad\text{if
}i=j\\\
\mathbb{J}_{\operatorname*{softmax}}\left(\frac{-h_{j}(\mathbf{x}^{-j})}{\lambda}\right)\frac{-\mathbb{J}_{x^{i}}(h_{j})}{\lambda}\quad\text{otherwise}.\end{cases}$
(14)

$\mathbb{J}_{\operatorname*{softmax}}$ is the Jacobian of the
$\operatorname*{softmax}$ function.

The effect of smoothing by the entropy-regularized Nash equilibrium, in the
context of the prisoner’s dilemma [15], is shown in Fig. 2. We choose a two-
player example here for the sake of visualizing it with a 2-dimensional weight
vector $w=[w_{1},w_{2}]$.

Algorithm 2 Entropy-Nash Solver

Input players’ cost functions $u$, entropy weight $\lambda$, convergence
threshold $\varepsilon$, $max\\_iter$
Output $\mathbf{x}$

1: Initialize $\mathbf{x}$ as random probability distributions

2: for $iter\leq max\\_iter$ do

3: $\mathbf{s}=(s^{i})_{i\in N}$ where
$s^{i}=softmax\left(-\frac{1}{\lambda}J\left(x^{-i},u^{i}\right)\right)$

4: Compute Jacobian matrix $\mathbb{J}_{F}$ by eq. 13

5: Compute step $d=\mathbb{J}_{F}^{-1}(\mathbf{x}-\mathbf{s})$

6: if $\|d\|_{2}<\varepsilon$ then

7: break

8: else

9: $\mathbf{x}\leftarrow\mathbf{x}-d$

10: end if

11: end for

12: return
$\mathbf{x}=\left[\operatorname*{softmax}\left(-\frac{1}{\lambda}J^{i}\left(x^{-i},u^{i}\right)\right)\right]_{i\in
N}$

###  VI-B Entropy-Nash Gradient Descent

Recall that our problem is to minimize the expected social cost. With the
Entropy-Nash solver defined we can write the problem as

$\displaystyle\min_{w}$ $\displaystyle J(\mathbf{x},V)+\gamma\|w\|_{1}$ (15)
s.t. $\displaystyle\tilde{u}=M(u,\Phi,w)$
$\displaystyle\mathbf{x}=\operatorname*{Entropy-Nash}(G_{\tilde{u}}).$

The gradient needed here mimics that of Nash solver in eq. 7, except we need
to differentiate through the Entropy-Nash solver on a relationship game. We
have defined function $F(\mathbf{x},w)$ in eq. 12, and by optimality
conditions given in eq. 11, we have $F(\mathbf{x},w)=0$. By implicit function
theorem [16, Theorem 9.7.2], we have

$\frac{\partial\mathbf{x}}{\partial
w}=-(\mathbb{J}_{\mathbf{x}}F)^{-1}\cdot\mathbb{J}_{w}F.$ (16)

Here, the inverse of the term $\mathbb{J}_{\mathbf{x}}F$ exists almost
everywhere since the $\mathbb{J}_{\mathbf{x}}F$ is always a square matrix.
With the gradients properly computed, we apply gradient descent using
Algorithm 3, called entropy-regularized Nash gradient descent (Entropy-Nash
GD).

Algorithm 3 Entropy-Nash Gradient Descent

Input relationship game $\\{G_{u}=(N,S,u),V,\Phi\\}$, step size $\alpha$,
convergence threshold $\beta$, sparsity coefficient $\gamma$
Output $w$

1: Initialize $w$ as a uniform distribution

2: while $\|\partial w\|\geq\beta$ do

3: $\partial w=\nabla_{w}(J(\mathbf{x},V)+\gamma\|w\|_{1})$

4: update $w=w-\alpha\cdot\partial w$

5: end while

6: return $w$

######  Running Example 4.

Applying Entropy-Nash GD with $\lambda=0.3$ on the 3-player, 2-route game, we
find the relationship weight vector $w=[0.124,0.124,0.124,0.124,0.124,0.124]$.
This results in a new Nash equilibrium of $\mathbf{x}=[[1,0],[1,0],[1,0]]$,
which coincides with the maximally socially desirable strategy profile of all
players choosing route $A$. This result does not look very sparse because
approximating with $L_{1}$-norm constraint means more weight are assigned to
more important relationship networks, and in the case of individual
relationship type all elements are equally impactful for changing the players’
cost functions.

##  VII Experiments

###  VII-A Experimental Setup

We implement our proposed solutions in Julia [17]. For Order-and-Design, we
use the algebraic modeling language JuMP [18], with the Gurobi Solver. For
Entropy-Nash GD, we implemented a new entropy-regularized Nash solver, and
computed its gradient using Zygote [19]. The source code is publicly available
at https://github.com/vivianchen98/relationship_game.

We use the $n$-player Nash equilibrium as our baseline. We applied the
proposed algorithms to the generalized traffic example similar to that in Fig.
1. $n$ players are traveling from origin to destination through $m$ routes,
where route $A$ is car-pool with a cost function of $u(l_{A})=2.5\cdot
n/l_{A}$, and other routes have cost functions to be multiples of their
corresponding traffic loads, with coefficients from $\\{1.5,2,4,4.5,5\\}$.

###  VII-B Effectiveness

First, we aim to demonstrate the effectiveness of the proposed methods in
forging more socially desirable game solutions than the baseline. Table. I
shows the performance of the proposed methods on 2-route traffic examples with
2 to 5 players. Order-and-Design gives rise to solutions equally or more
socially desirable than the baseline does. Entropy-Nash GD successfully leads
to maximally socially desirable strategy profiles in all cases, with tuning of
its parameters required.

The parameters needed tuning are the coefficient for sparsity penalty $\gamma$
and the entropy weight $\lambda$. The parameters are the same for $n=2,3$.
However, as we get to 4 players in the game, the $L_{1}$-norm for the weight
vector increases as its size doubles from $6$ when $n=3$ to $12$ when $n=4$.
Hence, we need to drop $\lambda$ from $1.0$ to $0.6$ because we do not want to
optimize more for the sparsity constraint than the primary objective of
minimizing the expected social cost. As the number of players further
increases, we need to continue decreasing $\gamma$. At the same time, more
players in the game lead to the possibility of multiple Nash solutions and
make the gradient descent easily stuck in local minima. To overcome this
situation with a higher degree of smoothing, we also need to gradually
increase the entropy weight $\lambda$, from $0.3$ when $n=2,3$ to $0.6$ when
$n=4$, and then again to $0.9$ when $n=5$.

TABLE I: $n$-player, 2-action traffic example with $V=\sum_{i=1}^{n}u^{i}$,
$\Phi=$ individual

Algorithms | Number of Players
---|---
Name | Result | 2 | 3 | 4 | 5
Optimal | $a^{*}$ | $[1,1]$ | $[1,1,1]$ | $[1,1,1,1]$ | $[1,1,1,1,1]$
$V_{min}$ | $3.33$ | $5.0$ | $6.67$ | $8.33$
Nash | $a$ | $[2,2]$ | $[2,2,2]$ | $[2,1,1,1]$ | $[1,2,1,1,1]$
$J(a)$ | $6.0$ | $10.30$ | $8.17$ | $9.83$
Order-and-Design | $\tilde{a}$ | $[1,1]$ | $[1,1,1]$ | $[2,1,1,1]$ | $[1,1,1,1,1]$
$J(\tilde{a})$ | $3.33$ | $5.0$ | $8.17$ | $8.33$
Entropy-Nash GD1 | $\lambda$ | 0.3 | 0.3 | 0.6 | 0.9
$\gamma$ | 1.0 | 1.0 | 0.3 | 0.1
$\tilde{x}$2 | $[1,1]$ | $[1,1,1]$ | $[1,1,1,1]$ | $[1,1,1,1,1]$
$J(\tilde{x})$ | $3.33$ | $5.0$ | $6.67$ | $8.33$

  * 1

All instances run with $\alpha=0.01,\beta=0.1$.

  * 2

Mixed strategy presented in the form of pure strategy when the particular pure
strategy is selected with probability 1 and every other strategy with
probability 0, i.e., $[[1.0,0.0],[1.0,0.0]]$ is denoted by $[1,1]$.

###  VII-C Scalability

Using the same generalized traffic cases, we also study the computational
scalability of the two algorithms with respect to the number of players from
$2$ to $18$. Fig. 3 shows the log-scale runtimes of two algorithms under
2-route traffic examples. The linear trendlines show both methods grow
exponentially with respect to the number of players, with Order-and-Design
growing faster than Entropy-Nash GD.

$2$$4$$6$$8$$10$$12$$14$$16$$18$$-2$$0$$2$$4$Number of players, $n$Log
Runtime, $\log_{10}(t)$ [s]Order-and-Design$\log_{10}(t)=0.306n-2.98$Entropy-
Nash GD$\log_{10}(t)=0.295n-2.91$ Figure 3: Log scale runtime with respect to
number of players. The trendlines are linear for both methods, suggesting both
methods scale exponentially, but Order-and-Design grows faster than Entropy-
Nash GD as $0.306>0.295$ in their equations.

###  VII-D Effect of relationship type

As shown in Fig. 1b, we look into the effect of three types of relationships:
individual relationships which represents one-to-one relations between any two
players in the game, all-people relationships which represents the relations
from one player to all other players, and reciprocity relationships which
represents the reciprocal relations between any two players. The results in
Table. II show that our hypothesis of autonomous agents being able to achieve
socially desirable behavior through instilling player relationships is true,
at least in this generalized traffic example. All three relationship types can
lead to the maximally socially desirable strategy profile via both solutions.
Relationship type individual takes more computation in Order-and-Design than
the other two types because it has more elements in the set and hence more
constraints in the linear program. However, Entropy-Nash GD takes fewer steps
to converge with the relationship type individual than the other two types
because more elements mean fewer constraints in the weight vector and
ultimately allow gradient descent to explore more freely.

TABLE II: Effect of three types of relationships (see 1b) on 3-player,
2-action traffic example with $V=\sum_{i=1}^{n}u^{i}$

Algorithms | Types of player relationships, $\Phi$
---|---
Name | Result | individual | all-people | reciprocity
Order-and-Design | $\tilde{a}$ | $[1,1,1]$ | $[1,1,1]$ | $[1,1,1]$
# constraint | 16 | 10 | 10
Entropy-Nash GD1 |  $\tilde{x}$2 | $[1,1,1]$ | $[1,1,1]$ | $[1,1,1]$
# step | 24 | 39 | 39

  * 1

All instances run with $\alpha=0.01,\beta=0.1$, and $\lambda=0.3,\gamma=1.0$.

  * 2

Mixed strategy presented in the form of pure strategy.

##  VIII Conclusion & Future Work

We have formalized a notion of a relationship game, and considered the new
problem of relationship weight vector design. We have proposed two solutions
to solve this problem. Order-and-Design is an exact method that designs
relationship weight vectors to achieve pure Nash equilibria in ascending order
of social costs by solving a series of Linear Program (LP) problems. Entropy-
regularized Nash gradient descent (Entropy-Nash GD) is a gradient descent
algorithm on an entropy-regularized Nash equilibrium.

For Order-and-Design, we presented a proof of its correctness and showed its
worst time to grow exponentially with the number of players. Empirical results
corroborate this theoretical finding and show runtime for the Entropy-Nash GD
grows slower. Experiments on generalized traffic examples demonstrate the
effectiveness of both methods to forge collaborative outcomes by finding
appropriate relationship weight vectors. Overall, Order-and-Design gives
sparser weight vectors when the scale of an example is small and does not
require any parameter tuning, whereas Entropy-Nash GD runs faster with more
players in the game yet needs more tuning. The usage of the two methods should
be determined based on the particular game setting in different problems.

Despite these encouraging results, there is ample room for future work. In
this work, we focus on static games, limiting the applicability of the methods
from sequential decision-making needed scenarios. Future work should
investigate the extension to dynamic games. Another direction is on the
improvement of the Entropy-Nash solver. Currently, we need to tune the
proportion of entropy needed in the objective in order to counter the
situation of non-unique Nash solutions. We intend to fix this by developing
solvers that only output unique solutions. Finally, the three types of player
relationships tested in this work are only a conspicuous set of dynamics among
players. More sophisticated relations can be studied in the future.

## References

  * [1] S. Suranovic, “Distinguishing Self-interest from Greed: Ethical Constraints and Economic Efficiency,” _Social Science Research Network_ , 2020.
  * [2] A. Nowé, P. Vrancx, and Y.-M. D. Hauwere, “Game Theory and Multi-Agent Reinforcement Learning,” in _Reinforcement Learning_ , 2012.
  * [3] T. Başar and G. J. Olsder, _Dynamic Noncooperative Game Theory_. SIAM, 1998.
  * [4] B. Kuipers, “Perspectives on Ethics of AI,” in _The Oxford Handbook of Ethics of AI_ , 2020.
  * [5] M. Kleiman-Weiner, R. Saxe, and J. B. Tenenbaum, “Learning a Commonsense Moral Theory,” in _Journal of Cognition_ , 2017.
  * [6] M. J. Kearns, M. L. Littman, and S. P. Singh, “Graphical Models for Game Theory,” in _Proceedings of the Conference in Uncertainty in Artificial Intelligence_ , 2001.
  * [7] J. Letchford, V. Conitzer, and K. Jain, “An “Ethical” Game-Theoretic Solution Concept for Two-Player Perfect-Information Games,” in _Proceedings of the International Workshop on Internet and Network Economics_ , 2008.
  * [8] A. Davoust and M. Rovatsos, “Social Contracts for Non-Cooperative Games,” in _Proceedings of the Conference on AI, Ethics, and Society_ , 2020.
  * [9] E. Koutsoupias and C. Papadimitriou, “Worst-Case Equilibria,” in _Journal of Computer science Review_ , 2009.
  * [10] Y. Narahari, _Game Theory and Mechanism Design_. World Scientific, 2014.
  * [11] S. Kakade, M. Kearns, J. Langford, and L. Ortiz, “Correlated Equilibria in Graphical Games,” in _Proceedings of the Conference on Electronic Commerce_ , 2003.
  * [12] C. Ramirez, V. Kreinovich, and M. Argaez, “Why $l1$ Is a Good Approximation to $l0$: A Geometric Explanation,” in _Journal of Uncertain Systems_ , 2013.
  * [13] B. Amos, “Differentiable Optimization-Based Modeling for Machine Learning,” Ph.D. dissertation, Carnegie Mellon University, 2019.
  * [14] R. D. McKelvey and T. R. Palfrey, “Quantal Response Equilibria for Normal Form Games,” in _Journal of Games and Economic behavior_ , 1995.
  * [15] M. J. Osborne and A. Rubinstein, _A Course in Game Theory_. MIT press, 1994.
  * [16] J. L. Taylor, _Foundations of Analysis_. American Mathematical Soc., 2012.
  * [17] J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah, “Julia: A Fresh Approach to Numerical Computing,” in _Jornal of SIAM Review_ , 2017\.
  * [18] M. Lubin and I. Dunning, “Computing in Operations Research Using Julia,” in _INFORMS Journal on Computing_ , 2015.
  * [19] M. Innes, A. Edelman, K. Fischer, C. Rackauckas, E. Saba, V. B. Shah, and W. Tebbutt, “A Differentiable Programming System to Bridge Machine Learning and Scientific Computing,” in _arXiv preprint arXiv:1907.07587_ , 2019.