Preplay Negotiations with Unconditional Offers of Side Payments in Two-Player Strategic-Form Games: Towards Non-Cooperative Cooperation

Abstract

I consider strategic-form games with transferable utility extended with a phase of negotiations before the actual play of the game, where players can exchange a series of alternating (turn-based) unilaterally binding offers to each other for incentive payments of utilities after the play, conditional only on the recipients playing the strategy indicated in the offer. Every such offer transforms the game payoff matrix by accordingly transferring the offered amount from the offering player’s payoff to the recipient’s in all outcomes where the indicated strategy is played by the latter. That exchange of offers generates an unbounded-horizon, extensive-form preplay negotiations game, which is the focus of this study. In this paper, I study the case where the players assume that their opponents can terminate the preplay negotiations phase at any stage. Consequently, in their negotiation strategies, the players are guided by myopic rationality reasoning and aim at optimising each of their offers. The main results and findings include a concrete algorithmic procedure for computing players’ best offers in the preplay negotiations phase and using it to demonstrate that these negotiations can generally lead to substantial improvement of the payoffs for both players in the transformed game, but they do not always lead to optimal outcomes, as one might expect.

1. Introduction

The traditional approach to non-cooperative games in strategic (normal) form makes no allowance for possible communication between the players prior to the game. This is one of the inherent reasons why some games in strategic form, such as the Prisoner’s Dilemma, have rather unsatisfactory— for example, strictly Pareto dominated—equilibria solutions. The argument is that the lack of communication between the players leads to the impossibility for them to coordinate or negotiate before the play of the game, with the aim of trying to reach mutually more beneficial outcomes in the actual game while still playing it in a non-cooperative mode. A natural mechanism enabling the possibility of such preplay negotiations was proposed and studied in [1,2]. It is based on the assumption that the players are able to communicate before playing the game and make unilaterally binding offers to other players for payments of explicitly declared amounts of utility, which are only contingent on the strategy played by the recipient of such an offer. More precisely, the underlying assumption proposed and studied in [1,2] is that before the actual game is played, any player X can make a binding offer to another player Y to pay him (I randomly assign genders for players only for the sake of convenience of expression), after the game is played, an explicitly declared amount of utility δ if Y plays a strategy s specified in the offer by X. (Clearly, such offers can only make sense when the payoffs come with transferable utilities).

The structure and outcome of the emerging preplay negotiations game between the players exchanging such offers depends crucially on some additional assumptions about the nature of the negotiation process (whether or not offers can be conditional on the opponents responding with matching offers, whether offers can be withdrawn, whether the players’ time is valuable, etc.). The case of preplay negotiations with conditional offers was analysed in [1,2], where it is shown that assuming valuable time (but not in general), the preplay negotiation phase essentially falls under the framework of Rubinstein’s bargaining model [3,4]. The reader is also referred to [2] for an extensive discussion on the related work and comparisons with other approaches.

The motivation for such studies stems from the realisation that agreements in various economic and political negotiations are usually reached in dynamic bargaining processes made of offers and counteroffers, rather than one-shot simultaneous proposals. Therefore, introducing an extensive-form bargaining procedure preceding the play of a strategic form game is relevant and important for the modelling and analysis of a wide spectrum of political, social, and economic situations involving negotiations and compromises between non-cooperative parties, such as the following:

• Collusions between two or more parties in an economic activity by exchanging “behind the curtain” agreements for mutual incentives and other quasi-legal incentives;
• Kickback schemes and other corruption schemes involving bribes in exchange of illegal favours;
• Pre- and post-election political negotiations;
• Compensations, concessions, out-of-court settlements of legal cases, etc.

For further discussion of such kinds of scenarios and the related approaches to preplay negotiations, see the discussion on related works in Section 6.

Building on the framework of preplay offers and negotiation games developed in [1,2], here, I consider and analyse the case when players can only exchange unconditional offers for incentive payments, that is, offers which are not made subject to explicit acceptance or making suggested or expected counter-offers by the recipient. Rubinstein’s bargaining model does not apply here, because, even when time is valuable, players generally stand to lose more by making early offers towards a desired outcome and thus making unilateral concessions, rather than waiting for the opponents to make such respective moves, leading to the same outcome. The self-disadvantaging effect of making first offers is illustrated by some examples in Section 5.

Furthermore, in this work, I assume, as is common in non-cooperative games, that the players cannot make any reliable assumptions or predictions about the behaviour of their opponents in the preplay negotiations phase of the game. In particular, players can expect that the preplay negotiations game can terminate immediately after their next offer, as their opponents may not be willing or able to make any further suitable offers in response. This is a natural and common assumption when players do not know well enough the others’ preferences, the methods for computing their value of the strategic game to be played, or the knowledge and beliefs about each other’s rationality, degree of patience, value of time, etc. Therefore, one cannot assess reliably the other players’ rational behaviour. Under this assumption, it can naturally be expected that the players are guided in their negotiation strategy by a myopic rationality reasoning that always aims at optimising each of their offers individually without expecting any cooperation by their opponents in extending the negotiation process further. Thus, here I study the myopic, locally rational behaviour of players, who follow step-wise optimal strategies in pursuit of the long-term objective of optimising the outcome of the resulting strategic game. I argue that this assumption is more natural and closer to reality than the alternative, where players expect that negotiations will for certain go on until all parties ultimately reach what they consider to be an optimal agreement. Thus, the players’ uncertainty in the opponents’ cooperation in the preplay negotiations process is both a feature and a consequence of their myopic rationality reasoning.

The examples and analysis presented here show that under these assumptions, the preplay negotiations can develop in essentially different ways, substantially improving the payoffs of both players in general while not always leading to optimal outcomes. In particular, the bargaining power of unconditional offers turns out to be substantially weaker than the bargaining power of players who can also exchange conditional offers, as studied in [1,2]. Here, I do not consider the issue of how preplay offers can be made binding on the offerers and therefore trusted by the recipients. There are various mechanisms that can ensure this, such as by signing contracts imposing penalties for defaults or by using trusted third parties. I simply assume here that such a mechanism is in place and analyse the game-theoretic consequences of that assumption.

An important point to emphasise again is that the unconditional preplay offers are assumed to only be unilaterally binding on the offering players but not on the recipients. The latter are still completely free to choose any of their available actions or strategies in the actual strategic game, so that game remains non-cooperative in nature. This is important to bear in mind, especially in the case of multi-player negotiation games, where players may receive several competing alternative offers, and the analysis and prediction of their strategic behaviour become much more involved. Still, the examples and results mentioned here clearly indicate that the possibility of making such unilaterally binding incentive offers leads, in general, to much more efficient and mutually beneficial solutions, thus providing a game-theoretic platform for the emergence of cooperation in an inherently non-cooperative setting.

The analysis of multi-player preplay negotiations is too complicated to be treated properly in a single publication, so in this paper, I focus on two-player strategic-form games with preplay negotiations involving only unconditional and irrevocable offers. I show that the analysis, even in this simple framework, is already far from trivial. As explained further, this paper does not attempt to provide an equilibrium analysis of the proposed framework, but rather accomplish the following:

• To describe and illustrate the idea of preplay negotiations with unconditional offers and make some important observations about them.
• To present and discuss the Myopic Rationality Assumption (I will use this term for lack of a better one that reflects precisely the concept at play here) and the notions of efficient strategies and negotiations guided by that assumption.
• To develop and illustrate with examples an algorithmic procedure for computing the most efficient offers;
• To explore and discuss the possible outcomes of the preplay negotiations under the Myopic Rationality Assumption.

In summary, the main contributions of this work are the following:

(i)

It demonstrates that preplay negotiations with unconditional offers in strategic form games are based on a very natural idea yet quite complex to analyse and prescribe optimal players’ behaviour;

(ii)

It proposes a concrete algorithmic procedure for computing the “best offers” in the preplay negotiation phase (i.e., offers that optimise the immediate expected reward for the offering player);

(iii)

It shows that if any effective offers have been made, then the resulting transformed game contains a Nash equilibrium consisting of pure dominant strategies that generally yield better outcomes for both players than their expected payoffs in the initial game.

The structure of the paper is as follows. Section 2 provides the preliminaries and background on preplay offers and the general concept of preplay negotiation games with some motivating examples. Section 3 presents the formal framework of preplay negotiation games with unconditional offers. Then, Section 4 introduces the Myopic Rationality Assumption (MRA) and defines feasible offers and efficient negotiation strategies in preplay negotiation games under the MRA. In Section 5, I focus on the two-player case, for which I develop a method for computing players’ “best efficient offers” under the MRA assumption. I illustrate the method with several examples and establish some basic results. In Section 6, I offer a brief literature review of related works. I end with some discussion on directions for further research and brief concluding remarks in Section 7.

2. Preliminaries and Motivating Examples

Here, I only provide the necessary background on the standard game-theoretic terminology and notation used in the paper plus a brief summary of the framework of non-cooperative strategic-form games with preplay negotiations and a few motivating examples. For a further general background on game theory, see [3], and for more details on strategic-form games with preplay negotiations, see [2] as well as the recent [5] for both theoretical and experimental overviews of the current research on bargaining.

2.1. Strategic-Form Games

This paper will only consider two-player strategic-form games (hereafter abbreviated as SFGs). The players will typically be called A and B, while X and Y will be used to refer to either of them, and an SFG for them is defined as a tuple $\mathcal{G}=({\Sigma }_A,{\Sigma }_B,\mathbf{u})$, where ${\Sigma }_A$ (reps. ${\Sigma }_B$) is a family of “strategies” for player A (resp. for B) and $\mathbf{u}=({\mathbf{u}}_A,{\mathbf{u}}_B)$, where ${\mathbf{u}}_X:{\Sigma }_A\times {\Sigma }_B\to \mathbb{R}$, and for each $X\in \{A,B\}$, is a payoff function assigning to player X a utility for each strategy profile. The game is played by each player X simultaneously choosing a strategy from ${\Sigma }_X$. The resulting strategy profile $\sigma$ is the outcome of the play, and ${\mathbf{u}}_X(\sigma )$ is the associated payoff for X, where for each $X\in \{A,B\}$. An outcome $\sigma$ is (strictly) dominated by an outcome ${\sigma }^{\prime }$ if ${\mathbf{u}}_X(\sigma )\le {\mathbf{u}}_X({\sigma }^{\prime })$ for each $X\in \{A,B\}$ and ${\mathbf{u}}_X(\sigma )<{\mathbf{u}}_X({\sigma }^{\prime })$ for at least one X. An outcome is Pareto optimal if it is not dominated by any outcome, and it is strongly Pareto optimal if the payoff for each player is greater than that in any other outcome. The total value of an outcome $\sigma$ is the sum of the payoffs ${\mathbf{u}}_A(\sigma )+{\mathbf{u}}_B(\sigma )$. An outcome is maximal if it has the highest total value amongst all outcomes of the game. Clearly, every maximal outcome is Pareto optimal.

2.2. Preplay Offers and Induced Game Transformations

Consider a generic two-player strategic-form game with players A and B having respective sets of strategies ${\Sigma }_A=\{A_1,\dots ,A_i,\dots \}$ and ${\Sigma }_B=\{B_1,\dots ,B_j,\dots \}$, with the outcomes defined by a payoff matrix as in the table in Figure 1.

Let us now assume that before the play of that game, each of the players ($X\in \{A,B\}$) can make a unilaterally binding offer to the other player Y for payment (transfer) of an amount of utility $\delta \ge 0$ after the play of the game, conditional on Y playing the strategy s specified in the offer. (The reason to allow vacuous offers with $\delta =0$ is not only for technical convenience but also because such offers can be used by players as signalling to enable coordination in cases where there is more than one preferred equilibrium, yielding the same payoff for the other player. See more on this in Section 5).

I will use the following notation for such an offer:

$$X\stackrel{\delta /s}{⟶}Y$$

Such an offer does not create any obligation for the recipient Y, and therefore it does not transform the game into a cooperative one, for Y is still free to choose any of his strategies when the game is actually played. Thus, when making her offer, X does not know before the game is played whether Y will “accept” that offer and play the strategy s desired by X, or not. Consequently, the technical effect of an offer, say $A\stackrel{\delta /B_j}{⟶}B$, is merely a transformation of the payoff matrix by accordingly transferring the offered amount of utility $\delta$ from the payoffs of the offering player A to those of the recipient B in all outcomes where the desired strategy $B_j$ is played by the latter. This is indicated in Figure 2.

I will call such game transformations offer-induced transformations, or just OI-transformations. For a general mathematical study and characterisation of the OI- transformations of payoff matrices, see [6]. Here, I summarise some observations about the game-theoretic effects of OI-transformations, which will be useful later on:

• An OI-transformation does not change the sum of the payoffs of all players in any outcome; it only redistributes it. In particular, it preserves the maximal outcomes.
• An OI-transformation does not change the preferences of the offering player regarding her own strategies and therefore preserves (weak or strict) dominance between the strategies of that player.
• The players can collude to redistribute the payoffs in any chosen outcome in any possible way by exchanging suitable offers contingent on the strategies generating that outcome.
• Moreover, the players can collude to make any chosen outcome a dominant strategy equilibrium by exchanging sufficiently high offers to make the strategies generating that outcome strictly dominant.

Thus, preplay offers can transform the payoff matrix radically though not arbitrarily.

2.3. Two Motivating Examples

The examples in this subsection are adapted from [2].

2.3.1. Prisoner’s Dilemma 1

Consider a standard version of the Prisoner’ s Dilemma game (PD) between players $\mathit{Row}$ and $\mathit{Column}$, given in Figure 3. Here and further on, the payoffs in the matrices are given first for $\mathit{Row}$ and then for $\mathit{Column}$.

The only Nash equilibrium (NE) of the game is $(D,D)$, which is also the maximin solution and the only outcome surviving the elimination of strictly dominant strategies, yielding a payoff of $(1,1)$.

Now, suppose $\mathit{Row}$ makes an offer $\mathit{Row}\stackrel{2/C}{⟶}\mathit{Column}$ to pay to $\mathit{Column}$ two units of utility (hereafter utils) after the game if $\mathit{Column}$ plays C. That offer transforms the game by transferring two utils from the payoff of $\mathit{Row}$ to the payoff of $\mathit{Column}$ in every entry of the column where $\mathit{Column}$ plays C, as in Figure 4.

In the resulting game, $\mathit{Row}$ still has the preference to play D, which strictly dominates C for him, while the dominant strategy for $\mathit{Column}$ is now C, and thus the only Nash equilibrium (and the only maximin solution) is $(D,C)$ with a payoff $(4,2)$, strictly dominating the original payoff $(1,1)$. Thus, even though $\mathit{Row}$ will still defect, the offer he has made to $\mathit{Column}$ makes it strictly better for $\mathit{Column}$ to cooperate.

Furthermore, $\mathit{Column}$ can now realise that she would be even better off if $\mathit{Row}$ would cooperate too, but for that, an extra incentive for $\mathit{Row}$ is needed. That incentive can be created by an offer $\mathit{Column}\stackrel{2/C}{⟶}\mathit{Row}$, which further transforms the game as in Figure 5.

In this game, the only Nash equilibrium is $(C,C)$ with a payoff $(5,5)$, which is also Pareto optimal and, in fact, maximal. Note that this is the same payoff for $(C,C)$ as in the original PD game, but now both players have created incentives for their opponents to cooperate and have thus escaped from the trap of the original inefficient Nash equilibrium $(D,D)$.

2.3.2. Prisoner’s Dilemma 2

Consider now another version of the Prisoner’s Dilemma game in Figure 6. The only Nash equilibrium in this game (and the only maximin solution) is again $(D,D)$, yielding the Pareto dominated payoff of $(3,3)$.

Note that, unlike the previous example, none of the players here can make a “rational” first offer to improve the outcome. For this, in order to provide a sufficient incentive for $\mathit{Column}$ to play C, $\mathit{Row}$ would have to offer him more than three, which is not rational for $\mathit{Row}$ because it would decrease his expected payoff in the transformed game. Indeed, an offer $\mathit{Row}\stackrel{3+d/C}{⟶}\mathit{Column}$ for $d>0$ transforms the payoff matrix in Figure 6, where in both outcomes in column C, the amount $3+d$ is transferred from the payoff of $\mathit{Row}$ to the payoff of $\mathit{Column}$. The result is the payoff matrix in Figure 7, which now has a strictly dominant equilibrium $(D,C)$, yielding a payoff of only $2-d$ for $\mathit{Row}$.

Likewise, it is not rational for $\mathit{Column}$ to make a good enough offer to $\mathit{Row}$ for changing the equilibrium. Thus, the mutually preferable maximal outcome $(C,C)$ cannot be attained unless the player making the initial offer can be sure to receive a matching offer from the other player, which would finally transform the game as in the previous example. Such cooperation can be reached by allowing the possibility of making conditional offers, studied in [1,2], but this is not enabled in the framework on unconditional offers studied here. Thus, we see that while unconditional preplay offers provide strong bargaining power, they do not trivialise non-cooperative games by turning them into cooperative games. (As shown in [1,2], even the exchange of conditional offers cannot always achieve that).

3. Preplay Negotiations Games

In the preplay negotiation games defined further, each player’s objective is to maximise their (subjectively determined) value of the (transformed) SFG to be played. (Note that the notion of “value of a game” used here is different from the usual notion of a value of a zero-sum game. The potential danger of confusion here is negligible because preplay offers make no practical sense in zero-sum games). In order to make this concrete, we need to adopt a concept of “value” for a player of any given strategic-form game. Intuitively, that is the player’s estimate of the expected payoff after the game is played. To make the concept of “value of an SFG” more precise, we need to make some assumptions regarding the solution concept that the players adopt in their rational reasoning about the game and its possible OI-transformations.

3.1. Solution Concepts and Players’ Values of Strategic-Form Games

A central question of this study is the following: What should be regarded as a solution of a strategic-form game with preplay offers? The possible answers to that question crucially depend on various additional assumptions mentioned earlier, on the adopted solution concept, and on the concrete procedure of preplay negotiations formalised in the notion of the “preplay negotiations game”. These are introduced and discussed in more detail in [1,2] and are only outlined here.

3.1.1. Solution Concepts and Solutions to Strategic-Form Games

Let $\mathbf{G}$ be the set of all strategic-form games for the set of players under consideration. By the solution concept for $\mathbf{G}$, I mean a map $\mathfrak{S}$ that associates with each $\mathcal{G}\in \mathbf{G}$ a non-empty set $\mathfrak{S}(\mathcal{G})$ of outcomes of $\mathcal{G}$, called the $\mathfrak{S}$-solution of the game. Solution concepts reflect the rationality assumptions of the players in the strategic games. A $\mathfrak{S}$-solution of a game $\mathcal{G}$ basically tells what outcomes of the game the players could or should collectively select in an actual play of that game if they all adopt the solution concept $\mathfrak{S}$.

Without committing to any specific solution concept for now, I will only assume that the one adopted by the players satisfies the following necessary conditions for every outcome in any solution prescribed by that solution concept:

(i) It must survive iterated elimination of strictly dominated strategies (IESDS); in other words, it must reflect the assumption that players would never play strictly dominated strategies, and it is common knowledge amongst them that IESDS is used in their strategic reasoning;

(ii) It must yield at least the maximin value of the game for each player i, or at least ${max}_{{\sigma }_i\in {\Sigma }_i}{min}_{{\sigma }_{-i}\in {\Sigma }_{-i}}{u}_i({\sigma }_i,{\sigma }_{-i})$, where $-i$ is the (set of) non-i player(s);

(iii) If the game has just one pure strategy Nash equilibrium, then it is the only outcome in the solution. (This condition does not extend over mixed strategy Nash equilibria, as I do not consider mixed strategies here).

I call such solution concepts acceptable. Thus, the weakest acceptable solution concept returns all outcomes that survive IESDS and where each player receives at least their maximin value of the game. Games for which the solution concept $\mathfrak{S}$ returns a single outcome will be called $\mathfrak{S}$-solved. For instance, every game with a strictly dominant strategy profile or with a single pure strategy Nash equilibrium is $\mathfrak{S}$-solved for any acceptable solution concept $\mathfrak{S}$. The games for which $\mathfrak{S}$ returns only maximal outcomes will be called optimally $\mathfrak{S}$-solvable. If for every player all these maximal outcomes provide the same payoff, I call the game perfectly $\mathfrak{S}$-solvable. Games that are $\mathfrak{S}$-solved and perfectly $\mathfrak{S}$-solvable (i.e., $\mathfrak{S}$ returns just one outcome, which is maximal) will be called $\mathfrak{S}$-perfectly solved.

The ideal ultimate objective of a preplay negotiation would be to transform the starting strategic form game into a $\mathfrak{S}$-perfectly solved one. However, this is not always possible (e.g., for any symmetric coordination game). The next best objective would be at least a perfectly $\mathfrak{S}$-solvable one. I will discuss further in the paper whether such an objective is always reachable.

3.1.2. Players’ Values of a Game

Intuitively, a player’s value of an SFG should reflect that player’s expected or guaranteed payoff in that game, and naturally, this would depend not only on the game itself but also on the adopted solution concept. How that value is computed will have a limited effect on the general theory and can be left as a separate issue. Here, I adopt a conservative approach and assume that for every acceptable solution concept $\mathfrak{S}$, game $\mathcal{G}$, and player X, the value of $\mathcal{G}$ for X relative to the solution concept $\mathfrak{S}$ is the minimal payoff that X receives from an outcome in the $\mathfrak{S}$-solution of the game $\mathcal{G}$.

3.2. Preplay Negotiations Games: Basic Concepts

The setting for strategic-form games with preplay offers begins with a given input SFG $\mathcal{G}$ and consists of two phases:

• A preplay negotiation phase, where the players negotiate how to transform the game $\mathcal{G}$ by exchanging unconditional offers. This phase constitutes an extensive form game, which I call a preplay negotiation game (PNG).
• An actual play phase, where after having agreed on some GOI transformation X in the previous phase, the players play the resulting game $\mathcal{G}(X)$.

Intuitively, players engage in preplay negotiations with the purpose of reaching a best for them possible agreement on GOI transformation of the original game $\mathcal{G}$.

3.2.1. Additional Assumptions

As mentioned earlier, the actual structure and possible outcomes of the preplay negotiation games depend essentially on several important additional assumptions, including the following:

• Conditionality of offers: Offers may be conditional upon an expected (suggested or demanded) counteroffer by the player who receives the offer, or they may be unconditional.
• Revocability of offers: Offers that have been made may possibly be withdrawn later in the negotiations phase, or they may be assumed to be irrevocable.
• Value of time: Time, measured discretely as the number of explicitly defined rounds of the negotiations, may have value for some (or all) of the players (i.e., they may strictly prefer a reward in the present to the same reward in the future).
• The order of making offers: The order in which offers are made by the different players can be essential, especially in the case of irrevocable offers. That order is assumed here to be set by a separate, exogenous protocol which is an additional component of the preplay negotiations game. For instance, it can be strictly alternating or random. However, the possibility of passing, which I will adopt here, essentially reduces the importance of the order of making offers.

These options and their effects on the preplay negotiations have been discussed in some detail in [2]. Here, I will assume that all offers are unconditional and irrevocable, the time is not valuable for any of the players, and the offers are made in strict alternation. Furthermore, I will assume that each player would always be better off by eventually ending the preplay negotiation phase and then playing the resulting outcome game rather than negotiating forever.

3.2.2. Preplay Negotiations Games with Unconditional and Irrevocable Offers

Here, I will only give an informal definition of preplay negotiations games under the assumptions made above as a special kind of extensive-form bargaining game. For a more formal definition in the general case (for any finite number of players) and further details, see [2].

A preplay negotiation game (PNG) can be defined generically as a turn-based, possibly infinite extensive-form game involving the following types of possible moves, which are available to the player whose turn it is to act:

• Make an offer;
• Pass;
• Opt out (terminate the negotiations).

The PNG starts with an input SFG and either ends with a transformed output SFG or goes on forever. More precisely, a history in the PNG is a finite or infinite sequence h of admissible moves by the players who take their turns (according to a set protocol). Every finite history in a PNG is associated with the current SFG, being the result of the GOI transformation of the input SFG, and composed of the sequence of all offers that are made so far. The current SFG of the empty history is the input SFG. A play of the PNG is any finite history at the end of which all players have passed or opted out at their last move, or any infinite history. The outcome of a play h of the PNG with an input SFG $\mathcal{G}$ is the resulting output SFG $h(\mathcal{G})$ (i.e., the current SFG at the end), if the play is finite, or “disagreement” if it is infinite. In order to eventually define realistic solution concepts for preplay negotiations games, we need to endow every history in such games with a value for every player. Intuitively, the value of a history for a player is the value for that player of the current SFG associated with that history if it is finite; otherwise, I assume it to be $-\infty$, thus assuming that any agreement is better than ultimate disagreement. (This assumption is not unconditionally justifiable. In cases where the game matrix includes negative payoffs (punishments), players may still prefer to procrastinate the preplay phase forever rather than bite the bullet and play. However, in this study, I exclude such scenarios).

4. Preplay Negotiation Games with Myopic Rationality

In order to fully understand how rational players may act in preplay negotiations, one has to describe and understand the subgame perfect equilibria of preplay negotiations games. This is an apparently very complex problem, the solution of which crucially depends not only on the specific optional assumptions regarding the types of allowed moves and the value of time but, most importantly, on the players’ common rationality assumptions in the PNG as well. This problem will be studied in a subsequent work. Here, I only consider an important special case of preplay negotiation games with unconditional and irrevocable offers, where players have no reliable information and no reliable assumptions about each other’s long-term behaviour and are therefore driven by the strive for optimising each of their offers in terms of “immediate rewards”.

Hereafter, I restrict the study to two-player games, though much of what follows still applies to the general case of n-player games.

4.1. The Myopic Rationality Assumption (MRA)

More precisely, I hereafter adopt the following Myopic Rationality Assumption, hereafter abbreviated as MRA, essentially stating that the players assume that the preplay negotiation can be terminated unilaterally by the opponent at any time. That happens when the opponent stops making any further offers or simply opts out. Consequently, rational players in such negotiation games adopt myopic behaviour to make sure that every offer they make optimally improves their value of the transformed game, as it may turn out to be the final offer in the preplay negotiations. This assumption is often well-justified (e.g., when players have no a priori knowledge about each other’s reasoning), guiding considerations for computing their value of the game and patience (value of time). (I also argue that this is how most agents with bounded rationality would act in real-life scenarios).

It is important to note that this scenario is essentially different from the one analysed in [2], where it is assumed that the players have stronger bargaining power by being allowed to withdraw offers or to make conditional offers that would only be enforced if the recipients make respective subsequent counteroffers. That possibility enables the players to adopt a long-term rationality assumption, according to which a player can afford making a currently suboptimal offer in the play of a PNG (i.e., an offer transforming the currently accepted game into one with a possibly lesser value for that player). The expectation, justified by that rationality assumption, is that the opponent, with likewise reasoning, will not opt out before the negotiation has reached an optimal outcome but will continue it for the sake of reaching a mutually better outcome. Respectively, the analysis in [2] is based on consideration of the subgame perfect equilibria of PNGs with conditional offers or withdrawals of offers.

On the other hand, under the MRA, whenever the players are to make the next move (offer) in the PNG, they have to calculate a currently optimal offer only based on the current SFG (i.e., one not taking into account any possible further continuations of the preplay negotiation). Thus, an optimal strategy of a player in such a PNG would only prescribe moves that would guarantee that the resulting transformed SFG has no lesser value for the player making that move than the currently reached SFG. To put it simply, the MRA prescribes to the players to play “step-wise optimal” strategies in the PNG that result in maximizing their immediate rewards. Thus, here we have to analyse the optimality of single moves rather than long-term strategies. Consequently, adopting the MRA makes the analysis somewhat easier. However, as we will see further, it still remains quite non-trivial, because a player who makes an unconditional offer in fact makes a unilateral concession for the expected mutual gain and thereby can put himself in a disadvantaged position by transforming the payoff matrix to the other player’s sole benefit. Therefore, players are generally more interested in receiving rather than making unconditional offers, as demonstrated in Example 3, and this essentially affects their strategic behaviour in the preplay negotiations phase.

4.2. Efficient Negotiation Strategies under the MRA

To carry out the analysis and make justified statements about the solutions of PNGs with the MRA assumed, I first need to define the important notions of “feasibility of moves” and “efficiency of negotiation strategies”. In this context, I will use the term “efficient” not in its traditional game-theoretic sense (i.e., applied to outcomes) but in the way outcomes are reached.

4.2.1. Types of Unconditional Offers

One can distinguish three types of unconditional offers:

• Effective offers of the kind $A\stackrel{d/\sigma }{⟶}B$ for a (large enough) $d>0$, which are the main type of offers, being used to change the recipient’s preferences and to influence his choice of strategy in the transformed SFG.
• Vacuous offers of the kind $A\stackrel{0/\sigma }{⟶}B$ for payment of 0, which can be used instead of passing but also (more importantly) as a kind of signalling (i.e., an indication that A expects B to play $\sigma$, for instance, for the sake of breaking the symmetry in the case of strategic games with several symmetric and equally optimal equilibria).
• $ϵ$-offers of the kind $A\stackrel{ϵ/\sigma }{⟶}B$ for a small enough $ϵ>0$, which I call the rationality threshold. These offers can be used, similarly, for breaking the symmetry when B has more than one best for her moves which, however, lead to outcomes that yield different payoffs for A. Using such a move, A can make any of these outcomes strictly preferable for B and thus can turn a weak equilibrium into a strict one at minimal cost.

Note that in ideal negotiations guided by the MRA, no player needs to make two consecutive offers, between which the opponent has passed or made a vacuous offer. Indeed, no player would be better off by making competing offers, contingent on two or more different strategies of the opponent. In fact, such multiple offers would send confusing signals to the opponent. Furthermore, two or more offers by the same player that are contingent on the same strategy of the opponent can and should (given the MRA) be combined into one. Therefore, under our assumptions, we can restrict our attention to two-player PNGs that consist of a sequence of strictly alternating offers made in turn by the players until both of them pass or opt out.

4.2.2. Feasible Offers and Strategies

Following the discussion above, a player’s offer is called weakly feasible if it does not decrease that player’s value of the current game in the game transformed by that offer, while the offer is (strictly) feasible if it strictly increases that value.

I call a strategy of a player in a PNG feasible if it involves making only (at least weakly) feasible offers and eventually prescribes opting out from the negotiations game. I argue that, under the MRA, a player’s strategy in the preplay negotiation phase can only be optimal if it is feasible. (I have not formally defined the “optimal strategy in a PNG”, so this is not a formal claim to which I can give a proof). The intuition, as explained earlier, is that the MRA means that players assume that the negotiation may terminate after their offer, so it would be irrational and suboptimal to make an offer that would decrease their current value of the game and hence their expected payoff.

4.2.3. Minimal Offers and Rationality Thresholds

While feasibility is a necessary condition for an offer to be made in a rational play of a PNG under the MRA, it is not sufficient for such an offer to be part of an equilibrium strategy. Clearly, an optimal offer from one player to another should be a minimal feasible one in the sense of providing just a sufficient incentive for the recipient of the offer to play the desired action but not more than that. The question of what is a minimal offer that achieves such an objective crucially depends on the solution concept adopted by the recipient and used to determine his value of the game. By our working assumption, such an offer must at least increase the maximin value of the game for the recipient.

Thus, if player A wants to induce with a preplay offer another player B to play a given strategy ${\sigma }_B$, then for any acceptable solution concept, it would suffice for A to make any offer that would turn $\sigma$ into a strictly dominant strategy for B. However, such an offer may be prohibitively costly for A or, depending on the solution concept and the rationality assumptions for B, unnecessarily high. Furthermore, when a player B receives an offer $A\stackrel{\delta /{\sigma }_B}{⟶}B$, she should naturally expect that A (unless possibly bluffing) wants B to play ${\sigma }_B$ and therefore intends to play A’s best response to ${\sigma }_B$. Therefore, B can anticipate the outcome of the transformed game, and if B considers that outcome to be better than her current value, that should suffice for A’s offer to work.

There is one technical caveat here. Often, there is no minimal offer that guarantees achieving the objective of turning the desired strategy of the opponent into a strictly dominant one. For instance, if it suffices for A to pay B any amount that is greater than d for that purpose, then any offer of $d+\delta$, for $\delta >0$ should do, so there would be no optimal choice for an offer. Clearly, however, there is a practical minimum beyond which no player would consider it worth optimising any further, so the space of such offers can be naturally discretised. Therefore, I will assume that such a sufficiently small rationality threshold $ϵ>0$, the same for all players, is fixed throughout the game and is common knowledge amongst the players. The threshold $ϵ$ can be regarded as the cost of the recipient for considering and enforcing the offer. Therefore, in order to ensure that a player would consider the offer made to him and choose an action leading to an outcome yielding him a payoff of $d^{\prime }$ rather than another one yielding him a payoff of only d, the difference $d^{\prime }-d$ must be made at least $ϵ$. We can furthermore safely assume that $ϵ$ is smaller than any positive difference between two payoffs in the starting SFG. Thus, we adopt the notion of a minimal (non-vacuous) offer, namely one that guarantees an increase of the expected payoff of the recipient by exactly $ϵ$.

On the other hand, in order to not accumulate $ϵ$-deviations from the optimal solutions in the course of the negotiation game or in the play of the resulting SFG, and to keep our analysis simpler and neater, I will still assume, in accordance with the standard rationality assumptions, that a player who is to choose between several already available outcomes in the current SFG would always choose, ceteris paribus, to act in favour of the best one (or any one of several equally best ones) for her, even if the difference with the second best outcome is below the threshold $ϵ$ but still positive.

4.2.4. Efficient Negotiations and Optimal Plays

I will call an offer $A\stackrel{\delta /{\sigma }_B}{⟶}B$ in a game $\mathcal{G}$ efficient if it is a minimal feasible offer (i.e., the values of $\mathcal{G}$ for both A and B are strictly improved in the transformed game $\mathcal{G}(A\stackrel{\delta /{\sigma }_B}{⟶}B)$, and the increase in the value for B is at least $ϵ$).

We now reach the following formal definition of efficiency of negotiation strategies under our standing assumptions:

Definition 1.

• A strategy of a player in a PNG is an efficient negotiation strategy if the following are true:
  (1) All offers that it prescribes are efficient or vacuous;
  (2) It prescribes vacuous offers or passing only when no efficient offers are possible;
  (3) Eventually, it prescribes “opt out” or “pass” forever, so there is no infinite history in the PNG on which the strategy prescribes an offer infinitely often;
• Anefficient play of a PNG is one where all players follow efficient negotiation strategies.
• A play h of a PNG is optimal under the adopted solution concept $\mathfrak{S}$ if any outcome in the solution $\mathfrak{S}(h(\mathcal{G}))$ of the transformed game $h(\mathcal{G})$ is maximal (i.e., a redistribution of the payoffs of some maximal outcome of the input game $\mathcal{G}$).

A remark on the last condition for the efficiency of a negotiation strategy is in order. That condition implicitly assumes that the player would be better off by eventually playing the transformed SFG rather than procrastinating forever. Unless both players get the worst possible payoffs (say, $-\infty$) on infinite plays of a PNG, that need not be the case if all outcomes in the player’s solution of every transformed SFG obtained in the negotiation phase yield negative payoff (i.e., loss) for the player. If that is the case for both players, then they could simply agree not to play the SFG if given such an option, or else the negotiation phase would have to be terminated exogenously, such as when the time for negotiations runs out. If that is the case for only one of the players, however, then the other will sooner or later pass or opt out, thus preventing an infinite preplay negotiation.

5. Efficient Plays of Two-Player Preplay Negotiation Games

Here I will propose a method for determining the best (for the offerer) efficient offers that a player can make in a two-player PNG on a given current SFG. I will illustrate with examples some possible evolutions and outcomes of efficient plays of preplay negotiation games and will draw some conclusions.

For presenting and illustrating the method, hereafter I adopt the solution concept $\mathfrak{S}$, prescribing as a solution for any strategic-form game $\mathcal{G}$ the set of outcomes generated by all pure strategy Nash equilibria of the game, if any such equilibria exist; otherwise, it is the set of outcomes generated by the maximin strategies of the players. As we will see further, the latter case will only possibly apply to the input SFG, because after the first offer, every current SFG in the PNG will have a pure strategy Nash equilibrium. The method presented here is easily amenable to other acceptable solution concepts.

5.1. Computing the Best Efficient Offers of a Player

What is a rational player’s reasoning based on the MRA when considering making an unconditional and irrevocable offer to another player on a given SFG $\mathcal{G}$? Suppose that player A considers making such an offer to player B. (When B is to make the offer, the reasoning is completely symmetric). Then, for each strategy $B_j$ of B, player A may consider making an offer contingent on B playing $B_j$. To make sure that B will play $B_j$ in the resulting SFG, it suffices to make $B_j$ a strictly dominant strategy for B. The necessary payment for that, however, can be unreasonably high for A, because after that payment, A’s best response to $B_j$ may yield a worse payoff than the current (e.g., maximin) value for A of the original SFG. Therefore, a more subtle reasoning is needed, which is presented by the following procedure:

• For each strategy $B_j$ of B, player A looks at her best response to $B_j$. Suppose for now that it is unique (e.g., $A_{i_j}$). Then, this is what B should expect A to play if B knows that A expects B to play $B_j$. In this case, A computes the minimal payment needed to make $B_j$ not necessarily a strictly dominant strategy but a best response to $A_{i_j}$ (i.e., the minimal payment that would make the strategy profile ${\sigma }_{i_j,j}=(A_{i_j},B_j)$ a Nash equilibrium). That payment is

  $${\delta }_{i_j,j}^A=\underset{k}{max}(u_B(A_{i_j},B_k)-u_B({\sigma }_{i_j,j})).$$
  Clearly, ${\delta }_{i_j,j}^A\ge 0$. Suppose it is positive, or it is 0, but is reached for more than one value of k. Then, in order to break B’s indifference and make ${\sigma }_{i_j,j}$ a strict Nash equilibrium, A has to add to ${\delta }_{i_j,j}^A$ a threshold amount $ϵ$, thus eventually producing the minimal necessary payment ${\delta }_j^A={\delta }_{i_j,j}^A+ϵ$.
• If A’s best response to $B_j$ is not unique, then A must compute the minimal payment ${\delta }_j^A$ needed to make $B_j$ the best response of B to each of A’s best responses to $B_j$. Clearly, that is the maximum of all ${\delta }_{i_j,j}^A$ computed above, possibly plus $ϵ$.
• Once ${\delta }_j^A$ is computed, A computes her payoff in the transformed game ${\widehat{\mathcal{G}}}_{B_j}$ after an offer $A\stackrel{{\delta }_j^A/B_j}{⟶}B$ in the outcome ${\sigma }_{i_j,j}$, which is

  $$v^A({\widehat{\mathcal{G}}}_{B_j})=u_A({\sigma }_{i_j,j})-{\delta }_j^A.$$
• Finally, A maximises over j:

  $$v^A(\widehat{\mathcal{G}})=\underset{j}{max}{v}^A({\widehat{\mathcal{G}}}_{B_j}).$$
  Now, there are four cases to consider:

  (a)

  If ${\delta }_j^A>0$ and the maximum $v^A(\widehat{\mathcal{G}})$ is achieved for only one j, then the best efficient offer of A is determined to be

  $$A\stackrel{{\delta }_j^A/B_j}{⟶}B.$$

  (b)

  If ${\delta }_j^A>0$ and the maximum $v^A(\widehat{\mathcal{G}})$ is achieved for more than one j, then A can choose any of these and compute her best efficient offer as above. Better still, A can choose the j yielding the least payoff for B, thus stimulating B to make her a further offer.

  (c)

  If ${\delta }_j^A=0$, and $v^A(\widehat{\mathcal{G}})$ is reached for only one value of j, then there is no need for A to make any offer, because in this case, there is a unique dominant strategy Nash equilibrium in the game, and it is such that A cannot make any offer that would improve on her payoff yielded by that Nash equilibrium.

  (d)

  If ${\delta }_j^A=0$, and $v^A(\widehat{\mathcal{G}})$ is reached for more than one values of j, then there are several dominant strategy Nash equilibria in the game, and A cannot make any offer that would improve on her payoff yielded by either of them, so A must still make a vacuous offer $A\stackrel{0/B_j}{⟶}B$ in order to indicate to B for which Nash equilibrium she will play.

After completing the computation outlined above, it is up to player A to decide whether to make the respective offer, leading to the value $v^A(\widehat{\mathcal{G}})$ if that offer would improve her current value, or not otherwise. The available alternatives for A are to pass, thus possibly ending the negotiations, or to just make a vacuous offer when appropriate (e.g., for the sake of indicating to B on which of the several equivalent Nash equilibria to coordinate (as in the symmetric coordination game)).

The procedure outlined above, originally presented in [7], has been implemented by François Schwarzentruber and is available for online use (cf. [8]). By its construction, it implies the following claim:

Theorem 1.

Given any input SFG $\mathcal{G}$, let $A\stackrel{{\delta }_j^A/B_j}{⟶}B$ be a best efficient offer from A to B in $\mathcal{G}$, as computed by the procedure described above. Then, the following are true:

• The resulting transformed game has a pure strategy Nash equilibrium ${\sigma }_{i_j,j}=(A_{i_j},B_j)$.
• The value for player A of that transformed game is $v^A(\widehat{\mathcal{G}})$.
• $v^A(\widehat{\mathcal{G}})$ is the best value for player A of a transformed game induced by an efficient offer from A to B in $\mathcal{G}$.

Corollary 1.

Any non-dominated efficient negotiation strategy for player A in a given PNG prescribes only making the best efficient offers or vacuous offers, passing, or opting out.

Since, after every effective offer, the total value of the resulting equilibrium outcome increases, and there are finitely many such outcomes, then clearly after a finitely repeated exchange of the best efficient offers between the two players, the game will be transformed to one which both players consider optimal in terms of their expected payoffs amongst all those that can be obtained by using unconditional preplay offers. At that stage, the preplay negotiations end. As we will show further, the resulting game may or may not already be solved in the sense defined in Section 3, but if any effective offers have been made, the resulting game would contain a Nash equilibrium consisting of pure dominant strategies, which would yield better outcomes for both players than their values of the initial SFG.

5.2. Solving Strategic Games by the Exchange of Best Efficient Offers: Examples

Here, I present some examples illustrating the method. I adopt the following notation: $d^{+}:=d+ϵ$ and $d^{-}:=d-ϵ$.

5.2.1. The Power of Best Efficient Offers

Example 1

(Perfectly solving a game by an efficient and optimal play).

Consider the following SFG $\mathcal{G}$ between players R (Row) and C (Column):

$$\begin{array}{c}\begin{array}{cccc}& C1& C2& C3\end{array}\\ \begin{array}{c}R1\\ R2\end{array}\begin{array}{|ccc|}\hline 2,10& 10,4& 5,1\\ 6,0& 4,4& 6,3\\ \hline\end{array}\end{array}$$

This game has no pure strategy Nash equilibria (PSNE), and the only dominated strategy is $C3$. The only maximin solution is $(R2,C2)$ with payoffs $(4,4)$. Hence, the value of this game for each of the players R and C is 4.

Suppose player R is to make the first offer. Let us compute the best efficient offer that R can make to C:

– The best response of R to $C1$ is $R2$. Then, ${\delta }_{2,1}^R=4-0+ϵ=4^{+}$, and $v^R({\widehat{\mathcal{G}}}_{C1})=6-4^{+}=2^{-}$.

– The best response of R to $C2$ is $R1$. Then, ${\delta }_{1,2}^R=10-4+ϵ=6^{+}$, and $v^R({\widehat{\mathcal{G}}}_{C2})=10-6^{+}=4^{-}$.

– The best response of R to $C3$ is $R2$. Then, ${\delta }_{2,3}^R=4-3+ϵ=1^{+}$, and $v^R({\widehat{\mathcal{G}}}_{C3})=6-1^{+}=5^{-}$.

Thus, $v^R(\widehat{\mathcal{G}})=v^R({\widehat{\mathcal{G}}}_{C3})=5^{-}$, meaning that R’s best offer to C is $R\stackrel{1^{+}/C3}{⟶}C$.

The resulting transformed game is

$$\begin{array}{c}\begin{array}{cccc}& C1& C2& C3\end{array}\\ \begin{array}{c}R1\\ R2\end{array}\begin{array}{|ccc|}\hline 2,10& 10,4& 4^{-},2^{+}\\ 6,0& 4,4& 5^{-},4^{+}\\ \hline\end{array}\end{array}$$

It has one PSNE, $(R2,C3)$, created by R’s offer and yielding a Pareto optimal outcome with payoffs $(5^{-},4^{+})$, which are the values of the players for this game. They are strictly better than their previous values, and moreover, the offer by C also serves as signalling for R towards that equilibrium. However, the outcome $(R2,C3)$ is not yet maximal.

Now, let us compute the best offer from player C to R in the transformed game:

– The best response of C to $R1$ is $C1$ and ${\delta }_{1,1}^C=4^{+}$. Therefore, $v^C({\widehat{\mathcal{G}}}_{R1})=10-4^{+}=6^{-}$.

– The best response of C to $R2$ is $C3$ and ${\delta }_{3,2}^C=0$. Thus, $v^C({\widehat{\mathcal{G}}}_{R2})=5^{-}$.

Thus, the best efficient offer of C now is $C\stackrel{4^{+}/R1}{⟶}R$.

Moreover, $v^C(\widehat{\mathcal{G}})=6^{-}$, which is better than C’s current value of $4^{+}$, so C can improve his value of the game by making that offer. The resulting transformed game is

$$\begin{array}{c}\begin{array}{cccc}& C1& C2& C3\end{array}\\ \begin{array}{c}R1\\ R2\end{array}\begin{array}{|ccc|}\hline 6^{+},6^{-}& {14}^{+},0^{-}& 8,-2\\ 6,0& 4,4& 5^{-},4^{+}\\ \hline\end{array}\end{array}$$

It has one PSNE, $(R1,C1)$, which is Pareto optimal. The strategy $R1$ is strictly dominant for R, yielding payoffs $(6^{+},6^{-})$, which are the values of the players for this game. They are strictly better than the previous ones of $(5^{-},4^{+})$ but not yet maximal. Therefore, let us see whether R can improve the resulting game any further, given that the strategy $R1$ is already his best response to all strategies of C:

– For $C1$, ${\delta }_{1,1}^R=0$ and $v^R({\widehat{\mathcal{G}}}_{C1})=6^{-}$;

– For $C2$, ${\delta }_{1,2}^R=6^{-}-0^{-}+ϵ=6^{+}$ and $v^R({\widehat{\mathcal{G}}}_{C2})={14}^{+}-6^{+}=8$;

– For $C3$, ${\delta }_{1,3}^R=6^{-}-(-2)+ϵ=8$ and $v^R({\widehat{\mathcal{G}}}_{C3})=8-8=0$.

Hence, R’s best offer to C is now $R\stackrel{6^{+}/C2}{⟶}C$, and $v^R(\widehat{\mathcal{G}})=v^R({\widehat{\mathcal{G}}}_{C2})=8$, which is better than R’s current value of $6^{+}$, so R will make that offer. The resulting transformed game is

$$\begin{array}{c}\begin{array}{cccc}& C1& C2& C3\end{array}\\ \begin{array}{c}R1\\ R2\end{array}\begin{array}{|ccc|}\hline 6^{+},6^{-}& 8,6& 8,-2\\ 6,0& {-2}^{-},{10}^{+}& 5^{-},4^{+}\\ \hline\end{array}\end{array}$$

It has strictly dominant strategies NE $(R1,C2)$ yielding payoffs $(8,6)$, which are the values of the players for this game. They are strictly better than the previous ones $(6^{+},6^{-})$. In fact, this is the (only) maximal outcome in the game, and one can now check that none of the players can make any further improving offers. Thus, the game is now perfectly solved, and this is the outcome of the negotiation phase.

The reader can check that if C makes the first offer, the negotiation phase will end after each player makes only one offer and with a slightly different transformed game but with the same solution. As we will see further, such confluence is not always the case.

5.2.2. The Possible Weakness of Effective Offers

The example above demonstrates the potential power of efficient offers for solving strategic-form games. On the other hand, the version of Prisoner’s Dilemma 2 in Figure 6 demonstrates the possible weakness of unconditional offers by showing that in preplay negotiation games where no conditional offers and no withdrawals are allowed, the players may be unable to reach any Pareto optimal outcome by means of exchanging efficient preplay offers. Moreover, the value of the game that a player can achieve by making any effective offer in such a preplay negotiations game can be worse than the original value of the game for every player, as demonstrated by the following example:

Example 2

(No player benefits from making an effective offer).

Consider the following game $\mathcal{G}$ between players R (row) and C (column):

$$\begin{array}{c}\begin{array}{ccc}& C1& C2\end{array}\\ \begin{array}{c}R1\\ R2\\ R3\end{array}\begin{array}{|cc|}\hline 3,3& 2,2\\ 9,1& 0,8\\ 0,7& 8,1\\ \hline\end{array}\end{array}$$

The game has no PSNE, and the only maximin outcome is $(R1,C2)$ with payoffs $(2,2)$, which is not Pareto optimal. The players have the potential to negotiate a mutually better deal in any of the outcomes in rows 2 and 3. However, it turns out that none of them can make a first efficient offer that would improve her expected payoff. Indeed, computing their best offers according to the procedure outlined above produces the following:

– The best response of R to $C1$ is $R2$. Then, ${\delta }_1^R=8-1+ϵ=7^{+}$ and $v^R({\widehat{\mathcal{G}}}_{C1})=9-7^{+}=2^{-}$. Likewise, ${\delta }_2^R=6^{+}$ and $v^R({\widehat{\mathcal{G}}}_{C2})=8-6^{+}=2^{-}$.

– $v^C({\widehat{\mathcal{G}}}_{R1})=3-6^{+}=-3^{-}$, $v^C({\widehat{\mathcal{G}}}_{R2})=8-9^{+}=-1^{-}$, and $v^C({\widehat{\mathcal{G}}}_{R3})=7-8^{+}=-1^{-}$.

Thus, $v^R(\widehat{\mathcal{G}})=2^{-}$, and $v^C(\widehat{\mathcal{G}})=0^{-}$. Both values are less than the respective maximin values of 2. Therefore, no player is interested in making a first offer and, under the MRA, the negotiation phase ends at the start after each player passes.

Thus, we have the following observation:

Proposition 1.

Not every strategic form game can be solved optimally by an efficient play of the preplay negotiation game with unconditional and irrevocable offers.

5.2.3. The Disadvantage of Making the First Offer

Even when each of the players can start an effective negotiation ending with a solved game, the solution may essentially depend on who makes the first effective offer, as shown by the next example.

Example 3

(Making the first offer can be disadvantageous). Consider the following game between R and C:

$$\begin{array}{c}\begin{array}{ccc}& C1& C2\end{array}\\ \begin{array}{c}R1\\ R2\\ R3\end{array}\begin{array}{|cc|}\hline 1,8& 10,4\\ 4,10& 1,11\\ 4,0& 2,2\\ \hline\end{array}\end{array}$$

If the first offer is made by R, then the preplay negotiation game ends with

$$\begin{array}{c}\begin{array}{ccc}& C1& C2\end{array}\\ \begin{array}{c}R1\\ R2\\ R3\end{array}\begin{array}{|cc|}\hline 1,8& 6^{-},8^{+}\\ 4,10& {-3}^{-},{15}^{+}\\ 4,0& {-2}^{-},6^{+}\\ \hline\end{array}\end{array}$$

where the only Nash equilibrium outcome is $(R1,C2)$. (It is also the only acceptable outcome, surviving the iterated elimination of strictly dominated strategies). This yields payoffs $(6^{-},8^{+})$, which are the values of the game for the players.

Respectively, if the first offer is made by C, then the preplay negotiation game ends with

$$\begin{array}{c}\begin{array}{ccc}& C1& C2\end{array}\\ \begin{array}{c}R1\\ R2\\ R3\end{array}\begin{array}{|cc|}\hline 4^{+},5^{-}& 9,5\\ 4,10& {-3}^{-},{15}^{+}\\ 4,0& {-2}^{-},6^{+}\\ \hline\end{array}\end{array}$$

where the only acceptable outcome is once again $(R1,C2)$ but now yielding payoffs $(9,5)$. Note that in both cases, the disadvantaged player is the one making the first offer.

The example above also indicates that the myopic approach, where a player always makes the best effective offer he can, may not be his best strategy. Passing the turn to the other player—that is, making a vacuous offer—could be strategically more beneficial. On the other hand, if both players keep exchanging only vacuous offers or passing, then they will never improve their values of the starting game. Yet, one can check in the example above that any pair of strategies, such that the following are true, is a subgame-perfect equilibrium strategy in the preplay negotiation phase:

• One of the players takes the initiative by making the first effective move with his best first offer, thereafter always responds with his current best effective offers while possible, and then passes.
• Meanwhile, the other player remains passive (makes only vacuous offers) until the first effective offer is made, thereafter keeps responding with her best offers while possible, and then passes.

5.2.4. Fear the Danaans Bearing Gifts

It may seem surprising, but unconditional offers are not always beneficial for the recipients either. Consider the game below on the left, where $R2$ is a strictly dominant strategy for $Row$, and therefore the outcome of the game should be $(R2,C2)$ with payoffs (3,3):

$$\begin{array}{cc}\begin{array}{c}\begin{array}{ccc}& C1& C2\end{array}\\ \begin{array}{c}R1\\ R2\end{array}\begin{array}{|cc|}\hline 1,5& 2,2\\ 2,0& 3,3\\ \hline\end{array}\end{array}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}& \begin{array}{c}\begin{array}{ccc}& C1& C2\end{array}\\ \begin{array}{c}R1\\ R2\end{array}\begin{array}{|cc|}\hline 2^{+},4^{-}& 3^{+},1^{-}\\ 2,0& 3,3\\ \hline\end{array}\end{array}\end{array}$$

However, an offer $C\stackrel{1^{+}/R1}{⟶}R$ (C’s best offer) will transform the game into the one on the right, where now $R1$ is strictly dominant for $Row$, leading to the outcome $(R1,C1)$ with payoffs $(2^{+},4^{-})$, where $Column$ is gaining while $Row$ is losing out, even though his payoffs have only improved. Furthermore, $Row$ has no feasible counteroffer to reverse the loss, and the negotiations end now. (The loss of $Row$ can easily be made much more dramatic, of course). A case can be made here about Trojan horse effects.

6. Literature Review of Related Works

Here, I include a brief review of the literature most relevant to the present work. Excluding my previous publications [1,2,7] on the topic, the other references mentioned here are related to the present work only by means of the general topics of bargaining and negotiations, but not in terms of the concrete framework and results presented here.

First, I will present some classic general references. The formal theory of bargaining goes back to Nash [9] and Harsanyi [10]. Since then, there have been extensive studies of negotiations and bargaining in cooperative and non-cooperative games (see, for example, the surveys in [11]). The preplay negotiation games studied here are based on bargaining games (see [3,4,12,13,14]).

Now for the immediate precursors of the present work. In [1], the extension of normal-form games with a preplay negotiations phase is introduced, where players can exchange preplay offers that are conditional on suggested matching offers of the same kind made in return by the recipient. The technical report in [7] is an early version of the present work, where inter alia, the procedure for computing the best efficient offers of a player (presented in Section 5.1) was first outlined. The follow-up paper [2] studied and analysed the solution concepts for two-player normal-form games with such a preplay negotiation phase under several assumptions for the bargaining power of the players, as well as the value of time for the players in such negotiations, and obtained results describing the possible solutions that can be achieved in such a negotiation process in the resulting bargaining games. The latter paper also contains a detailed account on some more closely related works and comparisons with them, including [15,16,17]. Here, I will supplement that account with brief comments on some additional relevant references, focusing mainly on bargaining related to strategic-form games.

In [18], a multi-stage bargaining procedure within a coalition of players in an n-person strategic game is considered, allowing the players to reach binding agreements on how to correlate their actions in the strategic game. Essential differences from the present approach in that proposed model include the possibilities for rejection of a proposal and for making threats. In addition, that bargaining procedure induces no transformations in the game payoff matrix.

In [19], a bargaining supergame over the strategies to play in a non-cooperative game is proposed, where the agreement reached by the players at the end of the bargaining process is the strategy profile that they will play in the original non-cooperative game. The parties in that bargaining process propose their own intended actions in response to what the other party has already declared or proposed. When the players confirm their proposals, the bargaining process ends, but the players only commit to play the agreed strategy profile if it is profitable for each of them, compared with the initially assumed and commonly known equilibrium outcome. The authors show that in some well-known two-player non-cooperative games such as the Prisoner’s Dilemma, the Hawk–Dove Game, and others, the proposed bargaining process gives rise to Pareto-efficient agreements that may be different from the Nash equilibrium of the original games. In a companion paper [20], the authors experimentally tested this bargaining mechanism in a Prisoner’s Dilemma and showed that the supergame equilibrium predictions were essentially verified. While close in purpose, that bargaining process is essentially different in spirit and in technical effect from the present proposal. In particular, the bargaining is intended to end with signing a contract on the strategy profile to be played in the original game. No transformations of the game payoff matrix are induced in that work, and there are simple examples of 2 × 2 games (e.g., for the Entry Game) where the preplay negotiations game transforms the game to one with better payoffs than what the bargaining process with confirmed proposals produces. In [21], this bargaining mechanism is extended to games with more than two strategies per player (e.g., oligopolies) and experimentally verifies the theoretical predictions, showing that, in more strategically complex games as well, players achieve through bargaining with confirmed proposals better payoffs than those they would obtain in the original non-cooperative game.

The present work also relates to other recent works on theoretical and behavioural models of bargaining, such as the recent volume [5] and, in particular, [22,23].

The recent related work [24] studied extensive-form games with interplay offers for incentive payments and showed how these can resolve or at least alleviate the problem of outcome inefficiency arising in extensive games.

Lastly, I also note that the dynamics of myopic best responses have been studied in the context of network formation (e.g., in [25]), which could provide some meaningful relationship with the kind of negotiation games with myopic players studied here.

7. Concluding Remarks and Further Agenda

7.1. A Brief Outlook on n-Player Games with Preplay Negotiations

A natural extension of the current work is to consider n-player strategic-form games with preplay negotiations for $n>2$. The analysis of the general n-player case is much more complicated than the two-player case. To begin with, the benefit for player A from player B’s playing a strategy induced by an offer from A to B crucially depends on the strategies that the remaining players choose to play, so an offer from one player to another does not have the clear effect that it has in the two-player case. Thus, a player may wish to make a collective offer to several (possibly all) other players in order to try to orchestrate their plays in the best way possible for her. Furthermore, a player may be able to benefit in different ways by making offers for side payments to different players or groups of players, and the accumulated benefit from these different offers may or may not be worth the total price paid for it. Lastly, when all players make their offers pursuing their individual interests only, the total effect may be completely unpredictable or even detrimental for all players. It is therefore natural that groups of players get to collaborate in coordinating their offers. Thus, a coalitional behaviour naturally emerges here, and the preplay negotiation phase incorporates playing a coalitional game to determine the partitioning of all players into coalitions that will coordinate their offers in the negotiation phase while keeping in mind that the transformed strategic-form game played after the preplay negotiation phase remains a non-cooperative game where every player eventually plays for themselves. That analysis is left to future work.

7.2. Summary of the Main Points and Some Open Questions

In this work, I studied the extension of two-player non-cooperative games with a preplay negotiations phase where the players can exchange unilaterally binding and irrevocable offers for payments of incentives to their opponents, which are only conditional on the opponent playing the strategy indicated in the offer. Such offers lead to simple transformations of the payoff matrix of the original strategic-form game but preserve its non-cooperative nature.

In order for the players to have a rational decision-making behaviour in the preplay negotiation phase, they must have their way of assessing their expected payoffs in the SFG, which is currently on the negotiation table. This is formalised by the notion of player’s value of an SFG, which each player determines subjectively, depending inter alia on the players’ mutual rationality assumptions and the adopted solution concept for strategic-form games. Here, I only make minimal and commonly acceptable assumptions, based on which players determine their value of an SFG. The analysis of the dependence of the preplay negotiations phase on the precise mechanisms for computing players’ values of the game is one of the most challenging directions for future work.

Furthermore, I have assumed and based my analysis of the preplay negotiation phase on the “Myopic Rationality Assumption”, implying that players always aim to optimise their next moves in the PNG, assuming that the negotiation phase may end immediately after it. Note that this assumption is not in conflict with the earlier assumptions made about the players’ solution concepts and rational reasoning when playing one-shot strategic games, because the latter and the former apply to essentially different kinds of games. One player may deem another to be quite predictable in taking once-off decisions and yet rather unpredictable in long-term negotiations.

Here, I have demonstrated that on the one hand, by exchanging preplay offers, players can possibly achieve mutually better or even optimal outcomes in the resulting transformed strategic form games, but on the other hand, their bargaining powers to achieve their best possible outcomes in such games can be substantially affected or even completely blocked by the potential disadvantage of making the first effective offer in such games and thus unilaterally exposing themselves. A natural question arises here: Under what conditions for the initial SFG does the preplay negotiation phase produce an optimal play and therefore lead to an optimally solvable game? This question seems quite challenging, and my conjecture is that there is no simple answer by means of a natural and explicit characterisation in terms of the payoff matrix of the initial SFG.

From the examples and observations in Section 5, it transpires that the strategy profile based on both players always making their currently best offers need not always be a Nash equilibrium in the PNG. Therefore, a full equilibrium analysis of PNGs with unconditional offers should go beyond the MRA. Such analysis could also employ forward induction reasoning, where past moves can be used to justify rational behaviour in the future (see [3]), which has yet to be explored. The effect of valuable time in preplay negotiations with unconditional offers remains unexplored, too.

The problem of inefficiency is not limited to strategic games; it also arises in extensive-form games, where players take actions observed by the others in turns, but are still assumed not be influenced or constrained in any other way by their opponents, which can lead to very poor outcomes, such as in the Centipede game. This problem is addressed in another recent and currently still ongoing piece of research on extensive-form games with interplay offers for incentive payments, reported in [24].

The present work also aims to indirectly provide a better understanding of some qualitative aspects of the observed bargaining outcomes in theory-driven economic experiments (fairness, focal points, etc.), as studied in [22,23] (see also the recent volume [5]).

Lastly, one clear limitation of the present work is that it is mostly theoretical work so far, and it would be very interesting to perform some supplementary empirical work in testing the proposed framework for preplay negotiations to confirm and extend the findings presented here. I leave that as a future work.