# Non-Obvious Manipulability for Single-Parameter Agents and Bilateral Trade

Thomas Archbold Bart de Keijzer Carmine Ventre  King’s College London
<EMAIL_ADDRESS>

###### Abstract

A recent line of work in mechanism design has focused on guaranteeing
incentive compatibility for agents without contingent reasoning skills:
_obviously strategyproof mechanisms_ [20] guarantee that it is “obvious” for
these imperfectly rational agents to behave honestly, whereas _non-obviously
manipulable_ (NOM) mechanisms [26] take a more optimistic view and ensure that
these agents will only misbehave when it is “obvious” for them to do so.
Technically, obviousness requires comparing certain extrema (defined over the
actions of the other agents) of an agent’s utilities for honest behaviour
against dishonest behaviour.

We present a technique for designing NOM mechanisms in settings where monetary
transfers are allowed based on _cycle monotonicity_ , which allows us to
disentangle the specification of the mechanism’s allocation from the payments.
By leveraging this framework, we completely characterise both allocation and
payment functions of NOM mechanisms for single-parameter agents. We then look
at the classical setting of bilateral trade and study whether and how much
subsidy is needed to guarantee NOM, efficiency, and individual rationality. We
prove a stark dichotomy; no finite subsidy suffices if agents look only at
best-case extremes, whereas no subsidy at all is required when agents focus on
worst-case extremes. We conclude the paper by characterising the NOM
mechanisms that require no subsidies whilst satisfying individual rationality.

##  1 Introduction

The prevailing solution concept in mechanism design is dominant-strategy
incentive-compatibility, otherwise known as strategyproofness, which
stipulates that for any joint strategy of the other agents, a given agent
always weakly prefers to act truthfully than to act dishonestly. The canonical
example of such a mechanism is the second-price sealed-bid auction, in which
it is always in an agent’s best interests to submit her true valuation for the
item to the auctioneer. While this is appealing from a theoretical standpoint
it relies on the assumption that the players of the game act perfectly
rationally, meaning they are able to correctly reason about the behaviour of
the other players as well as solve an optimisation problem to identify an
optimal strategy. This places a high cognitive or temporal burden on the
player and it can be unrealistic to assume this is how they act in the real
world.

Empirical evidence in fact shows that people facing mechanisms that are not
strategyproof might fail to understand that lying is beneficial. Examples
include mechanisms both with and without monetary transfers. The Deferred
Acceptance Algorithm, used in many countries to allocate doctors to hospitals,
is known to perform well in practice and produce stable outcomes, even though
hospitals could lie and hire better candidates [25]. Uniform-price auctions
are a natural generalisation of second-price auctions to the multi-unit case:
with a supply of $k$, they charge the winners the $(k+1)$-th highest bid for
each unit received. Variants of uniform-price auctions are used by search
engines to charge for sponsored ad slots and governments to sell bonds. These
auctions are famously not strategyproof and yet there is little evidence that
bidders cheat in practice [17]. On the other hand, there are manipulable
mechanisms where people can easily figure out a way to lie profitably: the
Boston Mechanism for school choice is known to be manipulable [23] and
empirical data shows evidence of misreports [9]. Similarly, there is evidence
of bid shading in pay-as-bid multi-unit auctions [6].

Motivated by these observations, Troyan and Morrill [26] study _non-obvious
manipulability_ , an alternative solution concept to strategyproofness for
cognitively limited agents. Under this relaxation of strategyproofness, simply
referred to as NOM, a mechanism is allowed to be vulnerable to certain types
of manipulations, specifically those which are harder to identify by agents
with bounded rationality. Instead of requiring the truthful action for each
agent $i$ to be a dominant strategy at each possible interaction of the player
with the mechanism, under non-obvious manipulability we need only to compare
best-case utilities for truthful outcomes (i.e., maximum, over the reports of
the other agents, utility for $i$ when she is truthful) to best-case utilities
for dishonest outcomes, _and_ similarly to compare worst-case utilities for
truthful outcomes to worst-case utilities for dishonest outcomes. This is
justified under the assumption that cognitively-limited agents can only
identify this type of _obvious_ manipulation, where the agents need only to
compare the extremes of her utility function.

In this paper we study NOM mechanisms that use monetary transfers. We have a
threefold aim: we want to (i) understand which restrictions NOM imposes on the
allocation function; (ii) characterise both allocation functions and payments
for the large class of single-parameter agents; and, (iii) assess the power of
NOM mechanisms for double-sided markets. We focus on the class of direct-
revelation mechanisms111Whether extensive-form NOM mechanisms are more
powerful than direct-revelation ones is an open problem. as in [26] and
develop both conceptual and technical tools to obtain answers against each of
these desiderata.

###  1.1 Our Contribution

In order to understand whether NOM is too permissive a solution concept in
terms of allocation functions, we take a careful look at the constraints that
NOM somewhat intrinsically imposes. Given an allocation function and payments
to augment it, NOM requires that truthtelling yields a greater utility than
misreporting for best- and worst-case outcomes. Indirectly, this means that
the utility for all the remaining outcomes is in between these best and worst
utilities. In other words, the set of incentive-compatibility constraints that
one ought to satisfy _depends on the actual payments and allocation function_
since they define the maximum and minimum utilities.

This is quite dissimilar from classic strategyproofness where the set of
constraints is independent from the components of the mechanism, but somewhat
closer to the twin solution concept of obvious strategyproofness (OSP) [20].
Differently from NOM, OSP requires truthtelling to be “obvious” over lying. It
turns out that the obviousness of being honest is captured by the extensive-
form implementation of the mechanism, which in turn implies that the set of
OSP incentive-compatibility constraints depends on this component of the
mechanism. This dependence for OSP is successfully handled in [11] via a
generalisation of the classical cycle-monotonicity technique for
strategyproofness [24].

As a first contribution of this work, we abstract the NOM dependency in terms
of what we call _labellings_ and extend the cycle monotonicity technique to
NOM. Informally, a labelling is a choice of profiles defining the best and
worst outcomes that the mechanism will define through its allocation and
payments. Given a labelling, we can identify two sets of constraints: (i) NOM
incentive-compatibility constraints between the given labels, and (ii)
labelling-induced constraints, that enforce the validity of the labels.
Similarly to previous work on cycle monotonicity, we define a weighted graph
$G_{i,f}^{\lambda}$ encoding these constraints for each player $i$, given the
allocation function $f$ and labelling $\lambda$. We prove that the existence
of payments guaranteeing the constraints is related to the cycles of this
graph.

Theorem 1 (informal). An allocation function $f$ is NOM implementable if and
only if there exists a labelling $\lambda$ such that no $G_{i,f}^{\lambda}$
has negative-weight cycles.

This result provides a powerful tool to study the class of allocation
functions for which one can find payments leading to NOM mechanisms. As a case
in point we apply our cycle monotonicity framework to the well-studied class
of single-parameter agents, in which each agent $i$ has a private type that is
described by a single number $t_{i}$. Her utility for the bid profile
$(x_{i},x_{-i})$ is the sum of the payment she receives from the mechanism and
her _valuation_ for the output she receives from the allocation function on
this bid profile; this valuation can be expressed as the product of $t_{i}$
and $f_{i}(x_{i},x_{-i})$. We observe that negative weight cycles in the graph
exist when the labels are antimonotone, meaning that, given two types $x_{i}$
and $x_{i}^{\prime}$ with $x_{i}<x_{i}^{\prime}$ from the _domain_ (also known
as type space) of player $i$, $f$ allocates more to agent $i$ for the label
corresponding to $x_{i}$ than it does for the label corresponding to
$x_{i}^{\prime}$. We then prove that a _monotone labelling_ guarantees no
negative-weight cycles and is possible whenever the image of $f_{i}$ is rich
enough. Specifically, we say that $f$ is _overlapping_ if for each agent $i$
and pair of types $x_{i},x_{i}^{\prime}$ the sets
$\\{f_{i}(x_{i},x_{-i})\\}_{x_{-i}}$ and
$\\{f_{i}(x_{i}^{\prime},x_{-i})\\}_{x_{-i}}$ have a non-empty intersection.

Theorem 2 (informal). An allocation function $f$ is NOM implementable for
single-parameter agents if and only if $f$ is overlapping.

Essentially, our second main contribution proves that as long as the labels
define a monotone restriction of the allocation function $f$ then there are
payments such that $f$ is part of a NOM mechanism for single-parameter agents.
This uncovers a connection with strategyproof mechanisms for single-parameter
agents, which allows us to also characterise the payment functions that NOM
mechanisms ought to use in this case. For strategyproof mechanisms $f$ must be
monotone for each fixed $x_{-i}$, and given this property it is known the form
payments must take [1]. We then observe that we can use the very same payments
along the monotone restriction defined by the labels, whilst we can easily
characterise the payments for the remaining profiles.

This result gives a complete picture on the power of NOM mechanisms for
single-parameter agents. We then ask if this finding can help assess the power
of NOM mechanisms for double-sided markets, where both sides of the market
consist of selfish agents. These markets are widespread but are notoriously
too complex for strategyproofness. We wonder whether the relaxation from no
manipulability at all to non-obvious manipulability can help in this context.
We study the classical setting of bilateral trade, in which a single item is
to be sold by a (strategic) seller who has a production cost for the item, to
a (strategic) buyer who has a valuation for the item. We want to guarantee
efficiency – trade occurs only when the buyer’s valuation is at least the
seller’s production cost –, weak budget balance (WBB) – upon trade, the buyer
pays more than the seller receives – and, individual rationality (IR) – the
quasi-linear utilities of both buyer and seller are non-negative. We know
already that NOM cannot simultaneously guarantee these three properties [26].
We here ask the extent to which a subsidy of $\alpha$, guaranteeing that the
buyer pays at least a fraction 1/$\alpha$ of the payment that the seller
receives upon trade (a.k.a., $\alpha$-WBB), would allow to obtain NOM,
efficiency and IR.

Theorem 3 (informal). Any NOM, IR and $\alpha$-WBB mechanism for bilateral
trade has unbounded $\alpha$.

The proof of this theorem actually highlights a more fine grained and
dichotomous state of affairs. The toolkit developed to prove our first two
main theorems can independently handle best-case labels (BNOM) and worst-case
labels (WNOM). We use our result for single-parameter agents to characterise
the monotone restriction of an allocation function $f$ guaranteeing efficiency
and BNOM (WNOM, respectively) for both the buyer and the seller. We prove that
the incentive-compatibility constraints for the monotone BNOM restriction
immediately yields unbounded $\alpha$ as we can conclude by our explicit
payment formula that the buyer pays $0$ for each of her best labels whereas
the seller needs to receive a positive payment for all of her best labels. For
WNOM, instead we observe that whilst incentive compatibility does not require
infinite subsidies, the infinite $\alpha$ is implied by the validity
constraints for the worst labels.

We can in fact shed further light on subsidies for BNOM and WNOM,
respectively. A technicality about the strategyproofness-inspired explicit
payment formulae is crucial here. Once $f$ is overlapping then the monotone
restriction of $f$ is only one possible way of guaranteeing BNOM and WNOM;
this choice in fact restricts to a _single line_ the labels used the
mechanisms. Can alternative labels lead to different payments satisfying IR
and finite subsidies for an overlapping and efficient $f$? The answer is more
surprising; non-single line BNOM mechanisms continue to require infinite
subsidies whereas non-single line WNOM mechanisms can actually guarantee WBB
(i.e., $\alpha=1$ and no subsidies). There exists in fact a definition of
worst labels that implement first-price auctions; it is not hard to see that
these auctions are WNOM.

We also show that we can further strengthen the incentive-compatibility
property on either side of the market to strategyproofness, e.g., the buyer
being strategyproof and the seller being WNOM, by combining first-price
auction for one side (seller in the example) and second-price auction for the
other (buyer in the example). Interestingly, this hybrid solution would leave
the spread (difference between the bids) to the market designer whereas a
fully WNOM bilateral trade (where both payments equal the bid) would be budget
balanced. We consider this result to be of significance for some classes of
double-sided markets, where the rationality is asymmetric and depends on the
role played in the market. This asymmetry might be useful to the market
designer in terms of gain from trade.

Finally, we conclude our paper by characterising individually rational NOM
mechanisms that might be inefficient but require no subsidies. Intuitively,
this result says that there exist trading windows defined by payment
thresholds that partition the domain of buyer and seller into three sets; bids
guaranteeing that the trade occurs, bids guaranteeing that the trade will not
occur, and bids where the decision to trade depends on the bid at the other
side of the market.

###  1.2 Related Work

There has been a growing body of work in the algorithmic mechanism design
literature that studies agents with bounded rationality. The aforementioned
notion of obvious strategproofness (OSP) was introduced by Li [20] to study
the setting in which agents lack contingent reasoning skills. Li characterises
OSP mechanisms as those in which agents lack the ability to reason contingent
upon unobserved events (such as concluding that a truthful bid is optimal in a
second-price sealed-bid auction), or those in which a mechanism may not be
able to commit to all outcomes. OSP is a more stringent solution concept than
strategyproofness and provides stronger incentive guarantees, thus OSP
mechanisms are harder to construct than strategyproof ones. Where the
Revelation Principle allows us to restrict our attention to direct mechanisms
for strategyproofness, the same is not true for OSP: the extensive-form
implementation of the mechanism is crucial to a mechanism’s obvious
strategyproofness. The relationship between the extensive-form implementation
and the allocation function of OSP mechanisms is studied in [11], where
together with the introduction of the cycle monotonicity variant for OSP
mechanisms with transfers, the authors give some bounds on the approximation
guarantee of these mechanisms for scheduling related machines. Binary
allocation problems are then studied in [10] first for single-parameter agents
with small domains and more recently in [12] for the general case. Further OSP
mechanisms using some form of verification power of the mechanism designer are
given in [15, 13, 18]. OSP mechanisms for combinatorial auctions with single-
minded bidders are given in [7]. Relaxations of OSP that interpolate between
OSP and strategyproofness are studied in [14].

Troyan and Morrill [26] consider agents with bounded rationality from the
opposite perspective and introduce the concept of non-obvious manipulability
(NOM) to study the types of manipulations available to a cognitively limited
agent. In contrast to OSP, where the worst-case truthful outcome must be at
least as good as the best-case dishonest outcome, NOM stipulates that both the
best- and worst-case truthful outcomes are no worse than the best- and worst-
case dishonest outcomes, respectively. They provide a characterisation of NOM
in the context of direct mechanisms and classify existing mechanisms as either
obviously manipulable (OM) or NOM in the settings of school choice, two-sided
matching, and auctions. They show, similarly to [20], that a manipulation is
obvious if and only if it can be recognised by a cognitively limited agent.
They go on to characterise OM matching mechanisms as ones which are either
stable or which Pareto-dominate a stable mechanism, and moreover show that all
stable mechanisms are individually rational, Pareto efficient, and NOM. For
the case of auctions they show that a generalisation of the second-price
single-item auction is NOM, the double auction for bilateral trade is OM, and
finally that every efficient, individually rational, and weakly budget
balanced mechanism for bilateral trade is OM.

There have been few papers that build directly on [26] so far. Aziz and Lam
[2] study NOM in the context of voting rules and provide conditions under
which certain rules and classes of rules are NOM. They show that certain rules
are OM if the number of outcomes is large relative to the number of voters.
They also look at how to compute such manipulations and present algorithms
based on polynomial-time reductions to the Constructive Coalitional Unweighted
Manipulation problem. These yield polynomial-time algorithms for computing
obvious manipulations under the $k$-approval voting rule. Ortega and Segal-
Halevi [22] study NOM and indirect mechanisms in the context of cake-cutting
and show that the conflict between truthtelling and fairness is resolved when
relaxing strategyproofness to NOM. They show that NOM is compatible with the
notion of proportionality, in which each agent receives an equal portion of
the cake, and that both of these properties are satisfied by a discrete
adaptation of the moving knife mechanism. Like [20], they note how incentive
properties may vary between theoretically equivalent mechanisms for agents
with bounded rationality.

##  2 Preliminaries

We consider mechanism design settings with the possibility of monetary
transfers. There is a set of $n$ _agents_ , where each agent $i$ has a certain
_type_ $t_{i}$ that comes from a type set $D_{i}$ also called _domain_. We let
$D=\times_{i\in[n]}D_{i}$ be the set of _type profiles_. There is furthermore
a set of possible _outcomes_ $O$, and the type of an agent specifies for each
outcome to what extent the agent values it. Thus, a type is a function mapping
outcomes to real numbers. For a type profile $t=(t_{1},t_{2},\ldots,t_{n})$,
player $i$, and type $x_{i}\in D_{i}$, we use the standard notation
$(x_{i},t_{-i})$ to denote the type profile obtained from $t$ by replacing
$t_{i}$ by $x_{i}$. We furthermore define $D_{-i}$ as
$\times_{j\in[n]\setminus\\{i\\}}D_{j}$.

The agents interact with a _mechanism_ $\mathcal{M}$ that solicits from the
agents their types. The mechanism selects, based on the agents’ reports, an
outcome and a payment for each agent. We may thus view $\mathcal{M}$ as a
function mapping $D$ to $O\times\mathbb{R}^{n}$. Agents are assumed to report
so as to maximise their _utility_ , and the agents’ utility functions are
standard quasi-linear ones: for an agent $i$, the output $(o,p)$ of the
mechanism results in a utility of $t_{i}(o)+p_{i}$. We overload the notation
and denote the utility of agent $i$ under $(o,p)$ by $t_{i}(o,p)$.

A _social choice function_ $f:D\to O$ is a function that maps some input $x$
from some domain $D$ to an arbitrary outcome $f(x)\in O$. We say that a
mechanism $\mathcal{M}$ _implements_ a given social choice function $f$ iff
for all $t\in D$, the outcome returned by $\mathcal{M}(t)$ is equal to $f(t)$.

Note that each player $i$’s type $t_{i}$ is private information and they may
therefore submit a misreport $x_{i}\neq t_{i}$ to a mechanism in an attempt to
gain a more favourable outcome. In this paper we are interested in finding,
for a given social choice function $f$, a mechanism $\mathcal{M}$ implementing
$f$ such that $\mathcal{M}$ is not obviously manipulable (NOM) by any of the
agents; we define this property precisely later in this section. This
objective boils down to finding an appropriate payment function
$p:D\rightarrow\mathbb{R}^{n}$ for $\mathcal{M}$ such that $\mathcal{M}=(f,p)$
is a mechanism that satisfies the NOM property.

We will in particular consider the setting where $O$ is a vector of length
$n$, and where the type of an agent $i$ is a function that is only dependent
on the $i$’th coordinate of the the outcome vector. In this case, we call the
outcomes _allocations_ , and we refer to the social choice function as an
_allocation function_. Restricting the social choice function to an allocation
function is clearly without any loss of generality, and is done purely for
interpretational purposes, since we mainly focus on auction settings in which
the mechanism assigns some object to each agent and an agent’s type describes
the utility she gets from that allocation.

The prevailing solution concept in mechanism design is that of
strategyproofness: a mechanism $\mathcal{M}$ is _strategyproof_ iff
$t_{i}(\mathcal{M}(t_{i},x_{-i}))\geq t_{i}(\mathcal{M}(x_{i},x_{-i}))$ for
all agents $i$, all $x\in D$, and all $t_{i}\in D_{i}$. Troyan and Morrill
[26] define NOM, which is a relaxation of strategyproofness, informally stated
as follows: a manipulation is defined as _obvious_ if either the best-case
dishonest outcome is strictly greater than the best-case truthful one, or if
the worst-case dishonest outcome is strictly greater than the worst-case
truthful one. Here, best-case and worst-case are defined with respect to the
type profile of all agents excluding $i$. Formally stated, mechanism
$\mathcal{M}$ is _best-case non-obviously manipulable (BNOM)_ if:

$\sup_{x_{-i}}\\{t_{i}(\mathcal{M}(t_{i},x_{-i}))\\}\geq\sup_{x_{-i}}\\{t_{i}(\mathcal{M}(x_{i},x_{-i}))\\}$
(1)

for all $t_{i},x_{i}\in D_{i}$ and for all players $i$. Similarly
$\mathcal{M}$ is _worst-case non-obviously manipulable (WNOM)_ if:

$\inf_{x_{-i}}\\{t_{i}(\mathcal{M}(t_{i},x_{-i}))\\}\geq\inf_{x_{-i}}\\{t_{i}(\mathcal{M}(x_{i},x_{-i}))\\}$
(2)

Mechanism $\mathcal{M}$ is _non-obviously manipulable (NOM)_ if it is both
BNOM and WNOM. If either inequality does not hold then $x_{i}$ is an obvious
manipulation of $\mathcal{M}$. We study the conditions under which we may
endow an obviously manipulable social choice function $f$ with payments $p$ to
achieve a mechanism $(f,p)$ that is non-obviously manipulable. If this is
possible then we will call $f$ NOM-implementable, with analogous definitions
for BNOM- and WNOM-implementability.

We consider several additional mechanism properties in our analysis. A
mechanism $\mathcal{M}=(f,p)$ is _individually rational (IR)_ if
$t_{i}(\mathcal{M}(t_{i},x_{-i}))\geq 0$ for all $t_{i},x_{i}\in D_{i}$,
$x_{-i}\in D_{-i}$, for each player $i$, and makes _no positive transfers
(NPT)_ if for all $p_{i}(x)\leq 0$ for all $x\in D$. In Section 5 we will also
study efficiency and budget-balance in the context of bilateral trade, which
we will define when needed.

We will often need to reference specific types from a player $i$’s domain. In
this case we will enumerate the types in the domain as
$t_{1},t_{2},\ldots,t_{d}$, and when we focus on single-parameter agents, we
will treat types as scalar multipliers rather than functions, and assume that
$t_{1}<t_{2}<\ldots<t_{d}$. We conclude this section by noting that NOM is a
strict relaxation of strategyproofness.

######  Theorem 2.1.

If mechanism $\mathcal{M}$ is strategyproof then it is also NOM.

###### Proof.

We will prove the claim by showing that if $\mathcal{M}$ is strategyproof then
it is both BNOM and WNOM, starting with the former. Fix player $i$ with type
$t_{i}$. By strategyproofness we have $t_{i}(\mathcal{M}(t_{i},x_{-i}))\geq
t_{i}(\mathcal{M}(x_{i},x_{-i}))$ for all $t_{i},x_{i}\in D_{i}$ and for all
$x_{-i}$. Assume for contradiction that $\mathcal{M}$ is obviously manipulable
in the best case, so
$\sup_{x_{-i}}\\{t_{i}(\mathcal{M}(x_{i},x_{-i}))\\}>\sup_{x_{-i}}\\{t_{i}(\mathcal{M}(t_{i},x_{-i}))\\}$
for some manipulation $x_{i}$. Let
$\hat{x}_{-i}\in\arg\sup\\{t_{i}(\mathcal{M}(x_{i},x_{-i}))$ denote the bid
profile leading to $i$’s best-case dishonest utility. Then

$t_{i}(\mathcal{M}(t_{i},\hat{x}_{-i}))\geq
t_{i}(\mathcal{M}(x_{i},\hat{x}_{-i}))>\sup_{x_{-i}}\\{t_{i}(\mathcal{M}(t_{i},x_{-i}))\\}$

and thus $t_{i}(\mathcal{M}(t_{i},\hat{x}_{-i}))$ is strictly greater than the
maximum utility $i$ gets when bidding $t_{i}$ truthfully, a contradiction. We
can arrive at a similar contradiction to show that $\mathcal{M}$ is also WNOM.
Let $\hat{x}_{-i}\in\arg\inf\\{t_{i}(\mathcal{M}(x_{i},x_{-i}))\\}$ be the bid
profile leading to $i$’s worst-case dishonest utility. So

$\inf_{x_{-i}}\\{t_{i}(\mathcal{M}(x_{i},x_{-i}))\\}>t_{i}(\mathcal{M}(t_{i},\hat{x}_{-i}))\geq
t_{i}(\mathcal{M}(x_{i},\hat{x}_{-i}))$

meaning $t_{i}(\mathcal{M}(x_{i},\hat{x}_{-i}))$ is strictly less than the
worst-case dishonest utility of player $i$. Thus strategyproof $\mathcal{M}$
is also NOM. ∎

##  3 Labellings

The extra flexibility of NOM mechanisms as opposed to strategyproof ones
enables a useful technique for designing them. While strategyproofness
requires satisfying a constraint on each pair of bid profiles $(x_{i},x_{-i})$
and $(x_{i}^{\prime},x_{-i})$ for every $x_{i},x_{i}^{\prime}\in D_{i}$ and
every $x_{-i}\in D_{-i}$, for NOM we may attempt, as a designer, to “choose”
for each player $i$ and type $t_{i}$ which two profiles of the opposing
players will lead to the best- and worst-case outcomes respectively; we need
then only satisfy the respective BNOM and WNOM constraints for those chosen
profiles. We model this concept with objects that we will call _labellings_.
These are simply designations of the type profiles that lead to an agent’s
best- and worst-case outcomes in $\mathcal{M}$ according to her true type and
what she reports.

Fix a player $i$ and let $d=|D_{i}|$ denote the size of their domain. The
_best-case and worst-case labellings_ respectively are the matrices
$\beta,\omega\in D_{-i}^{d\times d}$ in which

$\displaystyle\beta_{jk}\in\arg\sup_{x_{-i}}\\{t_{j}(\mathcal{M}(t_{k},x_{-i}))\\}$
$\displaystyle\omega_{jk}\in\arg\inf_{x_{-i}}\\{t_{j}(\mathcal{M}(t_{k},x_{-i}))\\},$

so that the entries at row $j$ and column $k$ denote the profile in $D_{-i}$
achieving the greatest and least utilities that can potentially be obtained by
player $i$ when reporting $t_{k}$ under the assumption that $i$ has type
$t_{j}$. Given a label $\lambda_{jk}$ for $\lambda\in\\{\beta,\omega\\}$ we
will sometimes write $\lambda_{jk}$ to denote the entire profile
$(t_{k},\lambda_{jk})$.

Originally introduced by Rochet [24] cycle monotonicity has been used for the
design of incentive-compatible mechanisms in various settings, including
truthful mechanisms for multidimensional scheduling [19], truthful mechanisms
with verification [27], and obviously strategyproof mechanisms [11], among
others. We will adapt this approach to our setting by using the labellings
$\beta,\omega$ to construct a graph for each player which we will then use to
characterise which social choice functions and labellings lead to NOM
mechanisms.

For a given player $i$, social choice function $f$, and labellings
$\beta,\omega$ of $\mathcal{M}$ for player $i$ we will define two directed
weighted multi-graphs $G_{i,f}^{\beta}=(V,E^{\beta},w)$ and
$G_{i,f}^{\omega}=(V,E^{\omega},w)$. Both graphs have the same node set which
is simply the set of all type profiles, i.e. $V=D$, and we represent edges as
a tuple $(x,y;t)$ where $x,y\in V$ and $t\in D_{i}$ can be thought of as an
annotation that is used to calculate an edge’s weight. Specifically an edge in
either graph is defined to have weight $w(x,y;t)=t(f(x))-t(f(y))$. We will
also use $x\rightarrow^{t}y$ to denote edges and paths in these graphs.

The edge sets $E^{\beta}$ and $E^{\omega}$ differ slightly in their
definitions but represent the same thing – given an edge $(x,y;t)$, the
utility of player $i$ on output $\mathcal{M}(x)$ is at least the utility on
output $\mathcal{M}(y)$ when she has type $t\in D_{i}$. From the labellings
$\beta,\omega$ arise two sets of constraints which we will call _labelling
constraints_ and _incentive-compatibility (IC) constraints_. For the former,
if a particular node $v$ of the graph is a label in $\beta$, say
$v=\beta_{jk}$, then when $i$ has type $t_{j}$ and bids $t_{k}$, her utility
on outcome $\mathcal{M}(t_{k},\beta_{jk})$ must be at least her utility on
outcome $\mathcal{M}(t_{k},x_{-i})$ for all $x_{-i}$. Hence there must be an
edge $(t_{k},\beta_{jk})\rightarrow^{t_{j}}(t_{k},x_{-i})$ for all $x_{-i}$
which represents the constraint $t_{j}(\mathcal{M}(t_{k},\beta_{jk}))\geq
t_{j}(\mathcal{M}(t_{k},x_{-i}))$ that is implicit in the definition of BNOM.
The same is true for labelling constraints for the worst-case labelling
$\omega$, but in this case there is an incoming (rather than outgoing) edge
$(t_{k},x_{-i})\rightarrow^{t_{j}}(t_{k},\omega_{jk})$ for every $x_{-i}$ and
each $\omega_{jk}$. The IC constraints represent the explicit constraints that
arise from NOM, which requires that best- and worst-case truthful outcomes are
no worse than best- and worst-case dishonest ones.

In short, labelling constraints designate a profile as leading to the best- or
worst-case outcome for $i$, while IC constraints ensure the requirements for
NOM are met. The formal definitions of these edge sets are given in (3) and
(4). Note that, given a type $t_{j}\in D_{i}$ and labelling
$\lambda\in\\{\beta,\omega\\}$ for player $i$, all edges corresponding to a
labelling constraint for $\lambda$ are contained in the subgraph of
$G_{i,f}^{\lambda}$ in which all nodes are of the form $(t_{j},x_{-i})$, i.e.
profiles in which $i$ reports type $t_{j}$ to the mechanism. When talking
about these edges we will refer to them as edges in the “$j$-island” of
$G_{i,f}^{\lambda}$. The edges representing the IC constraints are then
exactly those edges which cross from the $j$-island to the $k$-island of
$G_{i,f}^{\lambda}$ for any two types $t_{j},t_{k}\in D_{i}$.

$\displaystyle
E^{\beta}=\\{(t_{j},\beta_{ij})\rightarrow^{t_{i}}(t_{j},x_{-k})\,:\,t_{i},t_{j}\in
D_{i},x_{-k}\in
D_{-k}\\}\cup\\{(t_{i},\beta_{ii})\rightarrow^{t_{i}}(t_{j},\beta_{ij})\,:\,t_{i},t_{j}\in
D_{k}\\}$ (3) $\displaystyle
E^{\omega}=\\{(t_{j},x_{-k})\rightarrow^{t_{i}}(t_{j},\omega_{ij})\,:\,t_{i},t_{j}\in
D_{i},x_{-k}\in
D_{-k}\\}\cup\\{(t_{i},\omega_{ii})\rightarrow^{t_{i}}(t_{j},\omega_{ij})\,:\,t_{i},t_{j}\in
D_{k}\\}$ (4)

With the graph thus defined we use the cycle-monotonicity technique to derive
a necessary and sufficient condition for the NOM-implementability of a social
choice function based on the structure of the graph. We note that the proof of
necessity follows standard reasoning used in the literature, while the proof
of sufficiency is similar though requires some additional work. Moreover, this
characterisation only holds for finite domains as the argument requires
reasoning about shortest paths in $G_{i,f}^{\lambda}$, which are undefined in
infinite graphs.

######  Theorem 3.1.

Social choice function $f$ is:

  * •

BNOM-implementable if and only if for each agent $i$ there exists a best-case
labelling $\beta$ such that $G_{i,f}^{\beta}$ contains no negative weight
cycles.

  * •

WNOM-implementable if and only if for each agent $i$ there exists a worst-case
labelling $\omega$ such that $G_{i,f}^{\omega}$ contains no negative weight
cycles.

###### Proof.

We will prove the claim for WNOM and note that the proof for BNOM follows
identical reasoning.

($\implies$) Suppose payments $p$ exist such that $(f,p)$ is WNOM. Fix player
$i$ and assume for contradiction that every choice of $\omega$ induces a
negative weight cycle in $G_{i,f}^{\omega}$. Let $C=\langle
x^{(1)}\rightarrow^{t_{1}}x^{(2)}\rightarrow^{t_{2}}\ldots\rightarrow^{t_{k-1}}x^{(k)}\rightarrow^{t_{k}}x^{(1)}\rangle$
be such a cycle with
$w(C)=w(x^{(1)},x^{(2)};t_{1})+\ldots+w(x^{(k)},x^{(1)};t_{k})<0$. Since $f$
is WNOM-implementable then the inequality encoded by each edge is satisfied:

$\displaystyle t_{1}(f(x^{(1)}))+p_{i}(x^{(1)})\geq
t_{1}(f(x^{(2)}))+p_{i}(x^{(2)})$ $\displaystyle
t_{2}(f(x^{(2)}))+p_{i}(x^{(2)})\geq t_{2}(f(x^{(3)}))+p_{i}(x^{(3)})$
$\displaystyle\vdots$ $\displaystyle t_{k}(f(x^{(k)}))+p_{i}(x^{(k)})\geq
t_{k}(f(x^{(1)}))+p_{i}(x^{(1)})$

The sum of all the inequalities must also be satisfied, in which case the
payments cancel out and we are left with:

$t_{1}(f(x^{(1)}))-t_{1}(f(x^{(2)}))+t_{2}(f(x^{(2)}))-t_{2}(f(x^{(3)}))+\ldots+t_{k}(f(x^{(k)}))-t_{k}(f(x^{(1)}))\geq
0,$

which is simply the expression for the sum of edge weights along $C$.
Therefore we have $w(C)\geq 0$, a contradiction, so there must be a labelling
$\omega$ such that $G_{i,f}^{\omega}$ has no negative weight cycles.

($\impliedby$) Let $\omega$ be a labelling such that $G_{i,f}^{\omega}$ has no
negative weight cycles. Augment $G_{i,f}^{\omega}$ with an artificial node
$\gamma$ and an edge $(\gamma,x;0)$ for each $x\in D$ with weight 0. Since
$G_{i,f}^{\omega}$ contains no negative cycles and the addition of $\gamma$
creates no new cycles (since we only have outgoing edges from $\gamma$) then
shortest paths are well-defined in this new graph. We will now set
$p_{i}(x)=\text{SP}(\gamma,x)$, where SP denotes the shortest path between two
nodes in $G_{i,f}^{\omega}$. For any node $y$ connected to $x$ by an edge
labelled by type $t$, by definition of the shortest path we have
$\text{SP}(\gamma,y)\leq\text{SP}(\gamma,x)+w(x,y;t)$. Thus $p_{i}(y)\leq
pi(x)+t(f(x))-t(f(y))$ and so $t(f(x))+p_{i}(x)\geq t(f(y))+p_{i}(y)$ for any
two profiles $x,y$ connected by an edge labelled by type $t$. It remains to
show that, whenever such an edge appears as per our definition of
$G_{i,f}^{\omega}$, the corresponding WNOM constraint that it represents is
satisfied.

_Case 1: $t=x_{i}$._ In this case the edge $(x,y;t)$ either encodes an
incentive-compatibility constraint or a truthful labelling constraint. Suppose
first that it is the former. Then $x$ must be the profile in which $i$ gets
her lowest utility when she bids $x_{i}$ truthfully, while $y$ must be the
profile in which she gets her lowest utility when she has type $x_{i}$ and
bids $y_{i}$ dishonestly. Thus $x_{i}(f(x))+p_{i}(x)\geq x_{i}(f(y))+p_{i}(y)$
and so her worst-case truthful outcome is no worse than her worst-case
dishonest outcome when she has type $x_{i}$. Now suppose the edge encodes the
latter constraint. Then we have $x=(x_{i},x_{-i})$ and $y=(x_{i},x_{-i})$,
where $y$ designates the input yielding her her worst outcome when she has
type $x_{i}$. Thus $i$ prefers $\mathcal{M}(x)$ to $\mathcal{M}(y)$ and we
have $x_{i}(f(x))+p_{i}(x)\geq x_{i}(f(y))+p_{i}(y)$.

_Case 2: $t\neq x_{i}$._ In this case the edge $(x,y;t)$ encodes a labelling
constraint for a dishonest interaction of $i$ with $\mathcal{M}$. Now
$y=(x_{i},y_{-i})$ must be the profile in which $i$ receives her lowest
utility when she has type $t$ and bids $x_{i}$ dishonestly. Thus she prefers
the outcome when $\mathcal{M}$ is given input $x=(x_{i},x_{-i})$ and so
$t(f(x))+p_{i}(x)\geq t(f(y))+p_{i}(y)$.

In all cases whenever we have an edge $(x,y;t)$ all constraints are satisfied
and so the mechanism $(f,p)$ is WNOM. ∎

Some cycles are guaranteed to exist in $G_{i,f}^{\beta}$ and
$G_{i,f}^{\omega}$, regardless of the labellings we choose. We can use the
existence of such cycles to further study the conditions under which
particular social choice functions are implementable as NOM mechanisms.
Consider first any labelling $\beta$ and let $t_{j},t_{k}\in D_{i}$ be two
types from the domain of player $i$. In the $j$-island of $G_{i,f}^{\beta}$ w
have an edge from node $(t_{j},\beta_{jj})$, player $i$’s best outcome when
she bids $t_{j}$ truthfully, to all other nodes $(t_{j},x_{-i})$ and annotated
by type $t_{j}$. In particular one of these nodes will coincide with the
profile $(t_{j},\beta_{kj})$, the bid profile leading to $i$’s best outcome
when she bids $t_{j}$ dishonestly.222It may be the case that
$\beta_{jj}=\beta_{kj}$ in which case we would have a zero-weight self-loop,
but this does not affect the analysis. Symmetrically we have an edge from
$(t_{j},\beta_{kj})$ to every other node $(t_{j},x_{-i})$ annotated by type
$t_{k}$. Hence for any labelling we will have the two-cycle
$\langle(t_{j},\beta_{jj})\rightarrow^{t_{j}}(t_{j},\beta_{kj})\rightarrow^{t_{k}}(t_{j},\beta_{jj})\rangle$.
Now including incentive-compatibility edges, we have an edge from player $i$’s
best-case truthful profile to her best-case dishonest profile for each
possible manipulation when she has type $t_{j}$ and bids type $t_{k}$, and
using similar reasoning as before we can show that the four-cycle
$\langle(t_{j},\beta_{jj})\rightarrow^{t_{j}}(t_{k},\beta_{jk})\rightarrow^{t_{j}}(t_{k},\beta_{kk})\rightarrow^{t_{k}}(t_{j},\beta_{kj})\rightarrow^{t_{k}}(t_{j},\beta_{jj})\rangle$
is present in any best-case labelling we choose. We can repeat the reasoning
for any worst-case labelling $\omega$ to show the existence of two-cycles
$\langle(t_{j},\omega_{kj})\rightarrow^{t_{j}}(t_{j},\omega_{jj})\rightarrow^{t_{k}}(t_{j},\omega_{kj})\rangle$
and four-cycles
$\langle(t_{j},\omega_{jj})\rightarrow^{t_{j}}(t_{k},\omega_{jk})\rightarrow^{t_{k}}(t_{k},\omega_{kk})\rightarrow^{t_{k}}(t_{j},\omega_{kj})\rangle$
in $G_{i,f}^{\omega}$.

We can generalise these arguments to show that for any $p$ types
$t_{1},\ldots,t_{p}\in D_{i}$ there is always a cycle of length $2p$ which
alternates between traversing edges for labelling constraints and edges for
incentive-compatibility constraints. These $2p$-cycles have weight equal to
$w(C_{p}^{\beta})$ and $w(C_{p}^{\omega})$ where
$C_{p}^{\beta},C_{p}^{\omega}$ are given by:

$\displaystyle
C_{p}^{\beta}=\\{(t_{j},\beta_{jj})\rightarrow^{t_{j}}(t_{j+1},\beta_{(j+1),(j+1)})\,:\,j\in[p]\\}$
(5) $\displaystyle
C_{p}^{\omega}=\\{(t_{j},\omega_{(j-1),j})\rightarrow^{t_{j}}(t_{j+1},\omega_{j,(j+1)})\,:\,j\in[p]\\}$
(6)

where the index wraps around appropriately at -1 and $p+1$. Note that
$C_{p}^{\beta}$ and $C_{p}^{\omega}$ do not necessarily exist in
$G_{i,f}^{\beta}$ and $G_{i,f}^{\omega}$; it is simply that there are cycles
of length $2p$ which _are_ guaranteed to exist which have weight equal to
$C_{p}^{\beta}$ and $C_{p}^{\omega}$. Restricting our attention to a
particular $j$-island of $G_{i,f}^{\beta}$ and $G_{i,f}^{\omega}$ we can also
show that for any two types $t_{k},t_{\ell}\in D_{i}$ we will have the edges:

$\displaystyle\\{(t_{j},\beta_{kj})\rightarrow^{t_{k}}(t_{j},\beta_{\ell
j})\rightarrow^{t_{\ell}}(t_{j},\beta_{kj})\,:\,t_{j},t_{k},t_{\ell}\in
D_{i}\\}$ (7)
$\displaystyle\\{(t_{j},\omega_{kj})\rightarrow^{t_{\ell}}(t_{j},\omega_{\ell
j})\rightarrow^{t_{k}}(t_{j},\omega_{kj})\,:\,t_{j},t_{k},t_{\ell}\in
D_{i}\\}$ (8)

We will use these guaranteed cycles in the following section in which we
characterise the NOM-implementable allocation functions for single-parameter
agents.

##  4 Single-parameter agents

For the remainder of this work we shall consider single-parameter agents. In
this setting agent types can be described by a single number: when agent $i$
has type $t_{i}$ she values the outcome of $f$ on input $x$ as
$t_{i}(f(x))=t_{i}\cdot f_{i}(x)$, allowing us to decouple an agent’s type
from the outcome of the mechanism. Archer and Tardos [1] use this to
characterise truthfully-implementable work functions and then formulate
payments using the area under a curve. In our setting while the “shape” of the
allocation function will depend on the labelling we choose, we can use the
cycles given in (5) and (6) to show some necessary properties of any
labelling. Let $p=2$ for these cycles $C_{p}^{\beta}$ and $C_{p}^{\omega}$. By
Theorem 3.1 we know $\beta,\omega$ are valid labellings if and only if all
cycles in $G_{i,f}^{\beta}$ and $G_{i,f}^{\omega}$ are non-negative, thus
$w(C_{2}^{\beta}),w(C_{2}^{\omega})\geq 0$ in any valid labelling. Since
agents are single-parameter we may factor the expressions for the cycle
weights as follows:

$\displaystyle(t_{j}-t_{k})(f_{i}(t_{j},\beta_{jj})-f_{i}(t_{k},\beta_{kk}))\geq
0$ (9)
$\displaystyle(t_{j}-t_{k})(f_{i}(t_{j},\omega_{kj})-f_{i}(t_{k},\omega_{kj}))\geq
0$ (10)

for all $t_{j},t_{k}\in D_{i}$. In other words, when $t_{j}>t_{k}$ then player
$i$ must receive more from $f$ in her best truthful outcome of $\mathcal{M}$
when she has type $t_{j}$ than when she has type $t_{k}$, while she must
receive more in the worst case from $f$ when she misreports her true type
$t_{k}$ as $t_{j}$ compared to when she misreports her true type $t_{j}$ as
$t_{k}$. We will refer to this property as _label monotonicity_. Similarly the
two-cycles given in (7) and (8) must also have non-negative weight. We may
separate them as before to get:

$\displaystyle(t_{k}-t_{\ell})(f_{i}(t_{j},\beta_{kj})-f_{i}(t_{j},\beta_{\ell
j}))\geq 0$ (11) $\displaystyle(t_{k}-t_{\ell})(f_{i}(t_{j},\omega_{\ell
j})-f_{i}(t_{j},\omega_{kj}))\geq 0$ (12)

Let $S_{ij}=\\{f_{i}(t_{j},x_{-i})\,:\,x_{-i}\in D_{-i}\\}$ denote the set of
outcomes of $f$ for player $i$ when she submits bid $t_{j}$, and let
$S_{i}=\times_{j\in D}S_{ij}$. We will call $f$ _overlapping for $i$_ if there
exists $\mathbf{o}=(o_{1},\ldots,o_{d})\in S_{i}$ such that $o_{1}\leq
o_{2}\leq\ldots\leq o_{d}$. Let $\hat{f}_{i}:D_{i}\times S_{i}\to D$ denote a
pseudo-inverse of $f$ which returns any bid profile $x=(t_{j},x_{-i})$ such
that $f_{i}(x)=o_{j}$. We will show that $f$ is BNOM- and WNOM-implementable
if and only it is overlapping for each $i$. Our proof will be for the WNOM
case but note that the proof for BNOM follows exactly the same reasoning.

######  Theorem 4.1.

Allocation function $f$ is either BNOM- or WNOM-implementable for single-
parameter agent $i$ if and only if it is overlapping for $i$.

###### Proof.

($\implies$) Assume for the sake of contradiction that there are two bids
$t_{1},t_{2}\in D_{i}$ with $t_{1}<t_{2}$ such that $f$ is not overlapping for
$i$. That is, for any choice of $o_{1}\in S_{i1}$ we must have $o_{2}<o_{1}$
for $o_{2}\in S_{i2}$. Since $f$ is WNOM-implementable then there exists a
worst-case labelling $\omega$ such that the graph $G_{i,f}^{\omega}$ contains
no cycles of negative weight. By the monotone labelling property we require
$(t_{1}-t_{2})(f_{i}(t_{1},\omega_{21})-f_{i}(t_{2},\omega_{12}))\geq 0$, so
$f_{i}(t_{1},\omega_{21})\leq f_{i}(t_{2},\omega_{12})$. Since $o_{2}<o_{1}$
for any choice of $o_{1}$ then we must have
$f_{i}(t_{1},\omega_{j1})>f_{i}(t_{2},\omega_{k2})$ for all (not necessarily
distinct) $t_{j},t_{k}\in D_{i}$. Thus $f$ cannot be WNOM-implementable for
$i$, a contradiction, so $f$ must be overlapping for $i$.

($\impliedby$) We will use the overlaps of $f$ for player $i$ to define a
valid worst-case labelling $\omega$ and note that the exact same reasoning
carries over for best-case labellings $\beta$. Define iteratively the values
$W(j)=\max\\{\min_{o_{j}\in S_{ij}}\\{o_{j}\\},W(1),W(2),\ldots,W(j-1)\\}$ for
$j\in[d]$. Note that $W(j)\geq W(k)\iff t_{j}\geq t_{k}$. We will use $W$ to
label $f$ with $\omega_{ij}=\hat{f}_{i}(j,W(j))$ for each $t_{i},t_{j}\in
D_{i}$. Since for every bid $t_{j}$ we have $\omega_{ij}=\omega_{kj}$ for all
types $t_{i},t_{k}\in D_{i}$ we use a single subscript $\omega_{j}$ to denote
this bid profile. We now show that no cycles that appear in the graph
$G_{i,f}^{\omega}$ are negative and hence $\omega$ is a valid worst-case
labelling.

First note that since for every bid $t_{j}$ we label the worst-case outcome
for $i$ to occur at the same bid profile $\omega_{j}$ no matter her type, then
each subgraph of $G_{i,f}^{\omega}$ containing only nodes $(t_{j},x_{-i})$ in
which $i$ has bid $t_{j}$ will have no cycles, and these edges represent the
labelling constraints. Hence we need only focus on edges which go from node
$(t_{j},\omega_{j})$ to some $(t_{k},\omega_{k})$, which represent the
incentive-compatibility constraints. Recall that the type annotation on each
of these edges is always equal to the bid of player $i$ at the source node, so
every edge has the form
$(t_{u},\omega_{u})\rightarrow^{t_{u}}(t_{v},\omega_{v})$. Consider any cycle
$C$ in $G_{i,f}^{\omega}$ with weight $w(C)=\sum_{(u,v;t_{u})\in
C}t_{u}(f_{i}(\omega_{u})-f_{i}(\omega_{v}))$. We will refer to negative
weight edges in $C$ as “uphill” edges and positive weight edges as “downhill”
edges. We can safely ignore edges of zero weight. Note that uphill edges occur
when the output of $f$ for player $i$ is lower at the source than the
destination profile, and since $W(j)\geq W(k)\iff t_{j}\geq t_{k}$ then all
such edges go from a node in which $i$ bids a smaller type to one in which she
bids a larger one. The opposite is true for downhill edges. For a given bid
$t_{j}$ we will refer to the types $\max\\{t_{k}\in D_{i}\,:\,t_{k}<t_{j}\\}$
and $\min\\{t_{k}\in D_{i}\,:\,t_{k}>t_{j}\\}$ as the adjacent type to
$t_{j}$, and adjacent nodes in $G_{i,f}^{\omega}$ will be those in which $i$
submits adjacent types as bids to the mechanism. We will show that the weight
of $C$ is bounded below by the weight of a (non-simple) cycle $C^{\prime}$
which only contains edges between adjacent nodes, whose weight is in turn
always non-negative.

In the following we will use simply the label $\omega_{j}$ as shorthand for
the bid profile $(t_{j},\omega_{j})$. First consider a downhill edge
$e^{+}=\omega_{j}\rightarrow^{t_{j}}\omega_{j-k}$ going directly from
$\omega_{j}$ to $\omega_{j-k}$ that “skips” $k-1$ adjacent nodes. Since
$t_{j}>t_{j-k}$ then
$W(j)=f_{i}(t_{j},\omega_{j})>f_{i}(t_{j-k},\omega_{j-k})=W(j-k)$. The weight
$w(e^{+})$ of such an edge is therefore:

$\displaystyle w(e^{+})$
$\displaystyle=t_{j}[f_{i}(\omega_{j})-f_{i}(\omega_{j-k})]$
$\displaystyle=t_{j}[f_{i}(\omega_{j})-f_{i}(\omega_{j-1})+f_{i}(\omega_{j-1})-f_{i}(\omega_{j-2})+\ldots+f_{i}(\omega_{j-k+1})-f_{i}(\omega_{j-k})]$
$\displaystyle\geq
t_{j}(f_{i}(\omega_{j})-f_{i}(\omega_{j-1}))+t_{j-1}(f_{i}(\omega_{j-1})-f_{i}(\omega_{j-2}))+\ldots+t_{j-k+1}(f_{i}(\omega_{j-k+1})-f_{i}(\omega_{j-k}))$

Following the same reasoning we can show that the weight of an uphill edge
$e^{-}=(t_{j},\omega_{j})\rightarrow^{t_{j}}(t_{j+k},\omega_{j+k})$, in which
we skip $k-1$ adjacent nodes, can be similarly lower bounded:

$\displaystyle w(e^{-})$
$\displaystyle=t_{j}[f_{i}(\omega_{j})-f_{i}(\omega_{j+k})]$
$\displaystyle=t_{j}[f_{i}(\omega_{j})-f_{i}(\omega_{j+1})+f_{i}(\omega_{j+1})-f_{i}(\omega_{j+2})+\ldots+f_{i}(\omega_{j+k-1})-f_{i}(\omega_{j+k})]$
$\displaystyle\geq
t_{j}(f_{i}(\omega_{j})-f_{i}(\omega_{j+1}))+t_{j+1}(f_{i}(\omega_{j+1})-f_{i}(\omega_{j+2}))+\ldots+t_{j+k-1}(f_{i}(\omega_{j+k-1})-f_{i}(\omega_{j+k}))$

Notice in both cases that the right hand side of the final inequality is the
expression for the weight of a path between two non-adjacent nodes that only
traverses edges between adjacent nodes. Now if we take any cycle $C$ and
replace all such non-adjacent edges with a path comprising only adjacent edges
then we will be left with a non-simple cycle that is composed of many two-
cycles (see Figure 1). We know from the labelling monotonicity property of our
labelling $\omega$ that all two-cycles are non-negative, and so too must be
their sum. This non-negative value lower bounds $w(C)$, thus under $\omega$
there must be no negative cycles, and by Theorem 3.1 the proof is complete. ∎

$\geq$$-$$-$$+$$+$$+$$+$$-$ (a) Uphill edges

$\geq$$-$$-$$+$$+$$+$$+$$-$$-$$-$$+$$-$$-$$+$$\geq$$+$ (b) Downhill edges

Figure 1: Substituting cycles with non-adjacent types for cycles with only
adjacent types

######  Corollary 4.1.1.

Allocation function $f$ is NOM-implementable if and only if there exists non-
decreasing sequences $\mathbf{o}^{\beta},\mathbf{o}^{\omega}\in S_{i}$ for all
$i$, and unless $f_{i}$ is constant then
$\hat{f}_{i}(t_{j},o_{j}^{\beta})\neq\hat{f}_{i}(t_{j},o_{j}^{\omega})$.

###### Proof.

The vectors of real numbers $\mathbf{o}^{\beta},\mathbf{o}^{\omega}$
correspond to the outcomes at the best- and worst-case nodes of $\mathcal{M}$,
according to $\beta,\omega$ respectively. We have shown that $f$ is singularly
BNOM- or WNOM-implementable if and only if $\mathbf{o}^{\beta}$ and
$\mathbf{o}^{\omega}$ are non-decreasing sequences – we can combine them to
achieve a mechanism that is NOM, with the only extra caveat being that, unless
$f$ is constant, then the best- and worst-case outcomes occur at different bid
profiles.

Let $(t_{j},\hat{x}_{-i})$ be some bid profile at which $i$ receives both her
best- and worst-case utility when she bids $t_{j}$. Then
$\hat{f}_{i}(t_{j},o_{j}^{\beta})=\hat{f}_{i}(t_{j},o_{j}^{\omega})=(t_{j},\hat{x}_{-i})$.
Then the $j$-island of $G_{i,f}^{\beta,\omega}$ consists only of the two-
cycles
$\langle(t_{j},\hat{x}_{-i})\rightarrow^{t_{k}}(t_{j},x_{-i})\rightarrow^{t_{\ell}}(t_{j},\hat{x}_{-i})\rangle$
for all types $t_{k},t_{\ell}\in D_{i}$. Requiring the weights of all such
cycles to be non-negative means we need both
$(t_{k}-t_{\ell})(f_{i}(t_{j},\hat{x}_{-i})-f_{i}(t_{j},x_{-i}))\geq 0$ and
$(t_{\ell}-t_{k})(f_{i}(t_{j},\hat{x}_{-i})-f_{i}(t_{j},x_{-i}))\geq 0$, which
is only satisfied when $f_{i}(t_{j},\hat{x}_{-i})=f_{i}(t_{j},x_{-i})$ for all
$x_{-i}$. ∎

In the proof of sufficiency in Theorem 4.1 above we used a particular
labelling in which the best- and worst-case outcome for a given bid of player
$i$ all occurred at the same bid profile, no matter her type. These are of
course not the only labellings possible, and different labellings can and do
lead to different payments (as we will see in Section 5). For the following
characterisation, however, we will focus on the above type of _single-line_
labellings. Formally, a labelling $\lambda\in\\{\beta,\omega\\}$ is single-
line if $\lambda_{kj}=\lambda_{\ell j}$ for all $t_{j},t_{k},t_{\ell}\in
D_{i}$ for every player $i$. We shall call a mechanism single-line if the
labelling it uses is single-line. This allows us to express payments that NOM-
implement an allocation function succintly for single-parameter agents,
following a result originally due to Archer and Tardos [1].

In [1] they consider functions which allocate _work_ to the single-parameter
agents, so their types are analogous to costs rather than valuations. They
show that such a work function admits truthful payments if and only if it is
non-increasing and fully characterise the payments by expressing them using
various areas on the work curves. While our setting is one in which agent
types are valuations it is simple to translate between the two, and we show
that NOM payments exist if and only if the best- and worst-case curves are
non-decreasing. The proof of the following claim follows the exact same
reasoning as [1], where instead of treating $f$ as a function only of $x_{i}$
by fixing the bid profile of other bidders $x_{-i}$ we treat it as a function
only of $x_{i}$ by arguing that the labellings $\beta,\omega$ are fixed. We
can then solve the differential equations in the same way.

######  Theorem 4.2.

If $f_{i}$ is a single-line mechanism for player $i$ then $f$ is NOM-
implementable if and only if for each player $i$ payments are of the form:

$\displaystyle
p_{i}(t_{j},\lambda_{j})=h_{i}(\lambda)-t_{j}f_{i}(t_{j},\lambda_{j})+\int_{0}^{t_{j}}f_{i}(u,\lambda_{u})\,\mathrm{d}u$
(13)

for $\lambda\in\\{\beta,\omega\\}$, where
$h_{i}(\lambda)=h_{i}(\lambda_{1},\ldots,\lambda_{d})$ is an arbitrary
function that only depends on the labelling $\lambda$.

The remaining payments – for bid profiles which are not best- or worst-case
inputs – are then easy to define and entail some degree of flexibility. Since
we use a single-line mechanism we simply need to satisfy a total of
$|D_{-i}|-1$ constraints for each bid $x$ of player $i$ of the form
$t_{i}(f_{i}(t_{j},\beta_{j}))+p_{i}(t_{j},\beta_{j})\geq
t_{i}(f_{i}(t_{j},x_{-i}))+p_{i}(t_{j},x_{-i})$ for BNOM, and
$t_{i}(f_{i}(t_{j},x_{-i}))+p_{i}(t_{j},x_{-i})\geq
t_{i}(f_{i}(t_{j},\omega_{j}))+p_{i}(t_{j},\omega_{j})$ for WNOM. It is
important to note the move from discrete to continuous domains. This is not an
issue conceptually since the labels $\lambda$ are simply bid profiles. In
practice we would need to assume the existence of an oracle that returns the
labelled profile $\lambda_{jk}$ when queried with two types $t_{j}$ and
$t_{k}$. Note that when we have discrete domains this is not an issue but we
would need to replace the integral with a summation. By assuming IR and NPT we
can place restrictions on the functions $h_{i}(\beta)$ and $h_{i}(\omega)$.
When types are valuations we get $h_{i}(\beta)=h_{i}(\omega)=0$. When types
are costs then
$h_{i}(\beta)\geq\int_{0}^{t_{j}}f_{i}(u,\beta_{u})\,\mathrm{d}u$ and
$h_{i}(\omega)\geq\int_{0}^{t_{j}}f_{i}(u,\omega_{u})\,\mathrm{d}u$ for all
$x\in D_{i}$.

##  5 Bilateral Trade

We now study the bilateral trade setting in which there are two agents, $B$
and $S$, where $B$ is a potential buyer of an item that $S$ is looking to
produce and sell. The agents have types $v\in D_{B}$ and $u\in D_{S}$
respectively, where $v$ describes the buyer’s valuation for the item and $u$
describes the seller’s cost for producing the item. Let $D=D_{B}\times D_{S}$.
A mechanism for bilateral trade is a tuple $\mathcal{M}=(f,p)$ where
$f:D\to\\{0,1\\}$ indicates whether a trade takes place and
$p:D\to\mathbb{R}_{\geq 0}$ describes the payments. The agents’ utilities are
given by

$\displaystyle v(\mathcal{M}(x,y))=v\cdot f(x,y)-p_{B}(x,y)$ $\displaystyle
u(\mathcal{M}(x,y))=p_{S}(x,y)-u\cdot f(x,y)$

We focus primarily on studying the following three properties: a function $f$
is _efficient_ if trade only occurs whenever the buyer’s bid exceeds that of
the seller’s; a mechanism is _individually rational_ if an agent can never end
up worse off by submitting a truthful bid to the mechanism; and a mechanism is
weakly budget-balanced if the seller is never paid more than what we receive
as payment from the buyer. We can relax the last property to $\alpha$ weak
budget balance, where our payment to the seller is never more than an $\alpha$
factor away from the payment received from the buyer for $\alpha\geq 1$.
Formally:

  * •

Efficiency: $f(x,y)=1$ if and only if $x\geq y$ for all $(x,y)\in D$

  * •

Weak Budget Balance (WBB): $p_{S}(x,y)\leq p_{B}(x,y)$ for all $(x,y)\in D$

  * •

$\alpha$-WBB: $p_{S}(x,y)\leq\alpha\cdot p_{B}(x,y)$ for all $(x,y)\in D$ and
$\alpha\geq 1$.

Since its introduction by Chatterjee and Samuelson [5], bilateral trade has
received and continues to receive considerable attention in the economics and
algorithmic game theory literature. Here, we give a brief overview of some
examples of recent work. In their seminal work, Myerson and Satterthwaite [21]
show that there is no mechanism that is simultaneously Bayesian Incentive-
Compatible (BIC), IR, WBB, and efficient, thus efforts have largely been
focused on analysing the mechanisms satisfying an approximate form of
efficiency instead. Recently it was shown by Deng et al. [8] that there exists
a mechanism that guarantees a Bayes-Nash equilibrium with a constant-factor
approximation to the optimal “gains from trade” (GFT) (i.e. the expected
utility gain as a result of trading). Babaioff, Dobzinski, and Kupfer [3] show
that this mechanism cannot approximate the optimal GFT better than $0.495$ for
some distributions. Blumrosen and Dobzinski [4] show that for every pair of
distributions of types for the buyer and seller there exists a IR, WBB, fixed-
price mechanism – a mechanism that posts a price asks players to “take it or
leave it” – that achieves at least a $(1-1/e)$ fraction of the optimal
efficiency in dominated strategies. This was improved to $(1-1/e)+10^{-4}$ by
Kang, Pernice, and Vondrák [16].

The above merely form an example of some recent works on the topic. These
studies and most other works in the mechanism design literature are concerned
with implementations in dominant strategy or Bayes-Nash equilibria. Bilateral
trade under NOM was studied in [26], where it was proved that WBB, efficiency,
and IR cannot be satisfied simultaneously under NOM. In this section we
investigate this combination of properties further, where we relax WBB to
$\alpha$-WBB, and consider WNOM and BNOM separately as relaxations of NOM.

###  5.1 Single-line mechanisms require unbounded subsidies

Recall that when we use a single-line mechanism then NOM payments exist if and
only if they are of the form given in (13), and that this was technically for
the case in which payments are _given_ to players (since they are added to
their utilities) and moreover this was when agents valued the outcome of $f$,
as opposed to incurring a cost. This setup slightly changes in our setting for
bilateral trade: now the buyer values the outcome of $f$ and payments are
subtracted from her utility, while the seller induces a cost for producing the
item but receives payments as compensation. In the following discussion we
will highlight some of the issues of using single-line mechanisms for
bilateral trade mechanisms, so we note that the payments for such mechanisms
take the following form:

$\displaystyle
p_{B}(x,\lambda_{x})=h_{B}(\lambda)+xf(x,\lambda_{x})-\int_{0}^{x}f(u,\lambda_{u})\,\mathrm{d}u,$
$\displaystyle
p_{S}(\lambda_{y},y)=h_{S}(\lambda)+yf(\lambda_{y},y)-\int_{0}^{y}f(\lambda_{u},u)\,\mathrm{d}u,$

for $\lambda\in\\{\beta,\omega\\}$. Again note that if we have IR and NPT then
$h_{B}(\lambda)$ goes to zero, while for the seller this must be at least the
area under the curve.

Before proceeding with the following claims it will be useful to note a few
facts we will reuse. Let $x$ and $y$ be bids of the buyer and seller,
respectively. Whenever our bilateral trade mechanism is IR and efficient then
for all $x\geq y$ we require $p_{B}(x,y)\leq x$ and $p_{S}(x,y)\geq y$, while
for $x<y$ we have $-p_{B}(x,y)\geq 0$ and hence $p_{B}(x,y)=0$. Therefore
whenever trade does not take place the utility of the buyer is 0 no matter her
true type. In Lemma 5.1 and Lemma 5.3 we will prove that when we have a
single-line mechanism the curves representing the best- and worst-case
outcomes of $f$ are constant. Since the buyer receives value from the item
while the seller incurs a cost then by Theorem 4.1 the outcomes at her best-
and worst-case outcomes must be non-decreasing in her bid $x$; conversely
since the seller incurs a cost for producing the item then her curve must be
non-increasing. Since $f\in\\{0,1\\}$ and our mechanism is either BNOM or WNOM
then there must be a threshold $\theta\in[0,1]$ at which, for all bids that
are at least this threshold, the output of $f$ flips from one value to the
other, depending on the player we are analysing. For the buyer we must have
$f(x,\beta_{x})=f(x,\omega_{x})=1$ for all $x\geq\theta$, while for the seller
we require $f(\beta_{y},y)=f(\omega_{y},y)=0$ for all $y\geq\theta$. We will
show that these thresholds are placed at the extremes, i.e. 0 or 1.

######  Lemma 5.1.

In any efficient, IR, single-line BNOM mechanism $\mathcal{M}$ the best-case
outcomes occur for both the buyer and the seller when the trade is executed,
regardless of their bid.

###### Proof.

Consider first from the buyer’s side. Since $\mathcal{M}$ is single-line BNOM
then $f$ must be non-decreasing in the buyer’s bid, and let $\theta$ be such
that $f(x,\beta_{x})=1$ for all $x\geq\theta$. Fix $x$ and let $x<\theta$ and
$y$ be a bid of the seller such that $f(x,y)=1$. By the BNOM labelling
constrains we have $v(\mathcal{M}(x,\beta_{x}))=0\geq v-p_{B}(x,y)$ for all
$v\in D_{B}$, so $1\leq p_{B}(x,y)\leq x$, where the second inequality follows
from IR and efficiency. We arrive at a contradiction from our assumption that
$x<\theta$ since $1\leq x<\theta$ where $\theta\in[0,1]$. Thus $\theta\leq x$
for all $x$, meaning $\theta=0$: in other words $f$ is 1 everywhere and trade
always occurs in the buyer’s best-case outcome.

Now consider the seller. She incurs a cost for producing the item when the
trade is to be executed, hence from her perspective $f$ must be non-increasing
in her bid. As before there must be a threshold $\theta\in[0,1]$ such that
$f(\beta_{y},y)=1$ for all $y\leq\theta$ and 0 otherwise. For some bid
$y>\theta$ of the seller her best case utility is
$u(\mathcal{M}(\beta_{y},y))=p_{S}(\beta_{y},y)=h_{S}(\beta)+yf(\beta_{y},y)-\int_{0}^{y}f(\beta_{u},u)\,\mathrm{d}u$.
Recall that the value of $h_{i}(\beta)$ for costs is at least the area under
the work curve. Setting $h_{S}(\beta)$ to this area333We can of course pay the
seller more, as long as it doesn’t interfere with incentives. We will be using
this lemma to prove the impossibility of (bounded) $\alpha$-WBB, so if we can
show this when we are being as frugal as possible then the claim will hold
even when using more generous payments. Thus we set $h_{S}(\beta)$ to be as
small as possible, i.e. exactly the area under the curve, and this is enough
to prove the unboundedness. This same reasoning is used in the proof of Lemma
5.3. gives
$p_{S}(\beta_{y},y)=yf(\beta_{y},y)+\int_{y}^{1}f(\beta_{u},u)\,\mathrm{d}u$
so her best-case utility is 0. Now take any $x$ such that $f(x,y)=1$. By the
BNOM constraints we have $u(\mathcal{M}(x,y))=p_{S}(x,y)-u\leq 0$ for all $u$.
Combining this with individual rationality we have $u\geq p_{S}(x,y)\geq y$,
which gives us a contradiction if we take $u<y$. Thus $y\leq\theta$ for all
$y$ and so $\theta=1$, meaning trade always occurs in the best-case outcome
for the seller. ∎

As a corollary of Lemma 5.1 it must be that the buyer’s best outcome is that
she gets the item and pays nothing, while the seller’s is that she produces
the item and is paid at least her bid. Since we assume $\mathcal{M}$ is IR,
NPT, and single-line BNOM then payments are of the form given in (13). Thus
$p_{B}(x,\beta_{x})=0$ and $p_{S}(\beta_{y},y)\geq
y+\int_{y}^{1}f(\beta_{u},u)\,\mathrm{d}u=1$.

######  Theorem 5.2.

Any efficient, IR, single-line BNOM mechanism with $\alpha$-WBB has unbounded
$\alpha$.

###### Proof.

From Lemma 5.1 we know that $f(x,\beta_{x})=f(\beta_{y},y)=1$ for any $x\in
D_{B}$ and $y\in D_{S}$, while $p_{B}(x,\beta_{x})=0$ and
$p_{S}(\beta_{y},y)\geq y$. Thus we need to show that there always exists a
profile $(x^{*},y^{*})$ that appears on both the best-case curve of the buyer
and the seller to prove the claim. Take any bid $x$ of the buyer and let
$y=\beta_{x}>0$ be a bid of the seller. Since $f(x,y)=1$ then $p_{S}(x,y)\geq
y$ by efficiency and IR. The labelling constraints require
$u(\mathcal{M}(x,y))\geq u(\mathcal{M}(\beta_{y},y))$ for all $u$ and so
$p_{S}(\beta_{y},y)\geq p_{S}(x,y)\geq y$. Since $y=\beta_{x}$ then
$p_{S}(\beta_{y},y)\geq p_{S}(x,\beta_{x})\geq y>0$, while
$p_{B}(x,\beta_{x})=0$. Therefore at $(x,\beta_{x})$ the buyer pays 0 while
the seller must receive some positive amount.

Now let $y=0$: the following labelling will result in payments leading to the
desired result. For every bid $x$ of the buyer set $\beta_{x}=0$. Now for all
choices of the bid of the buyer $\beta_{y}$ leading to the seller’s best
outcome the resulting profile will also appear on the buyer’s best-case curve.
Again the buyer pays 0 while the seller must receive a positive amount. ∎

######  Lemma 5.3.

In any efficient, IR, single-line WNOM mechanism $\mathcal{M}$ the worst-case
outcomes occur for both the buyer and the seller when the trade is not
executed, regardless of their bid.

###### Proof.

As before first consider the buyer’s perspective. Assume there is a bid
$x>\theta$ and let $y$ be a bid of the seller such that $f(x,y)=0$. The
labelling constraints therefore require that $v-p_{B}(x,\omega_{x})\leq 0$ for
all $v\in D_{B}$, and combining this with the previous facts we get
$p_{B}(x,\omega_{x})=x$. Now taking $v>x$ the buyer’s utility at her worst-
case outcome is strictly positive, a contradiction. Hence $\theta\geq x$ for
all $x$, or $\theta=1$. Thus in the buyer’s worst case the trade is never
executed.

As for the seller let $y<\theta$ and let $x$ be such that $f(x,y)=0$. Then
$p_{S}(x,y)=0$, and since trade occurs in the seller’s worst case by
assumption then $p_{S}(\omega_{y},y)\leq y$. By (13) then
$p_{S}(\omega_{y},y)\geq
h_{S}(\omega)+yf(\omega_{y},y)-\int_{0}^{y}f(\omega_{u},y)\,\mathrm{d}u=h_{S}(\omega)+y-y\geq\theta$,
where the final inequality follows from the fact that $h_{S}(\omega)$ must be
at least the area under the curve for any IR and NPT mechanism. Thus
$p(\omega_{y},y)\geq\theta$ and $p_{S}(\omega_{y},y)\leq y$ where $y<\theta$,
a contradiction. So $\theta=1$ and the seller’s worst case always occurs when
the trade is not executed. ∎

######  Theorem 5.4.

Any efficient, IR, single-line WNOM mechanism with $\alpha$-WBB has unbounded
$\alpha$.

###### Proof.

Let $\mathcal{M}=(f,p)$ be an efficient, IR, single-line WNOM mechanism and
consider a bid $x\in D_{B}$ of the buyer for which $f(x,\omega_{x})=0$. By IR
we have $xf(x,\omega_{x})-p_{B}(x,\omega_{x})\geq 0$ and so
$p_{B}(x,\omega_{x})=0$. Thus $v(\mathcal{M}(x,\omega_{x}))=0$ for any $v$
when $f(x,\omega_{x})=0$. Let $y\in D_{S}$ be a bid of the seller such that
$f(x,y)=1$ and note that by efficiency $x\geq y$. Since the worst utility of
the buyer is 0 then $p_{B}(x,y)\leq v$ and thus we need
$p_{B}(x,y)\leq\min\\{x\,:\,x\geq y\\}$.

Consider the same setting for the seller and now a bid $y\in D_{S}$ such that
$f(\omega_{y},y)=0$. Let $x\in D_{B}$ be a bid of the buyer such that
$f(x,y)=1$. By the labelling constraints we have $p_{S}(x,y)-u\geq
p_{S}(\omega_{y},y)\geq 0$, hence $p_{S}(x,y)\geq u$ for all $u$ (since
$\mathcal{M}$ is single-line) and thus $p_{S}(x,y)\geq\max\\{y\,:\,x\geq
y\\}$. Thus for all $x\geq y$ we have:

$\displaystyle p_{B}(x,y)\leq\min\\{x\,:\,x\geq y\\}=y$ (14) $\displaystyle
p_{S}(x,y)\geq\max\\{x\,:\,x\geq y\\}=x$ (15)

Now consider the bid profile $(1,\varepsilon)$. The buyer must pay at most
$\varepsilon$ while the seller is to receive at least 1, and since
$\varepsilon$ is arbitrary we get the desired result. ∎

The following two results show that single-line mechanisms are overly
restrictive for WNOM and by using a more general labelling we can achieve weak
budget-balance. On the contrary, unbounded subsidies are unavoidable for BNOM
under any labelling.

######  Theorem 5.5.

There is an efficient, IR, WBB, WNOM mechanism.

###### Proof.

Let $D_{B}=[0,1]$ and $D_{S}=\\{0,1\\}$ and consider the labelling $\omega$ in
which $\omega_{jk}=1$ if and only if $t_{j}\geq t_{k}$, and 0 otherwise. Fix
some bid $x$ of the buyer and observe that all cycles within the $x$-island
have non-negative weight. There are only two nodes in these $x$-islands in
$G_{i,f}^{\omega}$, namely $(x,0)$ and $(x,1)$, and due to $\omega$ there is
an edge $(x,1)\rightarrow^{t}(x,0)$ for all $t\in[0,x)$ and an edge
$(x,0)\rightarrow^{t}(x,1)$ for all $t\in[x,1]$. Thus the cycle
$C=\langle(x,0)\rightarrow^{t_{j}}(x,1)\rightarrow^{t_{k}}(x,0)\rangle$ has
weight at least
$x(f(x,0)-f(x,1))+(x-\varepsilon)(f(x,1)-f(x,0))=\varepsilon>0$ for positive
$\varepsilon$, i.e. when $t_{j}=x$ and $t_{k}=x-\varepsilon$. There are many
other cycles in $G_{i,f}^{\omega}$ which use incentive-compatibility edges –
we will show that the shortest of such cycles have non-negative weight, and
observe that the weight of longer cycles will only increase. These cycles have
the form
$(x,1)\rightarrow^{x}(x+\varepsilon,0)\rightarrow^{t}(x+\varepsilon,1)\rightarrow^{x+\varepsilon}(x,1)$
for $t\in[x+\varepsilon,1]$, and its weight is minimised when
$t=x+\varepsilon$; the weight of the cycle therefore at least
$(-x)+(x+\varepsilon)+0=\varepsilon$ and hence non-negative. These are the
only types of cycles present in the graph induced by $\omega$, and since they
are all non-negative then $f$ is WNOM-implementable. It now remains to derive
the payments that this labelling produces.

Fix a bid $t_{j}$ of the buyer. Since $\omega_{jj}=1$ then trade does not
occur and we have $v(\mathcal{M}(t_{j},1))=0$ for all $v$. Since
$\omega_{ij}=0$ for $t_{i}<t_{j}$ then trade occurs and we have
$v-p_{B}(t_{j},0)\leq v(\mathcal{M}(t_{j},1))=0$. Thus for all $v<t_{j}$ we
have $p_{B}(t_{j},0)\geq v$ and so $p_{B}(t_{j},0)$ tends to $t_{j}$.
Combining this with IR we have $t_{j}\leq p_{B}(t_{j},0)\leq t_{j}$ and
therefore when the trade occurs the buyer pays her bid, and 0 otherwise. In
other words, this labelling induces first-price payments for the buyer.

Now consider payments for the seller where she gets paid her own bid when
trade occurs. It is straightforward to verify that these payments for the
seller are strategyproof and therefore NOM by Theorem 2.1. When trade occurs
the payments are $p_{B}(x,y)=x$ and $p_{S}(x,y)=y$, and 0 otherwise. Since
trade occurs only when $x\geq y$ then the payment given to the seller never
exceeds the amount extracted from the buyer, hence we achieve (exact) weak
budget balance. ∎

######  Theorem 5.6.

There is no efficient, IR, $\alpha$-WBB, BNOM mechanism with bounded $\alpha$.

###### Proof.

Let $f$ be an efficient allocation function for bilateral trade. We will prove
the claim by case analysis of all possible labellings on the subgraph of
$G_{B,f}^{\beta}$ containing only a $j$-island and a $k$-island for some types
$t_{j},t_{k}\in D_{B}$. Each general labelling falls into one of four cases:
it is single-line, for which we have already proved subsidies are unbounded;
it is invalid and leads to a negative cycle $G_{B,f}^{\beta}$, meaning
payments ensuring BNOM are impossible; it induces no negative cycles in
$G_{B,f}^{\beta}$ but otherwise leads to contradiction when taken with IR and
efficiency; or it leaves us with the same payments as in the single-line case,
meaning unbounded subsidies are unavoidable. The first two cases are
straightforward so we will focus on the latter two.

Let $D_{B}=[0,1]$ and $D_{S}=\\{0,1\\}$. First note that in any valid
labelling $\beta$ each $j$-island of $G_{B,f}^{\beta}$ will consist only of
two nodes, $(t_{j},0)$ and $(t_{j},1)$, hence for any labelling to be valid it
must be that $f(t_{j},\beta_{ij})\geq f(t_{j},\beta_{kj})\iff t_{i}\geq
t_{k}$. Now fix $t_{j},t_{k}\in D_{i}$ with $t_{j}<t_{k}$ and observe that by
IR we have $p_{B}(t_{j},0)\leq t_{j}$, so either $\beta_{jj}=(t_{j},0)$ or
$\beta_{jj}=(t_{j},1)$ and $p_{B}(t_{j},0)=t_{j}$. The two cases for $\beta$
we will discuss are as follows.

$\geq$$-$$-$$+$$+$$+$$+$$-$$-$$-$$+$$-$$-$$+$$\geq$$+$$(t_{j},0)$$(t_{k},0)$$(t_{j},1)$$(t_{k},1)$$0$$-t_{k}$$-t_{j}$$t_{k}$$t_{k}$$-t_{j}$$-t_{j}$$0$
(a) A valid BNOM labelling incompatible with IR and efficiency.

$\geq$$-$$-$$+$$+$$+$$+$$-$$-$$-$$+$$-$$-$$+$$\geq$$+$$(t_{j},0)$$(t_{k},0)$$(t_{j},1)$$(t_{k},1)$$0$$-t_{k}$$-t_{j}$$t_{k}$$t_{k}$$-t_{j}$$-t_{j}$$0$$(t_{j},0)$$(t_{k},0)$$(t_{j},1)$$(t_{k},1)$$0$$t_{k},t_{j}$$t_{k}$$-t_{j}$$-t_{j}$
(b) A valid BNOM labelling that yields single-line payments.

Figure 2: No BNOM labelling can achieve bounded subsidies in an efficient, IR
mechanism for bilateral trade.

_Case 1: $\beta$ is incompatible with IR and efficiency._ Consider $\beta$
where $\beta_{jj}=(t_{j},1)$, $\beta_{kj}=(t_{j},0)$, $\beta_{kk}=(t_{k},1)$,
and $\beta_{jk}=(t_{k},0)$. By the incentive-compatibility constraints
(represented by the red edge in Figure 2(a)) we have $0\geq
t_{k}-p_{B}(t_{j},0)=t_{k}-t_{j}$, a contradiction since $t_{j}<t_{k}$.

_Case 2: $\beta$ leads to single-line payments._ Consider $\beta$ where
$\beta_{jj}=\beta_{kj}=(t_{j},0)$, $\beta_{kk}=(t_{k},0)$, and
$\beta_{jk}=(t_{k},1)$ and whose graph $G_{B,f}^{\beta}$ is given in Figure
2(a) in which edges are annotated with their weights. By incentive-
compatibility constraints we have $0\geq t_{j}-p_{B}(t_{k},0)$ (represented by
red edge in Figure 2(b)) and hence $p_{B}(t_{k},0)\geq t_{j}$, as well as
$t_{k}-p_{B}(t_{k},0)\geq t_{k}-p_{B}(t_{j},0)$ (represented by the blue edge
in Figure 2(b)) and so $p_{B}(t_{k},0)\leq p_{B}(t_{j},0)$. Recall that we
have $p_{B}(t_{j},0)=t_{j}$ and therefore $t_{j}\leq p_{B}(t_{k},0)\leq
p_{B}(t_{j},0)=t_{j}$, so $p_{B}(t_{k},0)=t_{j}$. Now take $t_{j}=0$ and we
see that payments in a profile in which trade occurs are identically zero.
This is precisely the issue that leads to unbounded subsidies.

Each possible labelling, even when only considering two types $t_{j}$ and
$t_{k}$, falls into one of the four above mentioned cases. Thus the only valid
labellings that are not incompatible with IR and efficiency lead to exactly
the same payments as we get with a single-line mechanism. Hence subsidies
remain unbounded for arbitrary labellings for any efficient, IR, BNOM
mechanism. ∎

###  5.2 Characterising IR, WBB, NOM bilateral trade mechanisms

We close our analysis of NOM bilateral trade mechanisms by providing a full
characterisation of the class of IR, WBB, NOM mechanisms for this setting. We
introduce some notation to conveniently formulate our characterisation. For a
number $x$ we denote by $\text{succ}_{B}(x)$ and $\text{prec}_{B}(x)$
respectively the least element in $D_{B}$ strictly greater than $x$ and the
greatest element strictly less than $x$. We use $\text{succ}_{S}(y)$ and
$\text{prec}_{S}(y)$ to analogously for the seller’s domain $D_{S}$. Let
$H_{B}$ denote the least element in $D_{B}$ that is greater than every element
in $D_{S}$, and $L_{B}$ the greatest element in $D_{B}$ that is less than
every element in $D_{S}$. For a mechanism we may partition the type space into
three sets: $M_{0}^{B}$, $M_{1}^{B}$, and $M_{01}^{B}$. $M_{0}^{B}$ consists
of all bids of the buyer for which trade is guaranteed not to happen,
$M_{1}^{B}$ consists of all bids for which trade surely happens, and
$M_{01}^{B}$ consists of the remaining elements of $D_{B}$, where trade
depends on the seller’s bid. The sets $M_{0}^{S}$, $M_{1}^{S}$, and
$M_{01}^{S}$ can be defined analogously for the seller.

For a mechanism $M$ define the _utility interval_ $I_{B}(M,v,x)$ for the buyer
as the two numbers $(\ell,h)$ such that $\ell=\min\\{v(M(x,y))\,:\,y\in
D_{S}\\}$ and $h=\max\\{v(M(x,y))\,:\,y\in D_{S}\\}$, and define
$I_{S}(M,u,y)$ analogously for the seller. The NOM property imposes that
$I_{B}(M,v,v)\geq I_{B}(M,v,x)$ for all $v,x\in D_{B}$ and that
$I_{S}(M,u,u)\geq I_{S}(M,u,y)$ for all $u,y\in D_{S}$.

######  Theorem 5.7.

A deterministic bilateral trade mechanism $M$ for domains $D_{B},D_{S}$ is IR,
WBB, and NOM if and only if there are thresholds
$p_{B}^{\min},p_{B}^{\max},p_{S}^{\min},p_{S}^{\max}$, where $p_{B}^{\min}\leq
p_{B}^{\max}$ and $p_{S}^{\min}\leq p_{S}^{\max}$, such that:

  1. 1.

When trade doesn’t occur the buyer’s and the seller’s price are both zero.
When trade occurs the buyer’s price always exceeds the seller’s price, both
prices are non-negative, the buyer’s price is less than their valuation, and
the seller’s price is at least the buyer’s valuation.

  2. 2.

The set $M_{0}^{B}$ contains all types in $D_{B}$ less than $p_{B}^{\min}$,
the set $M_{1}^{B}$ contains all types in $D_{B}$ greater than $p_{B}^{\max}$,
and $M_{01}^{B}$ contains all types in $D_{B}$ in between $p_{B}^{\min}$ and
$p_{B}^{\max}$. If $p_{B}^{\min}$ is itself in $D_{B}$ then $p_{B}^{\min}$ is
in either $M_{0}^{B}$ or $M_{01}^{B}$. Similarly if $p_{B}^{\max}$ is in
$D_{B}$ then $p_{B}^{\max}$ is in either $M_{1}^{B}$ or $M_{01}^{B}$.

  3. 3.

For every type $x\in M_{01}^{B}\cup M_{1}^{B}$ the buyer’s payment in outcome
$M(x,y)$ is at least $p_{B}^{\min}$ for all $y\in D_{S}$, and there exists
some $y\in D_{S}$ such that in outcome $M(x,y)$ trade occurs and the buyer
pays $p_{B}^{\min}$. For every type $x\in M_{1}^{B}$ the buyer’s payment in
outcome $M(x,y)$ is at most $p_{B}^{\max}$ for all $y\in D_{S}$, and there
exists a $y\in D_{S}$ such that in outcome $M(x,y)$ trade occurs at price
$p_{B}^{\max}$.

  4. 4.

(Analogous to point 2 but for the seller) The set $M_{0}^{S}$ includes all
types in $D_{S}$ greater than $p_{S}^{\max}$, the set $M_{1}^{S}$ includes all
types in $D_{S}$ less than $p_{S}^{\min}$, and the set $M_{01}^{S}$ consists
of all types in $D_{S}$ in between $p_{S}^{\min}$ and $p_{S}^{\max}$. If
$p_{S}^{\min}$ itself is in $D_{S}$, then $p_{S}^{\min}$ is either in
$M_{1}^{S}$ or $M_{01}^{S}$. Similarly, if $p_{B}^{\max}$ is in $D_{S}$ then
$p_{B}^{\max}$ is in $M_{01}^{S}$ or $M_{1}^{S}$.

  5. 5.

(Analogous to point 3 but for the buyer) For every type $y\in M_{01}^{S}\cup
M_{1}^{S}$ there is some $x\in D_{B}$ such that in outcome $M(x,y)$ trade
occurs with seller’s price $p_{S}^{\max}$. For every type $y\in M_{1}^{S}$
there is furthermore a $x\in D_{B}$ such that in outcome $M(x,y)$ trade occurs
at price $p_{S}^{\min}$.

###### Proof.

($\implies$) Assume that $M$ is IR, WBB, and NOM. Point 1 follows directly
from IR and WBB. We will prove points 2 and 3, and since the proofs of points
4 and 5 follow analogous reasoning they are omitted. We assume for simplicity
of exposition that $M_{0}^{B}$, $M_{01}^{B}$, and $M_{1}^{B}$ are all non-
empty. In case one or more of these sets are empty, the proof reduces to a
simpler one.

Let $x_{0}^{\max}$ be the greatest type in $M_{0}^{B}$ and let $x$ be an
arbitrary type less than $x_{0}^{\max}$. We show that $x$ is in $M_{0}^{B}$.
Suppose the contrary and let $y$ be a seller’s type such that trade occurs in
outcome $M(x,y)$. The buyer’s price in $M(x,y)$ is at most $x$ by IR, and
hence it is less than $x_{0}^{\max}$. This means that the second element of
$I_{B}(M,x_{0}^{\max},x)$ is positive, while
$I_{B}(M,x_{0}^{\max},x_{0}^{\max})=(0,0)$; a contradiction to NOM. We have
now established that $x$ is in $M_{0}^{B}$ for all $x$ in $D_{B}$ where $x\leq
x_{0}^{\max}$.

Let $x_{1}^{\min}$ be the least type in $M_{1}^{B}$ and let $x$ be an
arbitrary type greater than $x_{1}^{\min}$. We show that $x$ is in
$M_{1}^{B}$. Suppose the contrary; then the first element of $I_{B}(M,x,x)$ is
0. However note that any buyer’s price charged when reporting $x_{1}^{\min}$
is less than $x_{1}^{\min}$ itself by IR, and hence is less than $x$. This
would mean that the first element of $I_{B}(M,x,x_{1}^{\min})$ is positive; a
contradiction to NOM. We have now established that $x$ is in $M_{1}^{B}$ for
all $x$ in $D_{B}$ where $x\geq x_{1}^{\min}$.

The above altogether shows that $M_{0}^{B}$, $M_{01}^{B}$, $M_{1}^{B}$
partition $D_{B}$ into three contiguous ranges: $M_{0}^{B}$ consists of all
valuations in $D_{B}$ up to and including $p_{0}^{\max}$, $M_{01}^{B}$
consists of all valuations in $D_{B}$ strictly in between $p_{0}^{\max}$ and
$p_{1}^{\min}$, and $M_{1}^{B}$ consists of all valuations in $D_{B}$ from
$p_{1}^{\min}$ and up.

Let $x$ be a type in $M_{01}^{B}\cup M_{1}^{B}$, and let $y$ be the seller’s
bid such that the buyer’s price is minimised in outcome $M(x,y)$. Denote this
price by $p(x)$. Thus we have that the second element of $I_{B}(M,x,x)$ is
$x-p(x)$. By NOM, for any other bid $x^{\prime}$ we have that the second
element of $I_{B}(M,x,x^{\prime})$ is at most $x-p(x)$. In particular for
$x^{\prime}$ in $M_{01}^{B}\cup M_{1}^{B}$ it holds that the second element of
$I_{B}(M,x^{\prime},x^{\prime})$ is $x^{\prime}-p(x^{\prime})$ and thus the
second element of $I_{B}(M,x,x^{\prime})$ is $x-p(x^{\prime})$. Thus,
$x-p(x^{\prime})\leq x-p(x)$, or equivalently $p(x)\leq p(x^{\prime})$. Since
this inequality holds for all $x,x^{\prime}$ in $M_{01}^{B}\cup M_{1}^{B}$, we
have that $p(\cdot)$ is constant over $M_{01}^{B}\cup M_{1}^{B}$, and we
define this constant as $p_{B}^{\min}$. Observe that $p_{B}^{\min}$ is at most
the least type in $M_{01}^{B}$, by IR (i.e., the type
$\text{succ}_{B}(x_{0}^{\max}))$. Furthermore $p_{B}^{\min}\geq x_{0}^{\max}$
because otherwise the second element of
$I_{B}(M,x_{0}^{\max},\text{succ}_{B}(x_{0}^{\max}))$ would equal
$x_{0}^{\max}-p_{B}^{\min}\geq x_{0}^{\max}-x_{0}^{\max}=0$, where 0 is the
second element of $I_{B}(M,x_{0}^{\max},x_{0}^{\max})$; a contradiction to
NOM. This establishes that the value $p_{B}^{\min}$ lies in the interval
$[x_{0}^{\max},\text{succ}_{B}(x_{0}^{\max})]$, as required from points 2 and
3 in the claim.

Let $x$ now be a type in $M_{1}^{B}$, and let $y$ be the seller’s bid such
that the buyer’s price is maximised in outcome $M(x,y)$. Denote this price by
$P(x)$. Thus, the first element of $I_{B}(M,x,x)$ is $x-P(x)$, for all $x\in
M_{1}^{B}$. Also, this implies that the first element of
$I_{B}(M,x,x^{\prime})$ is $x-P(x^{\prime})$ for all $x,x^{\prime}\in
M_{1}^{B}$, which in turn yields that $P(x)\leq P(x^{\prime})$ for all
$x,x^{\prime}\in M_{1}^{B}$, and hence $P(\cdot)$ is constant on $M_{1}^{B}$.
Let this constant be the value of $p_{B}^{\max}$.

Note that $p_{B}^{\max}$ is at most $x_{1}^{\min}$, by IR. Furthermore,
$p_{B}^{\max}\geq\text{prec}_{B}(x_{1}^{\min})$, as otherwise the first
element of $I_{B}(M,\text{prec}_{B}(x_{1}^{\min}),x_{1}^{\min})$ would be
positive. The first element of
$I_{B}(M,\text{prec}_{B}(x_{1}^{\min}),\text{prec}_{B}(x_{1}^{\min}))$ is 0;
contradicting with NOM. This proves that points 2 and 3 of the claim hold.

($\impliedby$) Assume that the 5 points of the claim hold for a mechanism $M$.
We show that M is IR, WBB, and NOM. The first two properties, IR and WBB,
follow trivially from point 1. We next show that NOM holds for the buyer. The
proof for the NOM-property for the seller is analogous and is therefore
omitted.

Let $x$ be a bid in $M_{0}^{B}$ so that $I_{B}(M,x,x)=(0,0)$. Obviously,
$I_{B}(M,x,x^{\prime})=(0,0)$ for all $x^{\prime}\in M_{0}^{B}$, as desired.
For $x^{\prime}\in M_{01}^{B}$ we know that the first element of
$I_{B}(M,x,x^{\prime})$ is 0 by definition of $M_{01}^{B}$. The second element
of $I_{B}(M,x,x^{\prime})$ is $x-p_{B}^{\min}$ by point 3, and $p_{B}^{\min}$
is at least $x$ by point 2, thus $x-p_{B}^{\min}$ is non-positive and
$I_{B}(M,x,x)\geq I_{B}(M,x,x^{\prime})$ for all $x^{\prime}\in M_{01}^{B}$,
as desired. For $x^{\prime}\in M_{1}^{B}$ we have
$I_{B}(M,x,x^{\prime})=(x-p_{B}^{\max},x-p_{B}^{\min})$, and both these
expressions are negative as $p_{B}^{\max}$ and $p_{B}^{\min}$ are both at
least $x$. Hence $I_{B}(M,x,x)\geq I_{B}(M,x,x^{\prime})$ for all
$x^{\prime}\in M_{1}^{B}$, as desired. This establishes that $I_{B}(M,x,x)\geq
I_{B}(M,x,x^{\prime})$ for all $x^{\prime}\in D_{B}$ and $x\in M_{0}^{B}$.

Next, let $x$ be a bid in $M_{01}^{B}$, so that
$I_{B}(M,x,x)=(0,x-p_{B}^{\min})$. For $x^{\prime}\in M_{0}^{B}$ we have that
$I_{B}(M,x,x^{\prime})=(0,0)\leq I_{B}(M,x,x)$. For $x^{\prime}\in M_{01}^{B}$
we have that $I_{B}(M,x,x)=I_{B}(M,x,x^{\prime})$ by definition of
$M_{01}^{B}$ and the properties of $p_{B}^{\min}$ stated under point 3 of the
claim. For $x^{\prime}\in M_{1}^{B}$ we have
$I_{B}(M,x,x^{\prime})=(x-p_{B}^{\max},x-p_{B}^{\min})$. Since
$p_{B}^{\max}\geq x$ the expression $x-p_{B}^{\max}$ is non-positive, so also
in this case we have $I_{B}(M,x,x)\geq I_{B}(M,x,x^{\prime})$. This
establishes that $I_{B}(M,x,x)\geq I_{B}(M,x,x^{\prime})$ for all
$x^{\prime}\in D_{B}$ and $x\in M_{01}^{B}$.

Lastly let $x$ be a bid in $M_{1}^{B}$, so that
$I_{B}(M,x,x)=(x-p_{B}^{\max},x-p_{B}^{\min})$. For any bid $x^{\prime}\in
M_{0}^{B}\cup M_{01}^{B}$ we have that trade may not occur, so that the first
element of $I_{B}(M,x,x^{\prime})$ is 0, which is less than or equal to
$x-p_{B}^{\max}$. If $x^{\prime}\in M_{0}^{B}$ then also the second element of
$I_{B}(M,x,x^{\prime})$ is 0, again less than $x-p_{B}^{\min}$. If
$x^{\prime}\in M_{01}^{B}$ then the second element of $I_{B}(M,x,x^{\prime})$
is $x-p_{B}^{\min}$, equal to the second element of $I_{B}(M,x,x)$. Thus
$I_{B}(M,x,x)\geq I(M,x,x^{\prime})$ for all $x^{\prime}\in M_{0}^{B}\cup
M_{01}^{B}$. For a bid $x^{\prime}\in M_{1}^{B}$ it simply holds that
$I_{B}(M,x,x^{\prime})=(x-p_{B}^{\max},x-p_{B}^{\min})=I_{B}(M,x,x)$, by the
properties of $p_{B}^{\max}$ and $p_{B}^{\min}$ in point 3 of the claim. This
establishes that $I_{B}(M,x,x)\geq I_{B}(M,x,x^{\prime})$ for all
$x^{\prime}\in D_{B}$ and $x\in M_{1}^{B}$. Altogether this yields that
$I_{B}(M,x,x)\geq I_{B}(M,x,x^{\prime})$ for all $x,x^{\prime}\in D_{B}$, i.e.
$M$ is NOM for the buyer. ∎

##  6 Conclusions

In this paper we have provided a series of results showing that NOM does not
trivialise the issues surrounding incentives, even in presence of monetary
transfers. It may still be impossible to obtain strong guarantees even if one
assumes that imperfectly rational agents will only deviate when it is easy for
them. Therefore, we believe that NOM mechanisms deserve to be better
understood.

Remaining with bilateral trade, we have shown that we cannot achieve all of
efficiency, IR, BNOM, and $\alpha$-WBB with bounded $\alpha$: what can we gain
if we also settle for approximate efficiency? For single-parameter agents, we
have shown that an allocation function is BNOM- and WNOM-implementable if and
only if it is overlapping, and that when this is the case a single-line
labelling is sufficient to define the payments. It would be interesting to
further explore what can be gained using a more general labelling than single-
line, and it is surprising that while this can alleviate the issues of
unbounded subsidies in bilateral trade for WNOM, the same is not true for
BNOM. In a similar vein, we have largely treated BNOM and WNOM as two sides of
the same coin, until they begin to diverge in Section 5. Similarly to [2], it
would be useful to further explore how the two sides of NOM relate to one
another, as well as the computational aspects of using NOM mechanisms.
Finally, we believe that the cycle monotonicity framework we have introduced
should help tackle multidimensional domains.

## References

  * [1] A. Archer and E. Tardos, Truthful mechanisms for one-parameter agents, in Proceedings 42nd IEEE Symposium on Foundations of Computer Science, 2001, pp. 482–491.
  * [2] H. Aziz and A. Lam, Obvious manipulability of voting rules, in Algorithmic Decision Theory, D. Fotakis and D. Ríos Insua, eds., Cham, 2021, Springer International Publishing, pp. 179–193.
  * [3] M. Babaioff, S. Dobzinski, and R. Kupfer, A note on the gains from trade of the random-offerer mechanism, CoRR, abs/2111.07790 (2021).
  * [4] L. Blumrosen and S. Dobzinski, (almost) efficient mechanisms for bilateral trading, Games and Economic Behavior, 130 (2021), pp. 369–383.
  * [5] K. Chatterjee and W. Samuelson, Bargaining under incomplete information, Operations Research, 31 (1983), pp. 835–851.
  * [6] A. H. csu and D. McAdams, “mechanism choice and strategic bidding in divisible good auctions: An empirical analysis of the turkish treasury auction market, Journal of Political Economy, 118 (2010), p. 833–865.
  * [7] B. de Keijzer, M. Kyropoulou, and C. Ventre, Obviously strategyproof single-minded combinatorial auctions, in 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), vol. 168 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, pp. 71:1–71:17.
  * [8] Y. Deng, J. Mao, B. Sivan, and K. Wang, Approximately efficient bilateral trade, CoRR, abs/2111.03611 (2021).
  * [9] U. Dur, R. G. Hammond, and T. Morrill, Identifying the harm of manipulable school-choice mechanisms, American Economic Journal: Economic Policy, 10 (2018), p. 187–213.
  * [10] D. Ferraioli, A. Meier, P. Penna, and C. Ventre, Automated optimal OSP mechanisms for set systems - the case of small domains, in Web and Internet Economics - 15th International Conference, WINE 2019, New York, NY, USA, December 10-12, 2019, Proceedings, vol. 11920 of Lecture Notes in Computer Science, Springer, 2019, pp. 171–185.
  * [11] , Obviously strategyproof mechanisms for machine scheduling, in 27th Annual European Symposium on Algorithms, ESA, vol. 144 of LIPIcs, 2019, pp. 46:1–46:15.
  * [12] D. Ferraioli, P. Penna, and C. Ventre, Two-way greedy: Algorithms for imperfect rationality, in Web and Internet Economics - 17th International Conference, WINE 2021, Potsdam, Germany, December 14-17, 2021, Proceedings, vol. 13112 of Lecture Notes in Computer Science, Springer, 2021, pp. 3–21.
  * [13] D. Ferraioli and C. Ventre, Probabilistic verification for obviously strategyproof mechanisms, in Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden, ijcai.org, 2018, pp. 240–246.
  * [14] , Obvious strategyproofness, bounded rationality and approximation - the case of machine scheduling, in Algorithmic Game Theory - 12th International Symposium, SAGT 2019, Athens, Greece, September 30 - October 3, 2019, Proceedings, vol. 11801 of Lecture Notes in Computer Science, Springer, 2019, pp. 77–91.
  * [15] , Approximation guarantee of OSP mechanisms: The case of machine scheduling and facility location, Algorithmica, 83 (2021), pp. 695–725.
  * [16] Z.-Y. Kang, F. Pernice, and J. Vondrák, Fixed-price approximations in bilateral trade, CoRR, abs/2107.14327 (2021).
  * [17] J. Kastl, Discrete bids and empirical inference in divisible good auctions, The Review of Economic Studies, 78 (2011), p. 974–1014.
  * [18] M. Kyropoulou and C. Ventre, Obviously strategyproof mechanisms without money for scheduling, in Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’19, Montreal, QC, Canada, May 13-17, 2019, 2019, pp. 1574–1581.
  * [19] R. Lavi and C. Swamy, Truthful mechanism design for multidimensional scheduling via cycle monotonicity, Games and Economic Behavior, 67 (2009), pp. 99–124.
  * [20] S. Li, Obviously Strategy-Proof Mechanisms, American Economic Review, 107 (2017), pp. 3257–3287.
  * [21] R. Myerson and M. Satterthwaite, Efficient mechanisms for bilateral trading, Journal of Economic Theory, 29 (1983), pp. 265–281.
  * [22] J. Ortega and E. Segal-Halevi, Obvious Manipulations in Cake-Cutting, arXiv:1908.02988 [cs, econ], (2019).  arXiv: 1908.02988.
  * [23] P. A. Pathak and T. Sönmez, Leveling the playing field: Sincere and sophisticated players in the boston mechanism, The American Economic Review, 98 (2008), p. 1636–1652.
  * [24] Rochet, J.-C., A necessary and sufficient condition for rationalizability in a quasi-linear context, Journal of Mathematical Economics, 16 (1987), pp. 191–200.
  * [25] A. E. Roth, A natural experiment in the organization of entry-level labor markets: regional markets for new physicians and surgeons in the united kingdom, American Economic Review, 81 (1991), p. 415–440.
  * [26] P. Troyan and T. Morrill, Obvious manipulations, Journal of Economic Theory, 185 (2020), pp. 1–26.
  * [27] C. Ventre, Truthful optimization using mechanisms with verification, Theoretical Computer Science, 518 (2014), pp. 64–79.