# Game-Theoretic Models of Moral and Other-Regarding Agents

Gabriel Istrate West University of Timişoara<EMAIL_ADDRESS>
###### Abstract

We investigate Kantian equilibria in finite normal form games, a class of non-
Nashian, morally motivated courses of action that was recently proposed in the
economics literature. We highlight a number of problems with such equilibria,
including computational intractability, a high price of miscoordination, and
problematic extension to general normal form games. We give such a
generalization based on concept of _program equilibria_ , and point out that
that a practically relevant generalization may not exist. To remedy this we
propose some general, intuitive, computationally tractable, other-regarding
equilibria that are special cases Kantian equilibria, as well as a class of
courses of action that interpolates between purely self-regarding and Kantian
behavior.

##  1 Introduction

Game Theory is widely regarded as the main conceptual foundation of strategic
behavior. The promise behind its explosive development (at the crossroads of
Economics and Computer Science) is that of understanding the dynamics of human
agents and societies and, equally importantly, of guiding the engineering of
artificial agents, ultimately capable of realistic, human-like, courses of
action. Yet, it is clear that the main models of Game Theory, primarily based
on the self-interested, rational actor model, and exemplified by the concept
of Nash equilibria, are not realistic representations of the richness of human
interactions. Concepts such as _bounded rationality_ [82], and the limitations
they impose on the computational complexity of agents’ cognitive models [75]
can certainly account for some of this difference. But this is hardly the only
possible explanation: People behave differently from ideal economic agents not
because they would be irrational [4], but since many human interactions are
cooperative, rather than competitive [89], guided by social norms such as
_reciprocity, fairness_ and _inequity-aversion_ [21], often involving
_networked minds_ , rather than utility maximization performed in isolation
[41], driven by moral considerations [90] or by other not purely self-
regarding behaviors, e.g. _altruism_ [50] and _spite_ [25, 24].

Moral considerations (should) interact substantially with game theory: indeed,
the latter field has been used to propose a reconstruction of moral philosophy
[14, 13, 15]; conversely, some philosophers have gone as far as to claim that
we need a _moral equilibrium theory_ [85]. Whether that’s true or not, it is a
fact that _homo economicus_ , the Nash optimizer of economics, is increasingly
complemented by a rich emerging typology of human behavior [42], that also
contains (in Gintis’s words) "homo socialis, the other-regarding agent who
cares about fairness, reciprocity, and the well-being of others, and homo
moralis 111since our agents are not necessarily human, we will use alternate
names such as ”moral agent” for this type of behavior. … the Aristotelian
bearer of nonconsequentialist character virtues".222Gintis proposes a taxonomy
of behavior with three distinct types of preferences: _self-regarding_ ,
_other regarding_ and _universalist_ ; a further relevant distinction is
between so-called _private_ and _public personas_ , that leads to further
types of behavior such as homo Parochialis, homo Universalis and homo Vertus.
See [42] for further details. These claims are well-documented experimentally:
for instance, Fischbacher et al. [34] investigated the percent of people
having self-regarding preferences in a public goods game, showing that it is
in the range of 30-40%, while the remaining were either other-regarding or
moral agents. Since artificial agents (will) interact with humans, such
concerns are highly relevant to the design of multiagent systems and justify
the study of alternative other-regarding notions, e.g. Rong and Halpern’s [46,
74] "cooperative equilibria" or _dependency theory_ [81, 44]. Other-regarding
considerations could be encoded (e.g. [33]) as _externalities_ into agents’
perceived utilities, that may lead them away from straightforward maximization
of their material payoffs. However, keeping them explicit may be important for
agent implementations.

The purpose of this paper is to contribute to the emerging literature on non-
Nashian, morally inspired game theoretic concepts and, equally important, to
bring its concerns and methods to the attention of the various interested
communities. We are inspired by what we believe is one of the most intriguing
classes of equilibrium concepts that can be seen as morally grounded: _Kantian
(a.k.a. Hofstadter) equilibria_ [73]. This notion emerged from three separate
lines of research converging on an identical mathematical definition, but
justifying it, however, from several very different perspectives:
_superrationality_ [52, 36], _team reasoning_ [7], and _Kantian optimization_
, respectively [73].

The common framework (crisply developed for symmetric coordination games) only
considers as relevant the action profiles where all agents choose _the same
action_ , choosing the action $x$ that, if played by everyone, maximizes
agents’ (identical) utility functions. The justification of this restriction
depends on the perspective: _superrationality_ assumes that if rationality
constrains an agent to choose a specific course of action $x$, then the same
reasoning compels all agents (at least in the case of symmetric games, when
all agents are positionally indistinguishable from the original agent) to also
choose $x$.333To cite Hofstadter: ”If reasoning dictates an answer, then
everyone should independently come to that answer. Seeing this fact is itself
the critical step in the reasoning toward the correct answer […]”. Though
superrationality does away with the assumption of counterfactual independence
of Nash equilibria, it is otherwise compatible with a particular version of
homo economicus that requires some very strong assumptions on agent
rationality (see [36] for a discussion). In contrast, _Kantian optimization_
justifies the limitation to symmetric profiles in a very different manner:
Roemer [71] suggested that agents often ignore the potential for action of the
other players, acting instead according to the _Kantian categorical
imperative_ [77] "act only according to that maxim whereby you can, at the
same time, will that it should become a universal law", that is, choose a
course of action that, if adopted by every agent, would bring all agents the
highest payoff. 444As recognized by Roemer himself and discussed e.g. in [22],
the connection of Kantian equilibria to actual Kantian ideas is quite loose.
Another possible interpretation is that Kantian equilibria embody rule
utilitarianism [49]. Finally, see [79] for a discussion of the normative
aspects of Kantian equilibria.  One way to formalize this idea, employed e.g.
in [2], is to decouple the material payoffs agents receive from their
(perceived) utility, which agents maximize in order to select the action.
Specifically, assume the given agent $i$ plays strategy $x$ against action
profile $y$. We assume that the material payoff the agent receives is
$\pi_{\\_}{i}(x,y)$. On the other hand the utility the agent uses to evaluate
alternative $x$ may not be equal to $\pi_{\\_}{i}(x,y)$ and may in fact, have
in fact nothing to do with $y$ at all! Instead,
$u_{\\_}{i}(x,\textbf{y})=\pi_{\\_}{i}(x,\overline{x}_{\\_}{-i}),$ where
$\overline{x}_{\\_}{-i}$ is the action profile where all agents other than $i$
play $x$ as well. That is, the agent evaluates the desirability of action $x$
in isolation from the actions of the other players, as if choosing $x$ could
somehow "magically" determine the other players to adopt the same strategy.
555Frank [37] refers to this as _voodoo causation_. Elster [32] argues that
Kantian optimization seems to be rooted in a form of _magical thinking_ ,
”causing agents to act on the belief (or act as if they believed) that they
can have a causal influence on outcomes that are effectively outside their
control”. We take a descriptive, rather than normative position: such
reasoning is something people simply do; understanding its implications is
strategically valuable. Alternatively, $\pi(x,\overline{x}_{\\_}{-i})$
measures the extent to which action $x$ is "the morally best course of
action". Such a justification is cognitively plausible: experiments have shown
[59] that people often employ such "universalization" arguments when judging
the morality of a given behavior.

The questions we attempt to start answering in this paper are:

  * 1.

Can we extend the definition of Kantian equilibria to cover all natural cases
of "Kantian behavior"?

However, we are not simply looking in our generalization for yet another
equilibrium notion of primarily mathematical interest, but for one satisfying
specific tractability requirements that ensure easy implementation in
computational agents. Specifically, a target concept should at least be: (I)
expressive, i.e. indicative of realistic behavior of human agents in
sufficiently typical situations (II) cognitively plausible: the equilibrium
should not be justifiable in terms of expensive epistemic assumptions (the way
common knowledge of rationality can be used to justify Nash equilibria [5]);
(III) logically tractable: proposed equilibria should be easy to specify
formally, in a way that translates to efficient implementations. (IV)
computationally tractable: equilibria should be easy to compute [75], since
bounded rational agents are assumed to compute (and play) them.

The main message of the paper is that any general notion of Kantian equilibria
may be of theoretical interest only: while an interesting extension for
certain symmetric games exists (Sec. 4) based on _program equilibria_ , it’s
not clear how to further extend it. Together with intractability (Thm. 2) this
suggests that a general, practically relevant, notion of Kantian equilibrium
might not exist.

  * 2.

What is the relation between Kantian equilibria and Bacharach’s (informally
defined) team-reasoning equilibria [7]? The answer is that Kantian equilibria
are a proper subset of team-reasoning equilibria.

  * 3.

Given that the answer to Q1 is negative, are there more specialized equilibria
related to Kantian optimization that satisfy (I)-(IV)? We will show that there
exist, indeed, several more restrictive equilibrium notions, satisfying
tractability and plausibility constraints, and relate them to Kantian
equilibria.

  * 4.

Real people are seldom purely selfish or purely Kantian. (How) can we
formalize this? We give such a definition, and motivate it through the case of
Prisoners’ Dilemma.

The outline of the paper is as follows: In Section 2 we review some basic
notions. In Section 3 we obtain some further results on (and highlight some
limitations of) Kantian equilibria: first of all, we point out that finding a
mixed Kantian equilibrium is computationally intractable even for two-player
symmetric games (Theorem 2). Second, multiple Kantian equilibria may exist,
and lack of coordination on the same equilibrium may be detrimental to
players, even with all of them playing a common linear combination of Kantian
actions. In Section 4 we discuss the problem of extending Kantian equilibria
to non-symmetric games. giving a proposal based on the concept of program
equilibria. As such, our proposal inherits the problems of this concept. Given
these problems, in Section 5 we propose several other-regarding
equilibria.666Generally, ethical egoism and its variant, rational egoism, are
not accepted as a basis of moral behavior; counterexamples exist, [69];
however, it’s fair to say that such positions are controversial, and somewhat
marginal. In contrast, moral and other-regarding behaviors are better aligned,
with other-regarding behavior often a consequence of moral play. We show
(Theorem 6) that these equilibria can be computed efficiently, that they are
indeed Kantian equilbria (according to our generalized definition), and that
they yield Kantian equilibria for symmetric coordination games. Finally, in
Section 6 we relax the assumption that the agents are other-regarding: we
assume that agents have a degree of greed, zero for Kantian agents, infinite
for Nashian agents. We show (Theorem 8) how our definition applies to
Prisoners’ Dilemma.

For reasons of space, all proof details are deferred to the Appendix. So have
we done, for reasons of abundance of technical details, with some of the
results: e.g. the ones the proper definition and characterization of Kantian
program equilibria (Theorems 9, 10), which also clarify the connection between
Kantian and _team reasoning equilibria_.

##  2 Preliminaries

We assume knowledge of basic results of game theory at the level of a textbook
such as, e.g. [66], in particular with concepts such as normal form games,
best response strategy, and mixed (Nash) equilibria. All the games $G$ we
consider are normal form and, unless mentioned otherwise, have identical
action sets $Act_{\\_}{G}$ for all players. Given a finite set $S$, we will
define $\Delta(S)$ to be the set of probability distributions on $s$. Elements
of $\Delta(S)$ are functions $c:S\rightarrow[0,1]$ satisfying
$\sum\limits_{\\_}{i\in S}c(i)=1$. $\Delta^{n}:=\Delta(\\{1,2,\ldots,n\\})$
is, geometrically, a $(n-1)$-dimensional simplex. When $G$ is a normal-form
game and $k$ a player in the game we will denote by $\Delta_{\\_}{G}^{k}$ the
set of mixed actions available to player $k$, identified with some simplex
$\Delta^{n}$ with a suitable dimension. We will occasionally drop $k$ from the
notation and simply write $\Delta_{\\_}G$ instead when the player is clear
from the context, or when all agents have the same action set. Given vectors
$x=(x_{\\_}{1},\ldots,x_{\\_}{n})$ and $y=(y_{\\_}{1},\ldots,y_{\\_}{n})$, we
say that _$x$ dominates $y$_ iff $x_{\\_}{i}\geq y_{\\_}{i}$ for all
$i=1,\ldots,n$. The domination is _strict_ if at least one inequality is. When
comparing (mixed) action profiles a and b, the domination relation may apply
to the vectors of agent utilities
$(u_{\\_}{1}(\textbf{a}),\ldots,u_{\\_}{n}(\textbf{a}))$ and
$(u_{\\_}{1}(\textbf{b}),\ldots,u_{\\_}{n}(\textbf{b}))$, respectively. Action
profiles that are strictly dominated may be assumed not to occur in game play.

A game with identical action sets is _diagonal_ if every pure action profile
is dominated by some profile on the diagonal, the set of action profiles where
all players play the same action. A particular class of diagonal games are
_coordination games_ , where all player utilities are zero outside the
diagonal. Such a game is _symmetric_ if, additionally, agent utilities are
identical for all action profiles on the diagonal.

######  Definition 1.

Let $G$ be a game with common action set $A$. A _variation function_ is a
function $\phi:\Xi\times A\rightarrow A$, for some set of parameters
$\Xi$.777The precise form of this definition follows [79], and is motivated by
Roemer’s definition of _additive/multiplicative Kantian equilibria_ , with
action set $A=\mathbb{R}_{\\_}{+}$ and variation functions $\phi(r,a)=a+r$,
$a\cdot r$, respectively. We will mostly be concerned with variation functions
of the type ”change (everyone’s) current action to b” (for $b\in A$).
Formally, $\Xi=A$ and $\phi(b,a)=b$. A _Kantian (Hofstadter) equilibrium_ is a
pure strategy profile $x^{opt}=(x^{opt}_{\\_}{1},\ldots,x^{opt}_{\\_}{n})$
that maximizes the material payoff of each agent, should everyone deviate
similarly. Formally, for every agent $i$ and $r\in\Xi$,

$V_{\\_}i(x^{opt}_{\\_}{1},\ldots,x^{opt}_{\\_}{n})\geq
V_{\\_}{i}(\phi(r,x^{opt}_{\\_}{1}),\ldots,\phi(r,x^{opt}_{\\_}{n})).$

######  Example 1.

One of the original applications of Kantian equilibria was Prisoners’ Dilemma
(PD, Fig. 1 (a)). Kantian equilibria provide an elegant solution to the
paradox: Kantian agents coordinate on action profile (C,C), as jointly doing
so gives them a higher payoff than the Nash equilibrium (D,D).

22[Player 1][Player 2] & C D

C $2,2$ $0,3$

D $3,0$ $1,1$

22[Player 1][Player 2] & B S

B $2,3$ $0,0$

S $1,1$ $3,2$

Figure 1: a. Prisoners’ Dilemma. b. BoS game as modified by Roemer.

Kantian equilibria are easiest to justify for symmetric diagonal games, since
in this case they dominate all other action profiles, thus can be properly
seen as "best course of action for all". There are symmetric (nondiagonal)
games, though, where no pure strategy Kantian equilibrium is adequate, and
which seem to compel us to considering mixed-strategy Kantian equilibria. An
example is Hofstadter’s "Platonia’s Dilemma" [52], a special case of the
_market entry games_ of Selten and Güth [78]:

######  Definition 2.

In Platonia Dilemma $n$ agents (say, $n=20$) are offered to win a prize.
Agents may choose to send their name to a referee. An agent wins the prize if
and only if it is the only one submitting their name: if zero or at least two
agents send their names then noone wins anything.

It is easy to see that both pure strategies, sending/not sending their name,
are equally bad if adopted by all agents: they get zero payoff. A better
option is to allow independent randomization:

######  Definition 3.

Given a game $G$ with identical actions, a mixed Kantian agent will choose a
mixed strategy $X^{OPT}\in\Delta_{\\_}G$ that maximizes its expected utility,
should everyone play $X$. For two-player symmetric games with game matrix $A$
and variation function $\phi(b,a)=b$ we have
$X^{OPT}=argmax\\{y^{T}Ay:y\in\Delta_{\\_}{G}\\}$.

######  Lemma 1.

In Platonia Dilemma the probabilistic strategy where each agent independently
submits their name with probability $p$ brings an expected profit to every
agent equal to $p(1-p)^{n-1}$. This quantity is maximized for $p=\frac{1}{n}$.
Thus the strategy with $p=\frac{1}{n}$ is a mixed Kantian equilibrium.

##  3 Limitations of Mixed Kantian Equilibria

In this section we note some properties of mixed Kantian equilibria. They are
mostly negative: finding a mixed Kantian equilibrium is intractable. Also,
such equilibria may be vulnerable to miscoordination.

###  3.1 The Computational Intractability of Mixed Kantian Equilibria

We make an easy observation concerning the computational complexity of mixed
Kantian equilibria in symmetric two player games. To our knowledge this has
not been discussed before. Note: such equilibria are guaranteed to exist,
since the $(n-1)$-dimensional simplex of mixed strategies is a compact set and
the common utility function is continuous. First of all, finding a mixed
Kantian equilibrium is easy in symmetric coordination games, as all such
equilibria coincide with pure Kantian equilibria.

######  Theorem 1.

Consider a finite symmetric coordination game. Then mixed Kantian equilibria
coincide with pure Kantian equilibria. Hence one can compute mixed Kantian
equilibria in polynomial time.

Platonia Dilemma with $n=2$ shows that Theorem 1 does not extend to general
symmetric games. This is no coincidence: in this case finding (or just
detecting) the optimal mixed strategy is intractable:

######  Theorem 2.

The following problem, called MIXED KANTIAN EQUILIBRIUM, is NP-hard:

  * INPUT: A two-player symmetric game $G$, and an aspiration level $r\in\mathbb{Q}$.

  * TO DECIDE: Is there a mixed strategy profile $x=(x_{\\_}1,\ldots,x_{\\_}N)$ such that the utility of every player under common mixed action $x_{\\_}{1}a_{\\_}1+x_{\\_}{2}a_{\\_}2+\ldots+x_{\\_}{m}a_{\\_}{m}$ is at least $r$?

###  3.2 Multiple Equilibria and miscoordination

Optimal diagonal action profiles may fail to be unique. If the agents are not
communicating (and no implicit coordination mechanisms are acting, e.g., one
of the action profiles being a _focal point_ , such as in the Hi-Lo game from
[8]), agents may reach a suboptimal action profile due to their lack of
coordination on the same optimal action: Consider, indeed, the game in Figure
2. $(C,C)$ and $(E,E)$ are equally good pure (and mixed) Kantian equilibria.
But if one player plays $C$ and the other plays $E$ the resulting outcomes are
the worst possible for both of them, being dominated by every single possible
strategy profile! Randomizing among Kantian actions might not help either:
miscoordination impacts even "Kantian" scenarios, where players, lacking a
salient equilibrium to coordinate on, play a joint mixed strategy formed of
Kantian actions.888Such a scenario is, of course, not justifiable from a usual
rational choice perspective. But it is justifiable in a Kantian setting where
every player believes that choosing a pure action $a$ will immediately make
all other players do the same: a player may use the Kantian imperative to
restrict itself to pure Kantian equilibria, then use the assumption to justify
playing a convex combination of pure Kantian equilibria it is indifferent
between. We quantify the degradation in performance as follows:

33[Pl1][Pl 2] & C D E

C $5,5$ $3,6$ $1,2$

D $6,3$ $4,4$ $6,3$

E $2,1$ $3,6$ $5,5$

22[][Pl2] & C D

C $10,1$ $0,0$

D $0,0$ $4,2$

22[][Pl2] & B S

B $6,1$ $0,0$

S $0,0$ $3,2$

22[][Pl2] & C S

C $10,10$ $100,200$

S $200,100$ $6,6$

Figure 2: (a). A game with multiple Kantian equilibria. (b). Modified BoS
(Example 3). (c). Modified BoS (Example 2). (d). An anti-coordination game.

######  Definition 4.

For a symmetric game $G$ with strictly positive payoffs let $NC$ be the set of
mixed action profiles composed of Kantian actions only. The _price of
miscoordination_ of $G$ is the ratio $p(G)=\sup\limits_{\\_}{a\in
NC}\frac{u_{\\_}{i}(X^{OPT})}{u_{\\_}{i}(a)}$. Because of symmetry this does
not depend on the particular choice of player $i$.

The following result shows that the price of miscoordination can be
arbitrarily large:

######  Theorem 3.

Let $G$ be a symmetric diagonal game with $k\geq 2$ players and $r\geq 1$ pure
Kantian actions. Then the price of miscoordination of $G$ is in the range
$[1,r^{k-1}]$. Both bounds are tight and can be reached in settings where
players choose a Kantian action uniformly at random.

The merit of this simple result is to point out that the definition of
generalized Kantian equilibria needs to include scenarios where randomness is
correlated, as in _correlated equilibria_ (see e.g. [80]).

##  4 Kantian Program Equilibria in (Pareto) Symmetric Games

Definition 1 of Kantian equilibria makes the most sense in symmetric
coordination games, but does not capture all the intuitive cases of Kantian
behavior. Indeed, let us consider the BoS game, as modified by Roemer (Fig. 1
(b)).999Roemer ([73], Proposition 2.3) argues that (S,B) is a simple Kantian
equilibrium. His argument is, however, ad-hoc, based on making this profile
”diagonal” by flipping the order of B and S for the second player, and the
conclusion that $(B,S)$ is Kantian is, we feel, unintuitive, since
$(B,B),(S,S)$ strictly dominate it. Our protocol plays
$\frac{1}{2}(B,B)+\frac{1}{2}(S,S)$, different from (and better than) what
Roemer calls the mixed Kantian equilibrium, where row player plays
$\frac{3}{8}B+\frac{5}{8}S$ and the column player plays
$\frac{3}{8}S+\frac{5}{8}B$. Intuitively, agents would perhaps agree that the
following protocol could be called Kantian, in that it is symmetric and both
players benefit if they both follow it: flip a fair coin; if it comes out
_heads_ , they (both) play $B$, else both play $S$. As described, the protocol
requires the centralized choice of a random bit, but it could easily be
implemented in a distributed manner by making each of the two agents flip a
(fair) coin and taking their XOR. The implementation of the protocol
(Algorithm 4) assumes that each agent is parameterized by an _agent ID_
$i\in\\{1,2\\}$ (not needed in this particular case) and vector $(myb,otherb)$
of random bit choices, one for each player, and shared between players.

An even more dramatic case is that of the game from Figure 2 (d), where the
best outcomes are not symmetric. In these cases it even seems irrational for
the agents to play symmetric action profiles, since these action profiles are
dominated by all the other action profiles! Rather, it is plausible that
agents would agree that they need to anticoordinate, but they have different
preferences for the joint action profile to coordinate upon. A "best for all"
solution would jointly play a random anti-coordinated profile
$\frac{1}{2}(C,S)+\frac{1}{2}(S,C)$. As in the previous example, this course
of action can be implemented by the two agents in a distributed manner, by
jointly playing according to the protocol in Algorithm 4. In this example, in
addition to the extra bit $otherb$ communicated by the other player, the
protocol of each agent makes explicit use of the agents’ own $id$,
$i\in\\{1,2\\}$. BoS BOS(i::ID,myb::BIT,otherb::BIT) Randomly choose a bit
myb∈{0,1} communicate mybit to the  other player as its otherb. if [myb⊕otherb
== 0] then play B else play S Anticoord Anticoord(i::ID,myb::BIT,otherb::BIT)
Randomly choose a bit myb ∈{0,1} communicate myb to the other player as its
otherb. if [myb⊕otherb ≡i  (mod 2)] then play C else play S

The intuitive conclusion of these two examples is simple: Definition 1 is not
sufficient. Some simple games may have coordinated protocols that could
properly be called "Kantian". In this section we give a somewhat more general
definition101010other plausible alternatives are discussed (and ruled out) in
Section 13 of the Appendix. Of special interest is the relation between
Kantian equilibria and _team-reasoning equilibria_. of Kantian equilibria, but
not for general games, only for a class of "symmetric" games. There are
multiple definitions of game symmetry in the literature [47, 87]; the most
important one requires that for every player $i$, action profile
$(x_{\\_}1,x_{\\_}2,\ldots,x_{\\_}n)$ and permutation $\sigma\in S_{\\_}{n}$,
we have
$u_{\\_}{\sigma(i)}(x_{\\_}1,x_{\\_}2,\ldots,x_{\\_}n)=u_{\\_}{i}(x_{\\_}{\sigma(1)},x_{\\_}{\sigma(2)},\ldots,x_{\\_}{\sigma(n)})$.
We we use a slightly less demanding definition (we call our version _Pareto
symmetry_ , see Definition 16 in the Appendix) to capture some asymmetric
games like Romer’s version of BoS. This game is asymmetric, but in an
inconsequential way: all the asymmetries concern dominated profiles. Our
extension is inspired by the concept of program equilibria [53, 86]. To define
these equilibria we associate to every finite normal-form game an extended
game whose actions correspond to _programs_. Agents’ programs have access to
own and others’ sources111111this aspect was important for Nashian
optimization. It will be less so for us, since deviations are not present in
the definition of Kantian equilibria. On the other hand, a Kantian agent
playing program $P$ can make sure it is not taken advantage upon by the other
players, either alone, as in [86], by reading other players’ programs and only
playing $P$ when all do, or with the help of a _mediator_ , which implements
on behalf of all players the following protocol: if all agents follow $P$ then
the mediator will simulate $P$ on behalf of the agent; otherwise it will play
in a Nashian way. , and can act on them. A program equilibrium is a Nash
equilibrium in the extended game. We extend this idea to Kantian equilibria:

######  Definition 5.

Given a (Pareto symmetric) game $G$ with identical actions sets for all
players, a _Kantian program equilibrium in $G$_ is a probability distribution
$p$ on the action profiles of $G$ such that: (a). $p$ has its support on the
set of Pareto optimal strategies. (b). $p$ is implemented by agents playing a
common program $P$ in the extended game. (c). there exists no probability
distribution $q$ with properties a. and b. such that the vector of expected
utilities $(E[u_{\\_}{i}(q)])$ strictly dominates the vector
$(E[u_{\\_}{i}(p)])$.

The assumption that _players have the same action sets_ is motivated by the
"common program" requirement of Def. 5 (b). Point (a). encodes a simple
rationality condition. Points (b). and (c). embody a generalized version of
the Kantian categorical imperative: (b). encodes the constraint of identical
behavior, (c). encodes the fact that implementing $p$ is "a best action" for
all players.

We only need to formalize what we mean by program in this definition. The
semantics is inspired by the one in [86], but the full formalization is
somewhat subtle. We defer a full presentation to Section 15 of the Appendix. A
couple of technical points are, however, worth stating:

  * -

The semantics of programs in [86] does not allow for any synchronization
between different versions of the same program, other than testing whether
they are syntactically equivalent. Since (as recognized in Theorem 3) we need
to include correlated randomness, we need to extend the semantics of programs
from [86], where this is not possible. There are many ways to do it, but one
way is to allow _correlated sampling from distributions_ : all the programs
get an identical sample from a given distribution.

  * -

However, simply adding correlated sampling of _action profiles_ to the
semantics of programs from [86] leads (see Theorem 9 in the Appendix) to
paradoxical results: every convex combination of Pareto optimal strategy
profiles would be a Kantian program equilibrium. This is an issue: in
Prisoners’ Dilemma profiles $(C,D),(D,C)$ could perhaps be justified from a
"team reasoning" perspective where one player "sacrifices itself" so that the
other one walks free. To accept them as "Kantian equilibria" seems, however,
problematic (see also the discussion in sections 13.3 and 14)

  * -

If, on the other hand, agent programs didn’t communicate at all, used no
private randomness, or used no specific ID/payoff information then they would
run identically for all agents, coordinating on the same action (excluding,
thus, scenarios like that of Example 3, that we want to model).

  * -

We will take a middle-ground approach, and assume that agents can use their ID
and the information about the game payoffs in a very limited way, that makes
the program act "identically with respect to a group of symmetries acting
transitively on the set of agents". This requires us to restrict ourselves to
the class of Pareto symmetric games of Definition 16, whose set of Pareto
dominant action profiles has such symmetries. The precise technical details
are spelled out in Section 15 of the Appendix, where we prove (Theorem 10) a
characterization of Kantian equilibria for Pareto symmetric games which also
shows that Kantian program equilibria are a strict subset of the class of
team-reasoning equilibria.

Algorithms 4.1 and 4.2 lend some credibility to the intuition that Kantian
equilibria are somehow related to some "symmetric" notion of correlated
equilibria. This intuition is correct: in Definition 19 (in the Appendix) we
define a notion of "correlated symmetric equilibrium". We then prove:

######  Theorem 4.

Correlated symmetric equilibria of symmetric games are Kantian program
equilibria.

Kantian program equilibria allow players to obtain a better expected payoff in
Platonia Dilemma:

######  Theorem 5.

Algorithm 4 implements a Kantian program equilibrium for Platonia Dilemma.

Choose-Winneri,b1,b2,…, bn Randomly choose an integer bi∈Zn
if [∑j=1^n bj≡i (mod n)]
then S(UBMIT)
else D(ON’T)

##  5 Some computationally efficient other-regarding equilibria

As defined in the previous section, Kantian program equilibria for games with
identical action sets inherit some of the definitional problems of "ordinary"
program equilibria. Among them:

  * -

_fragility_ : (Kantian) program equilibria are sensitive (see e.g. [65]) to
the precise specification of programs: do we insist that all agent programs
are syntactically identical, or just "do the same thing"? See [58, 51] for
some attempted solutions for program equilibria that could be adapted to our
setting.

  * -

_lack of generality_ : Definition 5 it is only applicable to (some of the)
games with identical action sets. To further generalize it to all finite
normal-form games one would need to specify what it means for two agents to
"take the same course of action" in settings with differing action sets.

  * -

_lack of predictive power_ : There may be multiple (even infinitely many)
Kantian program equilibria.

Given these objections, and with constraints (I)-(IV) in mind, we propose in
the sequel a substantially more modest approach: Rather than seeking a general
definition of Kantian equilibria we propose instead _several_ other-regarding
equilibria. They all correspond intuitively to real-life situations, are
tractable, can be justified by team reasoning and are related, for symmetric
coordination games, to Kantian equilibria. One was independently suggested in
[56], the other ones are first introduced here:

######  Definition 6.

A _Rawlsian equilibrium_ is a prob. distrib. over Pareto optimal profiles
maximizing the _egalitarian social welfare_ [27] (the expected utility of the
worst-off player) and is strictly dominated by no other profile with this
property. Such equilibria implement the idea of justice as fairness [70].

######  Example 2.

We modify the BoS example as in Fig. 2 (c): perhaps 1 is a classical music
lover, that gets a higher utility than the other player by going, together
with its partner, to any of the two concerts. Then (S,S) is the (unique)
Rawlsian equilibrium. Choosing such an equilibrium is an example of altruistic
behavior from player 1, since it maximizes the payoff of its non-music-lover
partner.

######  Definition 7.

A _Bentham-Harsányi equilibrium_ is a prob. distrib. on Pareto optimal
profiles maximizing the sum of expected payoffs. See [48] for a philosophical
motivation. A _best-off equilibrium_ is a prob. distrib. on Pareto optimal
profiles maximizing the largest expected payoff, and strictly dominated by no
profile with this property. E.g., in Exp. 2 (B,B) is the unique Bentham-
Harsányi/best-off equilibrium.

Although a best-off equilibrium may not seem "fair", there exist real-life
"team reasoning" situations that elicit behavior suggestive of such an
equilibrium: one such example is, for instance, scenarios where members of a
team "sacrifice" for one of their members (e.g. parents for a child).

The equilibrium notions we introduced so far implicitly assumed that player
utility is given by material payoffs. Sometimes the frustration a player feels
is derived by counterfactually comparing its realized payoff with all possible
ones. There are many implementations of this idea. The following notion
quantifies the extent to which a given profile is worse for the given player
than a random profile.

######  Definition 8.

The _percentile index of profile $a$ for player $i$_ is the percentage of
Pareto optimal profiles that would get $i$ a strictly better payoff than $a$.
A _Rawlsian percentile equilibrium_ is a profile minimizing the largest
expected percentile index of all players, and strictly dominated by no profile
with this property.

######  Example 3.

Consider the game shown in Figure 2 (b). Then percentile indices of Pareto
optimal profiles are $(0,100)$ for $(C,C)$, and $(100,0)$ for $(D,D)$,
respectively. Profile $\frac{1}{2}(C,C)+\frac{1}{2}(D,D)$ is a Rawlsian
percentile equilibrium. Player 1 gets average utility 7 while player 2 gets
average utility $\frac{3}{2}$.

An even less cognitively sophisticated model of agent frustration relies on
classifying outcomes as "happy/not happy". The following is a simple example
of such a notion:

######  Definition 9.

The _natural expectation point of player $i$_ is the median (over all
undominated pure strategy profiles) payoff. If there are two medians then the
average value is taken. A player is _happy in a pure strategy profile $a$_ iff
its payoff is larger or equal than its natural expectation point and _unhappy_
otherwise.

An _aspiration equilibrium_ is a mixed strategy profile that minimizes the
largest probability of unhapiness among all players and is strictly dominated
by no other profile with this property.

######  Example 4.

Take a coordination game with payoffs $(C,C)\rightarrow(10,1)$,
$(D,D)\rightarrow(9,2)$, $(E,E)\rightarrow(8,3)$, $(F,F)\rightarrow(4,7)$. The
natural expectation points of players are $8.5$ and $2.5$, respectively. The
first player is happy in $(C,C)$ and $(D,D)$, the second in $(E,E)$, $(F,F)$.
Hence in $\frac{1}{4}(C,C)+\frac{1}{4}(D,D)+\frac{1}{4}(E,E)+\frac{1}{4}(F,F)$
the players are happy $50\%$ of the time and no mixed action profile can do
any better.

Unlike general Kantian program equilibria, the equilibria we defined are
computationally tractable:

######  Theorem 6.

Rawlsian, Rawlsian percentile, Bentham-Harsányi, best-off, aspiration
equilibria existand can be found by solving a sequence of linear programs
(hence in polynomial time).

We now connect our other regarding equilibria to Kantian equilibria in
symmetric coordination games. We call an equilibrium point _extremal_ if it
cannot be written as a nontrivial convex combination of other (similar)
equilibria. We show that extremal self-regarding equilibria generalize Kantian
pure equilibria. Extremality is needed, since our equilibria are closed under
convex combinations (such combinations are justifiable from a magical thinking
perspective, see footnote 7), while pure Kantian equilibria are not. Because
of Thm. 2 no similar connection is likely for mixed Kantian equilibria:

######  Theorem 7.

In symmetric diagonal games Rawlsian, Bentham-Harsányi, best-off, Rawlsian
percentile, aspiration equilibria coincide with convex combinations of Kantian
pure equilibria.

##  6 Agents with bounded greed

So far we have assumed that people are other-regarding. In reality people are
not unrestricted optimizers, nor are they perfect Kantian moralists. Alger and
Weibull [2] attempted to interpolate between utilitarian agents and Kantian
ones, by defining _homo moralis_ to be an agent whose utility has the form
$u_{\\_}{i}(x,y)=(1-k)\pi(x,y)+k\pi(x,x)$, where $k\in[0,1]$ is the so-called
degree of morality of the agent. They showed that evolutionary models with
assortative mixing and incomplete information favor a particular kind of homo
moralis, those whose degree of morality coincides with the degree of
assortativity of the matching process. Interesting as this result is, it has
some weaknesses. For instance [2], homo moralis behaves like homo economicus
in Prisoners’ Dilemma and all constant-sum games when $k\neq 1$. In other
words, agent behavior is not sensitive to the degree of morality, as long as
the agent is not Kantian.

We give (for symmetric games, but the idea can be extended to general ones,
via Kantian program equilibria) a definition with the same overall intention,
but capturing a slightly different agent behavior:

######  Definition 10.

Let $\lambda\in[1,\infty]$. Agent $i$ is called _$\lambda$ -utilitarian_ if,
for every action profile $(a_{\\_}i,b)$, its utility
$u_{\\_}{i}(a_{\\_}{i},b)$ is (a).
$\pi_{\\_}{i}(a_{\\_}{i},(\overline{a_{\\_}{i}})_{\\_}{-i})$ if $a_{\\_}i$ is
a Kantian action. (b). 0 if $a_{\\_}{i}$ is not Kantian and
$\pi_{\\_}{i}(a_{\\_}{i},b)\leq\lambda\cdot\pi_{\\_}{i}(X^{OPT})$; (c).
$\pi_{\\_}{i}(a,b)$ if $a_{\\_}{i}$ is not Kantian and
$\pi_{\\_}{i}(a_{\\_}{i},b)\leq\lambda\cdot\pi_{\\_}{i}(X^{OPT})$. I.e., a
$\lambda$-utilitarian agent deviates from its Kantian action $X^{OPT}$ only if
the utility it obtains is more than $\lambda$ times larger.

We call the number $\frac{1}{\lambda-1}$ _the greed index_ of $i$. It varies
between 0 (Kantian agents) and $\infty$ (purely utilitarian ones). The natural
equilibrium concept for such agents is no longer Kantian, but Nash
equilibrium. Definition 10 allows giving an empirically plausible
justification of all possible outcomes in PD:

######  Theorem 8.

All pure action profiles in PD are Nash equilibria of agents with varying
degrees of greed.

##  7 Conclusions

Our main contribution is bringing Kantian equilibria (and related concepts) to
the attention of agent community, showing that this notion is theoretically
interesting, but that the road to implementable behaviors goes through less
general equilibrium concepts. Many of the notions we introduced, including
Kantian program equilibria and bounded greed agents, deserve further
investigation. For instance a justification like that of Theorem 8 could be
used as a rationality criterion. One could look for evolutionary
justifications of bounded greed agents along the lines of [2]. One could use
such agents in relation to work on the concept of _price of anarchy_ [76]. On
a more conceptual level, the use of _frames_ in game theory [8, 12] and how
this interacts with equilibrium notions deserves further study. Finally,
several open problems remain: Can we find algorithms for our equilibria that
bypass the need for solving multiple LP’s? Is the problem from Theorem 2 NP-
complete (i.e. in NP)?

## Appendix

##  8 Related Work

The literature on other-regarding game-theoretic models is quite large, and a
short section like this one cannot do justice to all the related, relevant
work. Instead we have chosen to highlight a modicum of references directly
relevant to our work.

The major impetus for this work was _Kantian optimization_. It was developed
in [71, 72], developing early ideas of Laffont [57]. The current status of the
theory is consolidated in the recent book [73]. A recent special issue of the
_Erasmus Journal of Economics_ is devoted to discussing and situating Roemer’s
contribution. Particularly valuable articles in this collection include [22,
79].

The other strand of ideas relevant to our work concerns the concept of
_program equilibria_ , defined in [86] and further investigated in [35, 55,
51, 58, 9, 30, 65]. There are several other related (and relevant) models,
such as the _translucent player_ model of [23, 45], or _mediated equilibria_
[61].

The two other paradigms leading to the same concept for two-player symmetric
coordination games, _superrationality_ and (especially) _team reasoning_ are,
of course, relevant to our approach. Superrationality is rather different,
though, and we only reiterate recommendations of [52, 36]. The main reference
for team reasoning is still [8]. We also recommend papers [84, 28, 43].

Notions of symmetry in games have been insufficiently investigated, and they
play an important role in defining Kantian programs. We refer to [47, 87] for
such studies.

Finally, an impressive amount of work on behaviorally relevant game-theoretic
notions related to moral behavior is summarized in [31]. While it is by no
means comprehensive (especially with respect to the computer science
literature), it is an excellent starting point.

##  9 Proof of Lemma 1

###### Proof.

Let $f(p)=p(1-p)^{n-1}$.
$f^{\prime}(p)=(1-p)^{n-1}-(n-1)p(1-p)^{n-2}=(1-p)^{n-2}(1-np)$, so $f$ is
increasing on $[0,1/n]$ and decreasing on $[1/n,1]$. ∎

##  10 Proof of Theorem 1

###### Proof.

$E[p]=\sum_{\\_}{i,j}a_{\\_}{i,j}p_{\\_}{i}p_{\\_}{j}\leq
max_{\\_}{k}(a_{\\_}{k,k})\cdot\sum_{\\_}{i,j}p_{\\_}{i}p_{\\_}{j}=max_{\\_}{i}(a_{\\_}{i,i})(\sum_{\\_}{k}p_{\\_}{k})^{2}=max_{\\_}{i}(a_{\\_}{i,i}).$
∎

In other words, for every distribution over actions there exists a pure action
that gives players at least the same payoff. To obtain equality we must have
$a_{\\_}{i,j}p_{\\_}{i}p_{\\_}{j}\leq max_{\\_}{k}(a_{\\_}{k,k})\cdot
p_{\\_}{i}p_{\\_}{j}$ for all $i,j$. We cannot have two distinct indices
$i\neq j$ with $p_{\\_}i,p_{\\_}j>0$, since $a_{\\_}{i,j}=0$,
$max_{\\_}{k}(a_{\\_}{k,k})>0$. So each equilibrium is a pure Kantian
equilibrium.

##  11 Proof of Theorem 2

###### Proof.

We point out to the existence of a reduction from CLIQUE to MIXED KANTIAN
EQUILIBRIUM, that shows that the latter problem is NP-hard. In fact the
reduction will only consider symmetric games with 0/1 payoffs.

Consider, indeed, a graph $g$. Let $k$ be an integer and $(g,k)$ be the
corresponding instance of CLIQUE.

Define the symmetric two-player game $G$ whose payoff matrix is the adjacency
matrix $A$ of $g$.

Mixed Kantian equilibria $x=(x_{\\_}1,\ldots,x_{\\_}N)$ of $G$ correspond to
optimal solutions of the following quadratic program:

$\left\\{\begin{array}[]{c}max(x^{T}Ax)\\\ x_{\\_}1+\ldots+x_{\\_}N=1\\\
x_{\\_}{1},\ldots,x_{\\_}N\geq 0.\end{array}\right.$ (1)

This is a problem that has been called [19] the standard quadratic
optimization problem, and has been investigated substantially in the global
optimization literature (see e.g. [18]). A beautiful result due to Motzkin and
Straus [62] can be restated as claiming that for programs whose matrix $A$ is
the adjacency matrix of a graph $g$, if $o$ is the optimum of problem (1) then
$\frac{1}{1-o}$ is the size of the maximum clique in $g$.

Hence $(g,k)\in CLIQUE$ if and only if $(G,\frac{k-1}{k})\in$ MIXED-KANTIAN-
EQUILIBRIUM.

∎

##  12 Proof of Theorem 3

###### Proof.

The price of miscoordination is insensitive to dividing all utilities by the
same factor $\lambda$, so w.l.o.g. one may assume that the utilities agent
receive on pure Kantian equilibrium profiles is 1. For the mixed action a
where players play the $r$ Kantian actions (w.l.o.g. $1,2,\ldots,r$) with
probabilities $p_{\\_}{1},p_{\\_}{2},\ldots p_{\\_}{r}$ (which add up to 1),
its expected utility is $E[u_{\\_}{i}(\textbf{a})]=\sum
u_{\\_}i(i_{\\_}{1},i_{\\_}{2},\ldots i_{\\_}{k})\cdot
p_{\\_}{i_{\\_}1}p_{\\_}{i_{\\_}2}\ldots
p_{\\_}{i_{\\_}k}\geq\sum\limits_{\\_}{i=1}^{r}p_{\\_}{i}^{k}\geq
r\cdot\frac{1}{r}^{k}=\frac{1}{r^{k-1}},$ by Jensen’s inequality. The upper
bound is obtained when off-diagonal action profiles formed of Kantian actions
only have utilities equal to 0. As for the lower bound, for diagonal games by
domination we have $u_{\\_}{i}(i_{\\_}{1},i_{\\_}{2},\ldots i_{\\_}{k})\leq
1$, so $E[u_{\\_}{i}(\textbf{a})]=\sum u_{\\_}{i}(i_{\\_}{1},i_{\\_}{2},\ldots
i_{\\_}{k})\cdot p_{\\_}{i_{\\_}1}p_{\\_}{i_{\\_}2}\ldots
p_{\\_}{i_{\\_}k}\leq\sum p_{\\_}{i_{\\_}1}p_{\\_}{i_{\\_}2}\ldots
p_{\\_}{i_{\\_}k}=(p_{\\_}{1}+p_{\\_}{2}+\ldots p_{\\_}{r})^{k}=1.$ A game
realizing the lower bound is the one where agent utilities on all pure action
profiles are equal to 1. ∎

##  13 Potential alternatives to Kantian program equilibria

###  13.1 Hofstadter equilibria in general games

Since we are looking to extend the definition of Kantian optimization from
symmetric coordination to general games, we first note that such extensions
exist under the other paradigm employed to define Kantian equilibria,
superrationality: Kant-Hofstadter equilibria have recently been extended to
non-symmetric games in [36]. The so-called _perfectly transparent equilibrium_
(PTE) relies on the iterated elimination of strategies that are not
individually rational. For games with without ties, that is those where an
agent is never indifferent between two action profiles, Fourny proves that at
most one action payoff can be a PTE. These facts suggest that one should at
least consider PTE as candidates for the extension of Kantian equilibria.
Unfortunately, they seem rather unsuitable. The following are some objections
against PTE:

  1. 1.

A first objection is epistemic complexity: PTE require knowledge of
rationality in _all possible worlds_ , which is stronger than common
knowledge. Also, Beard and Bail [10] have experimentally shown that people do
not always adequately perform even two levels of iterated elimination of
dominated strategies (for a review of the experimental literature see Chapter
12 of [31]). The elimination process leading to a unique PTE is at least
equally (if not more) cognitively expensive, since each round is based on a
more complicated type of rationality assumption (individual rationality versus
domination), also employing multiple rounds. Thus PTE are implausible from a
bounded rationality perspective.

  2. 2.

A second problem of PTE is that they do not alleviate the problem of multiple
equilibria and miscoordination: Fourny [36] acknowledges this problem, and
only defines PTE for games without ties, for which this issue does not exist.

  3. 3.

A final, and most daunting, objection against PTE is that _they produce
problematic predictions_ : in the game in Fig. 2 d. (see [20]), for instance,
the unique PTE is $(C,C)$. However, $(C,C)$ is dominated by both $(C,S)$ and
$(S,C)$ (and convex combinations thereof) hence it is difficult to justify $C$
as "the action that is best for all".

###  13.2 Berge Equilibria

Berge (or Berge-Zhukovsky) equilibria are another class of cooperative
equilibria. Originally defined in Berge’s monograph [11], they were studied in
the Soviet Union [91, 92], while remaining relatively obscure, until recently,
in the English-language literature. Formally, an action profile
$x^{*}=(x^{*}_{\\_}{1},x^{*}_{\\_}{2},\ldots x^{*}_{\\_}{n})$ is a _Berge
equilibrium_ if for every player $i$ and every partial profile $x^{-i}$,
$u_{\\_}{i}(x^{*}_{\\_}{i},x^{-i})\leq u_{\\_}{i}(x^{*})$. In other words, the
partial profile chosen by all but one of the agents is optimal for the
remaining agent, given its chosen action.

Kantian equilibria of symmetric coordination games coincide with Berge
equilibria. One could naturally hope that this extends to general games. But
this is not the case: Even though Berge equilibria are an intriguing concept,
worthy of further investigations, sadly they are inappropriate as extensions
of Kantian equilibria. First, there are three-player games [68] admitting no
mixed-strategy Berge equilibria, and deciding the existence of mixed-strategy
Berge equilibria is NP-complete [63]. For two-player games Berge equilibria
correspond [29] to the Nash equilibria of a modified games. In particular the
seminal existence theorem for mixed Nash equilibria guarantees the existence
of Berge equilibria in this case. Second, Berge equilibria capture indeed one
aspect of the Kantian categorical imperative, that of players choosing a
course of action that is "best for everyone". But _they fail to explicitly
capture the other one, that of all players doing, in some sense, "the same
thing"._ They are also vulnerable to miscoordination: an example is the game
Bach or Stravinsky ([66], see Figure 1 b.). Here the two agents may agree that
they should choose the same action, but don’t necessarily agree on which one.
Nor is the "obvious" mixed strategy $\frac{1}{2}C+\frac{1}{2}S$ a suitable
alternative. While it is the unique Berge equilibrium, it is not a Kantian
equilibrium: the expected player payoff, $\frac{3}{4}$, is inferior to what
they would get under either of $(C,C)$ or $(S,S)$!

###  13.3 Team reasoning

In a certain sense there already exists a solution to the problem of extending
Kantian equilibria from symmetric coordination games to general finite normal-
form games. It is based on the _team reasoning_ approach of [7].

In a nutshell, the idea is that under certain conditions agents switch from an
individual-oriented to a team-oriented mode (called in [8] mode-P reasoning)
based on the existence of a _team utility function_

######  Definition 11.

Let $M=\\{1,2,\ldots,m\\}$ be a set of agents, such that agent $i$ can choose
an act $a_{\\_}i$ from a finite set $A_{\\_}i$. Let $a=(a_{\\_}i)_{\\_}{i\in
M}$. A _team utility function_ is a function $U:\prod\limits_{\\_}{i\in
M}A_{\\_}{i}\rightarrow\mathbb{R}$.

It is required [7] that the team utility function is monotone, that is, if
profile $P$ strictly dominates profile $Q$ then $U(P)>U(Q)$.

######  Definition 12.

A _team reasoning equilibrium_ is a (mixed) profile a maximizing the team
utility function $U$.

That is, to team reason, an agent $i$ first computes a profile
$\textbf{a}\in\prod\limits_{\\_}{i\in M}A_{\\_}{i}$ maximizing $U(a)$ (we
assume that such an a is unique), then it plays $a_{\\_}i$. By the
monotonicity of the team utility function, a team reasoning equilibrium is
Pareto optimal.

The problems with using team reasoning to model Kantian equilibria are the
following:

  * -

as described team reasoning is too general: for any Pareto optimal profile $P$
one can create a team utility function that justifies playing $P$. Whereas
sometimes this may be appropriate, we repeat the observation from the main
paper: intuitively it does not make sense in Prisoners’ Dilemma to call
profiles such as $(C,D),(D,C)$ "Kantian equilibria". But one could create team
utility functions witnessing that they are team reasoning equilibria.

  * -

Similarly, in the game from Example 3 intuitively we don’t want to accept any
solution other than $\frac{1}{2}(C,S)+\frac{1}{2}(S,C)$ as a Kantian
equilibrium.

  * -

One could try to fix this latter problem by the choice of team utility
functions: namely we could assume team utility functions $U$ that are not
linear on the simplex of mixed strategies, in particular postulate that in the
game from Example 3 we have

$U(\frac{1}{2}(C,S)+\frac{1}{2}(S,C))>U(\lambda(C,S)+(1-\lambda)(S,C))$

for all $\lambda\in[0,1]\setminus\\{\frac{1}{2}\\}$. But this "solution" is
fairly ad-hoc, leaving too much information to the specification of $U$. Plus
it does not intuitively correspond to the Kantian categorical imperative,
since it formalizes what players _want_ , not the fact that players "do the
same thing".

It is true that team reasoning is related to Kantian equilibria: we revisit
this connection in the Section 14, where we show that team reasoning is
essentially equivalent to the model of Kantian program equilibria using the
definition of programs from [86]. In our view, though, Kantian optimization is
a more restrictive concept than team reasoning: in the game from Example 3 one
could justify playing $(C,S)$ or $(S,C)$ via arguments based on team
reasoning. It seems to us that one should be able to give a "Kantian
justification" for $\frac{1}{2}(C,S)+\frac{1}{2}(S,C)$ based on the game
matrix only, without recourse to any team utility function.

###  13.4 Correlated equilibria

The problem with the previous mixed strategy profile arose from
miscoordination. A conclusion is that one may need to give up the assumption
that players are choosing their actions independently, and assume, instead,
some form of _correlated strategy profiles_ , and perhaps, some version of
_correlated equilibria_ [6]. Such a choice could seem natural at first: Gintis
[39, 40] convincingly argues that correlated equilibria are more natural than
Nash equilibria, and can model a wide variety of social phenomena, including
social norms. Also [38], unlike Nash equilibria, computing correlated
equilibria is tractable. Many of the examples of other-regarding game-playing
we give in this paper can, indeed, be modeled with correlated equilibria.

######  Definition 13.

Given a strategic game $(N,(A_{\\_}i),(u_{\\_}i))$, a finite probability space
$(\Omega,\pi)$ and an information partition $P_{\\_}i$ of $\Omega$, e
_strategy for player $i$_ is a mapping $\sigma_{\\_}{i}:\Omega\rightarrow
A_{\\_}i$ that is constant on each class of the information partition
$P_{\\_}i$.

######  Definition 14.

A correlated equilibrium of a strategic game $(N,(A_{\\_}i),(u_{\\_}i))$
consists of

-

a finite probability space $(\Omega,\pi)$.

-

for each player $i\in N$ an information partition $P_{\\_}i$ of $\Omega$ and a
strategy function $\sigma_{\\_}i$ for player $i$ such that for any $i\in N$
and any strategy $\tau_{\\_}i$ of player $i$,

$\sum_{\\_}{\omega\in\Omega}\pi(\omega)u_{\\_}{i}(\sigma_{\\_}{-i}(\omega),\sigma_{\\_}{i}(\omega))\geq\sum_{\\_}{\omega\in\Omega}\pi(\omega)u_{\\_}{i}(\sigma_{\\_}{-i}(\omega),\tau_{\\_}{i}(\omega))$

Note that the probability space and the information partition are part of the
specification of the equilibrium.

This definition of correlated equilibria does not directly address the issue
of "the two agents doing the same thing". Also, since all Nash equilibria are
correlated equilibria, _some symmetric games have correlated equilibria that
can hardly be intuitively classified as "Kantian"_. This is the case of the
game _chicken_ [66], whose two Nash equilibria corresponding to one player
yielding to the other one are also correlated equilibria [67]. This example
also shows that simply eliminating strictly dominated equilibria does not
help, since it would not eliminate these "bad" equilibria.

##  14 Why adding correlated sampling to the model of programs from [86] may
yield unintuitive results for Kantian program equilibria

In this section we study the consequences of extending the notion of program
from [86] for the definition of Kantian equilibria. We do not give full
details of the semantics of original program equilibria (we refer to the
Appendix of [86] for more), but we give a couple of details below. First of
all, we adapt the EBNF grammar from [86]: The EBNF extends the one in [86] by
introducing a new instruction, called SYNC, two new sorts _joint-action_ and
_group-variable_ , and of corresponding rules connecting them. All changes in
the grammar compared to the one from [86] are bolded.

Informally, in the model of [86] (which we follow), variables can hold
arbitrary distributions of actions. Group variables can hold arbitrary
distributions of _action profiles_. A SYNC(<group-variable>) will sample,
_synchronously among all copies of the program_ , an action profile from the
distribution in the group-variable, returning the vector of actions composing
the action profile. By contrast, DO(<variable>) and DO(<action>) sample player
actions, independently across copies of the same program. We can project an
action profile to an action of a given player by means of PROJ. Other details
are just as in [86]: we use MYINDEX to let each agent know its index, and
MYPROGRAM to hold the source of its own program. The definition of conditions
has to be, of course, updated, to reflect the existence of joint actions.
Finally, just as in [86], variables are matrices with integer indices.

$\displaystyle<\mbox{program}>::=\mbox{
}\Lambda|<\mbox{program}>;|<\mbox{program}><\mbox{program}>|\\{<\mbox{program}><\mbox{program}>\\}|$
$\displaystyle\mbox{ }<variable>:=<action>|\mbox{ }<\mbox{group-
variable}>:=<\mbox{action-profile}>|$ $\displaystyle\textbf{<variable> :=
PROJ(<\mbox{group-variable}>)}|\mbox{ }DO(<action>)|\mbox{ }DO(<variable>)|$
$\displaystyle\mbox{ }\textbf{SYNC(<action-profile>)}|\mbox{
}\textbf{SYNC(<group-variable>)}|$ $\displaystyle\mbox{
}IF<condition>THEN<program>ELSE<program>|\mbox{ }STOP\mbox{ }$
$\displaystyle<condition>::=\mbox{ }(<\mbox{prog-
index}>|<\mbox{variable}>|<\mbox{action}>|\textbf{<\mbox{action-
profile}>}|<\mbox{player-index}>)$ $\displaystyle(==|!=)$ $\displaystyle\mbox{
}(<\mbox{prog-index}>|<\mbox{variable}>|<\mbox{action}>|\textbf{<\mbox{action-
profile}>}|<\mbox{player-index}>)$ $\displaystyle<action>::=\mbox{ an
arbitrary probability distribution of actions of the game. }$
$\displaystyle\textbf{<\mbox{action-profile}>}::=\textbf{\mbox{ an arbitrary
probability distribution of \text@underline{action profiles} of the game. }}$
$\displaystyle<\mbox{prog-
index}>::=P_{\\_}1|P_{\\_}{2}|\cdots|P_{\\_}{n}|MYPROGRAM$
$\displaystyle<\mbox{player-index}>::=1|2|\cdots|n|MYINDEX$
$\displaystyle<variable>::=X(integer,integer)$ $\displaystyle\textbf{<group-
variable>}::=\textbf{Y(integer,integer)}$

######  Theorem 9.

Consider a finite normal-form $G$. Then for any convex combination $W$ of
Pareto optimal strategy profiles there exists a program $P$ such that

  * -

when all agents play $P$ the resulting profile is $W$.

  * -

for no other program $Q$ it is true that the resulting profile $W_{\\_}Q$
strictly dominates $W$.

######  Corollary 1.

Kantian program equilibria with the definition of programs from [86] coincide
with team reasoning equilibria.

###### Proof.

We use essentially the same idea as in the proof of Theorem 2 in [86]. In
fact, the observation was made there that in the program equilibrium
constructed the theorem all agents use the same program (this is not a
requirement of "ordinary" program equilibria). For clarity we have omitted one
aspect from [86], that of programs inspecting other agents’ programs to
enforce cooperative behavior. This aspect is less important for us but can, of
course, be added back to Algorithm 14.1 below in similar way to those of the
program in [86].

Let indeed $W=w_{\\_}1P_{\\_}1+w_{\\_}2P_{\\_}2+\ldots+w_{\\_}mP_{\\_}{m}$,
where $P_{\\_}1,P_{\\_}2,\ldots,P_{\\_}m$ are the Pareto-optimal strategy
profiles and $w_{\\_}1,w_{\\_}2,\ldots,w_{\\_}m\geq 0$,
$\sum\limits_{\\_}{i=1}^{m}w_{\\_}i=1$. We consider the program PLAY-PARETO
specified informally as follows121212As in [86], we will neglect issues
related to representing real numbers in programs. That is, we will be working
in a model of _real computation_. Such computation models are found in other
areas of theoretical computer science: The most well-known is the BSS-model
[16].: Agents synchronously sample an index $j\in 1,2,\ldots,m$, value $j$
appearing with with probability $w_{\\_}{j}$. Then each agent $i$ performs
$DO(P_{\\_}{j,i})$. Since the random sampling is synchronized, when agent $i$
plays $P_{\\_}{i,j}$ all other agents $k$ play $P_{\\_}{k,j}$. Thus PLAY-
PARETO implements $W$. Formally:

Play-Pareto⋅ Let  Q= SYNCH(P1P2…Pmw1w2…wm )
DO(Q[MYINDEX])

The second claim is evident from Pareto optimality. ∎

##  15 A semantics of programs appropriate for Definition 5

Apparently, one reason the program equilibrium in the proof of Theorem 9 was
able to play an arbitrary Pareto optimal profile was that the agent was able
to use its ID MYINDEX as argument to an action profile in order to to select
the action to play (instruction DO(Q[MYINDEX])). Clearly, simply avoiding
vectors and ID’s as indices won’t do: instead of a vector $Q$ of size $r$ we
could simply use $r$ different variables $Q1,Q2,\ldots,Qr$, and achieve the
same goal through a convoluted sequence of IF-ELSE instructions:

    IF  (MYINDEX == 1)  DO(Q1) END;
    IF  (MYINDEX == 2)  DO(Q2) END;
    ....
    IF  (MYINDEX == r)  DO(Qr) END;

Another alternative that does not work is to modify the semantics of the SYNC
instruction such that, instead of returning the vector of agent actions as a
result of a SYNC instruction we only give agent $i$ access to its (the $i$’th)
component of the result: it could simply DO it. We are forced to conclude that
sampling action profiles may be too strong, hence we will drop the SYNC
instruction and replace it with something less powerful.

One idea might be to replace sampling from the space of probability
distributions on action profiles by sampling from an abstract "signal space"
$\Omega$. Just as in correlated equilibria, signals may encode e.g. random
choices of each individual program.

######  Example 5.

Consider the Algorithm 4.3 for Platonia Dilemma. Define $\Omega$ to be
$\mathbb{Z}_{\\_}{n}^{n}$. An element $b\in\Omega$ will specify a choice of
elements $b=(b_{\\_}1,b_{\\_}2,\ldots b_{\\_}n)$, occurring with probability
$\pi(b)=\frac{1}{n^{n}}$.

Simply replacing sampling of action profiles by sampling states in a signal
space is, however, not enough. The way agents use signals and their index to
compute the action to take must be highly constrained: (at least for symmetric
games) the joint behavior of agents must be "symmetric", and not favor any
particular action profile. If this didn’t happen then agent could "break
symmetry" on their own, the most extreme form of which is to coordinate on a
particular action profile.

We will formalize this transitivity using _group actions:_

######  Definition 15.

Given a group $\Gamma$ and set $\Omega$, an _action of $G$ on $\Omega$_ is a
mapping $\alpha:\Gamma\times\Omega\rightarrow\Omega$, often denoted by $g\cdot
x$ instead of $\alpha(g,x)$ such that:

  * -

$e\cdot x=x$ for all $x\in\Omega$.

  * -

$g_{\\_}1\cdot(g_{\\_}{2}\cdot x)=(g_{\\_}1\cdot g_{\\_}2)\cdot x$ for all
$g_{\\_}1,g_{\\_}2\in\Gamma$ and $x\in\Omega$.

######  Example 6.

In Platonia Dilemma $\mathbb{Z}_{\\_}{n}\times\mathbb{Z}_{\\_}{n}^{n}$ acts on
the set of signals $\Omega$ in the following way:
$(i;a_{\\_}1,a_{\\_}2,\ldots,a_{\\_}n)\cdot(b_{\\_}{1},b_{\\_}{2},\ldots,b_{\\_}{n})=(a_{\\_}{i+1}+b_{\\_}{i+1},\ldots
a_{\\_}{n}+b_{\\_}{n},a_{\\_}{1}+b_{\\_}{1},\ldots a_{\\_}{i}+b_{\\_}{i})$.

The following is the class of games to which our concept of Kantian program
equilibria will apply.

######  Definition 16.

A game $\Gamma$ is called _Pareto symmetric_ if there exists a group $H$
acting on the set of Pareto-optimal action profiles such that

  * -

For every Pareto optimal profile $a=(a_{\\_}1,a_{\\_}2,\ldots,a_{\\_}n)$ and
$u\in H$ there exists a permutation $\sigma\in S_{\\_}n$ such that $u\cdot
a=(a_{\\_}{\sigma(1)},\ldots,a_{\\_}{\sigma(n)})$.

  * -

For every two players $i\neq j$ and value $\lambda$

$|\\{u\in H:(u\cdot a)_{\\_}i=\lambda\\}|=|\\{u\in H:(u\cdot
a)_{\\_}j=\lambda\\}|$

Pareto symmetry embodies an intuitive notion of "fairness": if a Pareto
optimal profile favors a certain player $i$, then there are other Pareto
optimal profiles with identical payoffs (modulo a permutation of players)
compensating for that. Consequently, each player is indifferent between a fair
mixture of Pareto optimal positions in the same orbit of the action, although
in a specific certain profile it may distinguish between the positions of
other players. We also stress that in the previous definition $H$ acts on
_action profiles_ , not necessarily on individual actions.

######  Example 7.

Call ([83], see also [47]) a game _standard symmetric_ if there exists a
transitive subgroup $H$ of player permutations such that for $i\in N$, $\pi\in
H$ and action profile $a$, $u_{\\_}i(a)=u_{\\_}{\pi(i)}(\pi(a))$. Here
$\pi(a)$ is the action profile obtained from $a$ by permuting agent actions
according to $\pi$.

Every symmetric game is standard symmetric [47].

All standard symmetric games are Pareto symmetric: for every Pareto optimal
profile $a$, profile $\pi(a)$ is Pareto optimal. Group $H$ acts on Pareto
optimal action profiles in the obvious way: $\pi\cdot a=\pi(a)$.

######  Example 8.

Roemer’s version of BoS is a non-symmetric game that is Pareto symmetric:
$H=\mathbb{Z}_{\\_}{2}$, acting on $(B,B),(S,S)$ in the obvious manner:
$1\cdot(B,B)=(S,S)$, $1\cdot(S,S)=(B,B)$.

######  Example 9.

Platonia Dilemma is standard (hence Pareto) symmetric: the Pareto dominant
action profiles are the strings of length $n$ consisting of exactly one $S$
and $n-1$ $D$. The group $\mathbb{Z}_{\\_}{n}$ acts on the set of Pareto
optimal states in the obvious way: $i$ shifts the $S$ state exactly $i$
positions to the right. Composing this action with the morphism
$\mathbb{Z}_{\\_}{n}\times\mathbb{Z}_{\\_}{n}^{n}\rightarrow\mathbb{Z}_{\\_}{n}$,
$(i;a_{\\_}1,a_{\\_}2,\ldots,a_{\\_}n)\rightarrow
i+\sum\limits_{\\_}{k=1}^{n}a_{\\_}{k}\mbox{ (mod n)}$ we get that
$H=\mathbb{Z}_{\\_}{n}\times\mathbb{Z}_{\\_}{n}^{n}$ also acts on the Pareto
dominant action profiles.

Now a tentative definition of program suitable for Definition 5 might be:

######  Definition 17.

Let $\Gamma$ be a Pareto symmetric game with group $H$ acting on Pareto
optimal profiles. A program over game $\Gamma$ is specified by

  * -

a finite probability space $\Omega$ called _the signal space_. We assume that
$H$ also acts on $\Omega$ and that the measures of elements of $\Omega$ are
identical across orbits of $H$. We will denote this action of $H$ on $\Omega$
by $\circ$.

  * -

a mapping $P:\Omega\times[m]\rightarrow A$ such that

    * (1).

for every $\omega\in\Omega$, vector $P(\omega):=(P(\omega,i))_{\\_}{i=1,m}$ is
a Pareto-optimal profile in $G$.

    * (2).

for every $h\in H,\omega\in\Omega$, $P(h\circ\omega)=h\cdot P(\omega)$.

    * (3).

for every $i\neq j\in[m]$ there exists $h\in H$ such that for all
$\omega\in\Omega$ $P(\omega,j)=P(h\circ\omega,i)$. that is, $i$ and $j$ obtain
the same payoff (presumably playing the same program) modulo an action on the
space of signals.

######  Example 10.

Consider the Algorithm 4.2. Define $\Omega$ to be $\mathbb{Z}_{\\_}{2}^{2}$.
An element $b\in\Omega$ will specify a choice of bits $b=(b_{\\_}1,b_{\\_}2)$,
occurring with probability $\pi(b)=\frac{1}{4}$.
$\mathbb{Z}_{\\_}{2}\times\mathbb{Z}_{\\_}{2}^{2}$ acts on $\Omega$ in the
natural way,
$(i,a_{\\_}1,a_{\\_}2)\cdot(b_{\\_}1,b_{\\_}2)=(i+a_{\\_}1+a_{\\_}2+b_{\\_}1,i+a_{\\_}1+a_{\\_}2+b_{\\_}1)$.

Define function $P:\Omega\times\\{1,2\\}\rightarrow\\{S,D\\}$ by:
$P(0,0,1)=P(1,1,1)=D,P(0,1,1)=P(1,0,1)=S$,
$P(0,0,2)=P(1,1,2)=S,P(0,1,2)=P(1,0,2)=D$.

Then $P(i,j,1)=P(i+1,j,2)$ for all $(i,j)\in\mathbb{Z}_{\\_}{2}^{2}$.

We next prove two important properties of Kantian programs:

######  Lemma 2.

Let $\Gamma$ be a Pareto symmetric game. Consider a Kantian program
$\mathcal{P}$, and let $O$ be an orbit of the action of $H$ on the set of
Pareto optimal equilibria. Let $P_{\\_}1,P_{\\_}2$ be two such elements. Then
$P_{\\_}1,P_{\\_}2$ are generated with equal probability by the Kantian
program $\mathcal{P}$.

###### Proof.

Consider two action profiles $P_{\\_}1$ and $P_{\\_}2$. Let $\Omega_{\\_}1$ be
the set of elements in $\omega\in\Omega$ such that $P(\omega)=P_{\\_}1$, and
similarly for $P_{\\_}2$. We claim that sets $\Omega_{\\_}1$ and
$\Omega_{\\_}2$ have equal measure. This will follow from the claim that there
exists an element $h\in H$ such that
$\Omega_{\\_}2=\\{h\circ\omega:\omega\in\Omega_{\\_}1\\}$ and the fact that
the action preserves measure of elements of $\Omega$ across orbits of the
action.

To prove this claim it is enough to take $h\in H$ such that $h\cdot
P_{\\_}1=P_{\\_}2$. $h$ exists since $P_{\\_}1,P_{\\_}2$ are in the same orbit
of the action of $H$. Now everything follows from the property (2). ∎

######  Lemma 3.

Consider a Kantian program $\mathcal{P}$, and let $O$ be an orbit of the
action of $H$ on the set of Pareto optimal equilibria and two players $i\neq
j$. Then the average payoffs of $i,j$ across action profiles of the orbit $O$,
as generated by $\mathcal{P}$ are equal.

We will refer to the common value in Lemma 3 as _the worth of orbit $O$_.

######  Example 11.

In Prisoner’s Dilemma the worth of the profile $(C,C)$ is 2. The worth of the
orbit $(C,D),(D,C)$ is $3/2$.

###### Proof.

The lemma follows from the fact that $P(\omega,i)=P(h\cdot\omega,j)$. ∎

######  Definition 18.

Given orbit $O$ of the action of $H$ on the set of Pareto optimal profiles of
game $\Gamma$, denote by $U_{\\_}{O}$ the uniform distribution on the profiles
in $O$. That is, for every $P\in O$, $U_{\\_}{O}(P)=\frac{1}{|O|}$.

Given this, we can characterize Kantian program equilibria:

######  Theorem 10.

Kantian program equilibria, as formalized in Definition 5+Definition 17 are
characterized as convex combinations of distributions $U_{\\_}{O}$, where only
orbits $O$ of maximum worth appear with nonzero probability.

Hence Kantian program equilibria are a proper subset of team-reasoning
equilibria.

######  Example 12.

Consider the modified version of Prisoner’s Dilemma from Figure 3. Now agents
are indifferent131313at least as far as expected utility goes between playing
$(C,C)$ and playing $\frac{1}{2}(C,D)+\frac{1}{2}(D,C)$. Hence the Kantian
program equilibria of this game are
$\lambda\cdot(C,C)+\frac{1-\lambda}{2}(C,D)+\frac{1-\lambda}{2}(D,C)$, with
$\lambda\in[0,1]$.

22[Player 1][Player 2] & C D

C $2,2$ $0,4$

D $4,0$ $1,1$

Figure 3: Modified Prisoners’ Dilemma

###### Proof.

First, it is easy to see that all convex combinations of $U_{\\_}O$ can be
implemented by Kantian programs: informally, agents sample from a distribution
that will help decide which of the orbits to choose. Then they sample a random
action profile from the chosen orbit $O_{\\_}i$.

Now if the convex combination contained an orbit whose worth was not maximal
then it would fail to satisfy condition (c). of Definition 5. Conversely, all
convex combinations of orbits with maximal worth satisfy condition (c), hence
they are Kantian program equilibria.

Let’s first prove that every Kantian program equilibrium is a team
equilibrium. This is easy: define the team utility function $U$ as follows:
for every action profile $P$ belonging to orbit $O$, $U(P)$ is equal to the
worth of the orbit $O$. The monotonicity of $U$ is evident.

All convex combinations of elements in $O$ are a team equilibria, while only
$U_{\\_}{O}$ is a Kantian program equilibrium. So if $|O|>2$ there are team
equilibria that are not Kantian program equilibria.

∎

With this result in hand, we can modify the definition of Kantian programs to
make it "executable", by changing exactly one aspect of the EBNF from Section
14, without changing the class of distributions of action profiles sampled by
Kantian program equilibria.

Namely, instead of allowing action-profile variables to be initialized with
arbitrary distributions of action profiles, we will insist that

  * -

the distribution on action profiles is only supported on Pareto optimal
profiles.

  * -

the probability distribution is uniform on orbits of the action of $H$ (the
probabilities may, of course, vary between orbits).

Clearly, this is enough to simulate programs such as Algorithms 4.1,4.2,4.3.
Conversely, programs like these ones can easily implement any convex
combination of distributions $U_{\\_}{O}$.

##  16 Proof of Theorem 4

###### Proof.

To explain what Theorem 4 we need to explain what a correlated symmetric
equilibrium of a symmetric game is. It is not enough to require that the
distribution of action profiles in a correlated equilibrium be symmetric: as
we have mentioned, the probability space and agents’ information partition is
part of the specification of correlated equilibria. To qualify as "symmetric
equilibrium" we have to impose some symmetry properties on the signal space,
set of information partitions, and allowable deviations as well:

######  Definition 19.

Consider a symmetric game $\Gamma=(N,(A_{\\_}i),(u_{\\_}i))$. We remind the
reader that that means that for every permutation $\pi\in S_{\\_}{n}$ and
profile $a=(a_{\\_}1,a_{\\_}2,\ldots,a_{\\_}{n})$, we have

$u_{\\_}i(a_{\\_}{\pi(1)},a_{\\_}{\pi(2)},\ldots
a_{\\_}{\pi(n)})=u_{\\_}{\pi(i)}(a_{\\_}1,a_{\\_}2,\ldots,a_{\\_}{n})$

A _correlated symmetric equilibrium_ of $\Gamma$ consists of

-

a finite, symmetric probability space $(\Omega^{n},\xi)$, where $\Omega$ is a
finite set. That is, we assume that for every
$(\omega_{\\_}{1},\omega_{\\_}{2},\ldots,\omega_{\\_}{n})\in\Omega^{n}$ and
every $\pi\in S_{\\_}{n}$,

$\xi(\omega_{\\_}{1},\omega_{\\_}{2},\ldots,\omega_{\\_}{n})=\xi(\omega_{\\_}{\pi(1)},\omega_{\\_}{\pi(2)},\ldots,\omega_{\\_}{\pi(n)})$

-

for each player $i\in N$ an information partition
$P_{\\_}i=(P_{\\_}i^{1},\ldots,P_{\\_}{i}^{t})$ of $\Omega^{n}$ and a strategy
function $\sigma_{\\_}i$, such that for every $\pi\in S_{\\_}{n}$ and $t$,

$P_{\\_}{\pi(i)}^{t}=\pi(P_{\\_}{i}^{t})\mbox{ and that
}\sigma_{\\_}{i}|_{\\_}{P_{\\_}{i}^{t}}\equiv\sigma_{\\_}{\pi(i)}|_{\\_}{P_{\\_}{\pi(i)}^{t}}.$

-

for any $i\in N$ and any strategies $\tau_{\\_}i$ satisfying
$\tau_{\\_}{i}|_{\\_}{P_{\\_}{i}^{t}}\equiv\tau_{\\_}{\pi(i)}|_{\\_}{P_{\\_}{\pi(i)}^{t}}$
we have:

$\sum_{\\_}{\omega\in\Omega^{n}}\pi(\omega)u_{\\_}{i}(\sigma_{\\_}{-i}(\omega),\sigma_{\\_}{i}(\omega))\geq\sum_{\\_}{\omega\in\Omega^{n}}\pi(\omega)u_{\\_}{i}(\tau_{\\_}{-i}(\omega),\tau_{\\_}{i}(\omega))$
(2)

Note that the probability space and the information partition are part of the
specification of the equilibrium.

Now the fact that correlated symmetric equilibria satisfy properties (2) and
(3) from Definition 17 follows from the definition above. All it remains to
show is that property (1) is true as well, namely that for every
$\omega\in\Omega^{n}$, action profile $P=(\sigma_{\\_}{i}(\omega))_{\\_}{i}$
is a Pareto-optimal profile. Suppose it weren’t. Then there exists an action
profile $Q$ strictly dominating $P$.

Consider the following strategies $\tau_{\\_}{i}$:

$\tau_{\\_}{i}(\omega)=\left\\{\begin{array}[]{ll}\pi(Q)&\mbox{if
}\omega=\pi(P)\mbox{ for some }\pi\in S_{\\_}{n}\\\ \sigma_{\\_}{i}&\mbox{
otherwise.}\end{array}\right.$

Then $(\tau_{\\_}{i})$ would contradict equation 2. ∎

##  17 Proof of Theorem 5

###### Proof.

Points (a). and (b). from the definition of Kantian program equilibria are
clear, the only one that merits a discussion is point (c).

The expected utility of each player under Algorithm 4 is equal to $1/n$. Since
the sum of utilities of all players under a particular set of random choices
is equal to 1, no vector of expected utilities can strictly dominate the
vector $(1/n,1/n,\ldots,1/n)$ of expected utilities for the Algorithm. ∎

##  18 Proof of Theorem 6

Let $P_{\\_}{1},P_{\\_}{2},\ldots,P_{\\_}{m}$ be the undominated profiles in
game $G$ and, for every $P_{\\_}j$ and player $i$, let $p_{\\_}{i,j}$ be the
utility player $i$ gets from profile $P_{\\_}j$. To find a Rawlsian
equilibrium we first solve the LP (3). This computes the egalitarian social
welfare $z^{*}$. Now solve system (4) . This yields a profile
$(x_{\\_}{1}^{*},\ldots,x_{\\_}{m}^{*})$ which, by our observation, is a
Rawlsian equilibrium. The same programs with a different semantics for
$p_{\\_}{i,j}$ as the percentile of $P_{\\_}{j}$ among undominated profiles
from the point of view of $i$, computes Rawlsian percentile equilibria.

$\left\\{\begin{array}[]{l}\max(z)\\\ p_{\\_}{i,1}x_{\\_}{1}+\ldots
p_{\\_}{i,m}x_{\\_}{m}\geq z,i=1,\ldots,n\\\ x_{\\_}{1}+\ldots+x_{\\_}{m}=1\\\
x_{\\_}{i}\geq 0.\end{array}\right.$ (3)

$\left\\{\begin{array}[]{l}\max(\sum\limits_{\\_}{j=1}^{m}(\sum\limits_{\\_}{i=1}^{n}p_{\\_}{i,j})x_{\\_}{j})\\\
p_{\\_}{i,1}x_{\\_}{1}+\ldots p_{\\_}{i,m}x_{\\_}{m}\geq z^{*},i=1,\ldots,n\\\
x_{\\_}{1}+\ldots+x_{\\_}{m}=1\\\ x_{\\_}{i}\geq 0.\end{array}\right.$ (4)

As for Bentham-Harsányi equilibria, we directly solve

$\left\\{\begin{array}[]{l}\max(\sum\limits_{\\_}{j=1}^{m}(\sum\limits_{\\_}{i=1}^{n}p_{\\_}{i,j})x_{\\_}{j})\\\
x_{\\_}{1}+\ldots+x_{\\_}{m}=1\\\ x_{\\_}{i}\geq 0.\end{array}\right.$ (5)

For aspiration equilibria we first solve the program

$\left\\{\begin{array}[]{l}\min(z)\\\ \sum_{\\_}{k\in
U_{\\_}{i}}x_{\\_}{k}\leq z,i=1,\ldots,n\\\ x_{\\_}{1}+\ldots+x_{\\_}{m}=1\\\
x_{\\_}{i}\geq 0.\end{array}\right.$

where $U_{\\_}{k}$ denotes action profiles making $j$ unhappy to find the
smallest agent probability of unhappiness. We then maximize (using another LP)
social welfare over agents realizing the minimum. For best-off equilibrium the
algorithm is somewhat more complicated: first, for every player $i=1,\ldots,n$
the program (6) yields the largest payoff $y_{\\_}{i}^{*}$ player $i$ could
get. If $y_{\\_}j^{*}=max(y_{\\_}{i}^{*}:i=1,\ldots,n)$ is the global optimum
then the program (7) finds the largest social welfare when agent $j$ reaches
its optimal value. Maximizing the social welfare over all such optimal $j$’s
gives the best-off equilibrium.

$\left\\{\begin{array}[]{l}\max(\sum\limits_{\\_}{j=1}^{m}p_{\\_}{i,j}x_{\\_}{j})\\\
x_{\\_}{1}+\ldots+x_{\\_}{m}=1\\\ x_{\\_}{i}\geq 0.\end{array}\right.$ (6)
$\left\\{\begin{array}[]{l}\max(\sum\limits_{\\_}{j=1}^{m}(\sum\limits_{\\_}{i=1}^{n}p_{\\_}{i,j})x_{\\_}{j})\\\
x_{\\_}{1}+\ldots+x_{\\_}{m}=1\\\
\sum\limits_{\\_}{k=1}^{m}p_{\\_}{j,k}x_{\\_}{k}=y_{\\_}{j}^{*}\\\
x_{\\_}{i}\geq 0.\end{array}\right.$ (7)

##  19 Proof of Theorem 7

###### Proof Sketch.

Because of domination only pure action profiles on the diagonal need to be
considered. By symmetry, optimizing the worst-off utility or the social
welfare over mixed profiles with diagonal pure strategies in the support is
equivalent to maximizing the best-off utility, which implies that all pure
action profiles in the support of Rawlsian (Bentham-Harsányi, best-off)
equilibria are Kantian. The converse is easily seen to be true. A similar
argument works for Rawlsian percentile and aspiration equilibria. ∎

##  20 Proof of Theorem 8

###### Proof.

Bounded-greed agents still coordinate on the Kantian equilibrium $(C,C)$ as
long as both their greed indices are $<2$ (i.e. they would need at least a
twofold increase in payoff to deviate). If one of them has greed index $<2$
and the other one has greed index $\geq 2$, then the latter one will defect.
If both agents have greed indices $\geq 2$, then they will coordinate, just as
if utilitarian agents would do, on the Nash equilibrium $(D,D)$. ∎

## References

  * [1]
  * [2] Ingela Alger & Jörgen W Weibull (2013): _Homo moralis - preference evolution under incomplete information and assortative matching_.  Econometrica 81(6), pp. 2269–2302.
  * [3] Ingela Alger & Jörgen W Weibull (2016): _Evolution and Kantian morality_.  Games and Economic Behavior 98, pp. 56–67.
  * [4] Dan Ariely (2010): _Predictably irrational_.  Harper.
  * [5] Robert Aumann & Adam Brandenburger (1995): _Epistemic conditions for Nash equilibrium_.  Econometrica: Journal of the Econometric Society, pp. 1161–1180.
  * [6] Robert J Aumann (1974): _Subjectivity and correlation in randomized strategies_.  Journal of mathematical Economics 1(1), pp. 67–96.
  * [7] Michael Bacharach (1999): _Interactive team reasoning: A contribution to the theory of co-operation_.  Research in economics 53(2), pp. 117–147.
  * [8] Michael Bacharach (2006): _Beyond individual choice: teams and frames in game theory_.  Princeton University Press.
  * [9] Mihaly Barasz, Paul Christiano, Benja Fallenstein, Marcello Herreshoff, Patrick LaVictoire & Eliezer Yudkowsky (2014): _Robust Cooperation in the Prisoner’s Dilemma: Program Equilibrium via Provability Logic_.  arXiv preprint arXiv:1401.5577.
  * [10] T Randolph Beard & Richard O Beil (1994): _Do people rely on the self-interested maximization of others? An experimental test_.  Management Science 40(2), pp. 252–262.
  * [11] Claude Berge (1957): _Théorie générale des jeux à n personnes_.  138, Gauthier-Villars Paris.
  * [12] José Luis Bermúdez (2021): _Frame it Again: New Tools for Rational Decision-making_.  Cambridge University Press.
  * [13] Kenneth G. Binmore (1994): _Game theory and the social contract: just playing_.  M.I.T. Press.
  * [14] Kenneth G. Binmore (1994): _Game theory and the social contract: playing fair_.  M.I.T. Press.
  * [15] Kenneth G. Binmore (2005): _Natural justice_.  Oxford University Press, USA.
  * [16] Lenore Blum, Felipe Cucker, Michael Shub & Steve Smale (1998): _Complexity and real computation_.  Springer Science & Business Media.
  * [17] Immanuel Bomze, Werner Schachinger & Jörgen Weibull (2020): _Does moral play equilibrate?_ Economic Theory, pp. 1–11.
  * [18] Immanuel M Bomze (1997): _Evolution towards the maximum clique_.  Journal of Global Optimization 10(2), pp. 143–164.
  * [19] Immanuel M Bomze (1998): _On standard quadratic optimization problems_.  Journal of Global Optimization 13(4), pp. 369–387.
  * [20] Antoni Bosch-Domènech & Joaquim Silvestre (2019): _Experiment-inspired comments on John Roemer’s theory of cooperation_.  Review of Social Economy 77(1), pp. 69–89.
  * [21] Samuel Bowles & Herbert Gintis (2013): _A cooperative species: Human reciprocity and its evolution_.  Princeton University Press.
  * [22] Matthew Braham & Martin van Hees (2020): _Kantian Kantian Optimization_.  Erasmus Journal for Philosophy and Economics 13(2), pp. 30–42.
  * [23] Valerio Capraro & Joseph Y Halpern (2015): _Translucent players: Explaining cooperative behavior in social dilemmas_.  In: Proceedings of the 15th conference on Theoretical Aspects of Rationality and Knowledge.
  * [24] Jing Chen & Silvio Micali (2016): _Auction revenue in the general spiteful-utility model_.  In: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pp. 201–211.
  * [25] Po-An Chen & David Kempe (2008): _Altruism, selfishness, and spite in traffic routing_.  In: Proceedings of the 9th ACM conference on Electronic commerce, pp. 140–149.
  * [26] Vadim Cherepanov, Tim Feddersen & Alvaro Sandroni (2013): _Revealed preferences and aspirations in warm glow theory_.  Economic Theory 54(3), pp. 501–535.
  * [27] Yann Chevaleyre, Ulle Endriss, Jérôme Lang, Paul E Dunne, Michel Lemaitre, Nicolas Maudet, Julian Padget, Steve Phelps, Juan A Rodriguez-Aguilar & Paulo Sousa (2006): _Issues in Multiagent Resource Allocation_.  Informatica 30\.
  * [28] Andrew M Colman & Natalie Gold (2018): _Team reasoning: Solving the puzzle of coordination_.  Psychonomic Bulletin & Review 25(5), pp. 1770–1783.
  * [29] Andrew M Colman, Tom W Körner, Olivier Musy & Tarik Tazdaït (2011): _Mutual support in games: Some properties of Berge equilibria_.  Journal of Mathematical Psychology 55(2), pp. 166–175.
  * [30] Andrew Critch (2019): _A parametric, resource-bounded generalization of Löb’s theorem, and a robust cooperation criterion for open-source game theory_.  The Journal of Symbolic Logic, pp. 1–15.
  * [31] Sanjit Dhami (2016): _The foundations of behavioral economic analysis_.  Oxford University Press.
  * [32] Jon Elster (2017): _On seeing and being seen_.  Social choice and welfare 49(3-4), pp. 721–734.
  * [33] Ernst Fehr & Klaus M Schmidt (1999): _A theory of fairness, competition, and cooperation_.  The quarterly journal of economics 114(3), pp. 817–868.
  * [34] Urs Fischbacher, Simon Gächter & Ernst Fehr (2001): _Are people conditionally cooperative? Evidence from a public goods experiment_.  Economics letters 71(3), pp. 397–404.
  * [35] Lance Fortnow (2009): _Program equilibria and discounted computation time_.  In: Proceedings of the 12th Conference on Theoretical Aspects of Rationality and Knowledge, pp. 128–133.
  * [36] Ghislain Fourny (2020): _Perfect Prediction in normal form: Superrational thinking extended to non-symmetric games_.  Journal of Mathematical Psychology 96, p. 102332.
  * [37] Robert H Frank (2004): _What Price the Moral High Ground? Ethical Dilemmas in Competitive Environments_.  Princeton University Press.
  * [38] Itzhak Gilboa & Eitan Zemel (1989): _Nash and correlated equilibria: Some complexity considerations_.  Games and Economic Behavior 1(1), pp. 80–93.
  * [39] Herbert Gintis (2009): _The bounds of reason: game theory and the unification of the behavioral sciences_.  Princeton University Press.
  * [40] Herbert Gintis (2010): _Social norms as choreography_.  Politics, Philosophy & Economics 9(3), pp. 251–264.
  * [41] Herbert Gintis (2016): _Individuality and entanglement: the moral and material bases of social life_.  Princeton University Press.
  * [42] Herbert Gintis (2016): _A Typology of Human Morality_.  In David S. Wilson & Alan Kirman, editors: Complexity and Evolution: Towards a New Synthesis for Economics, M.I.T. Press.
  * [43] Natalie Gold & Andrew M Colman (2020): _Team reasoning and the rational choice of payoff-dominant outcomes in games_.  Topoi 39(2), pp. 305–316.
  * [44] Davide Grossi & Paolo Turrini (2012): _Dependence in games and dependence games_.  Autonomous Agents and Multi-Agent Systems 25(2), pp. 284–312.
  * [45] Joseph Y Halpern & Rafael Pass (2018): _Game theory with translucent players_.  International Journal of Game Theory 47(3), pp. 949–976.
  * [46] Joseph Y Halpern & Nan Rong (2010): _Cooperative equilibrium_.  In: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1-Volume 1, pp. 1465–1466.
  * [47] Nicholas Ham (2013): _Notions of Symmetry for Finite Strategic-Form Games_.  arXiv preprint arXiv:1311.4766.
  * [48] John C Harsanyi (1955): _Cardinal welfare, individualistic ethics, and interpersonal comparisons of utility_.  Journal of political economy 63(4), pp. 309–321.
  * [49] John C Harsanyi (1977): _Rule utilitarianism and decision theory_.  Erkenntnis 11(1), pp. 25–53.
  * [50] Martin Hoefer & Alexander Skopalik (2013): _Altruism in atomic congestion games_.  ACM Transactions on Economics and Computation (TEAC) 1(4), pp. 1–21.
  * [51] Wiebe van der Hoek, Cees Witteveen & Michael Wooldridge (2013): _Program equilibrium—a program reasoning approach_.  International Journal of Game Theory 42(3), pp. 639–671.
  * [52] Douglas Hofstadter (1985): _Dilemmas for Superrational Thinkers, Leading up to a Luring Lottery_.  In: Metamagical Themas: Questing for the Essence of Mind and Pattern, Basic Books.
  * [53] John V Howard (1988): _Cooperation in the Prisoner’s Dilemma_.  Theory and Decision 24(3), p. 203.
  * [54] Albert Xin Jiang & Kevin Leyton-Brown (2015): _Polynomial-time computation of exact correlated equilibrium in compact games_.  Games and Economic Behavior 91, pp. 347–359.
  * [55] Adam Tauman Kalai, Ehud Kalai, Ehud Lehrer & Dov Samet (2010): _A commitment folk theorem_.  Games and Economic Behavior 69(1), pp. 127–137.
  * [56] Ioannis Kordonis (2020): _A Model for Partial Kantian Cooperation_.  In: Advances in Dynamic Games, Springer, pp. 317–346.
  * [57] Jean-Jacques Laffont (1975): _Macroeconomic constraints, economic efficiency and ethics: An introduction to Kantian economics_.  Economica 42(168), pp. 430–437.
  * [58] Patrick LaVictoire, Benja Fallenstein, Eliezer Yudkowsky, Mihaly Barasz, Paul Christiano & Marcello Herreshoff (2014): _Program equilibrium in the Prisoner’s Dilemma via Löb’s theorem_.  In: Workshops at the Twenty-Eighth AAAI Conference on Artificial Intelligence.
  * [59] Sydney Levine, Max Kleiman-Weiner, Laura Schulz, Joshua Tenenbaum & Fiery Cushman (2020): _The logic of universalization guides moral judgment_.  Proceedings of the National Academy of Sciences 117(42), pp. 26158–26169.
  * [60] Yang-Yu Liu, Jean-Jacques Slotine & Albert-László Barabási (2011): _Controllability of complex networks_.  Nature 473(7346), pp. 167–173.
  * [61] Dov Monderer & Moshe Tennenholtz (2009): _Strong mediated equilibrium_.  Artificial Intelligence 173(1), pp. 180–195.
  * [62] Theodore S Motzkin & Ernst G Straus (1965): _Maxima for graphs and a new proof of a theorem of Turán_.  Canadian Journal of Mathematics 17, pp. 533–540.
  * [63] Ahmad Nahhas & HW Corley (2018): _The Computational Complexity of Finding a Mixed Berge Equilibrium for a $k$-Person Noncooperative Game in Normal Form_.  International Game Theory Review 20(04), p. 1850010.
  * [64] John Nash (1951): _Non-cooperative games_.  Annals of mathematics, pp. 286–295.
  * [65] Caspar Oesterheld (2019): _Robust program equilibrium_.  Theory and Decision 86(1), pp. 143–159.
  * [66] Martin Osborne & Ariel Rubinstein (1994): _A Course in Game Theory_.  M.I.T. Press.
  * [67] Christos H Papadimitriou & Tim Roughgarden (2008): _Computing correlated equilibria in multi-player games_.  Journal of the ACM (JACM) 55(3), pp. 1–29.
  * [68] Jarosław Pykacz, Paweł Bytner & Piotr Frąckiewicz (2019): _Example of a finite game with no Berge equilibria at all_.  Games 10(1), p. 7.
  * [69] Ayn Rand (1964): _The virtue of selfishness_.  Penguin.
  * [70] John Rawls (2001): _Justice as fairness: A restatement_.  Harvard University Press.
  * [71] John E Roemer (2010): _Kantian equilibrium_.  Scandinavian Journal of Economics 112(1), pp. 1–24.
  * [72] John E Roemer (2015): _Kantian optimization: A microfoundation for cooperation_.  Journal of Public Economics 127, pp. 45–57.
  * [73] John E Roemer (2019): _How We Cooperate: A Theory of Kantian Optimization_.  Yale University Press.
  * [74] Nan Rong & Joseph Y Halpern (2013): _Towards a deeper understanding of cooperative equilibrium: characterization and complexity_.  In: Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems, pp. 319–326.
  * [75] Iris van Rooij, Mark Blokpoel, Johan Kwisthout & Todd Wareham (2019): _Cognition and intractability: A guide to classical and parameterized complexity analysis_.  Cambridge University Press.
  * [76] Tim Roughgarden (2005): _Selfish Routing and the Price of Anarchy_.  M.I.T. Press.
  * [77] Sally Sedgwick (2008): _Kant’s groundwork of the metaphysics of morals: an introduction_.  Cambridge University Press.
  * [78] Reinhard Selten & Werner Güth (1982): _Equilibrium point selection in a class of market entry games_.  In: Games, economic dynamics, and time series analysis, Springer, pp. 101–116.
  * [79] Itai Sher (2020): _Normative Aspects of Kantian Equilibrium_.  Erasmus Journal for Philosophy and Economics 13(2), pp. 43–84.
  * [80] Yoav Shoham & Kevin Leyton-Brown (2009): _Multiagent systems: Algorithmic, game-theoretic, and logical foundations_.  Cambridge University Press.
  * [81] Jaime Simão Sichman & Rosaria Conte (2002): _Multi-agent dependence by dependence graphs_.  In: Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, pp. 483–490.
  * [82] Herbert Alexander Simon (1997): _Models of bounded rationality: Empirically grounded economic reason_.  3, MIT press.
  * [83] Noah D Stein (2011): _Exchangeable Equilibria_.  Ph.D. thesis, Massachusetts Institute of Technology.
  * [84] Robert Sugden (2003): _The logic of team reasoning_.  Philosophical explorations 6(3), pp. 165–181.
  * [85] William J Talbott (1998): _Why We Need a Moral Equilibrium Theory_.  In P. Danielson, editor: Modeling Rationality, Morality and Evolution, Oxford University Press.
  * [86] Moshe Tennenholtz (2004): _Program equilibrium_.  Games and Economic Behavior 49(2), pp. 363–373.
  * [87] Fernando A Tohmé & Ignacio D Viglizzo (2019): _Structural relations of symmetry among players in strategic games_.  International Journal of General Systems 48(4), pp. 443–461.
  * [88] Fernando A Tohmé & Ignacio D Viglizzo (2019): _Superrational types_.  Logic Journal of the IGPL 27(6), pp. 847–864.
  * [89] Michael Tomasello (2009): _Why we cooperate_.  MIT press.
  * [90] Michael Tomasello (2016): _A natural history of human morality_.  Harvard University Press.
  * [91] Vladislav I Zhukovskii (1985): _Some problems of non-antagonistic differential games_.  Matematiceskie metody v issledovanii operacij, pp. 103–195.
  * [92] Vladislav I Zhukovskiy & Konstantin N Kudryavtsev (2017): _Mathematical foundations of the Golden Rule. I. Static case_.  Automation and Remote Control 78(10), pp. 1920–1940.