Routing Mediators

1 Introduction

In many multi-agent systems it makes little sense to assume that agents will stick to their parts when provided with suggested strategies, if a deviation can increase their payoffs. While for any multi-agent encounter, represented as a strategic form game, there always exists a strategy profile for which unilateral deviations are not beneficial, requirements regarding the deviation of multiple players are rarely satisfied. In order to tackle this issue we consider in this paper the use of routing mediators, extending upon previous work in game theory and AI.

A mediator is a reliable entity that can interact with the players, and potentially act on behalf of the players that give him a permission to do so. However, a mediator can not enforce behavior. Indeed, an agent is free to participate in the game without the help of the mediator. This notion is highly natural; in many systems there is some form of reliable party that can be used as a mediator. In particular, brokers in financial markets, bidding club organizers in auctions, as well as routers in communication networks, can be viewed as mediators. Notice that we assume that the multi-agent interaction (formalized as a game) is given, and all the mediator can do is to perform actions on behalf of the agents that explicitly allow it to do so. The mediator's behavior on behalf of the agents that give it the right of play is pre-specified, and is conditioned on the information available to the mediator on all agents' actions.

This natural setting is different from the one discussed in the theory of mechanism design (see [Mas-Colell et al., 1995; Jackson, 2001] for an introduction) where a designer designs a new game from scratch in order to yield some desired behavior. The simplest form of mediator discussed in the game theory literature is captured by the notion of correlated equilibrium [Aumann, 1974]. This notion was generalized to communication equilibrium by [Forges, 1986; Myerson, 1986]. Another type of mediators is discussed in [Monderer and Tennenholtz, 2004]. However, in all these settings the mediator cannot act on behalf of the agents.

A more powerful type of mediators, which can perform actions on behalf of the agents who give the mediator the right of play is considered in [Monderer and Tennenholtz, 2006]. This type of mediators turns out to be a specific case of the mediators discussed in this paper. Namely, in this restricted setting the agents need to decide whether to give the mediator the right of play, while the mediator does not possess any further information on the agents' actions.

In order to illustrate the power of a reliable mediator consider the famous prisoners dilemma game:

In this classical example we get that in the only equilibrium both agents will play D, yielding both of them a payoff of 1. However, this equilibrium, which is also a dominant strategy equilibrium, is inefficient; indeed, if both agents deviate from D to C then both of them will improve their payoffs. Formally, (D,D) is not a strong equilibrium; it is not stable against deviations by coalitions. Indeed, there is no strong equilibrium in the prisoners dilemma game.

Consider now a reliable mediator who offers the agents the following protocol: if both agents agree to use the mediator services then he will play C on behalf of both agents. However, if only one agent agrees to use his services then he will play D on behalf of that agent. Notice that when accepting the mediator's offer the agent is committed to actual behavior as determined by the above protocol. However, there is no way to enforce the agents to accept the suggested protocol, and each agent is free to play C or D without using the mediator's services. Hence, the mediator's protocol generates a new game, which we call a mediated game, where a new strategy M is available for using the mediator services:

The mediated game has a most desirable property: in this game there is a strong equilibrium; that is, an equilibrium which is stable against deviations by coalitions. In this equilibrium both agents will use the mediator services, which will lead them to a payoff of 4 each!

Although the above example illustrates the potential power of a mediator who can act on behalf of agents who give him the right of play, the above mediator was very restricted. In general, a routing mediator possesses information about the actions taken by the agents. Consider a router in a typical communication network. Assume that messages submitted to the system must pass through this router. In addition, the router can suggest a protocol to the agents who may wish to use its services also in selecting appropriate routes. Hence, in this situation it is most natural to assume that the router can observe selected actions of all agents, and not only of those who give it the right of play. In order to illustrate the power of such routing mediator consider the following example:

Given the above game, assume we are interested in obtaining a socially optimal outcome, in which each agent gets a payoff of 6. It is easy to see that the column player can guarantee himself an expected payoff of 6.5 by playing B or C with probability 0.5 each. As a result, a routing mediator who is not informed about the pure realizations of the column player's strategies cannot implement any outcome in which that player gets a payoff less than 6.5. However, a routing mediator who can see the pure realizations of the deviating player and choose the punishment appropriately can enforce the outcome (6, 6) as a strong equilibrium! This can be achieved, for example, by the following protocol: If only agent i selects the mediator's services, the mediator will copy the action of the other player, j, on behalf of i; if both agents select to use the mediator's services then the mediator will perform C on behalf of both agents.

This example illustrates the important role of information in the definition of a routing mediator. Indeed, routing mediators can be classified based on the information they can access about the agents' actions. In this paper, we formally define routing mediators as a function of their available information. We distinguish between two types of available information:

1. Information about the actual action instantiations.
2. Information about the agents' programs (i.e. correlated strategies).

As we will show, having access to the agents' actions may sometimes be more powerful than having access to their programs, and vice versa.

Given the general setting of routing mediators, we prove that they can indeed significantly increase the set of desired outcomes that can be obtained by multi-agent behaviors which are robust against deviations by coalitions. Namely, we show that any minimally fair game possesses a fair and efficient correlated super-strong mediated equilibrium. In a correlated super-strong equilibrium, correlated deviations by any subset of agents can not benefit one of them without hurting another. A minimally fair game is a game in which all actions are available to all agents, and agents who select identical actions get identical payoffs. A particular example of minimally fair games are the symmetric games, but the family of minimally fair games is much wider. In particular, our results are applicable to congestion games and job-shop scheduling, two major topics of study in the interface between computer science and game theory.

2 Preliminaries

2.1 Games in strategic form

A game in strategic form is a tuple Γ = 〈N, (Xi)i∈N, (ui)i∈N〉, where N is a finite set of players, Xi is the strategy set of player i, and ui : X → ℜ is the payoff function for player i, where X = ×i∈NXi. If |N| = n, whenever convenient we assume N = {1, · · · , n}. Γ is finite if the strategy sets are finite.

For every S ⊆ N we denote XS = ×i∈SXi. When the set N is clear, XN\S will be also denoted by X-S , and moreover, X-{i} will be also denoted by X-i.

When we discuss subsets of a given set we implicitly assume non-emptiness unless we specify otherwise. Let Y be a set. The set of probability distributions with finite support over Y is denoted by Δ(Y ). That is, every c ∈ Δ(Y ) is a function c : Y → [0, 1] such that {y ∈ Y |c(y) > 0} is finite, and ∑y∈Y c(y) = 1. For every y ∈ Y we denote by δy the probability distribution that assigns probability 1 to y. Let I be a finite set, and let ci ∈ Δ(Yi), i ∈ I, where I is a finite set of indexes, and Yi is a set for every i ∈ I. We denote by ×i∈Ici the product probability distribution on Y = ×i∈I Yi that assigns to every y ∈ Y the probability ∏i∈I ci(yi).

Let Γ = 〈N, (Xi)i∈N, (ui)i∈N〉 be a game in strategic form, and let S ⊆ N. Every c ∈ Δ(XS) is called a correlated strategy for S . A correlated strategy for the set of all players N is also called a correlated strategy, and for every i, a correlated strategy for {i} is also called a mixed strategy for i. Let c ∈ Δ(X) and let S ⊆ N, the marginal probability induced by c on XS is denoted by c[S]. That is,

The expected payoff of i with respect to a correlated strategy c is denoted by Ui(c). That is,

For every i, and for every xi ∈ Xi, the mixed strategy δxi is called a pure strategy.

2.2 Strong equilibrium concepts

Let Γ = 〈N, (Xi)i∈N, (ui)i∈N〉 be a game in strategic form, and let x ∈ X. We say that x is a pure strong equilibrium [Aumann, 1959] in Γ if the following holds:

For every subset, S of players and for every yS ∈ XS there exists i ∈ S such that ui(yS, x-s) ≤ ui(x).

Let c ∈ Δ(X). We say that c is a correlated strong equilibrium (see [Rozenfeld and Tennenholtz, 2006]), if for every subset of players S , and for every correlated strategy for S, ξS ∈ Δ(XS) there exists i ∈ S such that Ui(ξS × c[-S]) ≤ Ui(c).

The notion of pure strong equilibrium is the one typically studied in the game theory literature when considering deviations by coalitions. The concept of correlated strong equilibrium considers also correlated deviations. Of course, a pure strong equilibrium is not necessarily a correlated strong equilibrium. Correlated strong equilibrium is a very natural requirement. In an environment in which the players fear/hope that correlated deviations are possible, we expect a strategy profile to be a correlated strong equilibrium in order to be believed/played by the players. In the scope of this article, we will consider such correlation possible, and therefore when we use the term strong equilibrium, we refer to correlated strong equilibrium.

The above definitions assumed that a player would agree to join a deviating coalition only if the deviation would result in a strict improvement of his payoff. A much stronger stability concept is needed if we fear that players may be persuaded to join a deviating coalition also in cases where such deviation would leave their payoff unchanged, but would increase the payoff of at least one of the other coalition members.

We say that c ∈ Δ(X) is a correlated super-strong equilibrium (or super-strong equilibrium) if there is no S ⊆ N and ξS ∈ Δ(XS), such that: for all i ∈ S, Ui (ξS, c[-S] ) ≥ Ui (c), and for at least one i ∈ S the inequality is strict.

A super-strong equilibrium is, in particular, a strong equilibrium, but not vice versa.

2.3 Information sets

Let Y be a set. We say that Ω is an information set on Y if Ω is a partition of Y .

Let y ∈ Y . By ω(y) we refer to the equivalence class of y in Ω, i.e. to P ∈ Ω s.t. y ∈ P.

We use these definitions in order to model situations in which an element y ∈ Y is chosen, and an agent has only partial information about the chosen element. It is assumed that, if Ω is the information set that is available to such agent, the agent is informed of ω(y).

Let Ω1,Ω2 be information sets on Y . We say that Ω1 refines Ω2 if for all y1, y2 ∈ Y if ω1(y1) = ω1(y2) then

ω2(y1) = ω2(y2). That is, an agent with available information Ω1 is informed at least as well as an agent with Ω2.

The above relation is a partial ordering of the information sets, which forms a lattice: the maximal possible information on Y is Ωfull = {{y}|y ∈ Y }; having such information means that for any choice of y ∈ Y , , the agent knows exactly which element was chosen. The minimal possible information on Y is Ω∅ = {Y }; that means that the agent has no information at all about any chosen element y ∈ Y .

3 Routing mediators

We now introduce routing mediators, a general tool for coordinating and influencing agents' behavior in games. A routing mediator is always assumed to be reliable, and he is endowed with a single ability: to play for the players who explicitly give him the right to play for them. The mediator cannot enforce the players to use his services, neither can he affect the players' utility values. However, routing mediators differ in the information they have on the strategy profile which is being chosen by the players.

Let Γ be a game in strategic form. A routing mediator for Γ is a tuple 〈m,Ω,Ψ, (cω,ψ)ω∈Ω,ψ∈Ψ〉, where the following holds:

• m /∈ Xi for all i ∈ N. m denotes the new strategy that is now available to each player: to send a message to the mediator, indicating that the player agrees to give the mediator the right of play for him. 1
• Ω is an information set on Z, where Z = ×i∈NZi, and Zi = Xi ∪ {m}. Ω represents the information available to the mediator about each pure realization of the players' correlated strategy.

Ω refines Ωbasic, which is defined as follows:

Given z ∈ Z, let T (z) denote {j ∈ N|zj = m}. That is, T (z) denotes the players who agree to give the mediator the right of play for them in z. Then, Ωbasic is the partition induced by the following equivalence relation on Z: z1 ≡ z2 iff T (z1) = T (z2) (For ω ∈ Ω we will use T (ω) to denote T (z) for some z ∈ ω).

That is, we demand that in each pure realization of the agents' strategy the mediator knows exactly which players give him the right of play for them.

• Ψ is an information set on Δ(Z ), which represents the information available to the mediator about the correlated strategy of the players. We place no restrictions on Ψ, in particular Ψ may equal Ψbasic = {Δ(Z )}, meaning that the mediator has no such information.
• For every ω ∈ Ω, ψ ∈ Ψ, cω,ψ ∈ Δ (XT(ω) ). That is, c is the conditional contract that is offered by the mediator: it specifies exactly which actions the mediator will perform on behalf of the players who agree to use his services, as a function of the information available to it about the strategy profile chosen by the agents.

1 [Monderer and Tennenholtz, 2006] show that no power is added if the communication between the mediator and the players includes more than one message type.

Every mediator M for Γ induces a new game Γ(M) in strategic form in which the strategy set of player i is Zi. The payoff function of i is defined for every c ∈ Δ(Z ) as follows:

The above definitions express the following interaction between the mediator and the players:

1. The players choose a profile c ∈ Δ(Z )
2. A joint coin flip is issued, determining a pure realization z ∈ Z of c
3. The mediator is informed of ω(z) and ψ(c)
4. The mediator issues a coin flip to determine a pure realization δT(z) of cω(z),ψ(c)
5. The payoff of each player i is given according to ui (δT(z), z[-T(z)] )

The payoffs of the players from the profile c are assumed to be their expected payoffs from both coin flips in steps 2,4.

The mediator is guaranteed to behave in a pre-specified way, however this behavior is conditional on the actions of the other agents. For this reason, although Ui(c) is well defined for any profile c ∈ Δ(Z ), in particular for pure profiles z ∈ Z, Ui(c) does not necessarily equal ∑z∈Z Ui(z)c(z), unless Ψ = Ψbasic. Nevertheless, the concepts of strong equilibrium can still be applied to Γ(M).

Let Γ be a game in strategic form, m /∈ ⋃i∈N Xi, Ω an information set on Z, Ψ an information set on Δ(Z ). Let mN denote the pure strategy profile ×i∈Nm ∈ Z. A correlated strategy c ∈ Δ(X) is a strong mediated equilibrium relatively to Ω,Ψ if there exists a mediator for Γ, M = 〈m,Ω,Ψ, (cω,ψ)ω∈Ω,ψ∈Ψ〉, with cω(mN ),ψ(mN ) = c, for which mN is a correlated strong equilibrium in Γ(M). The notion of super-strong mediated equilibrium can be defined similarly.

Note that the above definition coincides with the one of [Monderer and Tennenholtz, 2006] in the case where Ω = Ωbasic, Ψ = Ψbasic; i.e. they considered the case in which the mediator is only informed of the players that chose to delegate him the right to play for them in step 2; he has no information about the actions of the other players, neither about the correlated strategy that was chosen in step 1.

Situations which can be modelled by Ψ = Ψfull = {{c}|c ∈ Δ(Z )} are situations in which the mediator doesn't decide/reveal its action before the players choose theirs. For example, in a computerized setting, where the correlated deviation is implemented using a program which is submitted and executed on a server, and the mediator is located on this server, the mediator is fully informed about the correlated strategy of the players. In another example, even if the mediator is not informed about correlated deviations, the players might fear that such information leak is possible. Lastly, the players may consider a worst case behavior of the mediator, and therefore would agree to deviate only if the mediator can't possibly harm any one of them.

Ω ̸= Ωbasic can be used to model all the situations in which the mediator does indeed, as the name implies, "stand between" the players and the actual game, e.g. situations in which the play is only available through the mediator. For example, if the players' strategies are messages in a network and the mediator sits on the router, it might be reasonable to assume that Ω = Ωfull.

Observations: Suppose c ∈ Δ(X) is a strong (super-strong) mediated equilibrium relatively to Ω, Ψ.

1. Let w(c) = (w1, . . . ,wn) be the payoff vector induced by c. Then, for any c′ ∈ Δ(X) such that w(c′ ) = w(c), c′ is a strong (resp. super-strong) mediated equilibrium relatively to Ω, Ψ. In light of this, we will sometimes use the following notation: a payoff vector w can be implemented as a strong (super-strong) mediated equilibrium relatively to Ω,Ψ if there exists c ∈ Δ(X) such that w(c) = w and c is a strong (resp. super-strong) mediated equilibrium relatively to Ω, Ψ.
2. If Ψ = Ψfull, c can be implemented as a strong (resp. super-strong) mediated equilibrium relatively to Ω,Ψ even if the mediator is restricted to use only pure actions (i.e. satisfies cω,ψ ∈ XT(ω)).
3. If Ω′ refines Ω, then c is also a strong mediated equilibrium relatively to Ω′ , Ψ
4. If Ψ′ refines Ψ, then c is also a strong mediated equilibrium relatively to Ω, Ψ′

Observations 3, 4 show that the possible values of Ω,Ψ induce a four-end lattice of strong mediated equilibrium concepts, where the strongest (most stable) concept is obtained from Ωbasic,Ψbasic (since it assumes nothing on the information available to the mediator), and the weakest concept is obtained from Ωfull,Ψfull. Part of this lattice is depicted below (arrows mean increase in stability):

A natural question to ask is whether there exists a general relationship between the strong mediated equilibria concepts induced by Ωbasic,Ψfull and Ωfull,Ψbasic. The question is, what empowers the mediator more - increasing the information available to him on each pure outcome, or increasing the information about the correlated strategies?

As it turns out, this question does not have a general answer:

Proposition 1 There exists a game Γ and a strategy profile c which is a strong mediated equilibrium relatively to Ωfull,Ψbasic, but not a strong mediated equilibrium relatively to Ωbasic, Ψfull.

An example of such game and such profile appears in the introduction. A less intuitive result is the following:

Proposition 2 There exists a game Γ and a strategy profile c which is a strong mediated equilibrium relatively to Ωbasic,Ψfull, but not a strong mediated equilibrium relatively to Ωfull, Ψbasic.

However, note that the players 1, 2 were able to guarantee themselves the payoffs (6, 6) as a response to any contract offered by the mediator. In a sense, the information set Ψbasic means that the players are more informed than the mediator - the strategy of the mediator in this setting is fixed, and cannot depend on the correlated strategy chosen by the players; while their correlated strategy can be a best response to the mediator's strategy. When the information set Ψfull is considered, the mediator becomes more informed than the players: he can devise a response based on their correlated strategy. In this example, a mediator who is aware of the exact probabilities that the players 1, 2 assign to the profiles (A,A) and (B,B) can always respond by a pure strategy A or B on behalf of the third player in a way that will cause one of the players to get a payoff less than 5, making the deviation not beneficial for them.

A formal proof of the above intuition is technically cumbersome, and therefore is left to the full version.

4 The existence of strong mediated equilibrium

In this section we present our main result. We show a natural class of routing mediators that allow to implement fair and efficient outcomes as a correlated super-strong equilibrium in a very wide class of games.

Some definitions are needed:

A permutation of the set of players is a one-to-one function from N to N. For every permutation π and for every action profile x ∈ X we denote by πx the permutation of x by π. That is, (πx)πi = xi for every player i ∈ N.

Let Γ be a game in strategic form. Γ is a symmetric game if Xi = Xj for all i, j ∈ N and ui (x) = uπ(i) (πx) for every player i, for every action profile x ∈ X and for every permutation π.

Needless to say that symmetric games are most popular in computerized settings. For example, the extremely rich literature on congestion games in computer science deals with particular form of symmetric games [Papadimitriou, 2001]. However, our main result requires a weaker notion of symmetry:

Let Γ be a game in strategic form. Γ is a minimally fair game if for all i, j ∈ N,Xi = Xj and for every action profile x ∈ X, xi = xj implies that ui(x) = uj(x).

That is, a game is minimally fair if players who play the same strategy get the same payoff. The exact value of the received payoff may depend on the identities of the players who chose the strategy, as well as on the rest of the profile. In particular, every symmetric game is a minimally fair game; however, minimally fair games capture a much wider class of settings. For example, typical job-shop scheduling games are minimally fair games.

Note that in a minimally fair game, unlike in a symmetric game, the symmetric socially optimal payoff is not necessarily feasible. In order to capture our notion of fair and efficient outcomes in such games, we need to define the notion of lexicographic ordering on vectors of payoffs:

Let sort : ℜn → ℜn be a function that sorts the elements of real vectors in increasing order. Given two vectors w, w′ ∈ ℜn we say that w ≺l w′ (w is lexicographically smaller than w′ ) if there exists 1 ≤ i ≤ n such that sort(w)i < sort(w′ )i and for all 1 ≤ j < i sort(w)j = sort(w′ )j .

Let Γ be a minimally fair game. We say that a vector w ∈ ℜn is the max-min fair payoff of Γ if w is the lexicographically maximal feasible payoff vector in Γ. It is easy to see that such vector always exists, and is unique. Also, such vector is, by definition, Pareto optimal.

The fairness criterion we use is in fact the well-known max-min fairness criterion, as discussed in the communication networks literature (see e.g. [Kumar and Kleinberg, 2000]).

We are now ready to state our main result:

Theorem 1 Let Γ be a minimally fair game. Then, the maxmin fair payoff of Γ can be implemented as a super-strong mediated equilibrium relatively to Ωfull, Ψbasic.

Proof: Let w be the max-min fair payoff vector of Γ. Suppose w.l.o.g. that the vector w is sorted in increasing order and the players in N are renamed appropriately.

Let m /∈ ⋃i∈N Xi. We define a routing mediator M = 〈m, Ωfull, Ψbasic, (cω,ψ)ω∈Ωfull,ψ∈Ψbasic 〉 as follows: Ψbasic contains a single element, therefore it suffices to define cω(z) for all z ∈ Z. Let z ∈ Z. If T (z) = N, we define cω(z) to be the strategy profile that implements w. Otherwise, let T = T (z), let i =max{N \ T} (i.e. i is the highest indexed player among those who don't cooperate with the mediator in z), and let a = zi. We then define cω(z) = ×i∈T δa.

That is, the action of the mediator for each pure realization of the correlated profile is to have all the cooperating players copy the action of the deviator with the highest payoff in w.

Let S ⊆ N, ξS ∈ Δ(ZS). Let ξ = ξS × (×i∈N\Sδm) be the profile in Γ(M) that is obtained from the deviation of S

to ξS. Suppose, for contradiction, that S weakly benefits from deviating to ξS in Γ(M) relatively to mN ; that is, ∀i ∈ S Ui (ξ) ≥ wi and ∃i ∈ S Ui (ξ) > wi.

Let k be the highest indexed player in S. In every pure realization z of ξ, all the players in N \S play the same action as k: either because k ∈ T (z), or because k is, in particular, the highest indexed player in N \ T (z). Therefore, Uj (ξ) = Uk (ξ) for every player j ∈ N \ S; therefore, for every j ∈ {1, ..., k} \ S, Uj (ξ) ≥ wk ≥ wj, which means that all the players in S′ = {1, ..., k} can deviate to the correlated profile ξ ′ , in which the players in S play by ξ and the players in S′ \S copy the strategy of player k, and S′ would also weakly benefit from this deviation.

Therefore, we can assume w.l.o.g. that S = {1, . . . , k} for some 1 ≤ k < n. Let w′ be the payoff vector that is induced by ξ. We know that for every k ≤ j ≤ n, w′j = w′k ≥ wk. Since w is Pareto optimal, we know that k < n (otherwise, w′ would Pareto dominate w); w.l.o.g. we can assume that wk < wk+1.

We define a payoff vector w′′ as follows:

First, we note that (w′′ 1 , ..., w′′ k ) Pareto dominates (w1, ...,wk): if w′′ = w′ this follows from the fact that S weakly benefits from the deviation that results in w′ ; in the other case, the same holds since ε > 0.

Next, we note that the choice of ε ensures that w′′ i ≤ w′′ j for j ≤ k, i > k; combined with our previous observation, this implies that w ≺l w′′ , contradicting our choice of w.

Belowwe present two additional results, that can be proven using similar logic as behind the proof of Theorem 1. The proofs of these results are therefore omitted due to lack of space. Both results attempt to relax the requirements on the information set Ω, at the price of restricting attention to the class of symmetric games (Theorem 2) or considering strong instead of super-strong equilibrium (Theorem 3).

The relaxation of the requirements on Ω is based on the idea that in order to "punish" a set of deviating agents, we don't have to see the actions of all of them; it suffices, under some conditions, to observe only the action selected by a single deviator.

Formally, Ω must satisfy the following: there exists an ordering <P on N such that for all z, z′ ∈ Z if zmax<P {N\T(z)} ̸= z′max<P {N\T(z)} then ω (z) ̸= ω (z′ ). That is, Ω allows to distinguish between different actions of the highest ranked player (by <P ) among the deviators.

Theorem 2 Let Γ be a symmetric game, and suppose than an information set Ω on Z satisfies the above property.

Then, the symmetric optimal payoff vector w = (V, . . . , V ) in Γ can be implemented as a super-strong mediated equilibrium relatively to Ω, Ψbasic.

Theorem 3 Let Γ be a minimally fair game, and suppose than an information set Ω on Z satisfies the above property.

Then, the max-min fair payoff of Γ can be implemented as a strong mediated equilibrium relatively to Ω, Ψbasic.

5 Further work

The general aim of this research is to find rich settings in which routing mediators can help to achieve stability and/or efficiency. In this paper we concentrated on achieving stability against deviations by coalitions via the concept of correlated strong equilibrium; other desirable solution concepts can be of interest, e.g. pure equilibria concepts (Nash, strong), weakly dominant strategies, and coalition proof equilibrium [Bernheim et al., 1987].

Other models of multi-agent interaction, e.g. repeated games, or games with incomplete information, are also under consideration.