 Col.lecció d’Economia E18/378 
 
Valuation monotonicity, fairness and 
stability in assignment problems   
 
 
 
 
René van den Brink 
Marina Núñez 
Francisco Robles 
  
 
UB Economics Working Papers 2018/378 
 
 
Valuation monotonicity, fairness and stability in 
assignment problems  
 
 
Abstract: In this paper, we investigate the possibility of having stable rules for two- 
sided markets with transferable utility, that satisfy some valuation monotonicity and 
fairness axioms. Valuation fairness requires that changing the valuation of a buyer for 
the object of a seller leads to equal changes in the payoffs of this buyer and seller. This 
is satisfied by the Shapley value, but is incompatible with stability. A main goal in this 
paper is to weaken valuation fairness in such a way that it is compatible with stability. It 
turns out that requiring equal changes only for buyers and sellers that are matched to 
each other before as well as after the change, is compatible with stability. In fact, we 
show that the only stable rule that satisfies weak valuation fairness is the well-known 
fair division rule which is obtained as the average of the buyers-optimal and the sellers-
optimal payoff vectors. Our second goal is to characterize these two extreme rules by 
valuation monotonicity axioms. We show that the buyers-optimal (respectively sellers-
optimal) stable rule is char- acterized as the only stable rule that satisfies buyer-
valuation monotonicity which requires that a buyer cannot be better off by weakly 
decreasing his/her valuations for all objects, as long as he is assigned the same object 
as before (respectively object-valuation antimonotonicity which requires that a buyer 
cannot be worse off when all buyers weakly decrease their valuations for the object 
that is assigned to this specific buyer, as long as this buyer is assigned the same object 
as before). Finally, adding a consistency axiom, the two optimal rules are characterized 
in the general domain of allocation rules for two-sided assignment markets with a 
variable population.  
 
 
JEL Codes:  C71, C78, D63. 
 
Keywords: Assignment problem, valuation monotonicity, valuation fairness, stability, 
fair division rules, optimal rules.  
 
 
René van den Brink 
VU University and Tinberg  
 
Marina Nuñez 
Universitat de Barcelona 
 
Francisco Robles 
Universidad Carlos III de Madrid   
 
  
 
Acknowledgements: The authors acknowledge the support of the research grants ECO2017-
86481-P (Ministerio de Ciencia e Innovación) and 2017SGR778 (Generalitat de Catalunya).  
 
ISSN 1136-8365 
Keywords: assignment problems, stability, valuation monotonicity, valuation fairness,
fair division rule, optimal rules
1 Introduction
An allocation problem consists of a finite set of agents (that we call buyers) and a finite
set of objects that are to be allocated among the buyers. We assume that each object
belongs to a di↵erent seller and also that each buyer is willing to acquire at most one
object. Buyers have valuations over each available object and utility is quasi-linear in
money. Once these valuations are reported, an allocation rule determines an outcome:
who gets what and at what price. Notice that, once an object is allocated to a buyer,
this buyer transfers part of its utility to the seller by means of the price paid. Hence,
equivalently, an allocation rule determines a matching between buyers and sellers and
the resulting payo↵ for each agent.
We focus on those allocation rules that produce (pairwise) stable outcomes, that is,
outcomes that are not blocked by any pair of a buyer and a seller who are not matched
one to another but would be better o↵ if they were. The aim is to provide axiomatic
characterizations of some outstanding stable rules.
With such buyer-seller allocation problem with transferable utility, Shapley & Shubik
(1972) associates a coalitional game, the assignment game. These authors show that
the core coincides with the set of stable payo↵ vectors, and a consequence of its lattice
structure is the existence of two optimal stable payo↵ vectors: one that is optimal for
all buyers and the other optimal for all sellers.
In these buyer-seller markets, the buyers-optimal stable rule produces the minimum
competitive prices and coincides with the Vickrey multi-item auction. Hence it is of
relevance both in theory and practice.
Our first motivation comes also from Kojima & Manea (2010). There, in the com-
panion two-sided matching model where each agent has a preference list on the agents
on the opposite side of the market and monetary transfers are not allowed, the allo-
cation rule that is optimal for one side of the market (a deferred acceptance rule) is
characterized as the only stable rule that satisfies weak Maskin monotonicity.1
Similarly, we prove that in our buyer-seller market, among the set of stable rules,
each one of the two optimal stable rules is characterized by a monotonicity property:
the sellers-optimal stable rule is the only stable rule that satisfies object-valuation an-
timonotonicity and the buyers-optimal stable rule is the only stable rule that satisfies
buyer-valuation monotonicity. Object-valuation antimonotonicity requires that when all
buyers decrease their valuation of a given object but this does not change which buyer
receives that object, then the rule should not make this buyer worse o↵. Buyer-valuation
monotonicity requires that when one buyer decreases his valuations of all objects and
this fact does not change which object he receives, then the rule should not make this
buyer better o↵.
1We do not define formally weak Maskin monotonicity, since it refers to a model di↵erent to ours.
Roughly speaking, an allocation rule ' satisfies weak Maskin monotonicity if whenever agents change
from a preference profile R to R0 in such a way that, for any agent i, any object preferred to 'i(R)
under R0i is also preferred under Ri, then it holds that 'i(R0) is preferred to 'i(R) under R0i.
2
A valuation property that treats the buyers and sellers in a more balanced way is
valuation fairness being an equal treatment axiom which requires that, if a buyer’s
valuation for the object of one of the sellers changes, this has the same e↵ect on the
payo↵s of this buyer and the seller that owns the object.2 It is shown in van den Brink &
Pinte´r (2015) that the only rule that satisfies submarket e ciency (which requires that
every submarket allocates its own surplus among the buyers and sellers in the submarket)
and valuation fairness is the Shapley value (Shapley, 1953) being a well-known single-
valued solution for coalitional games. However, for assignment games, the Shapley
value may not assign a stable payo↵ vector. Since the core obviously satisfies submarket
e ciency, this implies that core stability is incompatible with valuation fairness.
A main goal in this paper is to weaken valuation fairness in a way that it becomes
compatible with core stability. We introduce a weaker form of valuation fairness, called
weak valuation fairness that requires that when a buyer modifies his valuation of the
object he is assigned by the rule, and after this change this object still remains assigned
to the same buyer, then the payo↵s to this buyer and to the seller that owns the object
change by the same amount. We show that weak valuation fairness is compatible with
core stability. More specific, we show that the only stable rule that satisfies weak
valuation fairness is the fair division rule (Thompson, 1981), being a well-known stable
rule where the payo↵ to an agent is the average between his/her maximum and minimum
stable payo↵s. This fair division rule is known to be pairwise monotonic, see Nu´n˜ez &
Rafels (2002), which requires that if one buyer weakly decreases his valuation of an
object, neither the buyer nor the owner of the object can be better o↵. However,
this monotonicity property is not enough to characterize the fair division rule among
the stable rules since, among others, the two optimal stable rules are also pairwise
monotonic.3
Our third and final goal is to look for axiomatizations of the two optimal stable
rules on the general domain of allocation rules for buyer-seller markets, that is, without
restriction to the subclass of stable rules. We can do this if we allow for a variable
population. For variable populations, consistency properties, that consider the e↵ect on
payo↵s when the population varies, have played a role in the axiomatization of solutions
for two-sided assignment markets. For instance, the core that can be seen as a set-
valued allocation rule, has been axiomatized using consistency axioms, see e.g., Sasaki
(1995) and Toda (2005). The model considered in Toda (2005) allows for individual
reservation values of the agents, which represent the payo↵s to those agents that remain
unmatched. Roughly speaking, the consistency property used in this axiomatization
requires that for each solution outcome, the same outcome should be recommended for
each subgame that results when some players leave with what they have received. A
single-valued stable allocation rule for the Shapley and Shubik assignment market that
has been characterized using some consistency, is the nucleolus that is characterized
in Llerena et al. (2015) by means of two axioms: derived consistency and symmetry of
maximum complaints of the two sides. The second property requires that the payo↵ to
the most disadvantaged buyer equals the payo↵ to the most disadvantaged seller. In this
setting of a variable population, we prove that the buyers optimal stable rule is the only
2This is based on the fairness axiom for communication graph games of Myerson (1977).
3Among non-stable rules, also the Shapley value satisfies pairwise monotonicity.
3
one that satisfies derived consistency and buyer-valuation monotonicity, while the sellers
optimal stable rule is the only one that satisfies derived consistency and object-valuation
antimonotonicity. Here, consistency is not required with respect to the subgame but
with respect to the derived game introduced in Owen (1992).
The paper is organized as follows. The buyer-seller assignment model is introduced in
Section 2, axiomatizations of the buyers-optimal and sellers-optimal stable rules among
the set of all stable allocation rules are provided in Section 3, while Section 4 contains
the characterization of the fair division rule. Section 5 provides axiomatizations of the
buyers and sellers optimal rules on the general class of allocation rules.
2 The model
Consider a market situation with two disjoint finite sets of agents: buyers and sellers.4
The set of buyers is denoted by B and the set of sellers is denoted by S. In this market,
each seller owns one and only one indivisible object on sale. On the other side of the
market, each buyer is interested in acquiring at most one object. Moreover, each buyer
i 2 B has a non-negative valuation in terms of money, aij 2 R+, for the object owned by
the seller j 2 S. We assume for the moment that the reservation price of each seller for
the object she owns is zero. Hence, for each buyer-seller pair (i, j) 2 B⇥S, the valuation
aij 2 R+ is the joint potential monetary gain for agents i and j if they trade. We denote
by ai = (aij)j2S a vector of valuations reported by buyer i and by AS the set of all
possible valuation vectors of each buyer i. A valuation profile is a = (ai)i2B 2 AB⇥S
where AB⇥S = AS⇥ ...⇥AS. With some abuse of notation, for any non-empty coalition
of buyers T ✓ B, aT and a T stand for (ai)i2T and (ai)i2B\T , respectively. AT⇥S is the
set of all valuation profiles for buyers in T ✓ B. Hence, a buyer-seller market is denoted
by a triplet (B, S, a).
Given a non-empty set of buyers B0 ✓ B and a non-empty set of sellers S 0 ✓ S,
a matching of the set of buyers B0 to the set of sellers S 0 is denoted by µ and it
consists of a subset of B0 ⇥ S 0 such that each agent in B0 [ S 0 appears in at most one
pair of µ. We denote by M(B0, S 0) the set of all such matchings. Given a matching
µ 2 M(B, S), denote by Sµ, the set of sellers matched to some buyer under µ, i.e.,
Sµ = {j 2 S | there is some i 2 B such that (i, j) 2 µ}. Similarly, Bµ denotes the set
{i 2 B | there is some j 2 S such that (i, j) 2 µ}.
Now, we focus on the notion of outcome of a market. An outcome consists of a payo↵
for each agent and a matching of B to S.
Definition 2.1. Consider a buyer-seller market (B, S, a). A payo↵ vector (u, v) 2 RB⇥
RS, is called a feasible payo↵ vector for (B, S, a) if there exists a matching µ 2M(B, S)
such that
1. ui + vj = aij for all (i, j) 2 µ,
2. ui = 0 for all i 2 B \Bµ,
4This model could be interpreted in alternative ways, for example, as a labour market in which the
set of agents are firms and workers.
4
3. vj = 0 for all j 2 S \ Sµ.
In that case, we say that (u, v;µ) is a feasible outcome for (B, S, a) and µ is compatible
with (u, v).
An outcome of a market then, specifies which agents are bilaterally trading. We
interpret an outcome of a particular market as follows. If a buyer i is matched to some
seller j, this buyer is paying the price vj to the seller for the object she has on sale.
Thus, point 1 in Definition 2.1, states that ui is the surplus of buyer i when he acquires
the object owned by seller j and pays vj. It is natural to require that if agents are not
trading, their payo↵ is zero. Notice that transfers between nonmatched pairs are not
allowed.
Definition 2.2. Consider a buyer-seller market (B, S, a). A matching µ 2M(B, S) is
optimal for (B, S, a) ifX
(i,j)2µ
aij  
X
(i,j)2µ0
aij for all µ
0 2M(B, S).
In the sequel, we introduce the notion of stable outcomes in order to capture the
idea of stable transactions among the agents.
Definition 2.3. Consider a buyer-seller market (B, S, a). A feasible outcome (u, v;µ)
for (B, S, a) is stable for (B, S, a) if
(i) ui   0 for all i 2 B and vj   0 for all j 2 S
(ii) ui + vj   aij for all (i, j) 2 B ⇥ S.
In that case, we say that (u, v) is a stable payo↵ vector for (B, S, a).
If an outcome (u, v;µ) is not stable in a market (B, S, a), then there is a buyer i 2 B
and a seller j 2 S who are not matched to each other at µ and ui + vj < aij. Then,
we say that this pair of agents (i, j) 2 B ⇥ S can block (u, v;µ). The underlying idea
is that each of them can obtain a greater payo↵ by leaving his/her current situation
and splitting their potential gain aij only among themselves. It follows easily, see for
instance Roth & Sotomayor (1990), that if (u, v;µ) is a stable outcome for a market
(B, S, a) then
µ 2M(B, S) is an optimal matching for (B, S, a) (1)
Now, let us introduce a coalitional game with transferable utility (TU-game)5 as-
sociated with this two-sided market. Consider a buyer-seller market (B, S, a). The
assignment game (B [ S,wa) associated with (B, S, a) is a TU-game and the worth of
any coalition of agents T ✓ B [ S is given as follows. First, since we need at least
one buyer and at least one seller to create a trade surplus, every coalition that contains
only buyers or only sellers has zero worth, i.e. wa(T ) = 0 if T \ B = ; or T \ S = ;.
Otherwise, if a coalition contains at least one buyer and at least one seller, then the
5 A coalitional game with transferable utility (N,w) is a pair formed by a finite set of players N and
a characteristic function w that assigns a real number w(T ) to each coalition T ✓ N , with w(;) = 0.
5
worth of the coalition is the maximal trade surplus that can be generated by matching
buyer-seller pairs, i.e.
wa(T ) = max
µ2M(T\B,T\S)
8<: X
(i,j)2µ
aij
9=; if T \ B 6= ; and T \ S 6= ;. (2)
Within TU-games, a prominent solution concept that captures a notion of stability
is the core. More precisely, the core of a TU-game (N,w) is the set C(w) = {x 2
RN | Pi2N xi = w(N),Pi2S xi   w(S) for all S ⇢ N} consisting of all payo↵ vectors
such that every coalition of agents earns at least the maximal surplus the agents in
the coalition can generate among themselves. It is shown in Shapley & Shubik (1972)
that the core of any assignment game is always non-empty and it coincides with the set
of stable payo↵ vectors. With respect to the structure of stable outcomes, Shapley &
Shubik (1972) shows that
if (u, v;µ) and (u0, v0;µ0) are stable outcomes for (B, S, a),
then (u, v;µ0) and (u0, v0;µ) are both stable for (B, S, a). (3)
The set of stable payo↵ vectors endowed with a partial order  B, which is the usual
order on the set of buyers’ payo↵ vectors, has a complete lattice structure (dual to
the lattice associated with order  S). As an immediate consequence, there is a unique
buyers-optimal stable payo↵, denoted by (u, v) 2 RB ⇥ RS such that u   u and v   v
for every other stable payo↵ vector (u, v) 2 RB ⇥ RS. And similarly there is a unique
sellers-optimal stable payo↵ (u, v) satisfying u  u and v  v for every other stable
payo↵ vector (u, v) 2 RB ⇥ RS. There is a simple expression for the maximum stable
payo↵ for any agent in the market, see for instance Roth & Sotomayor (1990). Consider
a market (B, S, a) and let k be a seller, then her maximum stable payo↵ in (B, S, a) is
given by
vk = max
µ2M(B,S)
8<: X
(i,j)2µ
aij
9=;  maxµ2M(B,S\{k})
8<: X
(i,j)2µ
aij
9=; , (4)
and the maximum stable payo↵ uk for any buyer k 2 B is obtained analogously.
In the following, we will introduce allocation rules for buyer-seller markets with the
objective of focusing on those that always produce a stable outcome.
Definition 2.4. Fix a set B of buyers and a set S of sellers. An allocation rule '
consists of maps (u, v;µ) from valuation profiles to feasible outcomes. That is, for each
a 2 AB⇥S, '(a) ⌘ (u(a), v(a);µ(a)) is a feasible outcome for (B, S, a).
Now, let us introduce stable rules as a subclass of allocation rules. A stable rule is
an allocation rule that always selects stable outcomes.
Definition 2.5. Fix a set B of buyers and a set S of sellers. An allocation rule ' ⌘
(u, v;µ) is a stable rule if for each valuation profile a 2 AB⇥S, '(a) = (u(a), v(a);µ(a))
is a stable outcome for (B, S, a).
6
In the next section, we introduce some monotonicity properties in order to study some
outstanding stable rules: the buyers-optimal stable rule, that for each valuation matrix
selects the buyers-optimal stable payo↵ vector together with a compatible matching,
and the sellers-optimal stable rule that selects the sellers-optimal payo↵ vector and a
matching compatible with this vector. Notice that for each of these two rules, the
associated payo↵ vector is uniquely determined but the compatible matching may not
be unique.
3 Axiomatization of optimal stable rules
In this section, we introduce axioms to obtain characterizations of the optimal stable
rules. The first axiom, object-valuation antimonotonicity, reflects the behaviour of an
allocation rule when all buyers weakly decrease their valuation for a single object.
Suppose that in a market (B, S, a), buyer t 2 B is acquiring the object owned by
seller k 2 S. Now, assume that every buyer in the market decreases his willingness to
pay for the object owned by this seller k. This could be explained by a loss of the quality
of the good. Then, if after this decrease in valuation, the rule again assigns object k
to buyer t, the payo↵ of buyer t will not decrease. Although buyer t’s willingness to
pay for the good owned by seller k might also decrease, compared to the other buyer’s
decrease in valuations, the valuation of buyer t is still high enough to guarantee that he
is matched to seller k. Then, the lower valuations for the good owned by seller k brings
buyer t in a stronger position against seller k.
Definition 3.1. Fix a set B of buyers and a set S of sellers. An allocation rule ' ⌘
(u, v;µ) satisfies object-valuation antimonotonicity (OVA) if for all a, a0 2 AB⇥S
for which there is a k 2 S such that a0ij = aij for all (i, j) 2 B ⇥ (S \ {k}) and a0ik  aik
for all i 2 B,
(t, k) 2 µ(a0) \ µ(a)) ut(a0)   ut(a).
Notice that this is a weak form of antimonotonicity since it only applies if the object
is assigned again to the same buyer. It turns out that among the stable rules, the
sellers-optimal stable rule is the only one satisfying object-valuation antimonotonicity.
Theorem 3.2. Fix a set B of buyers, a set S of sellers and let ' ⌘ (u, v;µ) be a stable
rule. For each a 2 AB⇥S, the payo↵ vector (u(a), v(a)) is the sellers-optimal stable
payo↵ vector for (B, S, a) if and only if ' satisfies OVA.
Proof. The “if” part. We prove that if a stable rule ' ⌘ (u, v;µ) satisfies OVA, then
for each valuation profile a 2 AB⇥S, the payo↵ vector (u(a), v(a)) is the sellers-optimal
stable payo↵ vector for the market (B, S, a). Assume by way of contradiction that for
some valuation profile a 2 AB⇥S and for some seller k 2 S, we have that vk(a) < vk
where vk is seller k’s maximum stable payo↵ in (B, S, a). Since ' is a stable rule
and because of the lattice structure of the set of stable payo↵ vectors, we have that
0  vk  vk(a) < vk. Notice that µ(a) is an optimal matching for (B, S, a), see (1).
Moreover, because of (3), (u, v;µ(a)) is a stable outcome for (B, S, a). Since vk > 0,
7
then feasibility implies that k is matched by µ(a). Let t 2 B be the buyer such that
(t, k) 2 µ(a).
Now, define the following valuation profile a0 2 AB⇥S by a0ij = aij for all (i, j) 2
B ⇥ (S \ {k}), a0ik = 0 for all i 2 B \ {t} and atk   vk < a0tk < atk   vk(a). Notice that
0  a0tk < atk. Now, we prove the following claim:
Claim: (t, k) 2 µ for all µ 2M(B, S) that is optimal for (B, S, a0).
First, define the following set of matchings M  ✓ M(B, S) by M  = {µ 2
M(B, S) | (t, k) /2 µ}. Notice that µ(a) 2 M(B, S) \M  where µ(a) is the matching
given by the rule ' considered at the beginning of this proof. We see that
P
(i,j)2µ(a) a
0
ij >P
(i,j)2µ0 a
0
ij for all µ
0 2M . Indeed,X
(i,j)2µ(a)
a0ij =
X
(i,j)2µ(a)\{(t,k)}
aij + a
0
tk >
X
(i,j)2µ(a)
aij   vk
=
X
(i,j)2µ(a)
aij  
✓ X
(i,j)2µ(a)
aij   max
µ2M(B,S\{k})
8<: X
(i,j)2µ
aij
9=;
◆
= max
µ2M 
8<: X
(i,j)2µ
a0ij
9=; , (5)
where the first inequality follows from a0tk > atk   vk, the second equality comes from
expression (4) for the maximum stable payo↵ and the third one from definition of a0.
Therefore, as a consequence of expression (5), we can guarantee that, if µ 2 M(B, S)
is an optimal matching for (B, S, a0), then it must hold (t, k) 2 µ and the claim is proved.
Now, since ' is a stable rule, if we apply ' to a0 2 AB⇥S we know that µ(a0) is
optimal for (B, S, a0). Hence, as a consequence of the previous claim, we have that
(t, k) 2 µ(a) \ µ(a0) and by the axiom OVA, we obtain
ut(a
0)   ut(a).
Making use of the fact that ' is a stable rule and stable outcomes are feasible outcomes,
we have
ut(a
0) = a0tk   vk(a0) and ut(a) = atk   vk(a).
Hence, we obtain a0tk   vk(a0) = ut(a0)   ut(a) = atk   vk(a), which implies that
vk(a0)  a0tk + vk(a)   atk < atk   vk(a) + vk(a)   atk = 0. This contradicts the fact
that ' selects a stable outcome because we should have vk(a0)   0 by condition (i) in
Definition 2.3. We conclude that our assumption that vk(a) < vk for some k 2 S does
not hold, and thus for each valuation profile a 2 AB⇥S, the payo↵ vector (u(a), v(a)) is
the sellers-optimal stable payo↵ vector for the market (B, S, a).
The “only if” part. We prove that if '⇤ ⌘ (u, v;µ⇤) is such that for each a 2 AB⇥S,
the payo↵ vector (u(a), v(a)) is the sellers-optimal stable payo↵ vector for (B, S, a),
8
then '⇤ satisfies OVA. Let a, a0 2 AB⇥S and k 2 S be such that a0ij = aij for all (i, j) 2
B ⇥ (S \ {k}) and a0ik  aik for all i 2 B. Moreover, assume that (t, k) 2 µ⇤(a0)\ µ⇤(a).
By expression (4) of the maximum stable payo↵, we have
ut(a) = atk   vk(a) = atk  
P
(i,j)2µ⇤(a) aij +maxµ2M(B,S\{k})
nP
(i,j)2µ aij
o
= maxµ2M(B,S\{k})
nP
(i,j)2µ aij
o
 maxµ2M(B\{t},S\{k})
nP
(i,j)2µ aij
o
= maxµ2M(B,S\{k})
nP
(i,j)2µ a
0
ij
o
 maxµ2M(B\{t},S\{k})
nP
(i,j)2µ a
0
ij
o
= a0tk  
P
(i,j)2µ⇤(a0) a
0
ij +maxµ2M(B,S\{k})
nP
(i,j)2µ a
0
ij
o
= a0tk   vk(a0) = ut(a0),
(6)
where the first equality comes from the feasibility of stable outcomes, the third one
because
µ⇤(a) \ {(t, k)} 2 argmaxµ2M(B\{t},S\{k})
8<: X
(i,j)2µ
aij
9=; ,
and the fifth and seventh follow from a similar reasoning with respect to a0. Therefore
'⇤ satisfies OVA and this completes the proof.
The reader will easily see that we can obtain a sort of “dual” axiomatization for
the buyers-optimal stable rule. To this end, we introduce the axiom of buyer-valuation
monotonicity which refers to the behavior of an allocation rule when a single buyer
weakly decreases his valuations of all objects.
Definition 3.3. Fix a set B of buyers and a set S of sellers. An allocation rule ' ⌘
(u, v;µ) satisfies buyer-valuation monotonicity (BVM) if for all a, a0 2 AB⇥S for
which there is a t 2 B such that a0ij = aij for all (i, j) 2 (B \ {t})⇥ S and a0tj  atj for
all j 2 S,
(t, k) 2 µ(a0) \ µ(a)) ut(a0)  ut(a).
Buyer-valuation monotonicity states that a buyer cannot be better o↵ by weakly
decreasing his valuations for all objects, as long as this buyer is assigned the same
object in both situations. Then, an immediate consequence of Theorem 3.2, by simply
interchanging the roles of buyers and sellers in its proof, is the following axiomatization
of the buyers-optimal stable rule.
Theorem 3.4. Fix a set B of buyers, a set S of sellers and let ' ⌘ (u, v;µ) be a stable
rule. For each a 2 AB⇥S, the payo↵ vector (u(a), v(a)) is the buyers-optimal stable
payo↵ vector for every buyer-seller market (B, S, a) if and only if ' satisfies BVM.
The above monotonicity axioms, OVA and BVM, refer to how payo↵s of the rule
react to the change of some valuation. This is di↵erent from manipulability axioms where
some agents may report false valuations in search of a higher surplus. The following
definition states a notion of manipulability by a group of buyers.
Definition 3.5. An allocation rule ' ⌘ (u, v;µ) is manipulable by a non-empty group
of buyers B0 ✓ B at a 2 AB⇥S if there is a profile a0B0 2 AB0⇥S such that for each i 2 B0,
the following two conditions hold:
9
1. there is j 2 S such that (i, j) 2 µ(a0B0 , a B0),
2. aij   vj(a0B0 , a B0) > ui(a).
Definition 3.6. Fix a set B of buyers and a set S of sellers. A stable rule ' ⌘ (u, v;µ) is
buyers strategy-proof (BSP) if it is not manipulable by any group of buyers B0 ✓ B
at any a 2 AB⇥S.
It is known, from Pe´rez-Castrillo & Sotomayor (2017), that the property of buyers
strategy-proofness also characterizes the buyers-optimal competitive-equilibrium rule
among the class of all competitive-equilibrium rules. Since in the Shapley & Shubik
(1972) assignment game the set of stable payo↵ vectors coincides with the set of com-
petitive equilibrium payo↵ vectors, the following characterization of the buyers-optimal
stable rule in terms of buyers strategy-proofness is straightforward.
Theorem 3.7. (Pe´rez-Castrillo & Sotomayor, 2017) For any set of buyers B and any
set of sellers S, let ' ⌘ (u, v;µ) be a stable rule. The vector (u(a), v(a)) is the buyers-
optimal stable payo↵ vector for any valuation profile a 2 AB⇥S if and only if ' is BSP.
Buyer-valuation monotonicity seems a rather weak axiom, but it turns out to be
strong enough to characterize the buyers-optimal rule among the stable rules. On the
other hand, buyers strategy-proofness, requiring non manipulability by groups of buyers,
seems rather strong, but it is weak enough for existence of a stable rule that satisfies
this property.
For more general preferences, not necessarily quasi-linear, and allowing for budget
constraints, Miyake (1998) also proves that the buyers-optimal auction is the only rule
that is (individually) strategy-proof among those rules that select a stable allocation.
The fact that the buyers-optimal stable rule satisfies buyers strategy-proofness can also
be deduced from a result in Demange & Gale (1985) for a related model with more
general preferences.
4 Axiomatization of the fair division rule
Apart from the two optimal stable rules analyzed until now, another outstanding stable
rule for assignment markets is the rule that produces the fair division point (Thompson,
1981). Given an assignment market (B, S, a), the payo↵ vector of the fair division rule
'⌧ ⌘ (u⌧ , v⌧ ;µ) satisfies u⌧ (a) = 12(u(a)+u(a)) and v⌧ (a) = 12(v(a)+v(a)). The stability
of the fair division rule follows straightforwardly since its payo↵ vector is the midpoint
of two stable payo↵ vectors. Nu´n˜ez & Rafels (2002) proves that the fair division rule of
an assignment market (B, S, a) equals the ⌧ -value (Tijs, 1981) of the related assignment
game (B [ S,wa) and that this rule satisfies pairwise monotonicity.
Definition 4.1. Fix a set B of buyers and a set S of sellers. An allocation rule ' ⌘
(u, v;µ) satisfies pairwise monotonicity (PM) if for all a, a0 2 AB⇥S such that there
is a buyer-seller pair (t, k) 2 B⇥S, a0ij = aij for all (i, j) 2 B⇥S\{(t, k)} and a0tk  atk,
it holds that
ut(a
0)  ut(a) and vk(a0)  vk(a).
10
Pairwise monotonicity states that if only one buyer weakly decreases his valuation
for an object, then nor this buyer neither the owner of the object can be better o↵. In
fact, in the aforementioned paper, the pairwise monotonicity of the fair division rule is
obtained as a consequence of the pairwise monotonicity of the two optimal stable rules.
It is shown in van den Brink & Pinte´r (2015) that also the Shapley value is pairwise
monotonic on the domain of assignment games. Moreover, these authors show that
the Shapley value is the only solution for assignment games that satisfies submarket
e ciency and valuation fairness.
Valuation fairness requires that when a single valuation is modified, both the buyer
and the seller that owns the object see their payo↵ changed by the same amount.
Definition 4.2. Fix a set B of buyers and a set S of sellers. An allocation rule ' ⌘
(u, v;µ) satisfies valuation fairness (VF) if for all a, a0 2 AB⇥S such that there is
a buyer-seller pair (t, k) 2 B ⇥ S, a0ij = aij for all (i, j) 2 (B \ {t}) ⇥ (S \ {k}) and
a0tk  atk, it holds that
ut(a
0)  ut(a) = vk(a0)  vk(a).
Given a buyer-seller market (B, S, a), a submarket is determined by a subset of
buyers B0 ✓ B and a subset of sellers S 0 ✓ S such that every buyer in B0 has value
zero for the objects that belong to sellers in S \ S 0, and buyers in B \ B0 have value
zero for the objects that belong to sellers in S 0. A payo↵ vector for market (B, S, a) is
submarket e cient if, for every submarket, the total payo↵ to agents in the submarket
equals the worth wa(B0 [ S 0) of the submarket.
Notice that no stable rule satisfies VF, since, by the definition of the core, they
all are submarket e cient. Hence, if a stable rule also satisfied VF, then, by van den
Brink & Pinte´r (2015), its payo↵ vector should coincide with the Shapley value which
contradicts that the rule is stable.
However, from our Theorem 3.2 and Theorem 3.4, we deduce that the fair division
rule satisfies a weaker form of valuation fairness which, similar as OVA and BVM,
requires equal changes only for matched pairs.
Definition 4.3. Fix a set B of buyers and a set S of sellers. An allocation rule ' ⌘
(u, v;µ) satisfies weak valuation fairness (WVF) if for all a, a0 2 AB⇥S such that
there is a buyer-seller pair (t, k) 2 B ⇥ S, a0ij = aij for all (i, j) 2 (B \ {t})⇥ (S \ {k})
and a0tk  atk, it holds that
(t, k) 2 µ(a) \ µ(a0)) ut(a0)  ut(a) = vk(a0)  vk(a).
Proposition 4.4. The fair division rule satisfies WVF in assignment markets with set
of buyers B and set of sellers S.
Proof. Let '⌧ ⌘ (u⌧ , v⌧ , µ) be the fair division rule. Fix a set B of buyers and a set
S of sellers, and a, a0 2 AB⇥S such that a0ij = aij for all (i, j) 2 (B \ {t}) ⇥ (S \ {k})
and a0tk  atk. Assume (t, k) 2 µ(a) \ µ(a0). In the proof of Theorem 3.2, showing
that the sellers-optimal stable rule satisfies OVA, we get ut(a
0) = ut(a) (see (6)) which,
with the fact that stable outcomes are feasible, implies that vk(a)  vk(a0) = atk   a0tk.
Similarly, from the proof that the buyers-optimal stable rule satisfies BVM, we obtain
11
vk(a
0) = vk(a) and hence ut(a)   ut(a0) = atk   a0tk. By definition of the fair division
rule '⌧ we have
u⌧t (a
0)  u⌧t (a) = v⌧k(a0)  v⌧k(a) =
1
2
(a0tk   atk). (7)
Notice from (7) that when a single valuation is increased (or decreased), the payo↵
of the fair division rule to the two related agents increases (or decreases) by the same
amount.
Moreover, the next theorem shows that on the domain of stable rules on buyer-seller
markets with a fixed set of agents, WVF characterizes the fair division rule.
Theorem 4.5. Fix a set of buyers B and a set of sellers S, and let ' ⌘ (u, v;µ) be a
stable rule. The payo↵ vector (u(a), v(a)) is the fair division point of (B, S, a) for each
a 2 AB⇥S if and only if ' satisfies WVF.
Proof. Let ' ⌘ (u, v;µ) be a stable rule that satisfies WVF and denote by (u⌧ (a), v⌧ (a))
the fair division point for the buyer-seller market (B, S, a), for any a 2 AB⇥S. Assume
that ' is not the fair division rule. Then, without loss of generality we can assume there
is a k 2 S and a0 2 AB⇥S such that
0  vk(a0) < v⌧k(a0). (8)
Let us write " = v⌧k(a
0)  vk(a0) > 0. Notice that v⌧k(a0) > 0 implies that k is matched
by µ(a0). Let t 2 B be such that (t, k) 2 µ(a0).
Starting with a0, define recursively for r = 1, 2, ..., a sequence of valuation profiles
ar 2 AB⇥S, as long as vk(ar 1) < v⌧k(ar 1), by
arij = a
r 1
ij for all (i, j) 2 B ⇥ (S \ {k}),
arik = 0 for all i 2 B \ {t}, and
artk = a
r 1
tk   v⌧k(ar 1). (9)
So, in all these valuation profiles, all buyers except t have valuation zero for the object
owned by seller k, while buyer t’s valuation for the object owned by seller k is updated
by subtracting the fair division payo↵ of the seller from the valuation in the previous
valuation profile. All other valuations stay the same.
Notice that, for all r   1, artk   0 since the fair division rule is a stable rule and as
a consequence artk = a
r 1
tk   v⌧k(ar 1) = u⌧t (ar 1)   0. Moreover,
artk = a
r 1
tk   v⌧k(ar 1) < ar 1tk   vk(ar 1) (10)
since we continue as long as vk(ar 1) < v⌧k(a
r 1).
We first prove the following claim.
Claim: For all r   1,
a) (t, k) 2 µ for any µ that is optimal for (B, S, ar),
b) v⌧k(a
r)  vk(ar) = v⌧k(a0)  vk(a0) = ", and
c) v⌧k(a
r) = 12r v
⌧
k(a
0)
12
We prove the claim by induction on r. Consider first r = 1. To this end, define
the following set of matchings M  ✓ M(B, S) by M  = {µ 2 M(B, S) | (t, k) /2 µ}.
Notice that µ(a0) 2M(B, S) \M . We will see that P(i,j)2µ(a0) a1ij > P(i,j)2µ0 a1ij for
all µ0 2M . Indeed,X
(i,j)2µ(a0)
a1ij =
X
(i,j)2µ(a0)\{(t,k)}
a0ij + a
1
tk >
X
(i,j)2µ(a0)
a0ij   vk(a0)
=
X
(i,j)2µ(a0)
a0ij  
✓ X
(i,j)2µ(a0)
a0ij   max
µ2M(B,S\{k})
8<: X
(i,j)2µ
a0ij
9=;
◆
= max
µ2M(B,S\{k})
8<: X
(i,j)2µ
a1ij
9=; = maxµ2M 
8<: X
(i,j)2µ
a1ij
9=; , (11)
where
(i) the first inequality follows from a1tk = a
0
tk v⌧k(a0) > a0tk vk(a0) which in its turn
follows from v⌧k(a
0)  vk(a0) by stability of the fair division rule, and v⌧k(a0) = vk(a0)
would imply v⌧k(a
0) = vk(a0) = vk(a
0) which is in contradiction with the assumption
(8),
(ii) the second equality comes from expression (4) for the maximum stable payo↵
and
(iii) the third (and fourth) equality follows from the definition of a1ik for all i 2 B\{t}.
Therefore, as a consequence of expression (11), we can guarantee that, if µ 2
M(B, S) is an optimal matching for (B, S, a1), then it must hold that (t, k) 2 µ and (a)
is proved for r = 1.
Now, since ' is a stable rule, µ(a1) is optimal for (B, S, a1) and (a) guarantees that
(t, k) 2 µ(a0) \ µ(a1). Then WVF of ' implies
ut(a
0)  ut(a1) = vk(a0)  vk(a1)
and again from stability of ' we have ut(a0) = a0tk   vk(a0) and ut(a1) = a1tk   vk(a1),
which leads to
vk(a
0)  vk(a1) = 1
2
(a0tk   a1tk) = v⌧k(a0)  v⌧k(a1),
where the second equality follows from (7). As a consequence, v⌧k(a
1) vk(a1) = v⌧k(a0) 
vk(a0) = " and (b) is proved for r = 1.
Finally, by definition of a1 in (9),
v⌧k(a
1)  v⌧k(a0) =
1
2
a1tk  
1
2
a0tk =
1
2
a0tk  
1
2
v⌧k(a
0)  1
2
a0tk =  
1
2
v⌧k(a
0)
which gives v⌧k(a
1) = 12v
⌧
k(a
0) and (c) is proved for r = 1.
To prove the claim for r > 1, we assume as induction hypothesis that ar 1 satisfies
(a), (b) and (c) and prove that ar also does. The proof of part (a) is analogous to the
one in case r = 1. Now, stability of ' guarantees that µ(ar) is optimal for (B, S, ar) and
hence (t, k) 2 µ(ar)\µ(ar 1). Then, since ' satisfies WVF we obtain ut(ar 1) ut(ar) =
13
vk(ar 1)  vk(ar) and again from stability of ' we have ut(ar 1) = ar 1tk   vk(ar 1) and
ut(ar) = artk   vk(ar), which leads to
vk(a
r 1)  vk(ar) = 1
2
(ar 1tk   artk) = v⌧k(ar 1)  v⌧k(ar),
where the second equality follows from (7). As a consequence, v⌧k(a
r)   vk(ar) =
v⌧k(a
r 1)  vk(ar 1) = " and v⌧k(ar) = 12v⌧k(ar 1) = 12r v⌧k(a0), showing (b) and (c).
This concludes the proof of the claim.
Once the claim is proved, notice that since v⌧k(a
0)   " > 0, there exists m 2 N such
that v⌧k(a
m) = 12m v
⌧
k(a
0) < ". Then, v⌧k(a
m)   " = vk(am) < 0, which contradicts that
'(am) is a stable outcome.
5 Axioms for the optimal stable rules on the general
domain of rules and variable population
The characterization results presented in Section 3 for the two optimal stable rules are
obtained on the class of assignment markets with a fixed set of agents B[S, and among
the set of stable allocation rules for these markets. Next, we show that the previous
results easily provide characterizations of the two optimal stable rules among the set of
general allocation rules, without imposing stability. To this end, we will make use of a
consistency property and hence we will allow for a variable population. Moreover, as
in Owen (1992), in order to guarantee that the reduced market remains in the class of
assignment markets, we enlarge this class by allowing for individual reservation values,
which stand for the gain of an agent when he remains unassigned.
Let U b and U s be the universe of buyers and sellers respectively. Given a set of
buyers B ✓ U b and a set of sellers S ✓ U s, each buyer i 2 B has a non-negative
valuation aij 2 R for the object of seller j 2 S, and also a reservation value ai0   0.
Each seller j 2 S has also a reservation value a0j   0 for his own object. By introducing
a fictitious agent on each side of the market, we summarize these valuations in a matrix
a = (aij)(i,j)2B0⇥S0 , where B0 and S0 are the set of buyers and sellers, respectively,
enlarged with the fictitious agents, and by convention a00 = 0. A triple (B, S, a) as
defined above is called a buyer-seller assignment market with reservation values .
Given a non-empty subset of buyers B0 ✓ B and a non-empty subset of sellers
S 0 ✓ S, a matching is now a partition of B0 [ S 0 in mixed pairs and singletons. With
some abuse of notation we continue denoting by M(B0, S 0) the set of matchings for B0
and S 0. Given a market (B, S, a), a matching µ is optimal if the addition of the values
of the elements of partition µ is not less than that of any other matching µ0 2M(B, S).
Now, the notions of feasible outcome and stable outcome follow easily for this setting.
Definition 5.1. Consider a buyer-seller assignment market with reservation values
(B, S, a). A payo↵ vector (u, v) 2 RB⇥RS, is called a feasible payo↵ vector for (B, S, a)
if there exists a matching µ 2M(B, S) such that
(i) ui + vj = aij for all i 2 B, j 2 S such that {i, j} 2 µ and
(ii) uk = ak0 if k 2 B, {k} 2 µ, vk = a0k if k 2 S, {k} 2 µ.
14
Then we say that (u, v;µ) is a feasible outcome for (B, S, a) and µ is compatible with
(u, v).
Definition 5.2. Consider a buyer-seller assignment market with reservation values
(B, S, a). A feasible outcome (u, v;µ) for (B, S, a) is stable for (B, S, a) if
(i) ui   ai0 for all i 2 B, vj   a0j for all j 2 S and
(ii) ui + vj   aij for all i 2 B and j 2 S.
Then we say that (u, v) is a stable payo↵ vector for (B, S, a).
To each buyer-seller assignment market with reservation values (B, S, a), we associate
a TU game (B [ S,wa) in a way similar to (2). We first define wa({i}) = ai0 for all
i 2 B, wa({j}) = a0j for all j 2 S and wa({i, j}) = aij for all (i, j) 2 B ⇥ S. Then, for
all ; 6= T ✓ B [ S,
wa(T ) = max
µ2M(T\B,T\S)
X
R2µ
wa(R).
The core of this assignment game with reservation values coincides with the set of
stable payo↵ vectors of (B, S, a) and also has a lattice structure with an optimal stable
payo↵ for each side of the market.
Consistency is a standard property used to analyze the behavior of allocation rules
with respect to a reduction of the population. A notion of reduced market for assignment
markets with reservation values is the derived market of Owen (1992). Consistency with
respect to this reduced assignment market is used in Llerena et al. (2015) to characterize
the nucleolus. In the derived assignment market relative to a coalition T , only the buyers
and sellers who belong to T are active, values for the objects ‘that are still in the market’
are the same as in the original market, and the individual reservation values are modified
taking into account the possibilities to trade with agents outside the derived market.
Definition 5.3. Let (B, S, a) be an assignment market, ; 6= T ✓ B[S and z = (u, v) 2
RB⇥RS. The derived assignment market relative to T at z is (B \T, S \T, aT,z) where
aT,zij = aij for all (i, j) 2 (B \ T )⇥ (S \ T ) and
(i) aT,zi0 = max
 
ai0,maxj2S\T{aij   vj}
 
, for all i 2 B \ T,
(ii) aT,z0j = max
 
a0j,maxi2B\T{aij   ui}
 
, for all j 2 S \ T.
Definition 5.4. On the domain of assignment markets with reservation values, an al-
location rule ' = (u, v;µ) assigns to each market (B, S, a) an outcome
'(B, S, a) ⌘ (u(B, S, a), v(B, S, a);µ(B, S, a))
that is feasible for this market.
Derived consistency means that in a derived market, the payo↵s for the buyers and
sellers that are still in the market do not change.
15
Definition 5.5. On the domain of assignment markets with reservation values, an al-
location rule ' ⌘ (u, v;µ) is derived consistent (DC) if for all markets (B, S, a) and
all coalitions ; 6= T ✓ B [ S,
ui(B \ T, S \ T, aT,z'(B,S,a)) = ui(B, S, a) for all i 2 B \ T and
vj(B \ T, S \ T, aT,z'(B,S,a)) = vj(B, S, a) for all j 2 S \ T,
where z'(B,S,a) = (u, v) if '(B, S, a) = (u, v).
Theorem 5.6. On the domain of assignment markets with reservation values,
1. the sellers-optimal stable rules are the only ones that satisfy DC and OVA,
2. the buyers-optimal stable rules are the only ones that satisfy DC and BVM.
Proof. We sketch the proof for the buyers-optimal stable rule, since the proof for the
sellers-optimal stable rule is analogous. From Proposition 2 in Llerena et al. (2015), on
the class of assignment markets with reservation values, derived consistency implies core
selection, i.e. stability of the rule. Together with Theorem 3.2 in the previous section6,
this guarantees the uniqueness of the rule’s payo↵ vector, that is, the buyers-optimal
stable rules are the only stable rules that can be DC and BVM. It only remains to prove
that indeed these rules are DC.
Take a buyer-seller market (B, S, a) and apply a buyers-optimal stable rule '(B, S, a) =
(u(a), v(a);µ(a)), and let z'(B,S,a) = (u(a), v(a)) be the buyers-optimal stable payo↵.
The derived market at ; 6= T ✓ B [ S and z'(B,S,a) = (u(a), v(a)) is (B \ T, S \
T, aT,z
'(B,S,a)
). We denote by z'(B,S,a)|T = (u(a)|T , v(a)|T ) the restriction of z
'(B,S,a) to
agents in T . Since the core of the assignment game satisfies derived consistency, see
Llerena et al. (2015), we have that z'(B,S,a)|T = (u(a)|T , v(a)|T ) is a stable payo↵ vector
for the derived market. We show that z'(B,S,a)|T is the buyers-optimal stable payo↵ vector
of the derived market (B \ T, S \ T, aT,z'(B,S,a)).
Assume on the contrary that there exists a stable payo↵ vector (u0, v0) of (B\T, S \
T, aT,z
'(B,S,a)
) and i0 2 B \ T such that u0i0 > ui0(a). Define then the following payo↵
vector: (u00, v00) 2 RB ⇥ RS with
u00i = u
0
i for all i 2 B \ T ; u00i = ui(a) for all i 2 B \ T,
v00j = v
0
j for all j 2 S \ T ; v00j = vj(a) for all j 2 S \ T.
We want to see that (u00, v00) is a stable payo↵ vector for the initial market (B, S, a).
Indeed, notice first, taking Definition 5.3 into account, that u00i   ai0 for all i 2 B and
v00j   a0j for all j 2 S. The reader will find easily that, since (u(a), v(a);µ) is a stable
outcome of (B, S, a), then
(a) aT,z
'(B,S,a)
i0 = ui(a) for all i 2 B \ T ,
(b) aT,z
'(B,S,a)
0j = vj(a) for all j 2 S \ T and
6Theorem 3.2 is stated and proved for buyer-seller markets with null reservation values but it is
straightforward to see that it also holds if we allow for non-negative reservation values.
16
(c) the matching µ0 2M(B \ T, S \ T ) such that {i, j} 2 µ0 if and only if {i, j} 2 µ
and {i, j} ✓ T is optimal for (B \ T, S \ T, aT,z'(B,S,a)).
In a derived market at a stable payo↵ vector, buyers are matched to the same sellers as
in the original market if both buyer and seller belong to the derived market, and buyers
(respectively sellers) who originally are matched to a seller (respectively buyer) outside
the market, stay unassigned in the derived market but with a modified reservation value.
As a consequence, (u00, v00;µ) is a feasible outcome for (B, S, a). Moreover,
(a’) For all (i, j) 2 (B \ T )⇥ (S \ T ) and (i, j) 2 (B \ T )⇥ (S \ T ), u00i + v00j   aij.
(b’) For all (i, j) 2 (B \ T )⇥ (S \ T ),
u00i + v
00
j = u
0
i + vj(a)   max
k2S\T
{aik   vk(a)}+ vj(a)   aij,
where the first inequality follows since u0i   aT,z
'(B,S,a)
i0   maxk2S\T{aik   vk(a)}.
(c’) For all (i, j) 2 (B \ T )⇥ (S \ T ),
u00i + v
00
j = ui(a) + v
0
j   ui(a) + max
k2B\T
{akj   uk(a)}   aij,
where the first inequality follows similar as under (b).
Since (u00, v00) is a stable allocation for (B, S, a), u00i0 = u
0
i0 > ui0(a), contradicts that '
is the buyers-optimal stable rule. Hence, ui(a) = ui(aT,z
'(B,S,a)
) for all i 2 B \ T , and
the buyers-optimal stable rule ' is derived consistent.
The axioms in the above characterizations are independent. The rule that associates
each valuation profile with the nucleolus payo↵ vector satisfies DC but neither OVA
nor BVM. In order to show that a rule satisfies OVA but not DC, tag the agents in
the following way, B = {1, 2, 3, ...} and S = {10, 20, 30, ...}. Consider now the rule
that associates each valuation profile with the diagonal matching ({i, i0} 2 µ(a) for
i 2 {1, 2, ..., n} where n = min{|B|, |S|}) and the payo↵ vector ui = 0 for all i 2 B,
vj = aij if j 2 S and there exists i 2 B such that {i, j} 2 µ(a), vj = 0 otherwise. This
rule satisfies OVA but not DC. A similar rule can be defined that satisfies BVM but not
DC.
Comparing Theorems 3.2 and 3.4 on one hand, and parts 1 and 2 of Theorem 5.6
on the other hand, we see that Theorems 3.2 and 3.4 characterize the sellers-optimal
and buyers-optimal rules among the stable rules , while Theorem 5.6 characterizes these
rules among all rules . But this comes ‘at a cost’, namely that we need to allow for a
variable population and we need to introduce reservation values for unassigned agents.
However, it is then su cient to use derived consistency which is a very natural property
for a variable population.
Since the fair division rule is not derived consistent, we cannot provide as a corollary
a straightforward axiomatization of this rule in the general class of rules (not imposing
stability) for variable population, as we have done for the two optimal stable rules.
17
6 Concluding remarks
In the class of all coalitional games, Young (1985) proves that core stability is incompat-
ible with coalitional monotonicity, which states that if the worth of only one coalition
is raised, no agent in this coalition can be worse o↵. For assignment markets, coali-
tional monotonicity is not an appealing property since when one buyer raises only one
of his valuations, several coalitions increase their worth. Pairwise monotonicity is a
more suitable monotonicity requirement for these buyer-seller markets, and it is com-
patible with stability since several stable rules (such as the buyers-optimal stable rule,
the sellers-optimal stable rule and the fair division rule) meet this requirement.
In this paper, we have proved that stability is also compatible with other monotonic-
ity properties such as object-valuation antimonotonicity and buyer-valuation monotonic-
ity. Moreover, these two monotonicity properties allow to discriminate between the two
optimal stable rules: the sellers-optimal stable rule, respectively the buyers-optimal sta-
ble rule. Adding derived consistency, we obtain characterizations of the two optimal
stable rules in the class of assignment markets with reservation values and variable pop-
ulation. Notice that derived consistency is a property that these optimal stable rules
have in common with the nucleolus on the same class of markets (Llerena et al., 2015).
Young (1985) also introduces strong monotonicity for TU-games which requires that
the payo↵ for a player does not decrease if the game changes in such a way that none
of his marginal contributions decrease. In van den Brink et al. (2013), Young’s mono-
tonicity is weakened by requiring the payo↵s of a player only to be nondecreasing if
its marginal contributions do not decrease and, moreover, also the worth of the ‘grand
coalition’ v(N) does not decrease. Casajus & Huettner (2014) shows that weakening
strong monotonicity in this way in Young’s axiomatizations characterizes the class of
egalitarian Shapley values being all convex combinations of the Shapley value and equal
division solution introduced by Joosten (1996).7 Considering assignment games, it is
interesting to observe that buyer-valuation monotonicity and pairwise monotonicity are
weaker than weak monotonicity since only one buyer increasing his value for the good
of one or more seller, does not decrease his marginal contributions and also does not
decrease the worth of the grand coalition in an assignment game. This makes buyer-
valuation monotonicity and pairwise monotonicity even nicer axioms for assignment
games.
Although, in two-sided markets where one side represents an institution, it may be
of social interest to choose the stable allocation rule that favors the weak side of the
market (students, resident doctors or bidders in an auction), in a buyer-seller market
where both sides are equally important, a more balanced payo↵ distribution between the
two sides of the market could be more reasonable. The fair division rule is characterized
as the only stable rule that satisfies weak valuation fairness, which is a weaker form of
valuation fairness as used in the characterization of the Shapley value for assignment
games provided in van den Brink & Pinte´r (2015), hence establishing some kind of
connection between the fair division rule and the Shapley value in buyer-seller markets.
Another weaker version of valuation fairness is based on weak di↵erential marginality
of Casajus & Yokote (2017) which weakens the fairness property of van den Brink (1991)
7This is shown for games where there are at least three players.
18
or the equivalent di↵erential marginality property of Casajus (2011). Applying weak
di↵erential marginality to assignment games requires that only increasing the valuation
of a buyer for the good o↵ered by one seller, changes the payo↵s of this buyer and seller
in the same direction (but not necessarily by the same amount). Our weak valuation
fairness is neither stronger nor weaker than this weak fairness axiom. On one hand,
our axiom makes a requirement on the payo↵s of a buyer and a seller only if the buyer
and seller stay matched while weak di↵erential marginality makes a requirement on
the payo↵s irrespective whether the buyer and seller stay matched or not. On the other
hand, our axiom requires equal changes, while weak di↵erential marginality only requires
changes to be in the same direction.
References
Casajus, A. 2011. Di↵erential marginality, van den Brink fairness and the Shapley value.
Theory and Decision, 71, 163–174.
Casajus, A., & Huettner, F. 2014. Weakly monotonic solutions for cooperative games.
Journal of Economic Theory, 154, 162–172.
Casajus, A., & Yokote, K. 2017. Weak di↵erential marginality and the Shapley value.
Journal of economic Theory, 167, 274–284.
Demange, G., & Gale, D. 1985. The strategy structure of two-sided matching markets.
Econometrica, 53, 873–888.
Joosten, R. 1996. Dynamics, equilibria and values dissertation. Maastricht University,
Maastricht.
Kojima, F., & Manea, M. 2010. Axioms for derrefed acceptance. Econometrica, 78,
633–653.
Llerena, F., Nu´n˜ez, M., & Rafels, C. 2015. An axiomatization of the nucleolus of the
assignment game. International Journal of Game Theory, 44, 1–15.
Miyake, M. 1998. On the incentive properties of multi-item auctions. International
Journal of Game Theory, 27, 1–19.
Myerson, R. 1977. Graphs and cooperation in games. Mathematics of Operations Re-
search, 2, 225–229.
Nu´n˜ez, M., & Rafels, C. 2002. The assignment game: the ⌧ -value. International Journal
of Game Theory, 31, 411–422.
Owen, G. 1992. The assignment game: the reduced game. Annales d’E´conomie et de
Statistique, 71–79.
Pe´rez-Castrillo, D., & Sotomayor, M. 2017. On the manipulability of competitive equi-
librium rules in many-to-many buyer-seller markets. International Journal of Game
Theory, 46, 1137–1161.
19
Roth, A., & Sotomayor, M. 1990. Two-sided matching: A study in game theoretic
modeling and analysis. Cambridge University Press, Cambridge.
Shapley, L. S., & Shubik, M. 1972. The assignment game I: the core. International
Journal of Game Theory, 1, 111–130.
Shapley, L.S. 1953. A value for n-person games. In: Kuhn, H.W., Tucker, A.W. (Eds.),
Contributions to the Theory of Games Volume II. Annals of Mathematical Studies,
28, 307–317.
Thompson, G. L. 1981. Auctions and market games. In: Aumann, R. (ed), Essays in
Game Theory and Mathematical Economics in Honor of Oskar Morgenstern.
Tijs, S. 1981. Bounds for the core and the ⌧ -value. In: Moeschlin, O. and Pallaschke,
P. (Eds.), Game Theory and Mathematical Economics. North Holland Publishing
Company, 123–132.
van den Brink, R. 1991. An axiomatization of the Shapley value using a fairness property.
International Journal of Game Theory, 30, 309–319.
van den Brink, R., & Pinte´r, M. 2015. On axiomatizations of the Shapley value for
assignment games. Journal of Mathematical Economics, 60, 110–114.
van den Brink, R., Funaki, Y., & Ju, Y. 2013. Reconciling marginalism with eaglitar-
ianism: consistency, monotonicity and implementation of egalitarian Shapley value.
Social Choice and Welfare, 40, 693–714.
Young, H. P. 1985. Monotonic solutions of cooperative games. International Journal of
Game Theory, 14, 65–72.
20