Price and Choose

Federico Echenique, Matías Núñez

► To cite this version:

Federico Echenique, Matías Núñez. Price and Choose. American Economic Journal: Microeconomics, 2025, 17 (2), pp.1-27. 10.1257/mic.20230095. hal-05511714

HAL Id: hal-05511714

https://hal.science/hal-05511714v1

Submitted on 15 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
PRICE & CHOOSE<fnref n="1" />

Federico Echenique<fnref n="2" />

Matías Núñez<fnref n="3" />

May 2024

<footnote n="1">¹We thank Yaron Azrieli, Danilo Coelho, Haluk Ergin, Yukio Koriyama, Jean-François Laslier, Olivier Tercieux, Hal Varian, Rodrigo Velez, Dimitrios Xefteris as well as seminar and conference participants in Caltech, Oxford and USC for their useful remarks and comments. We also thank the editor and two anonymous referees for suggestions on an initial draft that significantly improved the paper. The authors thank the France-Berkeley fund for their support. Matías Núñez is supported by a grant of the French National Research Agency (ANR), "Investissements d'Avenir" (LabEx Ecodec/ANR-11-LABX-0047).</footnote>

<footnote n="2">²fede@econ.berkeley.edu. UC Berkeley.</footnote>

<footnote n="3">³matias.nunez@polytechnique.edu. CREST, CNRS, Ecole Polytechnique, ENSAE.</footnote>
Abstract

We describe a sequential mechanism that fully implements the set of efficient out-
comes in environments with quasi-linear utilities. The mechanism asks agents to
take turns in defining prices for each outcome, with a final player choosing an out-
come for all: Price & Choose. The choice triggers a sequence of payments, from each
agent to the preceding agent. We present several extensions. First, payoff inequali-
ties may be reduced by endogenizing the order of play. Second, our results extend to
a model without quasi-linear utility, to a setting with an outside option, robustness
to max-min behavior and caps on prices.

JEL Codes: D71, D72.

**Keywords:** Efficiency, Subgame-perfect implementation, Mechanism, Prices.
# 1 Introduction

Ted and Joanna Kramer are getting a divorce. It gets messy. Not only do they need to divide their assets, but they must decide on a complex arrangement for custody and visitation rights of their son Billy. Many possible outcomes are on the table, and the Kramers agree to use an outside arbitrator to find a solution. The arbitrator, Judge Atkins, does not know the Kramers' preferences over the different possible solutions, but wants to find a good compromise despite his ignorance.

Our paper proposes a simple solution for Judge Atkins and the Kramers. The solution is optimal, in the sense of producing an efficient outcome in any equilibrium of the ensuing game of Kramer vs. Kramer, and relies on two key aspects of the problem: First, that Joanna and Ted know each other very well. Their preferences are common knowledge between them. Judge Atkins does not know the Kramers' preferences, but can leverage their shared knowledge. Second, Ted has a high-paying job as an advertising executive; so they have money available to facilitate an agreement.

Our solution is a simple dynamic mechanism that we call *Price and Choose* (P&C in the sequel). It works as follows:

1. The first mover sets up a zero-sum price vector that specifies a price for each of the different options.

2. The second mover chooses one of the options as the outcome, and pays the first mover the specified price.

We prove that any equilibrium outcome of P&C is Pareto efficient.<fnref n="1" /> The intuition behind our result is straightforward: The first mover's best choice is to make the second mover indifferent among all options; otherwise she is not playing optimally, as she can improve by slightly altering the price vector without modifying the choice of the second mover. This indifference implies that the second mover obtains her

<footnote n="1">¹There is a relation between P&C and the classical take-it-or-leave-it mechanism (or TOL), where a monetary transfer and an alternative is proposed by one agent and his opponent either accepts it or opts out. The TOL mechanism requires an outside option, which may prove a challenge for applications like the Kramers' in the introduction. As will be shown, P&C extends beyond the two-player, quasi-linear, model with an outside option required by TOL.</footnote>
average utility across the options in equilibrium. The second part of our argument
shows that the second mover chooses the best option(s) for the first mover. A differ-
ent choice could not emerge in equilibrium, as the first mover would “punish” her by
slightly modifying prices. This ends our argument since the option that maximizes
the payoff of the first mover, including transfers, is necessarily one that maximizes
the sum of the utilities: an efficient option.

Our paper contributes to the general theory of implementation, and to the more
practical literature on arbitration. We proceed to discuss each of these connections
in more detail.

Arbitration is a private dispute resolution method that does not involve courts.
While the model in our paper is quite general, the problem faced by arbitrators,
such as Judge Atkins, is a good application of several aspects of the model we de-
velop.<fnref n="2" /> Our method allows the (two) involved parties to choose the arbitrator who
will resolve the dispute.<fnref n="3" /> These institutions may specify a structured selection pro-
cedure to help the parties exercise their right of choice, such as the American Associ-
ation of Arbitrators (for instance, using vetoes, points, etc.). Two recent papers have
proposed methods to improve the procedures used by practitioners. The first one,
de Clippel et al. (2014), proposes a “shortlisting” mechanism. Shortlisting works in
only two stages, and the paper tests its validity in the lab. The second paper, Barberà
and Coelho (2022), considers procedures with more steps, but achieving less in-
equality among players. A key common ingredient in the problems studied in these
two papers is that they do not allow for monetary transfers between the players.

The lack of transfers is a realistic feature of some problems, but not of others. For
problems like the Kramers', it makes sense to assume that money is available, and
that it may be used to facilitate an agreement. Economic theory has shown that in-
troducing transfers (or prices) can serve as a powerful coordination tool and lead to
welfare gains. Our proposal relies on transfers, but can accommodate rather general

<footnote n="2">²Arbitration is not the only application of our work; note that our results extend to a setting with an arbitrary number of players so that agreements among countries or firms is also a good illustration of the current results.</footnote>

<footnote n="3">³As argued by Barberà and Coelho (2022), practically all cross-border commercial disputes are resolved by arbitration.</footnote>
preferences over money. In the paper, we first consider a setting where preferences
are quasilinear, and two players need to reach an agreement. Our goal is to design
mechanisms that implement the utilitarian goal (that is, players end up maximiz-
ing the sum of the individual utilities). With quasilinear preferences, utilitarianism
captures economic efficiency exactly. Then we generalize the result to a setting with
separable, but non-quasilinear, preferences over transfers. In consequence, our re-
sults allow for example, for general attitudes towards risky monetary lotteries.

Next, we turn to a discussion of implementation. Implementation theory studies
procedures for collective decision-making in the presence of selfish agents who may
disagree on their preferences over outcomes. So-called full implementation looks
for procedures that induce a desirable outcome, regardless of equilibrium selection.
It is often difficult to achieve when there are only two agents, as in the example
with Joanna and Ted. Our paper considers full (subgame perfect) implementation in
a general social choice problem with monetary transfers. The P&C mechanism we
propose has the benefit of being natural and bounded, in contrast with some well-
known proposals in the literature on implementation that rely on integer games and
unbounded message spaces to rule out equilibria (see Jackson (1992) for a critical
review). Implementation is often challenging when there are only two agents, but
our baseline analysis of the P&C applies precisely to the model with two agents.
In fact, the extension to *n* agents works by recursively applying our result for two
agents.

The literature on implementation with transfers is not new. The classic demand-
revealing mechanisms (see Clarke (1971) and Groves (1976)) achieve implemen-
tation in dominant strategies, even though they fail to be budget-balanced. These
mechanisms require utility to be quasi-linear in transfers. Our mechanism, in con-
trast, achieves full implementation in subgame-perfect equilibrium; but it is budget
balanced, and does not require quasilinear utility. Groves and Ledyard (1977) de-
scribe a mechanism that yields efficient Nash equilibria for the public-goods prob-
lem, see Groves (1979) for an excellent summary. The more recent literature has
shifted its attention to simple mechanisms: Varian (1994) designs compensation
mechanisms that achieve efficiency in the presence of externalities. Such mecha-
nisms are not balanced off-equilibrium, whereas the P&C mechanism is balanced by definition.<fnref n="4" /> Similarly, Jackson and Moulin (1992) describe simple mechanisms that implement efficient allocations in undominated Nash equilibria; yet, the implementation result requires indivisible public goods and quasi-linear utilities. As we have mentioned above, our results extend beyond this setting.

The main result is stated in a stylized setting, but our arguments turn out to generalize in various ways. Specifically, we show that the P&C mechanism can be adapted, and efficiency still implemented, in the following variations of our basic model:

• $n$ players. Moving in order, all players but the last one, choose a price vector that the next player faces. Prices must add to zero across outcomes (and transfers are balanced, adding to zero across players, by design). The last player chooses an outcome, say $x$. Then each player pays their predecessor the price that they demanded for $x$. Here the first mover receives a transfer but does not make any, the last mover makes a transfer but does not receive any, whereas each of the other players receives and makes transfers. Our two-player result can be applied recursively to show that the mechanism implements the efficient options. (Section 5.)

• Endogenous order of play. We tackle the implied first-mover advantage in P&C by having players bid for the role of moving first. (Section 6). There is an alternative approach to dealing with the first-mover advantage by constraining prices to add up to a non-zero constant. This is briefly discussed after our basic result is stated.

• Non-quasi linear preferences. We consider a model in which agents have general additively separable preferences over money and outcomes, and show that the main result of the paper continues to hold. (Section 7.1.)

<footnote n="4">⁴The compensation mechanisms in Varian (1994) rely on fines to ensure that both players accurately report each other’s “type,” which pushes transfers to be balanced in equilibrium; with three players and more, compensation mechanisms rely on classical implementation ideas to make each player’s payment do not depend on his own report. The P&C mechanism does not depend on this logic since it gives each player either the possibility of setting a price vector (except the last one) which balances the transfers.</footnote>
* Outside option. We consider an extension of P&C where players can opt out and select an outside option. We show that the main message of the paper continues to hold. (Section 7.2.)

* Robust implementation. We relax the assumption that players play an exact subgame-perfect Nash equilibrium. Instead, the agents are $\epsilon$-maximizing, and one player makes a pessimistic worst-case assumption over the possible $\epsilon$-optimizing choices of the other player. (Section 7.3.)

* Price caps. We discuss an extension of P&C where prices cannot be above a certain boundary, and show that the resulting mechanism also achieves full implementation of efficient alternatives. (Section 7.4.)

The rest of the paper is organized as follows. Section 2 reviews the literature. After laying down the model in Section 3, Section 4 presents the P&C mechanism for two players and the implementation argument. Sections 5 extends the model to an arbitrary number of players and Section 6 discusses how to tackle the first-mover advantage. Section 7.1 deals with non quasi-linear utilities; Section 7.2 considers the setting with an outside option, Section 7.3 presents the robustness of the mechanism with respect to adversarial behavior, and finally, Section 7.4 adapts P&C to a setting where prices are capped.

## 2 Review of the literature

Classical results in implementation say that, with two players, and in the absence of transfers, the only Pareto efficient rule that is implementable is dictatorship (see Maskin (1999) and Hurwicz and Schmeidler (1978)). While more permissible results arise when domains are restricted (Moore and Repullo (1990) and Dutta and Sen (1991)), or when mechanisms are not deterministic (Laslier et al. (2021)), a commonly-held view is that it is hard to design mechanisms with desirable properties in two-player settings. This has led the literature to consider the short mechanisms (short in the sense of few steps) proposed by de Clippel et al. (2014) and Barberà and Coelho (2022).
Our P&C mechanism deviates from these papers by working in an environment
with transfers, and by being dynamic in nature—one player sets up a price and the
other player chooses an option. The resulting solution concept is subgame-perfect
Nash equilibrium. One strand of the literature is concerned with the design of mech-
anisms with transfers. Beyond the papers previously cited, Hurwicz (1977), Dutta et
al. (1995), Sjöström (1996) and Saijo et al. (1996) study Nash implementation when
players announce prices and quantities. Among other findings, they prove that the
no-envy and Pareto correspondence are implementable. Moore and Repullo (1988)
prove that in the quasi-linear setting, any social choice rule is implementable with
two players. Yet, this result has been subject to several criticisms (see Aghion et al.
(2012)); and Moore and Repullo (1988) themselves write that their mechanisms “are
far from simple; players move simultaneously at each stage and their strategy sets
are unconvincingly rich.” Our P&C mechanism is arguably very simple, and uses a
natural economic framework. It also continues to work, even when we deviate from
the quasi-linear setting (Section 7.1).<fnref n="5" />

A literature in social choice theory (see Green (1993), Chambers (2005), and Chambers and Green (2005)) considers similar environments to ours, and studies efficient solution axiomatically. This work is, however, not concerned with implementation.

In dynamic environments with transfers, the P&C mechanism is also related to
Gary Becker’s “Rotten Kid theorem;” see Bergstrom (1989) for a formal analysis.
Bergstrom shows how to achieve efficiency in the Rotten Kid two-stage game, where
a benevolent planner makes transfers to several selfish players. His main result in-
volves quasi-linear preferences, but also discusses extensions that do not involve
these preferences. To cite the most relevant of them, Chen et al. (2023) considers
two-stage stochastic mechanisms that achieve full implementation under initial ra-
tionalizability in complete information environments. Chen et al. (2022) consider
implementation allowing for lotteries and monetary transfers in the mechanism and

<footnote n="5">⁵Our model with transfers, but non-quasi-linear preferences, is related to the recent literature on matching problems with imperfectly transferable utility such as Legros and Newman (2007), Chiapori and Salanié (2016) and Galichon et al. (2019).</footnote>
characterize the implementable rules. This is, of course, different from P&C which
is not a random mechanism.

Given our motivation, we should mention the literature on dissolving partner-
ships: for example Crampton et al. (1987). The literature is usually focused on mech-
anism design, not full implementation, and considers more restrictive environments
than we have studied here. Crawford and Heller (1979) and McAfee (1992) consider
variations of the “cut and choose” mechanisms, which were an inspiration of sorts
for our mechanism. The name “price and choose” is meant to highlight this con-
nection. Of course, cut and choose (or divide and choose) make sense for alloca-
tion problems, not for the general social choice environments we have studied here.
Among the literature on cake-cutting, the work of Nicolò and Velez (2017) is rele-
vant; they consider sequential Divide-and-compromise rules under monetary trans-
fers, which share some common ideas with P&C, but are designed for situations
where a collectively owned indivisible good is to be divided between two agents.
Furthermore, Brown and Velez (2016) study these procedures experimentally, and
find evidence that second movers tend to be adversarial, an assumption related to
our extension in section 7.3.

Finally, we should also mention the literature that crafts mechanisms implement-
ing efficient options, such as Perez-Castrillo and Wettstein (2002), Ehlers (2009) and
Eguia and Xefteris (2021). The common feature of the mechanisms designed by these
papers is that they are simultaneous, and rely on lotteries as tie-breaking devices.
Our approach differs from theirs in that we design a deterministic dynamic (with
sequential choices) mechanism. We think of this distinction as an advantage. On the
one hand, de Clippel et al. (2014) and Camerer et al. (2016) have shown that sub-
game perfect equilibrium is a good predictor in the lab for a particular mechanism,
namely shortlisting. The shortlisting mechanism is closely related to P&C, since the
first-mover proposes a list of alternatives, and her opponent selects an alternative
from the proposed list. On the other hand, Nash equilibrium often performs poorly
in experimental designs with simultaneous interactions and lotteries.
# 3 The model

**Utilities.** We consider a finite set $N$ of players, with generic element $i$, who bargain over a finite set of options denoted by $A = \{a_1, a_2, \dots, a_k\}$. Players have quasi-linear utility functions, defined over the options in $A$ and money. So player $i$ has a utility function $u_i: A \to \mathbb{R}$, and enjoys a utility of $u_i(a) + t_i$ if the outcome is $a \in A$ and they receive a monetary transfer $t_i$.<fnref n="6" /> For each player $i$, we write $\text{Avg}_i$ to denote $\frac{1}{k} \sum_{j=1}^k u_i(a_j)$, the average utility over $A$ for player $i$.

Utilitarian welfare from an option $a$ is $\sum_{i \in N} u_i(a)$, and $\text{MAX}(u) = \max\{\sum_{i \in N} u_i(a) : a \in A\}$ denotes the maximum utilitarian welfare.

**Outcomes.** For each $i, t^i$ denotes the monetary transfer that player $i$ obtains and $t = (t^1, \dots, t^n) \in \mathbb{R}^n$ is a vector of transfers. An *allocation*, or *outcome*, $(a, t^1, \dots, t^n)$ is a decision (that is, an option in $A$) coupled with a vector of transfers.

**Welfare.** An allocation $(a, t^1, \dots, t^n) \in A \times \mathbb{R}^n$ is *Pareto optimal* if there is no other allocation $(\tilde{a}, \tilde{t}^1, \dots, \tilde{t}^n) \in A \times \mathbb{R}^n$ with $1) u_i(a) + t_i \le u_i(\tilde{a}) + \tilde{t}_i$ for all $i, 2) u_i(a) + t_i < u_i(\tilde{a}) + \tilde{t}_i$ for all least one $i$, and $3) \sum_{i=1}^n \tilde{t}_i \le \sum_{i=1}^n t_i$. An outcome $a \in A$ is *efficient* if $\text{MAX}(u) = \sum_{i=1}^n u_i(a)$, so it achieves maximum utilitarian welfare. It is well known that an allocation $(a, t_1, \dots, t_n) \in A \times \mathbb{R}^n$ is Pareto optimal if and only if $a$ is efficient.

**Subgame perfect implementation.** We provide an informal definition of subgame-perfect implementation because the paper is devoted to a particular mechanism. A general definition is rather cumbersome and would be a distraction from the main point of the paper.

A mechanism specifies a game-form: this means that, when the mechanism is coupled with utility functions over outcomes for each of the players, it defines an extensive-form game. For a mechanism $\theta$, let $\text{SPNE}^\theta(u)$ be the set of subgame perfect equilibria when the utility profile is $u$. A mechanism *subgame perfect* implements the set of efficient options if for any $u$, any member of $\text{SPNE}^\theta(u)$ selects an efficient option and any efficient option is selected by some member of $\text{SPNE}^\theta(u)$.

<footnote n="6">⁶The assumption of quasi-linearity is relaxed in Section 7.1</footnote>
# 4 Price & Choose mechanism

We proceed with our baseline result by first describing the Price & Choose mechanism for two players, and showing that it achieves full implementation in subgame-perfect Nash equilibrium of the efficient outcomes.

Consider an instance of our model with two players. The Price & Choose mechanism requires player 1 to choose a price vector; that is, a price for each option. Prices may be positive or negative, and “budget balanced,” in the sense that they must add up to zero. Player 2 then chooses an alternative in $A$, and pays player 1 the price that she demanded for that alternative.

The formal definition of the Price & Choose mechanism (P&C) follows. Let $P = \{p \in \mathbb{R}^{|A|} : \sum_{a \in A} p(a) = 0\}$.

**Timing:**

1. Player 1 chooses a price vector $p \in P$.

2. Player 2 chooses an option $a \in A$ and transfers $p(a)$ to Player 1.

For any option $a$ chosen at the second stage and any price vector $p$ set in the first stage, the payoffs associated to this mechanism equal $g(p, a) = (g_1(p, a), g_2(p, a)) = (u_1(a) + p(a), u_2(a) - p(a))$.

Now it is obvious that the P&C mechanism defines an extensive form game, given the players' utility functions. A strategy profile in the game induced by the P&C mechanism is a pair $\sigma = (\sigma_1, \sigma_2)$, with $\sigma_1 \in P$ and $\sigma_2 : P \to A$. It is also obvious that there exists at least one subgame perfect Nash equilibrium in pure strategies, as this is a finite perfect-information game.

We say that the P&C mechanism *implement* the efficient options in subgame-perfect equilibrium if, for any subgame-perfect Nash equilibrium $\sigma = (\sigma_1, \sigma_2)$, $\sigma_2(\sigma_1)$ is efficient; and, conversely, for any efficient outcome $a \in A$, there is a subgame-perfect Nash equilibrium $\sigma = (\sigma_1, \sigma_2)$ with $a = \sigma_2(\sigma_1)$.

**Proposition 1.** The P&C mechanism subgame-perfect implements the set of efficient options.
**Proof.** The proof is divided in four steps: the existence of a price vector that makes Player 2 indifferent between all options (Step A), the proof that this price vector is the unique one compatible with equilibrium behavior (Step B), the proof that any equilibrium selects an efficient option (Step C) and finally (Step D) the construction of an equilibrium selecting an efficient option and the converse construction: for each efficient option, there is an equilibrium implementing it.

**Step A:** there is one and only one price $p^* \in P$ with $g_2(p^*, a_j) = u_2(a_j) - p^*(a_j)$ is constant in $j$.

Indeed if $\theta = u_2(a) - p(a)$, then

$$k\theta = \sum_{j=1}^{k} u_2(a_j) - \sum_{a \in A} p(a) = k\text{Avg}_2,$$

as $p \in P$. Therefore, $p^*(a) = u_2(a) - \theta = u_2(a) - \text{Avg}_2$.

**Step B:** If $\sigma$ is a subgame-perfect Nash equilibrium, then $\sigma_1 = p^*$.

Let $\sigma$ be a subgame-perfect equilibrium, $p = \sigma_1$ and $a_i = \sigma_2(p)$. We claim that $g_2(p, a) = u_2(a) - p(a)$ is constant for any $a$. Suppose then, towards a contradiction, that there are $j$ and $h$ with $g_2(p, a_h) > g_2(p, a_j)$. Let $H$ be the set of $h$ with $a_h \in \text{argmax}\{u_2(a_j) - p(a_j) : 1 \le j \le k\}$, and note that $i \in H$ while $j \notin H$. Consider the price vector $p'$ that is identical to $p$ except that $p'(a_i) = p(a_i) + \varepsilon, p'(a_h) = p(a_h) + 2\varepsilon$ for $h \in H \setminus \{i\}$, and $p'(a_j) = p(a_j) - \varepsilon - 2\varepsilon(|H| - 1)$ for any $a_j \notin H$. For $\varepsilon > 0$ small enough, Player 2 finds it uniquely optimal to choose $a_i$, while Player 1's payoff is strictly greater. A contradiction.

Since $g_2(p, a_j) = u_2(a_j) - p(a_j)$ is constant in $j$, by Step A, $p = p^*$.

**Step C:** If $\sigma$ is a subgame-perfect Nash equilibrium, then $\sigma_2(p^*) \in \text{argmax}\{u_1(a_j) + u_2(a_j) : 1 \le j \le k\}$.

Suppose, towards a contradiction, that $\sigma_2(p^*) = a_j$ and that $u_1(a_j) + u_2(a_j) < u_1(a_i) + u_2(a_i)$. By definition of $p^*$, however, $u_2(a_j) - p^*(a_j) = u_2(a_i) - p^*(a_i)$. Suppose now that player 1 chooses a price vector $p' \in P$ that is identical to $p^*$, except in that $p'(a_i) = p(a_i) - \varepsilon$ and $p'(a_j) = p^*(a_j) + \varepsilon$, for $\varepsilon > 0$. Then we have that $\sigma_2(p') = a_i$, as now $a_i$ is
the uniquely optimal choice for player 2, while

$$u_1(a_j) + p^*(a_j) = u_1(a_j) + u_2(a_j) - \text{Avg}_2 < u_1(a_i) + u_2(a_i) - \varepsilon - \text{Avg}_2 = u_1(a_i) + p'(a_i),$$

for $\varepsilon > 0$ small enough, contradicting that $\sigma$ is a subgame-perfect Nash equilibrium. **Step D:** For every efficient outcome, there is a subgame-perfect Nash equilibrium that selects it.

Observe that Step A is a general remark on the mechanism whereas Steps B and C deal with any subgame perfect equilibrium. This means that in any subgame perfect equilibrium: $\sigma_1 = p^*$ and $\sigma_2(p^*) \in \text{argmax}\{u_1(a_j) + u_2(a_j) : 1 \le j \le k\}$. In other words, any subgame perfect equilibrium outcome is efficient. Let $a_j$ be an efficient outcome. Consider the strategy profile $\sigma_1 = p^*$ and $\sigma_2(p^*) = a_j$. Player 2 is playing a best response since $p^*$ is making him indifferent between all options. Player 1's payoff equals :

$$u_1(a_j) + p^*(a_j) = u_1(a_j) + u_2(a_j) - \text{Avg}_2 = \text{MAX}(u) - \text{Avg}_2.$$

This means that, given $p^*$, Player 1 is indifferent among all efficient options. Now, suppose that Player 1 alters the price vector to force Player 2 to choose another efficient option. Any option $a_h$ with a price $p(a_h) > p^*(a_h)$ will not be chosen by Player 2. This means that if Player 1 wants to induce Player 2 to choose some option $a_l$ he must set $p(a_l) < p^*(a_l)$; however, this implies that if Player 2 chooses $a_l$ Player 1's payoff is lower or equal than $\text{MAX}(u) - \text{Avg}_2$ since Player 1's payoff is increasing in $p(a_l)$, a contradiction. Hence, any efficient option is selected in some subgame perfect equilibrium.

Observe that, in Step D, the existence of a subgame-perfect Nash equilibrium is established. $\square$

The P&C mechanism confers the first player an advantage, as the equilibrium payoffs to Player 2 are always $\text{Avg}_2$, while Player 1 gets a payoff that is greater than $\text{Avg}_1$. We consider this issue in detail in Section 6, but we note here that the assumption that prices in $P$ add to zero may be modified to avoid (or exacerbate) the payoff
imbalance.

Indeed, for any constant $\alpha$, we may define the P&C mechanism with Player 1 choosing a price in $P_{\alpha} = \{p \in \mathbb{R}^{|A|} : \sum_{j=1}^{k} p(a_j) = \alpha\}$. By considering a modified game, with $P = P_{\alpha}$ as above, but in which Player 2's utility is $u_2 - \frac{\alpha}{k}$, and 1's utility is $u_1 + \alpha/k$, we see that P&C again subgame-perfect implements the efficient alternative. Now, however, Player 2's payoff is $\text{Avg}_2 - \frac{\alpha}{k}$ while 1's payoff is $\text{MAX}(u) - \text{Avg}_2 + \frac{\alpha}{k}$. A negative value of $\alpha$ serves to balance the payoffs to the two agents.

An outside agent like Judge Atkins, who does not know the utilities of players 1 and 2, may want to use $P_{\alpha}$ in order to balance the P&C mechanism, but not know the proper value of $\alpha$. It is, however, possible to endogenize the needed value of $\alpha$. One idea is to proceed as follows:

1. Player 1 proposes a real number $\alpha$.

2. Player 2 decides between being the choosers (so that Player 1 is the proposer) or the proposer (and Player 1 becomes the choosers).

3. The proposer set-up a price vector with $p \in P_{\alpha}$ and

4. The choosers select an alternative $a_j$ and pays $p(a_j)$ to the proposer.

By replicating the arguments in Proposition 1, one can show that, in equilibrium, $\alpha = \frac{k}{2}(\text{Avg}_1 + \text{Avg}_2 - \text{MAX}(u))$ so that Player 2 is indifferent between the two roles. This means that the respective payoffs equal $\frac{1}{2}(\text{MAX}(u)) - \frac{1}{2}(\text{Avg}_2 - \text{Avg}_1)$ and $\frac{1}{2}(\text{MAX}(u)) + \frac{1}{2}(\text{Avg}_2 - \text{Avg}_1)$. This version with an endogenous sum of the prices induces a redistribution between players with respect to the default version of P&C, in which the prices sum up to 0 and payoffs equal $(\text{MAX}(u) - \text{Avg}_2, \text{Avg}_2)$. The main difference between the P&C with endogenous $\alpha$ is that the payoff difference only depends on the players' average payoff, and not on the total payoff $\text{MAX}(u)$.

Section 6 fleshes out a related idea for balancing payoffs in the P&C mechanism.
# 5 Price & Choose with many players

We now turn to a many-player version of the problem. We shall see that the previous result implies that a simple *n*-player variation of our P&C mechanism achieves subgame-perfect implementation of the efficient options. In this mechanism, the first *n* − 1 players propose, one after the other, a balanced price vector that they demand as payment from the next player in the order. The *n*th player chooses an option *a* ∈ A. The endogenously set prices determine the transfers made between consecutive players. A balanced price vector remains a vector of prices such that the sum of prices equals zero.

## Timing:

1. Player 1 sets up a price vector $p^2 \in P$.

2. For each $i = 2, \dots, n-1$, Player $i$ sets up a price vector $p^{i+1} \in P$, knowing prices $p^2, \dots, p^i$.

3. Player *n* chooses an option *a* as the outcome given the prices $p^2, \dots, p^n$.

## Transfers.

Say that *a* is the option chosen by Player *n*; this means that Player *n* pays Player *n* − 1 the price $p^n(a)$. In turn, Player *n* − 1 has to pay the price $p^{n-1}(a)$ to Player *n* − 2. This applies to any Player *m* with *m* = 2, ..., *n* − 1, so that he pays $p^m(a)$ to player *m* − 1 while receiving the transfer $p^{m+1}(a)$ from player *m* + 1. Finally, Player 1 receives the transfer $p^2(a)$ from Player 2, but makes no further payments. This entails that, assuming quasi-linear preferences, the payoffs associated to the option *a* and the price vector $p = (p^2, \dots, p^n)$ equal:

$$g_n(p, a) = u_n(a) - p^n(a),$$

$$g_m(p, a) = u_m(a) - p^m(a) + p^{m+1}(a) \text{ for } m = 2, \dots, n-1,$$

$$g_1(p, a) = u_1(a) + p^2(a).$$
**Proposition 2.** The $P^{n-1}$&C mechanism subgame-perfect implements the set of efficient options.

*Proof.* We prove first that any equilibrium outcome of the $P^{n-1}$&C mechanism is an efficient option. We use Proposition 1 and proceed by induction. Fix a subgame-perfect Nash equilibrium $\sigma = (\sigma_1, \dots, \sigma_n)$. Define $p^{n+1} = p^1 = (0, \dots, 0)$ so that, for any player $i$, if the option $a$ is the outcome, with the sequence of prices $p^2, \dots, p^n$, then $i$'s payoff is $u_i(a) - p^i(a) + p^{i+1}(a)$.

The proof uses an auxiliary two-player P&C game, on which we apply Proposition 1. Let $G(v_1, v_2)$ denote the two-player P&C game with utility functions $v_1$ and $v_2$ for, respectively, players 1 and 2.

For any $i \le n-1$, consider the game $G(u_i - p^i, \sum_{j=i+1}^n u_j)$. Any equilibrium outcome $(p^{i+1}, a^i)$ involves:

1. $a^i \in \argmax_{a \in A} [u_i(a) - p^i(a) + \sum_{j=i+1}^n u_j(a)]$,

2. and $\sum_{j=i+1}^n u_j(a) - p^{i+1}(a) = \frac{1}{k} \sum_{\tilde{a} \in A} \sum_{j=i+1}^n u_j(\tilde{a})$, for all $a \in A$, which uniquely defines $p^{i+1}$.

So, in equilibrium, the unique $p^{i+1}$ chosen results in maximizing:

$$u_i(a) - p^i(a) + \sum_{j=i+1}^{n} u_j(a).$$

Consider a subgame in which it is player $i$'s time to move, and there are given prices $p^1, \dots, p^i$ chosen by the players $j < i$. We claim that, in any SPNE, $p^{i+1} = \sigma^i(p^1, \dots, p^i)$ chosen by Player $i$ must be part of a SPNE of the game $G(u_i - p^i, \sum_{j=i+1}^n u_j)$.

Indeed this is obviously true for $i = n-1$. So, reasoning by induction, suppose that it holds true for any player $j > i$. By the inductive hypothesis, for any $p^{i+1}$ chosen by player $i$, Player $i+1$ will choose $p^{i+2}$ to be part of a SPNE of $G(u_{i+1} - p^{i+1}, \sum_{j=i+2}^n u_j)$.

So Player $i+1$'s strategy, given $(p^1, \dots, p^{i+1})$, will result in an option that maximizes $u_{i+1} - p^{i+1} + \sum_{j=i+2}^n u_j$. By reasoning as in the case of two players, we see that $i$'s strategy will leave $i+1$ indifferent among inducing any of the possible actions. Indeed, if there exists $a, a'$ with $u_{i+1}(a) - p^{i+1}(a) + \sum_{j=i+2}^n u_j(a) > u_{i+1}(a') - p^{i+1}(a') +
$\sum_{j=i+2}^{n} u_j(a')$, then $i$ could raise $p^{i+1}$ for the actions that are in the same indifference class as the chosen option and, without changing the chosen option, obtain a strictly higher payoff. So

$$p^{i+1}(a) = \sum_{j=i+1}^{n} u_j(a) - \frac{1}{k} \sum_{\tilde{a} \in A} \sum_{j=i+1}^{n} u_j(\tilde{a}) \text{ for all } a \in A$$

and the payoff to Player $i$ from choosing $p^{i+1}$ is

$$u_i(a) - p^i(a) + p^{i+1}(a) = u_i(a) - p^i(a) + \sum_{j=i+1}^{n} u_j(a) - \frac{1}{k} \sum_{\tilde{a} \in A} \sum_{j=i+1}^{n} u_j(\tilde{a}).$$

So Player $i$ will choose $p^{i+1}$ to maximize $u_i(a) - p^i(a) + \sum_{j=i+1}^{n} u_j(a)$.

This concludes the proof by induction.

If we now consider the game $G(u_1, \sum_{j=2}^{n} u_j)$, and recall that $p^1 = 0$. The prior argument establishes that any subgame-perfect Nash equilibrium outcome is efficient.

We now show the converse argument: for any efficient outcome $\tilde{a}$, there is an equilibrium where $\tilde{a}$ is the outcome.

By applying Proposition 1, we know that for any pair of utility functions $(u_1, u_2)$ and any alternative $\tilde{a}$ that maximizes $\sum_{h=1}^{2} u_h(a)$, the two-player P&C game $G(u_1, u_2)$ admits an equilibrium selecting $\tilde{a}$.

We have also deduced earlier in the proof that, for any player $i = 1, \dots, n-1$, the unique equilibrium prices proposed in any subgame where $i$ moves first are equivalent to the ones in the two-player P&C game $G(u_i - p^i, \sum_{j=i+1}^{n} u_j)$. So are the selected alternatives in equilibrium. Indeed, we know that, in equilibrium, any player moving after $i$ is indifferent. Thus, there is an equilibrium selecting any efficient alternative $\tilde{a}(i)$ in $\arg\max_{a \in A} \sum_{h=i}^{n} u_h(a) - p^i(a)$. Indeed, as long as any player moving after $i$ is indifferent and Player $n$ selects an efficient alternative in the subgame, no Player has a profitable deviation. The formal proof consists in showing by induction that any Player moving after $i$ obtains $\text{Avg}_i$ in equilibrium while Player $i$ obtains $\sum_{h=i}^{n} u_h(a(i)) - p^i(a(i)) - \sum_{h=i+1}^{n} \text{Avg}_i$ (we omit it for brevity). By recalling that $p^1 = 0$ by definition and considering the whole game, it follows that, for any alternative $\tilde{a}(1)$
with $\bar{a}(1) = \arg\max_{a\in A} \sum_{j=1}^n u_j(a)$, there is an equilibrium selecting it concluding the proof. $\square$

# 6 Bid, Price & Choose

The P&C mechanism implements a Pareto efficient option in the general model of social choice with transfers, but it does so with a particular set of transfers. In fact, the first mover is treated asymmetrically with respect to the other players. Consider $P^{n-1}\&C$ and note that every player other than the first player in the order receives a payoff that equals $\text{Avg}_i$, their average payoff from an option in $A$. The first moving player will receive, instead, a payoff that equals $\text{MAX}(u) - \sum_{j\neq1} \text{Avg}_j > \text{Avg}_1$; a first-mover advantage.

To correct the resulting unequal welfare distribution, we could proceed as was suggested after we stated the proof of Proposition 1. We could also randomize the order of play and select uniformly the identity of the first-mover.<fnref n="7" /> This will lead to an *ex-ante* equal surplus split (that is, before the lottery takes place) but would still generate ex-post inequality. Since we care about the ex-post allocation of the surplus, we focus here on ideas suggested in the literature by Jackson and Moulin (1992) and Pérez-Castrillo and Wettstein (2001); where biding in an auction determines the order of play. Specifically, all players bid to be the first mover, and the highest bidder wins (ties being broken by a uniform draw). The revenue from the winning bid is equally split among the rest of the players. Then the players play the P&C mechanism, where the player with the winning bid is the first mover. As we show, this bidding stage reduces inequality among players, and makes the equilibrium payoffs order-independent. That is, in equilibrium, players have no preferences ex-post over the stages at which to participate.

More formally, consider an auction for the role of choosing first. Each player submits a bid, $b_i \ge 0$. Let $W = \{i : b_i = \max\{b_j : 1 \le j \le n\}\}$ be the set of winners — the set of players who submitted the highest bids. One winner is chosen at random (uniformly) to pay their bid and become the first mover. The bid collected from the

<footnote n="7">⁷We thank a referee for this suggestion.</footnote>
first mover is then distributed in equal shares among the rest of the players. So if $i \in W$ is selected, then $i$ pays $b_i$ and becomes the first mover, while all the remaining players receive a payment of $\frac{1}{n-1}b_i$. The order of play among players who are not first is determined at random.

**Proposition 3.** *Bid, Price & Choose subgame-perfect implements the set of efficient options. Moreover, in any equilibrium, if $U^i$ are the equilibrium payoffs to players $i = 1, \dots, n$, then*

$$U^i - U^j = \text{Avg}_i - \text{Avg}_j.$$

*Proof.* Let $\eta = \sum_{i=1}^n u_i(a^*) - \sum_{i=1}^n \text{Avg}_i$, where $a^*$ is an efficient outcome, and $b^* = \frac{n-1}{n}\eta$. Consider a P&C subgame, after the order of play has been determined, and observe that, in any subgame-perfect equilibrium outcome of this subgame, the payoffs to a player $j$ who is not the first mover is $\text{Avg}_j$, while the payoff to a player $i$ who is the first mover is $\text{Avg}_i + \eta$. Thus, if $i$ is a winner of the auction, and is randomly chosen to move first, their payoff is $\text{Avg}_i + \eta - b_i$. Any player $j \neq i$ gets payoff $\text{Avg}_j + b_i/(n-1)$. By definition, $\eta - b^* = b^*/(n-1)$, so the difference in payoffs is as in the statement of Proposition 3.

Note first that there exists a symmetric Nash equilibrium of the auction with $b_i = b^*$ for all $i$, as $\eta - b^* = b^*/(n-1)$ ensures that the payoff from winning and losing are the same. Bidding higher than $b^*$ would ensure winning, but with a strictly lower payoff; and bidding lower than $b^*$ would result in losing, but getting the same payoff as with a bid of $b^*$.

This symmetric equilibrium is not unique, but all other equilibria have the same outcome. Indeed there is no Nash equilibrium with a single winner, as the winner would gain from lowering their bid. For any $W$ with at least two players, there is a Nash equilibrium with $b_i = b^*$ for $i \in W$ and $b_i < b^*$ for $i \notin W$. This follows from the same argument as above.

Finally, consider a profile of bids with a set of winners choosing $b' \neq b^*$. At $b'$ the payoff from winning differs from the payoff from losing. If the latter is higher, a winner has an incentive to lower their bid. If the latter is lower, they can benefit by raising their bid. So there is no Nash equilibrium in which the winning bid differs
# 7 Extensions

We consider four extensions of our basic model and results. In the first extension we relax the assumption that utility over monetary transfers is quasilinear. We adopt a model with additively separable preferences, but allowing for very general preferences over transfers. Remarkably, the main message that P&C implements the efficient outcomes goes through. Our second extension introduces an outside option, and provides a modified mechanism implementing efficient outcomes with an added voluntary participation property. The third extension relaxes the assumption of full rationality, introduces adversarial behavior, and shows that the implementation result under P&C and two players is robust to this behavioral assumption. Finally, our last extension introduces an upper-bound on the prices that players can propose in the P&C mechanism.

## 7.1 Non-quasi-linear preferences

We turn to a generalization of our model to the case when agents' preferences are additively separable, but not necessarily quasilinear in monetary transfers. The P&C mechanism is the same as the benchmark mechanism used in Section 5 to implement efficient outcomes when preferences are quasi-linear with $n$ players. The main difference deals with how players' payoffs are transformed when making/receiving a monetary transfer.

Recall that $P = \{p \in \mathbb{R}^{|A|} : \sum_{a \in A} p(a) = 0\}$ denotes the set of price vectors with zero sum. When the outcome is $(a, m_1, \dots, m_n) \in A \times \mathbb{R}^n$ then player $i$'s utility is $u_i(a) + \eta_i(m_i)$ for $i = 1, \dots, n$. In other words, we assume that agents' utilities satisfy *additive separability*. We assume that the functions $\eta_i : \mathbb{R} \to \mathbb{R}$ are strictly monotone, continuous and surjective.

In the non-quasilinear case, the allocation of money is explicitly part of the efficiency consideration. Consider a strategy profile $\sigma$; let $p^2, \dots, p^n$ be the sequence of
prices on the path of $\sigma$, and $\bar{a}$ be the chosen option. The outcome resulting from $\sigma$ is then $(\bar{a}, \bar{m}_1, \dots, \bar{m}_n)$ with $\bar{m}_1 = p^2(\bar{a})$, $m_2 = p^3(\bar{a}) - p^2(\bar{a})$, $\dots, m_{n-1} = p^n(\bar{a}) - p^{n-1}(\bar{a})$ and $m_n = -p^n(\bar{a})$. We say that this outcome is *efficient* if there is no $(a', m'_1, \dots, m'_n) \in A \times \mathbf{R}^n$ with $\sum_{i=1}^n m'_i \le 0$ and $u_i(a') + \eta_i(m'_i) \ge u_i(\bar{a}) + \eta_i(m_i)$ for all $i$ with at least one strict inequality for some agent $i$.

**Proposition 4.** With additively separable preferences, the SPNE outcome of the P&C mechanism is an efficient allocation.

The proof of Proposition 4 is in Appendix A. Observe that the statement is weaker than what is claimed in our main results. We only say that equilibrium outcomes are efficient, not that there is full implementation. The characterization of efficient transfers is an added complication in the non-quasilinear case, and we do not deal with the full implementation problem for this case.

## 7.2 Outside option

We turn to a version of our model in which the player who makes a choice has an outside option available that provides her with certain exogenous bargaining power. In practice, agents are often endowed with some property rights or outside options that make their participation in the mechanism voluntary. For example, a particular case of our model is when each outcome corresponds to the allocation of some set of indivisible private goods. In this case, the outside option may be a given endowment of private goods.

More formally, we augment the set $A$ of alternatives with an outside option $a_0$. An equilibrium outcome is *individually rational* for a player if she obtains a utility equal to or larger than the one she receives with the outside option.

In this augmented setting, we slightly modify the P&C mechanism to reach efficiency. This modification is rather simple: we keep the main structure unchanged without imposing anymore a restriction on the sum of prices. With $n$ players, we define the Unconstrained P&C's mechanism proceeds as follows:

**Timing:**
1. Player 1 sets up a price vector $p^2 \in \mathbb{R}^{|A|}$.

2. For each $i = 2, \dots, n-1$, Player $i$ either sets up a price vector $p^{i+1} \in \mathbb{R}^{|A|}$, knowing prices $p^2, \dots, p^i$ or selects the outside option $a_0$ (for free).

3. Player $n$ chooses an option $a$ as the outcome given prices $p^2, \dots, p^n$, or selects the outside option $a_0$.

If some player selects $a_0$, then $a_0$ is the outcome, there are no transfers, and each player $i$ obtains utility $u_i(a_0)$. If no player selects $a_0$, then Player $n$ selects an alternative $a$ and transfers are given by prices, identical to the ones in P&C with $n$ players. For ease of notation, we write $u_i^* = u_i(a_0)$ to denote the utility of Player $i$ when the outside option is selected; $u^* = (u_1^*, \dots, u_n^*)$ is the vector of such utilities.

**Proposition 5.** For any specification of $u^*$, the Unconstrained P&C implements the set of efficient and individually rational allocations.

*Proof.* Fix a subgame-perfect Nash equilibrium $\sigma = (\sigma_1, \dots, \sigma_n)$. Define $p^{n+1} = p^1 = (0, \dots, 0)$ so that, for any player $i$, if the option $a$ is the outcome, with the sequence of prices $p^2, \dots, p^n$, then $i$'s payoff is $u_i(a) - p^i(a) + p^{i+1}(a)$.

Consider first any subgame where Player $n-1$ moves first. Remark that, independently of Player $n-1$'s proposal, Player $n$ can obtain a utility $u_n^*$ by opting out. In such a subgame, if $p_n = \sigma_{n-1}(p^1, \dots, p^{n-1})$ and $a = \sigma_n(p^1, \dots, p^n)$, then $u_n(a) - p^n(a) = u_n^*$ as both agents are optimizing. So Player $n-1$'s payoff will be $u_{n-1}(a) + u_n(a) - p^{n-1}(a) - u_n^*$, which is maximized when $a$ is efficient in the subgame. Player $n-1$ can induce any efficient $a$ by setting a price that leaves $n$ indifferent with $u_n^*$, and large prices for all other options. Now we may complete the proof by induction.

For any $i = 1, \dots, n$, let $\bar{a}_i \in \operatorname{argmax}\{\sum_{h=i}^n u_h(a) : a \in A\}$. Assume now that in any subgame where Player $j$ moves first with $j > i$:

1. the alternative selected is efficient in the subgame with utilities $(u_j - p^j, u_{j+1}, \dots, u_n)$

2. each Player $h$ with $h = j+1, \dots, n$ obtains payoff $\kappa_h$ with

$$\kappa_h = \sum_{l=h}^{n} u_l(\bar{a}_h) - \sum_{l=h+1}^{n} u_l^*$$
Consider now a subgame where Player *i* moves first. The payoff for Player *i* + 1 equals $u_{i+1}(\tilde{a}) - p^{i+1}(\tilde{a}) + p^{i+1}(\tilde{a})$, where $\tilde{a}$ is the selected option. For any price vector $p^i$, the inductive hypothesis tells us that the payoff of Player *i* + 1 can be rewritten as $\sum_{h=i+1} u_h(a) - p^{i+1}(a) - \sum_{h=i+2}^{n} u_h^*$, with *a* being the choice in the subgame. This is maximized when *a* is efficient in the subgame. Moreover, Player *i* can always induce Player *n* to choose the efficient option by setting $p_*^i$ that makes Player *i* + 1 uniquely prefer the efficient option, which, by the inductive hypothesis, leads to the implementation of this option. This concludes the proof by induction by recalling that $p^1 = 0$.

It is easy to see that unconstrained P&C fully implements the efficient outcomes. In any subgame $p^1, \dots, p^i$, for any outcome $a$ that maximizes $\sum_{h=i}^n u_h(a') - p^i(a')$, set $p_*^{i+1}(a), \dots, p_*^n(a)$ so that $p_*^h(a) = \sum_{j=h}^n u_j(a) - \sum_{j=h+1}^n u_j(a)u_j^*$ and $p_*^h(a')$ is sufficiently large for $a' \neq a$. This defines a SPNE strategy profile for each choice of efficient outcome. □

*Remark 1.* We may define a constrained version of P&C with an outside option, by adding the constraint that prices add to zero. This will modify the above when the value of the outside option falls below the average utility of agents’ over the options in *A*. We omit the details, but emphasize that this may be a way of addressing an imbalance in bargaining power, when the outside option does leaves some players in a weak position (see also Section 6).

## 7.3 P&C as a robust mechanism

The analysis so far hinges, of course, on complete information among the players, and on the assumption of equilibrium play. We now discuss two deviations from these assumptions: perturbations from the complete information assumption and approximate equilibrium with adversarial behavior.

Regarding the first robustness check, Aghion et al. (2012) study implementation with transfers under perturbations of the complete information assumption. They prove that any mechanism that subgame perfect implements a social choice
function which fails to be Maskin monotonic<fnref n="8" /> under complete information admits a sequential equilibrium with undesirable outcomes when information is perturbed. Their result is stated for finite strategy sets as well as for countably infinite ones, so it does not exactly apply to P&C and our setting. For completeness, however, we now show by example that the social choice function that the P&C mechanism implements is not Maskin monotonic. To see why, consider the next example involving three alternatives and quasi-linear preferences over transfers. Let $A = \{a_1, a_2, a_3\}$ be the set of options and $u = (u_1, u_2)$ and $u' = (u_1, u'_2)$ denote two possible utility profiles with $u_1 = u_2 = (1,0,-1)$ and $u'_2 = (1,-2,-1)$. The set of allocations equals $\{(a', t_1, t_2) \in A \times \mathbb{R}^2 \text{ with } t_1 + t_2 = 0\}$, where $a'$ is the implemented option and $t_1, t_2$ are the transfers of players 1 and 2 respectively. The sum of the transfers is zero since Player 2 makes a transfer to Player 1 in the P&C mechanism. Recall that a social choice function $f$ maps the set of utility vectors $U$ into the set of allocations. A social choice function is Maskin monotonic on $U$ if for any pair of utility vectors $u, u' \in U$, if $x = f(u)$ and

$$ \{(i, y) \mid u_i(x) \ge u_i(y)\} \subseteq \{(i, y) \mid u'_i(x) \ge u'_i(y)\}, $$

(i.e. no player ranks $x$ lower when moving from $u$ to $u'$) then $x = f(u')$. The allocation $x$ chosen by the P&C mechanism where 1 is the first-mover equals $x = (a_1, 1, -1)$ since $a_1$ is the efficient option and the price vector is $p = (1, 0, -1)$. When moving from $u$ to $u'$, no player ranks $x$ lower since (i) the utility function of 1 remains unchanged and (ii) for player 2, the utilities of $a_1$ and $a_3$ remain unchanged whereas the utility of $a_2$ goes down. If the rule is Maskin monotonic, $x$ should be chosen in $u'$. Yet, the chosen allocation in $u'$ is $y = (a_1, 2/3, -2/3)$ and clearly $x \ne y$, violating Maskin monotonicity. As said, however, the results of Aghion et al. (2012) do not strictly speaking apply to our model and it remains to see if our results suffer from the lack of robustness that they study.<fnref n="9" />

<footnote n="8">⁸Maskin monotonicity plays a central role in implementation theory since any Nash implementable social choice function needs to satisfy it.</footnote>

<footnote n="9">⁹Some of the main results in the paper of Aghion et al. deal with direct revelation mechanisms, so they are focused on mechanisms that naturally differ from P&C.</footnote>
We now consider a different robustness test in the spirit of robust mechanism design (see Carroll (2019) for an excellent overview). The deviations we have in mind relax the notion of equilibrium in two ways: First, players are only approximately optimizing; they are “ε-maximizers.” Second, the assumption of approximate optimization gives rise to ambiguity in how the second player will choose, and we assume that Player 1 operates under a worst-case scenario. So Player 1 expects that the ambiguity will be resolved adversarially by Player 2. As we prove below, the P&C mechanism still achieves efficient implementation in the perturbed setting we have outlined.

The assumption that Player 2 is adversarial could be motivated by ideas of negative reciprocity (see Fehr et al. (2021) for a recent contribution on this idea in implementation), in which players’ utilities depend negatively on the utility level of their opponent. Observe also that, in the equilibrium of P&C in Section 3, the opposite behavior arises: Player 2 is indifferent between all alternatives and he chooses the one maximizing Player 1’s payoff (this occurs, as we show, endogenously; it is not an assumption).

Formally, we say that, for a fixed $\varepsilon > 0$, option $a$ is an $\varepsilon$-maximizer for Player 2 if there is no $a'$ that is better than $a$ by more than $\varepsilon$. This is equivalent to saying that $a$ is an $\varepsilon$-maximizer for Player 2 $\iff g_2(p,a) + \varepsilon \ge g_2(p,a')$ for any $a' \ne a$. We denote by $\beta_i^\varepsilon(p)$ the set of $\varepsilon$-maximizers at the price vector $p$ for Player 2. The adversarial nature of Player 2 is then captured by setting $\sigma_2(p) \in \operatorname{argmin}\{g_1(p,a) : a \in \beta_2^\varepsilon(p)\}$. In words, Player 2 selects the option among $\varepsilon$-maximizers that minimizes Player 1’s payoff.

Similarly, we say that Player 1 is $\varepsilon$-maximizing when choosing a price vector $p \in P$ if $g_1(p, \sigma_2(p)) + \varepsilon \ge g_1(p', \sigma_2(p'))$ for all $p' \in P$.

To sum up, we say that the strategy profile $\sigma = (\sigma_1, \sigma_2)$ is a $\varepsilon$-robust subgame perfect Nash equilibrium if

1. $\sigma_2(p) \in \operatorname{argmin}\{g_1(p,a) : a \in \beta_2^\varepsilon(p)\}$ for all $p \in P$,

2. and Player 1 is $\varepsilon$-maximizing when choosing $\sigma_1 \in P$.

We say that $\sigma_2(\sigma_1)$ is the *outcome* of the $\varepsilon$-robust subgame perfect Nash equilibrium
$\sigma$.

For simplicity we assume here that there is a unique efficient alternative. We expect that the argument generalizes to settings with more than one efficient option.

**Proposition 6.** For any $\varepsilon > 0$ small enough, the unique $\varepsilon$-robust subgame perfect Nash equilibrium outcome of P&C is the efficient outcome.

*Proof.* Let $p^*$ be the price vector constructed in the proof of Proposition 1. So $g_2(p^*, a_j) = u_2(a_j) - p^*(a_j)$ is constant in $j$ and $p^*(a_j) = u_2(a_j) - \text{Avg}_2$ for each $a_j \in A$.

Without loss of generality, we say that the (unique) efficient option is $a_1 \in A$. So $\text{MAX}(u) = u_1(a_1) + u_2(a_1) > u_1(a_j) + u_2(a_j)$ for all $j \neq 1$.

Choose $\varepsilon > 0$ small enough so that

$$u_1(a_j) + u_2(a_j) + \frac{k-1}{k} \varepsilon < u_1(a_1) + u_2(a_1) - 2\varepsilon \quad (1)$$

for all $j \neq 1$.

Before we get started, observe that if $a_j = \sigma_2(p)$, then $a_j \in \beta_2^\varepsilon(p)$, and hence $u_2(a_j) - p(a_j) + \varepsilon \geq u_2(a_h) - p(a_h)$ for all $h \neq j$. Therefore:

$$u_2(a_j) - p(a_j) \geq \text{Avg}_2 - \frac{k}{k-1}\varepsilon. \quad (2)$$

The proof is now divided in two steps. In Step A, we exhibit an $\varepsilon$-subgame-perfect Nash equilibrium that selects $a_1$. In Step B, we show that, despite the potential multiplicity of equilibria, all of them select option $a_1$ as the equilibrium outcome.

**Step A:** Consider the strategy profile $\sigma$ defined by

$$a_1) q^* = (p(a_1^*) - \varepsilon, p(a_2^*) + \frac{\varepsilon}{k-1}, p(a_3^*) + \frac{\varepsilon}{k-1}, \dots, p(a_k^*) + \frac{\varepsilon}{k-1})$$

b) Player 2 chooses $a_1$ if $p = q^*$ and minimizes the payoffs of Player 1 over $\beta_\varepsilon^2(p)$ otherwise.

To see why this is an $\varepsilon$-equilibrium, observe that with $q^*$, the payoffs of both
players are respectively equal to:

$$ 
\begin{aligned}
g_1(q^*, \cdot) &= (u_1(a_1) + p(a_1^*) - \varepsilon, u_1(a_2) + p(a_2^*) + \frac{\varepsilon}{k-1}, \dots, u_2(a_k) + p(a_k^*) + \frac{\varepsilon}{k-1}) \\
g_2(q^*, \cdot) &= (u_2(a_1) - p(a_1^*) + \varepsilon, u_1(a_2) - p(a_2^*) - \frac{\varepsilon}{k-1}, \dots, u_2(a_k) - p(a_k^*) - \frac{\varepsilon}{k-1}).
\end{aligned}
$$

Thus, $\beta_2^\varepsilon(q^*) = \{a_1\}$, so that Player 2 chooses $a_1$ as we have claimed. To complete the proof, we need to check that Player 1 does not have a profitable deviation that exceeds their payoff by at least $\varepsilon$. Assume, towards a contradiction, that Player 1 can find a price vector $p$ that ensures him a payoff strictly greater than $g_1(q^*, a_1) + \varepsilon$. Let $a_j = \sigma_2(p)$. Then we have $u_1(a_j) + p(a_j) > u_1(a_1) + q^*(a_1) + \varepsilon$.

There are two cases to consider. The first case is when $a_j = a_1$. Then $u_1(a_1) + p(a_1) > u_1(a_1) + q^*(a_1) + \varepsilon$ implies that $p(a_1) > q(a_1^*) + \varepsilon = u_2(a_1) - \text{Avg}_2$. Thus $\text{Avg}_2 > u_2(a_1) - p(a_1)$, and we conclude that there exists $a_j$ with $u_2(a_j) - p(a_j) > u_2(a_1) - p(a_1)$.

At the same time, $a_1 = \sigma_2(p)$, which implies that $a_1 \in \beta_2^\varepsilon(p)$. But then $u_2(a_j) - p(a_j) > u_2(a_1) - p(a_1)$ means that $a_j \in \beta_2^\varepsilon(p)$, so $\sigma_2(p) = a_1$ is only possible if $u_1(a_1) + p(a_1) \le u_1(a_j) + p(a_j)$ (by the definition of $\sigma_2$). Adding up these inequalities, we obtain that

$$ u_1(a_1) + p(a_1) + u_2(a_1) - p(a_1) < u_1(a_j) + p(a_j) + u_2(a_j) - p(a_j), $$

which contradicts the definition of $a_1$.

The second case to consider is when $a_j \neq a_1$. Then the assumption that $q^*$ is not an $\varepsilon$-optimum yields that

$$ u_1(a_j) + p(a_j) > u_1(a_1) + q^*(a_1) + \varepsilon = u_1(a_1) + u_2(a_1) - \text{Avg}_2. $$

Combine this inequality with Equation (2) to obtain that

$$ u_1(a_j) + p(a_j) + u_2(a_j) - p(a_j) > u_1(a_1) + u_2(a_1) - \frac{k-1}{k}\varepsilon, $$

contradicting (1).

**Step B:** Consider any $\varepsilon$-subgame perfect equilibrium $(p, \sigma_2)$. We claim that $\sigma_2(p) = a_1$, and suppose (towards a contradiction) that $\sigma_2(p) = a_j \neq a_1$.
We first observe that $u_1(a_j) + p(a_j) \ge u_1(a_1) + u_2(a_2) - \text{Avg}_2 - 2\epsilon$, because Player 1 may select $q^*$ (as constructed in Step A) and guarantee a payoff of $u_1(a_j) + p(a_j) \ge u_1(a_1) + u_2(a_2) - \text{Avg}_2 - \epsilon$.

By (2), we obtain

$$u_1(a_j) + p(a_j) + u_2(a_j) - p(a_j) \ge u_1(a_1) + u_2(a_2) - \text{Avg}_2 - 2\epsilon + \text{Avg}_2 - \frac{k-1}{k}\epsilon = u_1(a_1) + u_2(a_2) - 2\epsilon - \frac{k-1}{k}\epsilon,$$

contradicting (1). □

## 7.4 Capped Price & Choose

We now consider a modified version of P&C in which there is a bound on the prices that the Players may put on the alternatives. The motivation for such capped price vectors is that arbitrarily large prices may not be feasible in practice, and that capping prices could be seen as a measure to protect the welfare of Player 2.

Formally, for any $\tau \in \mathbb{R}$, we define the set of feasible prices by $P^\tau = \{p \in \mathbb{R}^{|A|} : p(a_j) \le \tau$ for each $a_j \in A\}$. The number $\tau$ is an upper bound on prices. The Capped P&C mechanism with upper-price limit $\tau$ works as follows.

**Timing:**

1. Player 1 chooses a price vector $p^2 \in P^\tau$.

2. For each $i = 2, \dots, n-1$, Player $i$ chooses a price vector $p^{i+1} \in P^\tau$, knowing prices $p^2, \dots, p^i$.

3. Player $n$ chooses an option $a$ as the outcome given the prices $p^2, \dots, p^n$.

We assume quasi-linear preferences and that each player pays the price associated to the option selected by Player $n$. This implies that the payoffs associated to the option $a$ are the same as in Section 3, with quasi-linear preferences.

**Proposition 7.** For any $\tau \in \mathbb{R}$, the capped P&C mechanism with upper-bound $\tau$ subgame perfect implements the set of efficient options.
*Proof.* Fix a subgame-perfect Nash equilibrium $\sigma = (\sigma_1, \dots, \sigma_n)$. Define $p^{n+1} = p^1 = (0, \dots, 0)$ so that, for any player $i$, if $a \in A$ is the outcome, with the sequence of prices $p^2, \dots, p^n$, then $i$'s payoff is $u_i(a) - p^i(a) + p^{i+1}(a)$.

The proof proceeds by induction. Our inductive hypothesis is: For any $i = 1, \dots, n$ and any subgame defined by a sequence of prices $p^1, \dots, p^i$, the outcome chosen by $\sigma$ in the subgame maximizes $\sum_{h=i}^n u_h(a) - p^i(a)$.

The base case is obvious: When $i = n$, the hypothesis is true by assumption of P&C.

So fix $i \le n-1$ and suppose that the hypothesis holds for any subgame $p^1, \dots, p^j$ with $j = i+1, \dots, n$.

Consider an arbitrary sequence of prices $(p^1, \dots, p^i)$. Suppose that $a^*$ is the equilibrium alternative, and $p_*^{i+1}, \dots, p_*^n$ the sequence of equilibrium prices, chosen in the subgame defined by $(p^1, \dots, p^i)$ according to $\sigma$.

*Claim:* $p_*^{i+1}(b) = \tau$ for all $b \in \operatorname{argmax}\{\sum_{h=i+1}^n u_h(a) : a \in A\}$, and

$$ \sum_{h=i+1}^{n} u_h(a^*) - p_*^{i+1}(a^*) = \max\{\sum_{h=i+1}^{n} u_h(a) : a \in A\} - \tau $$

*Proof.* Let

$$ m(p_*^{i+1}) := \operatorname{argmax}\{\sum_{h=i+1}^{n} u_h(a) - p_*^{i+1}(a) : a \in A\}. $$

First we show that $p_*^{i+1}(a) = \tau$ for some $a \in m(p_*^{i+1})$. Indeed, otherwise player $i$ may raise the price of $a^*$ by $\epsilon$, and the price of all other $a \in m(p_*^{i+1}) \setminus \{a^*\}$ by $2\epsilon$; keeping the rest of the prices unchanged. If $q$ is the resulting price vector, we may choose $\epsilon > 0$ small enough that $q \in P^\tau$ and $m(q) = \{a^*\}$. By the inductive hypothesis, $a^*$ is the equilibrium outcome in the subgame $(p^1, \dots, p^i, q)$. This deviation to $q$ would increase the transfer to Player $i$ without changing the option chosen in the subgame following $i$'s choice.

So at least some $a \in m(p_*^{i+1})$ has $p_*^{i+1}(a) = \tau$. Then for any $b \in \operatorname{argmax}\{\sum_{h=i+1}^n u_h(a) : a \in A\}$, $\sum_{h=i+1}^n u_h(b) - p_*^{i+1}(b) \ge \sum_{h=i+1}^n u_h(a) - p_*^{i+1}(a)$. Then, $a^* \in m(p_*^{i+1})$ implies $\sum_{h=i+1}^n u_h(a^*) - p_*^{i+1}(a^*) = \max\{\sum_{h=i+1}^n u_h(a) : a \in A\} - \tau$. $\square$
Observe that the claim implies that $i$'s payoff under $\sigma$ in this subgame is

$$u_i(a^*) - p^i(a^*) + p_*^{i+1}(a^*) = -p^i(a^*) + \tau - \max\{\sum_{h=i+1}^n u_h(a) : a \in A\} + \sum_{h=i}^n u_h(a^*)$$

We now proceed to prove the hypothesis for $i$: We claim that $a^*$ maximizes $a \mapsto \sum_{h=i}^n u_h(a) - p^i(a)$. Suppose, towards a contradiction, that there exists $a' \in A$ with $\sum_{h=i}^n u_h(a') - p^i(a') > \sum_{h=i}^n u_h(a^*) - p^i(a^*)$. Then $i$ could modify $p_*^{i+1}$ to ensure a profitable deviation: Let $q \in P^\tau$ be

$$q(a') = \tau - \max\{\sum_{h=i+1}^n u_h(a) : a \in A\} + \sum_{h=i+1}^n u_h(a') - \varepsilon$$

and $q(a) = \tau$ for all $a \neq a'$. Then $a'$ is the unique maximizer of $a \mapsto \sum_{h=i+1}^n u_h(a) - q(a)$, as the claim implies that

$$\max\{\sum_{h=i+1}^n u_h(a) - p_*^{i+1}(a) : a \in A\} = \max\{\sum_{h=i+1}^n u_h(a) : a \in A\} - \tau < \sum_{h=i+1}^n u_h(a') - q(a')$$

and $q(a) \ge p_*^{i+1}(a)$ for all $a \neq a'$. By the inductive hypothesis, then, the outcome in the subgame following the choice of $q$ by $i$ is $a'$. In consequence, $i$'s payoff from choosing $q$ is

$$\begin{align*}
u_i(a') - p^i(a') + q(a') &= \sum_{h=i}^n u_h(a') - p^i(a') + \tau - \max\{\sum_{h=i+1}^n u_h(a) : a \in A\} - \varepsilon \\
&> \sum_{h=i}^n u_h(a^*) - p^i(a^*) + \tau - \max\{\sum_{h=i+1}^n u_h(a) : a \in A\} \\
&= u_i(a^*) - p^i(a^*) + p_*^{i+1}(a^*),
\end{align*}$$

where the inequality follows from $\sum_{h=i}^n u_h(a') - p^i(a') > \sum_{h=i}^n u_h(a^*) - p^i(a^*)$ and the choice of a small enough $\varepsilon > 0$. The price vector $q$ would be a profitable deviation: a contradiction. The inductive argument completes the proof that any subgame-perfect Nash equilibrium outcome is efficient. For the converse argument, let $\bar{a}$ be any efficient outcome. In any subgame, defined by a sequence of prices $p^1, \dots, p^i$, let
$a(p^i)$ maximize $a \mapsto \sum_{h=i}^{n} u_h(a) - p^i(a)$ and define

$$ \sigma^i(p^1, \dots, p^i)(a(p^i)) = \tau + \sum_{h=i}^{n} u_h(a(p^i)) - \max\{\sum_{h=i}^{n} u_h(a) : a \in A\} $$

and $\sigma^i(p^1, \dots, p^i)(a) = \tau$ for all $a \neq a(p^i)$. On path, with prices $p^1, \dots, p^i$ set $a(p^i) = \bar{a}$.

□

# 8 Conclusion

We have considered implementation in the general social choice problem with money, and an arbitrary number of agents. Our proposed solution, the Price & Choose mechanism, is a simple procedure for reaching efficient agreements. A remarkable feature of our approach is that it relies on prices, and does not require penalties, integer games, off-equilibrium threats, or lotteries; all classical techniques used by mechanism designers to discipline players and achieve full implementation. Our solution requires the availability of money, but does not rely on the narrow assumption of quasilinear preferences.

The main shortcoming of our approach is that it assumes complete information and equilibrium behavior; we have addressed this weakness by considering a model with maxmin and $\epsilon$-optimizing behavior, and shown that the set of efficient options remains implemented by the P&C mechanism - whether experimentally subjects manage to reach efficient agreements through the described methods remains an empirical question.<fnref n="10" />

A potentially appealing extension of the current work is to understand how P&C mechanisms can help in specific applied problems that the literature has previously addressed, such as the efficient allocation of pollution emissions among a fixed set of firms (as Duggan and Roberts (2002)) or the design of a revenue-maximizing auction between one seller and multiple buyers in the presence of externalities (Jehiel et al.

<footnote n="10">¹⁰Another possible extension is to understand how to achieve similar results in incomplete information settings with interdependent preferences (see Ollár and Penta (2022) for recent work in this direction).</footnote>
(1996)).

## References

Aghion, Philippe, Drew Fudenberg, Richard Holden, Takashi Kunimoto, and Olivier Tercieux, “Subgame-perfect implementation under information perturbations,” *Quarterly Journal of Economics*, 2012, 127 (4), 1843–1881.

Barberà, Salvador and Danilo Coelho, “Compromising on compromise rules,” *RAND Journal of Economics*, 2022, 53 (1), 95–112.

Bergstrom, Theodore C., “A fresh look at the rotten kid theorem—and other household mysteries,” *Journal of Political economy*, 1989, 97 (5), 1138–1159.

Brown, Alexander L. and Rodrigo A. Velez, “The costs and benefits of symmetry in common-ownership allocation problems,” *Games and Economic Behavior*, 2016, 96, 115–131.

Camerer, Colin F., Anna Dreber, Eskil Forsell, Teck-Hua Ho, Jürgen Huber, Magnus Johannesson, Michael Kirchler, Johan Almenberg, Adam Altmejd, Taizan Chan et al., “Evaluating replicability of laboratory experiments in economics,” *Science*, 2016, 351 (6280), 1433–1436.

Carroll, Gabriel, “Robustness in mechanism design and contracting,” *Annual Review of Economics*, 2019, 11, 139–166.

Chambers, Christopher P., “Multi-utilitarianism in two-agent quasilinear social choice,” *International Journal of Game Theory*, 2005, 33, 315–334.

— and Jerry R. Green, “Additive rules for the quasi-linear bargaining problem,” 2005. Mimeo, Caltech.

Chen, Yi-Chun, Richard Holden, Takashi Kunimoto, Yifei Sun, and Tom Wilkening, “Getting dynamic implementation to work,” *Journal of Political Economy*, 2023, 131.
____, Takashi Kunimoto, Yifei Sun, and Siyang Xiong, “Maskin meets Abreu and Matsushima,” *Theoretical Economics*, 2022, 17, 1683–1717.

Chiappori, Pierre-André and Bernard Salanié, “The econometrics of matching models,” *Journal of Economic Literature*, 2016, 54 (3), 832–61.

Clarke, Edward, “Multipart pricing of public goods,” *Public choice*, 1971, pp. 17–33.

Crampton, Peter, Robert Gibbons, and Paul Klemperer, “Dissolving a Partnership Efficiently,” *Econometrica*, 1987, 55, 615–632.

Crawford, Vicent P and William P Heller, “Fair division with indivisible commodities,” *Journal of Economic Theory*, 1979, 21 (1), 10–27.

de Clippel, Geoffroy, Kfir Eliaz, and Brian Knight, “On the Selection of Arbitrators,” *American Economic Review*, November 2014, 104 (11), 3434–58.

Duggan, J. and J. Roberts, “Implementing the efficient allocation of pollution,” *American Economic Review*, 2002, 92 (4), 1070–1078.

Dutta, Bhaskar and Arunava Sen, “A necessary and sufficient condition for two-person Nash implementation,” *Review of Economic Studies*, 1991, 58 (1), 121–128.

____, ____, and Rajiv Vohra, “Nash implementation through elementary mechanisms in economic environments,” *Economic Design*, 1995, 1 (1), 173–203.

Eguia, Jon X. and Dimitrios Xefteris, “Implementation by vote-buying mechanisms,” *American Economic Review*, 2021, 111 (9), 2811–28.

Ehlers, Lars, “Choosing wisely: the natural multi-bidding mechanism,” *Economic Theory*, 2009, 39 (3), 505–512.

Fehr, Ernst, Michael Powell, and Tom Wilkening, “Behavioral constraints on the design of subgame-perfect implementation mechanisms,” *American Economic Review*, 2021, 111 (4), 1055–91.
Galichon, Alfred, Scott Duke Kominers, and Simon Weber, “Costly concessions: An empirical framework for matching with imperfectly transferable utility,” *Journal of Political Economy*, 2019, 127 (6), 2875–2925.

Green, Jerry R., “Compensatory Transfers in Two-Player Decision Problems,” *International Journal of Game Theory*, 1993, 33 (2), 159–180.

Groves, Theodore, “Information, incentives, and the internalization of production externalities,” in “Theory and measurement of economic externalities,” Elsevier, 1976, pp. 65–86.

—, “Efficient collective choice when compensation is possible,” *Review of Economic Studies*, 1979, 46 (2), 227–241.

— and John Ledyard, “Optimal allocation of public goods: A solution to the” free rider” problem,” *Econometrica*, 1977, pp. 783–809.

Hurwicz, Leonid, “On the dimensional requirements of informationally decentralized Pareto-satisfactory processes,” *Studies in resource allocation processes*, 1977, pp. 413–424.

— and David Schmeidler, “Construction of outcome functions guaranteeing existence and Pareto optimality of Nash equilibria,” *Econometrica*, 1978, pp. 1447–1474.

Jackson, Matthew, “Implementation in undominated strategies: A look at bounded mechanisms,” *Review of Economic Studies*, 1992, 59 (4), 757–775.

— and Hervé Moulin, “Implementing a public project and distributing its cost,” *Journal of Economic Theory*, 1992, 57 (1), 125–140.

Jehiel, Philippe, Benny Moldovanu, and Ennio Stacchetti, “How (not) to sell nuclear weapons,” *American Economic Review*, 1996, pp. 814–829.

Laslier, Jean-François, Matías Núñez, and M. Remzi Sanver, “A solution to the two-person implementation problem,” *Journal of Economic Theory*, 2021, 194, 105261.
**Legros, Patrick and Andrew F Newman**, "Beauty is a beast, frog is a prince: Assortative matching with nontransferabilities," *Econometrica*, 2007, 75 (4), 1073–1102.

**Maskin, Eric**, "Nash equilibrium and welfare optimality," *Review of Economic Studies*, 1999, 66 (1), 23–38.

**McAfee, R. Preston**, "Amicable divorce: Dissolving a partnership with simple mechanisms," *Journal of Economic Theory*, 1992, 56 (2), 266–293.

**Moore, John and Rafael Repullo**, "Subgame perfect implementation," *Econometrica*, 1988, pp. 1191–1220.

__and__, "Nash implementation: a full characterization," *Econometrica*, 1990, pp. 1083–1099.

**Nicolò, Antonio and Rodrigo A. Velez**, "Divide and compromise," *Mathematical Social Sciences*, 2017, 90, 100–110.

**Ollár, Mariann and Antonio Penta**, "Efficient Full Implementation via Transfers: Uniqueness and Sensitivity in Symmetric Environments," in "AEA Papers and Proceedings," Vol. 112 2022, pp. 438–43.

**Pérez-Castrillo, David and David Wettstein**, "Bidding for the surplus: a non-cooperative approach to the Shapley value," *Journal of Economic Theory*, 2001, 100 (2), 274–294.

**Pérez-Castrillo, David and David Wettstein**, "Choosing wisely: A multibidding approach," *American Economic Review*, 2002, 92 (5), 1577–1587.

**Saijo, Tatsuyoshi, Yoshikatsu Tatamitani, and Takehiko Yamato**, "Toward natural implementation," *International Economic Review*, 1996, pp. 949–980.

**Sjöström, Tomas**, "Implementation by demand mechanisms," *Economic Design*, 1996, 1 (1), 343–354.

**Varian, Hal R.**, "A solution to the problem of externalities when agents are well-informed," *The American Economic Review*, 1994, pp. 1278–1293.
# A Proof of Proposition 4

Let $\sigma = (\sigma_1, \dots, \sigma_n)$ be a subgame-perfect Nash equilibrium. Let $p^i, i = 2, \dots, n$ be the prices set on the equilibrium path. Let $\bar{a}$ be the outcome chosen on the path of play. For notational economy, define the price vectors $p^0$ and $p^{n+1}$ by $p^0(a) = p^{n+1}(a) = 0$ for all $a$.

**Lemma 1.** There exists a unique solution $(\alpha_i, p^i) \in \mathbf{R} \times P, i = 2, \dots, n$, to the system of equations

$$u_i(a) + \eta_i(p^{i+1}(a) - p^i(a)) = \alpha_i \text{ for all } a \in A, i = 2, \dots, n.$$

*Proof.* The system is solved recursively. Denote the solution by $(\alpha_i, p^i)$. Consider player $i$ and suppose that $p^i(a) = p^{i+1}(a)$ are given, with $p^{i+1} = 0 \in P$. Define a function $f_a: \mathbf{R} \to \mathbf{R}$ by

$$f_a(x) = p^i(a) - \eta_i^{-1}(x - u_i(a))$$

for each $a \in A$. Note that $f_a$ is continuous, strictly monotonically decreasing, and that $f_a(\bar{x}) = \bar{x}$. Then there exists $\underline{x}$ and $\bar{x}$ so that $\sum_{a \in A} f_a(\underline{x}) < 0 < \sum_{a \in A} f_a(\bar{x})$. By the intermediate value theorem, there is then $\alpha_i \in (\underline{x}, \bar{x})$ with $\sum_{a \in A} f_a(\alpha_i) = 0$. Define $p^i(a) = f_a(\alpha_i)$ for $a \in A$. Then $p^i \in P$ and $u_i(a) + \eta_i(p^{i+1}(a) - p^i(a)) = \alpha_i$ for all $a \in A$.

Observe that the value of $\alpha_i$ is uniquely determined (given $p^i(a) = p^{i+1}(a)$). Indeed, if there were two, say $\alpha_i$ and $\alpha'_i$ with $\alpha_i < \alpha'_i$, then $p^i(a) = p^i(a) - \eta_i^{-1}(x - u_i(a))$ for $x \in \{\alpha_i, \alpha'_i\}$. Impossible since the right-hand side is strictly monotonic in $x$, and we need the price vector $p^i$ to be in $P$ and thus add to zero.

Finally, $p^i$ is uniquely determined from $p^i(a) = p^{i+1}(a) - \eta_i^{-1}(x - u_i(a))$ for all $a \in A$. $\square$

**Lemma 2.** Fix $i = 1, \dots, n$. Consider a subgame given by the sequence of prices $p^0 = 0, \hat{p}^1, \dots, \hat{p}^i$. Let $p^{i+1}, \dots, p^n$ be the prices, and $\hat{a}$ be the chosen outcome, on the path of $\sigma$ in this subgame. Then $\hat{a}$ maximizes player $i$'s payoff:

$$u_i(\hat{a}) + \eta_i(p^{i+1}(\hat{a}) - \hat{p}^i(\hat{a})) \geq u_i(a) + \eta_i(p^{i+1}(a) - \hat{p}^i(a))$$
for all $a \in A$. And if $i < n$ then $i$ chooses $p^i$ to leave $i+1$ indifferent among all alternatives:

$$u_{i+1}(a) + \eta_{i+1}(p^{i+1}(a) - \hat{p}^i(a)) = \alpha_{i+1},$$

for all $a \in A$, for some $\alpha_{i+1}$.

*Proof.* The proof is by induction. The first statement is obviously true for $i = n$ in any subgame, by definition of Price & Choose. We prove the second statement for $i = n-1$. Suppose (towards a contradiction) that there is $a, a' \in A$ with $u_n(a) + \eta_n(p^{n+1}(a) - p^n(a)) > u_n(a') + \eta_n(p^{n+1}(a') - p^n(a'))$, then

$$u_n(\hat{a}) + \eta_n(p^{n+1}(\hat{a}) - p^n(\hat{a})) \ge u_n(a) + \eta_n(p^{n+1}(a) - p^n(a)) \\ > u_n(a') + \eta_n(p^{n+1}(a') - p^n(a')).$$

Player $n-1$ may then increase the price of $\hat{a}$ by $\varepsilon$ while increasing the price of the other outcomes in $\arg\max\{u_n(a) + \eta_n(p^{n+1}(a) - p^n(a)) : a \in A\}$ by more than $\varepsilon$ and compensating for these increases by decreasing the price of $a'$. The resulting price vector would be in $P$; when $\varepsilon > 0$ is small enough, the unique optimal choice for $n$ would be $\hat{a}$, but the price received by $n-1$ would be strictly higher as well as the corresponding payoff. A contradiction as $\sigma$ is a SPNE.

Suppose now that both statements are true for any subgame in which the first mover is one of the players $i+1, \dots, n$. We first show the second statement for player $i$. The argument is the same as earlier: player $i$ can otherwise increase the price of $\hat{a}$ so that it is the uniquely optimal outcome for the next player. By the inductive hypothesis, $\hat{a}$ would still be chosen in the resulting subgame but at a larger price received by $i$. This would contradict that $p^{i+1}$ is chosen in the subgame-perfect equilibrium.

Finally, we turn to proving the first statement for player $i$. Suppose, towards a contradiction, that there is $a \in A$ with:

$$u_i(a) + \eta_i(p^{i+1}(a) - \hat{p}^i(a)) > u_i(\hat{a}) + \eta_i(p^{i+1}(\hat{a}) - \hat{p}^i(\hat{a})),$$

where $p^{i+1}$ is the price indicated by $\sigma_i$ in the subgame. Then $i$ may increase the price to $i+1$ of the outcome $\hat{a}$, and decrease the price of $a$, so that the payoff to $i$ from
outcome *a* remains higher than that of *â*. We have seen that *i* + 1 was indifferent between all options at the prices *p*<sup>*i*+1</sup>. The modified prices would then give *i* + 1 strictly higher utility from choosing *a* than any other outcome. By the inductive hypothesis, then, *a* would be the outcome in the subgame resulting from *i* modified price vector. But this would be a profitable deviation from *σ* by *i*; a contradiction. ☐

We proceed to prove Proposition 4. Suppose (towards a contradiction) that there is $\tilde{a} \in A$ and $m_1, \dots, m_n$ with $\sum m_i = 0$ so that $u_i(\tilde{a}) + \eta_i(m_i) \ge u_i(\bar{a}) + \eta_i(p^{i+1}(\bar{a}) - p^i(\bar{a}))$ with a strict inequality for at least one agent $i$. Since the $\eta_i$ are continuous and strictly increasing, this means we can take $\tilde{a}$ and $m_1, \dots, m_n$ to satisfy $u_i(\tilde{a}) + \eta_i(m_i) > u_i(\bar{a}) + \eta_i(p^{i+1}(\bar{a}) - p^i(\bar{a}))$ for all $i$.

Let $\tilde{p}^i \in P$ be such that $m_i = \tilde{p}^{i+1}(\tilde{a}) - \tilde{p}^i(\tilde{a})$. Such prices exist because we can take $\tilde{p}^n(\tilde{a}) = -m_n$, and $\tilde{p}^i(\tilde{a}) = -\tilde{p}^{i+1}(\tilde{a}) - m_i$ for all $i = 2, \dots, n-1$. Then $\tilde{p}^2(\tilde{a}) = -\sum_{j=2}^n m_j = m_1$. For $a \ne \tilde{a}$ we define prices arbitrarily to ensure that $\tilde{p}^i \in P$. Again we define $\tilde{p}^{n+1} = 0$.

First note that for $i = 2, \dots, n$

$$
\begin{align*}
u_i(\tilde{a}) + \eta_i(\tilde{p}^{i+1}(\tilde{a}) - \tilde{p}^i(\tilde{a})) &= u_i(\tilde{a}) + \eta_i(m_i) \\
&> u_i(\tilde{a}) + \eta_i(p^{i+1}(\tilde{a}) - p^i(\tilde{a})) \\
&= u_i(\tilde{a}) + \eta_i(p^{i+1}(\tilde{a}) - p^i(\tilde{a})),
\end{align*}
$$

here the second equality follows from the indifference property of any SPNE that we
have shown in Lemma 2.

Thus

$$
\tilde{p}^{i+1}(\tilde{a}) - \tilde{p}^i(\tilde{a}) > p^{i+1}(\tilde{a}) - p^i(\tilde{a}) \implies p^i(\tilde{a}) - \tilde{p}^i(\tilde{a}) > p^{i+1}(\tilde{a}) - \tilde{p}^{i+1}(\tilde{a}),
$$

as $\eta_i$ is strictly monotonically increasing. We have $p^{n+1} = \tilde{p}^{n+1} = 0$, so recursively we
see that $\tilde{p}^i(\tilde{a}) < p^i(\tilde{a})$ for all $i$. This means that $\tilde{p}^2(\tilde{a}) < p^2(\tilde{a})$.

As a consequence,

$$
u_1(\tilde{a}) + \eta_1(\tilde{p}^2(\tilde{a})) < u_1(\tilde{a}) + \eta_1(p^2(\tilde{a})) \le u_1(\tilde{a}) + \eta_1(p^2(\tilde{a})),
$$
where the last inequality follows because the selected $\bar{a}$ in SPNE maximizes the pay-
off of the first mover in any subgame, as shown in Lemma 2, in contradiction to the
assumption that alternative $\bar{a}$ and transfer $m_1$ is preferred by Player 1 to alternative
$\bar{a}$ with transfer $p^2(\bar{a})$.