Content area
One-sided assignment problems combine important features of two well-known matching models. First, as in roommate problems, any two agents can be matched and second, as in two-sided assignment problems, the division of payoffs to agents is flexible as part of the solution. We take a similar approach to one-sided assignment problems as Sasaki (Int J Game Theory 24:373-397, 1995) for two-sided assignment problems, and we analyze various desirable properties of solutions including consistency and weak pairwise-monotonicity. We show that for the class of solvable one-sided assignment problems (i.e., the subset of one-sided assignment problems with a non-empty core), if a subsolution of the core satisfies [Pareto indifference and consistency] or [invariance with respect to unmatching dummy pairs, continuity, and consistency], then it coincides with the core (Theorems 1 and 2). However, we also prove that on the class of all one-sided assignment problems (solvable or not), no solution satisfies consistency and coincides with the core whenever the core is non-empty (Theorem 4). Finally, we comment on the difficulty in obtaining further positive results for the class of solvable one-sided assignment problems in line with Sasaki's (1995) characterizations of the core for two-sided assignment problems. [PUBLICATION ABSTRACT]
Soc Choice Welf (2010) 35:415433
DOI 10.1007/s00355-010-0447-8
ORIGINAL PAPER
Received: 31 August 2009 / Accepted: 23 February 2010 / Published online: 13 May 2010 The Author(s) 2010. This article is published with open access at Springerlink.com
Abstract One-sided assignment problems combine important features of two well-known matching models. First, as in roommate problems, any two agents can be matched and second, as in two-sided assignment problems, the division of payoffs to agents is exible as part of the solution. We take a similar approach to one-sided assignment problems as Sasaki (Int J Game Theory 24:373397, 1995) for two-sided assignment problems, and we analyze various desirable properties of solutions including consistency and weak pairwise-monotonicity. We show that for the class of solvable one-sided assignment problems (i.e., the subset of one-sided assignment problems with a non-empty core), if a subsolution of the core satises [Pareto indifference and consistency] or [invariance with respect to unmatching dummy pairs, continuity, and consistency], then it coincides with the core (Theorems 1 and 2 ). However, we also prove that on the class of all one-sided assignment problems (solvable or not), no solution satises consistency and coincides with the core whenever the core is nonempty (Theorem 4). Finally, we comment on the difculty in obtaining further positive results for the class of solvable one-sided assignment problems in line with Sasakis (1995) characterizations of the core for two-sided assignment problems.
B. Klaus (B)
Faculty of Business and Economics, University of Lausanne, Internef 538, 1015 Lausanne, Switzerland e-mail: [email protected]
A. Nichifor
Department of Economics, Maastricht University, P.O. Box 616, 6200 MD Maastricht, The Netherlandse-mail: [email protected]
Consistency in one-sided assignment problems
Bettina Klaus Alexandru Nichifor
123
416 B. Klaus, A. Nichifor
1 Introduction
Most racket sports (tennis, squash, badminton, etc.) have established top level doubles competitions. At the start of each tournament, there is a pre-dened time frame in which players have to organize themselves into pairs. The players are professionals who can make good estimates with respect to the potential gains of each possible pair. Once pairs are formed, partners cannot be changed during a tournament. If a player fails to form a pair he cannot participate in the doubles tournament. The players, with very few exceptions, are driven not only by their passion for the sport but also by pecuniary interests. The latter play an important role as the prizes at stake in the tournaments represent the players most significant source of revenue. This situation leads to a problem, where (rational) players have to simultaneously decide upon how to form pairs and how to distribute payoffs. Since reshufing of the pairs between tournaments is minor, we assume that there are many instances where the problem faced by the players has a stable solution. But what properties would this solution satisfy? What would happen to the solution if some pairs dropped out of the competition with their gains? From one tournament to another changes in the player hierarchy are relatively small. Consequently, players estimations with respect to the potential gains of each pair are likely to be adjusted by small amounts only. Does the adjustment affect the solution? Could we have distinct solutions that for each player keep the payoff invariant, but recommend different pairs to form? We call the situation described in this example a one-sided (assignment) problem, and we call the properties of the solutions hinted at in the questions above consistency, continuity, and Pareto indifference.
More generally, one-sided problems capture situations where any two agents may negotiate whether or not to enter a partnership and how to allocate resulting payoffs. Hence, a one-sided problem can be viewed as a very simple model of simultaneous network formation and allocation of value. Alternatively, a one-sided problem can be modeled in form of a cooperative game with transferable utility (see Remark1). Furthermore, one-sided problems have many similarities with two well-known matching problems: roommate problems (Gale and Shapley 1962) and assignment problems (Shapley and Shubik 1972). In roommate problems, agents have preferences over other agents and being alone (or consuming an outside option), and agents can either be matched in pairs or remain single. A one-sided problem coincides with a roommate problem if any single agent consumes his own value and any pair of agents consumes their joint value according to a predetermined division. In other words, a one-sided problem models a roommate problem where the assumption that payoffs to agents are xed ex-ante is relaxed. In two-sided (assignment) problems, the set of agents is partitioned into two sets and only agents from different sets can form pairs. Then, based on how agents are matched in such a two-sided market, the division of payoffs to agents is exible and part of the solution. Here, we generalize both models by allowing for one-sided matching as in roommate problems and for exible division of payoffs as in two-sided problems.
Eriksson and Karlander (2001), Sotomayor (2005), and Talman and Yang (2008) modeled and analyzed one-sided problems, although the terminology for one-sided problems differs in these papers. Eriksson and Karlander (2001) refer to roommate games with transferable utility, Sotomayor (2005) analyzes one-sided assignment
123
Consistency in one-sided assignment problems 417
games, and Talman and Yang (2008) study partner formation problems. We use the one-sided terminology to emphasize the relation of our results with those of Sasaki (1995) for two-sided assignment problems. A one-sided problem consists of a set of agents and a value function that species the value each pair of agents creates if matched (single agents do not create any value). A feasible outcome for a one-sided problem is a matching that partitions the set of agents in pairs and singletons and a payoff vector that divides the total value of the matching between the agents. A solution assigns to any one-sided problem a non-empty subset of feasible outcomes. As in many other economies, a concept of special interest is the core. Eriksson and Karlander (2001) use graph theory techniques and give a characterization of the core by a forbidden minors criterion. Sotomayor (2005) uses combinatorial arguments to identify necessary and sufcient conditions for the non-emptiness of the core. Talman and Yang (2008) use linear programming to provide necessary and sufcient conditions under which the core exists. Since there exist one-sided problems without core outcomes, strictly speaking the core is not a solution.
We call a one-sided problem with a non-empty core solvable. First, we show that a solvable one-sided problem is not essentially equal to a two-sided problem (Example 2), i.e., a solvable one-sided problem cannot always be mapped onto a core-isomorphic two-sided problem. Then, we aim to extend insights from the normative analysis of two-sided problems to solvable one-sided problems.
For two-sided problems, several characterizations of the core use consistency as a central property. Consistency is an invariance requirement of the solutions if some couples and singles leave with their payoffs. In order to understand this property, suppose that after agents are matched and payoffs are divided according to the solution, some agents leave with their assignment, and for the remaining agents, we apply the same solution. A solution would be considered to be inconsistent if it solves the problem for the remaining agents differently than before. For a comprehensive survey on consistency, see Thomson (2009).
In his rst characterization, Sasaki (1995, Theorem 2) considers consistency in conjunction with individual rationality, couple rationality, Pareto optimality, continuity, and weak pairwise-monotonicity. In his second characterization, Sasaki (1995, Theorem 4) replaces continuity by Pareto indifference. He proves both characterizations by showing that (Step 1) the core satises all properties used in both characterizations, (Step 2) a solution that satises all properties as stated in each of the characterizations is a subsolution of the core, and (Step 3) a solution that is a subsolution of the core and satises all properties as stated in each of the characterizations coincides with the core. For a two-sided problem closely related to the one investigated by Sasaki (1995), Toda (2005) also obtains two characterizations of the core (Toda 2005, Theorems 3.1 and 3.2) and he discusses how his results relate to Sasakis results (Toda 2005, page 249).
We adopt the properties considered by Sasaki (1995) to see how far his results for two-sided problems can be extended to one-sided problems. Since Sasaki (1995) characterized the core, we start by restricting attention to the class of solvable one-sided problems. First, and corresponding to Step 1 of Sasakis analysis, we prove that on the class of solvable one-sided problems, the core satises all of the properties considered by Sasaki (1995) (Proposition 1). Second, and corresponding to Step 3 of Sasakis
123
418 B. Klaus, A. Nichifor
analysis, we show that for the class of solvable one-sided problems, if a subsolution of the core satises (i) Pareto indifference and consistency or (ii) invariance with respect to unmatching dummy pairs, continuity, and consistency, then it coincides with the core (Theorems 1 and 2). Note that invariance with respect to unmatching dummy pairs is a property that we introduce, and that without it neither our Theorem 2 nor Sasakis corresponding Theorem 1 would be correct (see Example 5). Adapting Sasakis Step 2 directly to solvable one-sided problems turns out to be impossible because certain steps in the proof would transform a solvable one-sided problem into one with an empty core. We discuss this issue with Step 2 for solvable one-sided problems in Subsect. 4.2. It is currently an open question if Sasakis (1995, Theorems 2 and 4) characterizations of the core can be extended to the class of solvable one-sided problems. Finally, we prove that on the class of all one-sided problems (solvable or not), no solution satises consistency and coincides with the core whenever the core is non-empty (Theorem 4).
2 Model and definitions
Let N be the set of potential agents and N be the set of all non-empty nite subsets
of N, i.e., N = {N
N
R+ such that for each i N, (i, i) = 0, is a characteristic
function for N. For each pair (i, j) P(N), (i, j) 0 is the monetary benet, or
value, that i and j can jointly obtain. We call (i, i) the reservation value of agent i and normalize it to be 0. Let (N) be the set of all characteristic functions on P(N).
A one-sided (assignment) problem is a pair (N, ) N (N). A two-sided
(assignment) problem is a one-sided problem where the set of agents N can be partitioned in two subsets M and W, i.e., N = M W and M W = , and all
pairs of agents from the same subset or side fail to generate strictly positive values,i.e., for each (i, j) M M and (i, j) W W, (i, j) = 0. We denote the
set of all one-sided problems for N N by N , and the set of all one-sided prob
lems by = NN N . From now on, we refer to one-sided problems simply as
problems, except when referring to one-sided problems in comparison to two-sided problems.
Let N N . A matching for N (or N ) is a function : N N of
order two, i.e., for each i N, ((i)) = i. Two agents i, j N are matched
if (i) = j (or equivalently ( j) = i); for convenience, we also use the notation
(i, j) . If i = j, then we say that agents i and j form a couple. If i = j, we say
that agent i remains single. Thus, at any matching , the set of agents is partitioned into a set of couples C() = {(i, j) P(N) | (i) = j, i = j} and a set of sin
gles S() = {i N | (i) = i}, with |N| = 2|C()| + |S()|. For simplicity, we
also denote a matching by a vector, e.g., for N = {1, 2, 3} and matching such that
C() = {(1, 2)} and S() = {3}, we write = (2, 1, 3). Let M(N) denote the set
of matchings for N (or ).
| > |N| > 0}. For each N N , we denote the set of
distinct pairs that agents in N can form (including the degenerate case where agent i N forms the pair (i, i)) by P(N) = {(i, j) N N | i j}. For each N N ,
a function : P(N)
123
Consistency in one-sided assignment problems 419
In the following, we assume that N .
A matching M(N) is optimal for if for each M(N), (i, j) (i, j)
(i, j) (i, j). Let OM( ) denote the set of these matchings. Note that OM( ) = .
A feasible outcome for is a pair (, u) M(N)
R|N| where is a matching and u is a payoff vector such that iN ui = (i, j) (i, j) = (i, j)C() (i, j).
Let F( ) denote the set of feasible outcomes for .
A feasible outcome (, u) is Pareto optimal for if for each M(N), iN ui = (i, j) (i, j) (i, j) (i, j). Let PO( ) denote the set of these outcomes.
Note that if is optimal for , then any feasible outcome (, u) is Pareto optimal for .
The next property is a voluntary participation condition based on the idea that an agent can always enforce his reservation value by staying single.
A feasible outcome (, u) is individually rational for if for each i N, ui 0.
Let IR( ) denote the set of these outcomes.
Next, we require that if two agents form a couple, they receive a total payoff that is greater than or equal to their value.
A feasible outcome (, u) is couple rational for if for each (i, j) C(), ui +
u j (i, j). Let CR( ) denote the set of these outcomes.1 Non-negativity of values
and feasibility imply that if a feasible outcome (, u) is couple rational, then for each (i, j) C(), ui + u j = (i, j) and for each i S(), ui = (i, i).
If, at a feasible outcome (, u), there are two agents (i, j) P(N) such that i = j
and ui + u j < (i, j), then i and j have an incentive to form a couple in order to
obtain a higher payoff. In this case, {i, j} is a blocking pair for the outcome (, u).
A feasible outcome (, u) is stable for if it is individually rational for and no blocking pairs exist, i.e., (, u) IR( ) and for each (i, j) P(N) such that
i = j, ui + u j (i, j). Let S( ) denote the set of these outcomes.
It is well-known that if an agent is single at a stable outcome, then at each stable outcome, he receives his reservation value (e.g., Roth and Sotomayor 1990, Lemma 8.5).
A problem N is solvable if S( ) = . The following example shows that the
set of stable outcomes may be empty.
Example 1 (A problem that is not solvable) Let N = {1, 2, 3}, be dened by
(1, 2) = (2, 3) = (1, 3) = 1, and = (N, ). Then, for each (, u) F( ), u1 + u2 + u3 1 and there exist two agents i and j, i = j, such that
ui + u j < (i, j) = 1. Thus, S( ) = . Remark 1 (The set of stable outcomes equals the core) The set of stable outcomes coincides with the core (Sotomayor 2005, Proposition 1). Alternatively, we could model a problem N as the cooperative game with transferable utility (TU)
whose characteristic function assigns to each coalition S, the number (S)
maxM(S){ (i, j) (i, j)} with () = 0. The core of N is the set C( ) = {(, u) F( ) | for all S N, iS ui (S)}. Thus, for any problem N ,
a feasible outcome is in the core if no coalition of agents S N can improve their
payoffs by rematching among themselves.
1 Our definition of couple rationality is identical to the one in Sasaki (1995) and it implies (pairwise) feasibility in Toda (2005) and Sotomayor (2005).
123
420 B. Klaus, A. Nichifor
From now on, we simply refer to the set of stable outcomes as the core.
Eriksson and Karlander (2001) nd many similarities between solvable one-sided problems and two-sided problems. The impression one might get is that in the core of solvable one-sided problems, there always exists a two-sided partition of the agents. Then, it is possible that for each solvable one-sided problem, there exists a core-isomorphic two-sided problem, i.e., by choosing the appropriate partition of agents (setting the values of now incompatible pairs equal to zero) one can convert the one-sided problem into a two-sided problem without changing the set of core outcomes. The following example shows that this cannot always be done.
Example 2 (Two-sided and solvable one-sided problems are not core-isomorphic) Let N = {1, 2, 3}, be dened by (1, 2) = 2, (2, 3) = (1, 3) = 1, and = (N, ).
Then, is solvable because S( ) = {(, u) | = (2, 1, 3) and u = (1, 1, 0)}. The
unique stable matching induces a natural partition of the set of agents N = M W
where agents 1 and 2 have different genders. Assume that this solvable one-sided problem can be mapped onto a core-isomorphic two-sided problem and, without loss of generality, M = {1, 3} and W = {2}. Then, formally, we can associate with a
two-sided problem (M W, ), where we dene as the restriction of to fea
sible (manwoman) pairs, i.e., (1, 2) = 2, (2, 3) = 1, and (1, 3) = 0 (agents 1
and 3 are both male and now do not create any positive value). The problem is still solvable since S( ) = {(, u ) | = (2, 1, 3) and u = (, 2, 0) for [0, 1]}.
Observe that u 1 u1, u 2 u2, and u 3 = u3, and that the same matching is part of
both S( ) and S( ). Thus, S( )
S( ) and consequently is not core-isomorphic to .
A solution species how to form couples and how to distribute payoffs among the agents. Formally, a solution associates with each a non-empty subset of
feasible outcomes, i.e., for each , ( ) F( ) and ( ) = . A solution is
a subsolution of solution if for each , ( ) ( ).
3 Properties of solutions
In this section, we introduce desirable properties of solutions.
Individual rationality: for each , ( ) IR( ).
Couple rationality: for each , ( ) CR( ).
Pareto optimality: for each , ( ) PO( ).
The next property requires that if an outcome is chosen by the solution, then all feasible outcomes with the same payoff vector have to be part of the solution.
Pareto indifference: for each and each (, u) ( ), if ( , u) F( ), then
( , u) ( ).
123
Consistency in one-sided assignment problems 421
Note that we use the term Pareto indifference with some abuse of terminology since agents preferences are only indirectly determined by payoffs (each agents preference relation is strictly monotonic in his payoff).
For the next property, we introduce the notion of a dummy pair for a matching: two agents who are a couple at a given matching but do not create any strictly positive value. Let N . For M(N), i and j are a dummy pair at if (i, j) C()
and (i, j) = 0. Let D A(, ) denote the set of agents that form dummy pairs at .
We call D A(, ) the set of dummy agents at .
The following property requires that if an outcome for which the matching contains dummy pairs is chosen by the solution, then all feasible outcomes obtained by unmatching some of the dummy agents have to be part of the solution.
Invariance with respect to unmatching dummy pairs: for each , each (, u)
( ), and all ( , u) F( ) such that C( ) C() and S( ) \ S()
D A(, ), ( , u) ( ).2
Note that invariance with respect to unmatching dummy pairs has no bite if D A(, ) = . Furthermore, Pareto indifference implies invariance with respect
to unmatching dummy pairs.
The following is a standard technical requirement. Loosely speaking, it requires that small changes in the value function do not cause large changes in the payoffs and no sudden changes in supporting matchings.
Let N N . Let {k}kN be a sequence of characteristic functions for N. Then,
we write k
k
if for each (i, j) P(N), k(i, j)
k
(i, j). Let {uk}kN be a sequence of payoff vectors for N. Then, we write uk
k
u if for each
Continuity: for each N N , each M(N), each sequence {k}kN, and each
sequence {uk}kN such that for each k
N, k (N) and (, uk) (N, k), if
u, then (, u) (N, ).
Thus, a solution satises continuity if it is a closed correspondence. Our definition of continuity is one of the possible generalizations of continuity from functions to correspondences and in line with upper-hemicontinuity.3
In order to dene the next property, we rst introduce the notion of a subproblem. Let = (N, ), N N, and P(N ) = {(i, j) N N | i j}. We denote by
|N the restriction of value function to P(N ), i.e., |N : P(N )
R+ is such
that for each (i, j) P(N ), |N (i, j) = (i, j). Then, |N = (N , |N ) N is
a subproblem of .
2 Note that C( ) C() implies S( ) S().
3 Under some mild requirements (e.g., compactness), our closed-correspondence continuity is equivalent to upper-hemicontinuity. Continuity of correspondences is usually dened by requiring upper- and lower-hemicontinuity. Hence, strictly speaking, we (as well as Sasaki 1995) use the term continuity to shorten the name of our continuity property with some abuse of terminology.
i N, uki
k
ui.
(N, k)
k
(N, ) and uk
k
123
422 B. Klaus, A. Nichifor
For any matching M(N), we denote by (N ) the set of agents who are
matched to agents in N , i.e., (N ) = {i N | 1(i) N }. Furthermore, for each
u
R|N |
R|N|, let u|N denote the restriction of payoff vector u to N , i.e., u|N u
such that for each i N , u i = ui.
Next is an invariance requirement of the solutions if some couples and singles leave with their payoffs.
Consistency: for each N N , each N , each (, u) ( ), and each N N
such that (N ) = N , (|N , u|N ) (|N ).
For a comprehensive survey on consistency, see Thomson (2009).
Finally, we introduce a monotonicity property that requires that if the value of a couple increases, then the total payoff of the couple should not decrease.
Weak pairwise-monotonicity: for each N N , each (N), each (i, j)
P(N), i = j, and each (N) such that
(i, j) (i, j) and (1) (i , j ) = (i , j ), otherwise, (2)
if (, u) (N, ), then there exists (, u) (N, ) such that ui + uj
ui + u j .
4 Results
4.1 Positive results on the class of solvable problems
Our rst positive result is that the core of solvable problems satises all of the above properties, which extends a similar result by Sasaki (1995, Propositions 3 and 4) for two-sided problems to solvable one-sided problems.4
Proposition 1 On the class of solvable problems, the core satisesindividual rationality,couple rationality,Pareto optimality,Pareto indifference,invariance with respect to unmatching dummy pairs, continuity, consistency, and weak pairwise-monotonicity.
ProofIndividual rationality, couple rationality, and Pareto optimality: for each solvable , if (, u) S( ), then it is immediate that (, u) PO( )IR( )CR( ).
Pareto indifference and invariance with respect to unmatching dummy pairs: for each solvable , assume (, u) S( ). Let ( , u) F( ). Then, since any blocking
pair for ( , u) would also be a blocking pair for (, u), ( , u) S( ). Furthermore,
Pareto indifference implies invariance with respect to unmatching dummy pairs. Continuity: let N N , M(N), {k}kN, and {uk}kN such that for all k
N, k (N) and (, uk) S(N, k). Assume that (N, k)
k
(N, ) and
4 The core of solvable problems also satises another consistency property called converse consistency. However, since we do not use converse consistency in the sequel, we do not include this result here.
123
Consistency in one-sided assignment problems 423
uk
k
u. Since the correspondence of feasible outcomes is continuous, (, u) is
feasible. By stability, for each i N, uki 0 and for each (i, j) P(N), uki + ukj
k(i, j). Letting k , for each i N, ui 0 and for each (i, j) P(N), ui +
u j (i, j). Hence, (, u) S(N, ).
Consistency: for each solvable , if (, u) S( ), then there is no blocking pair
for (, u). Hence, no blocking pair exists in any of the (smaller) reduced problems, and all reduced problems are solvable.
Weak pairwise-monotonicity: let N, (i, j) P(N), and , (N) be as in the
definition of weak pairwise-monotonicity. We show that (, u) S(N, ) implies
that there exists (, u) S(N, ) such that ui + uj ui + u j .
Let (, u) S(N, ).
Case 1 (i) = j.
Let = and dene u as follows: ui = ui + [(i, j) (i, j)]/2, uj =
u j + [(i, j) (i, j)]/2 and for each i N \ {i, j}, ui = ui . By (1), (i, j)
(i, j) and consequently ui, uj 0. Thus, (, u) IR(N, ). Since (i, j)
C(), ui + uj = (i, j). By definition of u, for each (i , j ) = (i, j), ui + uj =
ui + u j . Since (, u) S(N, ), ui + u j (i , j ) and by (2), (i , j ) =
(i , j ). Thus, for each (i , j ) P(N) such that i = j we have ui + uj
(i , j ), i.e., (, u) S(N, ). Note that ui+uj = ui +u j +[(i, j)(i, j)]
which by (1), yields ui + uj ui + u j .
Case 2 (i) = j.
Let (, u) S(N, ). Then, OM(N, ) and consequently,
(i , j ) (i , j ) (i , j ) (i , j ). By (2) and since (i, j) / C(),
(i , j ) (i , j ) = (i , j ) (i , j ). Thus,
(i , j ) (i , j ) (i , j ) (i , j ). (3)
Case 2.1 (i) = j.
By (3) and feasibility, i N ui = (i , j ) (i , j ) (i , j ) (i , j ) =
i N ui . Suppose ui + uj < ui + u
j . Then, i N\{i, j} ui = (i , j )\{(i, j)} (i , j ) > i N\{i, j} ui . Thus, there exists
(i , j ) = (i, j) such that (i , j ) C() and (i , j ) > ui +u j . However, by
(2), (i , j ) = (i , j ). Hence, (i , j ) > ui + u j , which is a contradiction
to (, u) S(N, ). Therefore, ui + uj ui + u j .
Case 2.2 (i) = j.
Further, assume / OM(N, ). Then, (3) is strict and by (2), (i , j ) (i , j ) = (i , j ) (i , j ). Consequently, (i, j) (i, j) > (i, j) (i, j), which is
a contradiction to OM(N, ). Alternatively, now assume OM(N, ).
Then, we could have chosen u = u, which gives ui + uj = ui + u j .
123
424 B. Klaus, A. Nichifor
Remark 2 (The class of solvable one-sided problems is closed) An immediate consequence of the continuity of the core (Proposition 1) is that the class of solvable problems is topologically closed, i.e., if for all k
N, (N, k) N is solvable,
u, then (N, ) is also solvable.
The next theorem is a counterpart of Sasaki (1995, Theorem 3) for solvable problems.
Theorem 1 On the class of solvable problems, if is a subsolution of the core satisfying consistency and Pareto indifference, then coincides with the core.
Proof Let N be a solvable problem. Then, ( ) S( ). We prove that
( ) S( ), i.e., we show that (, u) S( ) implies (, u) ( ).
Let (, u) S( ). Let n
N
(N, k)
k
(N, ) N and uk
k
\N and N = N {n}. For each i N, let (i, n) =
ui = ui and for each (i, j) P(N), (i, j) = (i, j). Let = (N, ). Let
(n) = n and for each i N, (i) = (i). Upon the arrival of the new agent
n, no blocking pair is created when extending matching to matching . Hence, (, u) S( ) and OM( ). From the definitions of and u, observe that
every agent i N can maintain his utility level ui by matching with the new agent n.
Let (
,) S( ). Recall that if an agent is single at a stable outcome, then at each sta
ble outcome, he receives his reservation value. Thus, since (n) = n, un = n = 0.
Since (
,) S( ), then for each i N,i =i + n (i, n) = ui. The
inequality cannot be strict as this would contradict OM( ). Thus, = u,
i.e., (
, u) S( ).
By assumption, ( ) S( ). Thus, S( ) ( ) = , i.e., there exists
(
, u) S( ) such that (
, u) ( ). Since (, u) F( ), by Pareto indif
ference (, u) ( ). Note that N N such that (N) = N, |N = , and
(|N , u|N ) = (, u). By consistency, (|N , u|N ) ( |N ). Thus, (, u) ( ).
The next theorem is a counterpart of Sasaki (1995, Theorem 1) for solvable problems.
Theorem 2 On the class of solvable problems, if is a subsolution of the core satisfying invariance with respect to unmatching dummy pairs, continuity, and consistency, then coincides with the core.
We prove Theorem 2 in AppendixA.
We show with Examples 3, 4, 5, and 6 at the end of this section that the properties in each of our theorems are independent.
Remark 3 (Invariance with respect to unmatching dummy pairs and Sasakis (1995) Theorem 1) Note that Sasaki (1995, Theorem 1) states a similar result to our Theorem 2 for two-sided problems without imposing invariance with respect to unmatching dummy pairs: If is a subsolution of the core satisfying consistency and continuity, then = S. With Example 5, we show that adding invariance
with respect to unmatching dummy pairs is indeed required (also for two-sided problems).
123
Consistency in one-sided assignment problems 425
For two-sided and solvable one-sided problems where reservation values are not xed, but are allowed to vary (see, for instance, Toda 2005), our Theorem 2 holds without requiring invariance with respect to unmatching dummy pairs.
Theorem 3 On the class of solvable one-sided problems with non-negative reservation values that are allowed to vary, if is a subsolution of the core satisfying continuity and consistency, then coincides with the core.
We prove Theorem 3 in Appendix B.
Observe that Theorems 2 and 3 imply that xing reservation values is not without loss of generality (for both one-sided and two-sided problems).
The following examples demonstrate the independence of properties in Theorems 1 and 2 (Examples 3 and 6 can easily be adjusted for independence in Theorem 3).
Example 3 (A solution that violates consistency, but satises all of the remaining properties in each theorem) Observe that for any N , |N| = 2, with N = {i, j}
and (i, j) > 0, S( ) = {(, u) | (i) = j and u = (, (i, j) ) for [0, (i, j)]}. For these problems, dene to be a subsolution of the core at which the
agent with the lowest index receives the maximum payoff. Formally, for each N N
and each N ,
( ) =
(, u) S( ) | (i) = j, ui = (i, j), and u j = 0
if N = {i, j}, (i, j) > 0, and i < j; S( ) otherwise.
Example 4 (A consistent subsolution of the core that is not Pareto Indifferent) Fix two distinct agents k, l
N. Then, if N is such that k, l N, check if there
exist different stable outcomes at which agents k and l are matched and not matched, respectively. If that is the case, then assign the strict subset of stable outcomes at which agents k and l are not matched. For all other problems, assign the set of all stable outcomes. Formally, for each N N and each N ,
( ) =
dened in Example 4 in two
Example 5 (A consistent and continuous subsolution of the core that is not invariant with respect to unmatching dummy pairs) We vary
as dened in Example 4 by changing (i) as follows. For each N N and each N ,
( ) =
S( )\ {( , u) S( ) | (k) = l}
ifk, l N and {(, u) S( ) | (k) = l} = ; (i) S( ) otherwise. (ii)
Next, to establish the independence of invariance with respect to unmatching dummy pairs and continuity, we vary the solution
different ways.
S( )\ {( , u) S( ) | (k) = k and (l) = l}
if k, l N and {(
, u) S( ) | (k) = k and
S( ) otherwise.
(l) = l} = ;
123
426 B. Klaus, A. Nichifor
In order to illustrate that violates invariance with respect to unmatching dummy pairs, let N = {k, l}, be such that (k, l) = 0, = (N, ), and let ,
be such that
(l) = l. However, in violation of invariance with respect
to unmatching dummy pairs, ( ) = {(, u)}
{(, u), ( , u)} = S( ), where
u = (0, 0). Example 6 (A consistent and invariant with respect to unmatching dummy pairs sub-solution of the core that is not continuous) We modify
as dened in Example 4 by adding (k, l) > 0 to (i). For each N N and each N ,
( ) =
, u) ( ).
, u) / ( ).
4.2 Impossibilities and limitations
Recall that for two-sided problems, the core is always non-empty, while for one-sided problems, the core may be empty (see Example 1). The positive results centered around consistency in the previous subsection were obtained when restricting attention to the class of solvable problems. But is it possible to obtain consistency and nice core properties for the entire class of one-sided problems? The following theorem and corollary show some impossibilities.
Theorem 4 No solution coincides with the core whenever the core is nonempty and satises consistency.
Proof Let be a consistent solution such that for each solvable problem
, ( ) = S( ). Let N = {1, 2, 3, 4, 5}, such that (1, 2) = (2, 3) = (3, 4) =
(4, 5) = (1, 5) = 1, for all (i, j) P(N) \ {(1, 2), (2, 3), (3, 4), (4, 5), (1, 5)},
(i, j) = 0, and = (N, ). Note that for any M(N), 2|C()| + |S()| = |N| = 5. One can easily show that S( ) = (the proof is similar to the arguments
used in Example 1).
Case 1 Let (, u) ( ) such that [|C()| = 0 and |S()| = 5] or [|C()| = 1
and |S()| = 3].
Hence, there exists {i, j} S() such that j = i + 1 (modulo 5). Thus, (i, j) =
1. Let N = {i, j} and consider the subproblem |N . Then, S(|N ) = {( , u ) |
(i) = j and u = (, 1 ) for [0, 1]} and (|N , u|N ) / S(|N ) (because
(k) = l,
(k) = k and
S( )\{( , u) S( ) | (k) = l}
if k, l N, {(, u) S( ) | (k) = l} = , and (k, l) > 0; S( ) otherwise.
In order to illustrate that violates continuity, let N = {k, l, m} and be such that
(k, l) = (l, m) = 1 and (k, m) = 0. Furthermore, for each > 0 let be
such that (k, l) = 1 + , (l, m) = 1, and (k, m) = 0. Let = (N, ) and
= (N, ) be the corresponding problems, ,
be such that (l) = m, (k) = k,
and
(k) = l,
(m) = m, u = (0, 1, 0), and u = (0, 1 + , 0), with uk, ul, um the
order of components in each payoff vector. Then, for each > 0, (
However, in violation of continuity, u
0
u and (
123
Consistency in one-sided assignment problems 427
ui = u j = 0). Since S(|N ) = , (|N ) = S(|N ). Hence, in contradiction to
being consistent, (|N , u|N ) / (|N ).
Case 2 Let (, u) ( ) such that |C()| = 2 and |S()| = 1.
Without loss of generality, assume C() = {(1, 2), (3, 4)} and S() = {5}.
Step 1 Let N = {1, 2, 5} and consider the subproblem |N . Then, S(|N ) =
{( , u ), ( , u ) | = (2, 1, 5), = (5, 2, 1), and u = (1, 0, 0)}. Since
S(|N ) = , (|N ) = S(|N ).
If u1 = 1, then in contradiction to being consistent, (|N , u|N ) / (|N ).
Hence, u1 = 1.
Step 2 Let N = {3, 4, 5} and consider the subproblem |N . Then, S(|N ) ={( , u ), (
, u ) | = (4, 3, 5),
= (3, 5, 4) and u = (0, 1, 0)}. Since
S(|N ) = , (|N ) = S(|N ).
If u4 = 1, then in contradiction to being consistent, (|N , u|N ) / (|N ).
Hence, u4 = 1.
Step 3 Let N = {1, 2, 3, 4} and consider the subproblem |N . Note that S(|N ) =
(e.g., (|N , (0, 1, 1, 0)) S(|N )). Hence, (|N ) = S(|N ).
By consistency, (|N , u|N ) (|N ). Recall that |N = (2, 1, 4, 3), (1, 2) +
(3, 4) = 2, and by Steps 1 and 2, u1 = u4 = 1. But then, u2 = u3 = 0 and
(2, 3) = 1 imply that (2, 3) is a blocking pair for (|N , u|N ); contradicting
(|N ) = S(|N ).
Theorem 4 together with Theorems 1 and 2 implies the following two impossibility results.
Corollary 1
(a) No solution is a subsolution of the core whenever the core is nonempty and satises invariance with respect to unmatching dummy pairs, continuity, and consistency.
(b) No solution is a subsolution of the core whenever the core is nonempty and satises Pareto indifference and consistency.
Sasaki (1995) provides the following two characterizations of the core for two-sided problems (similarly as for Sasakis 1995, Theorem 1, we have corrected his Theorem 2 by adding invariance with respect to unmatching dummy pairs.5)
Sasakis (1995) Theorem 2. On the class of two-sided problems, the core is the unique solution satisfying individual rationality, couple rationality, Pareto optimality, invariance with respect to unmatching dummy pairs, continuity, consistency, and weak pairwise-monotonicity.
Sasakis (1995) Theorem 4. On the class of two-sided problems, the core is the unique solution satisfying individual rationality, couple rationality, Pareto optimality,
5 Note that solution S as dened in Example5 satises all properties stated in Sasaki (1995) Theo
rem 2.
123
428 B. Klaus, A. Nichifor
Pareto indifference, consistency, and weak pairwise-monotonicity.
For two-sided problems, Sasaki (1995) proves his characterizations of the core as follows.
Step 1. The core satises all properties used in both characterizations (his Propositions 3 and 4).
Step 2. A solution that satises all properties as stated in each of the characterizations is a subsolution of the core (his Theorems 2 and 4).
Step 3. Finally, using Sasaki (1995, Theorems 1 and 3), the characterizations follow.
Note that with Proposition 1 and Theorems 1 and 2, we have established Sasakis Steps 1 and 3 for solvable one-sided problems. Observe, however, that in these steps, weak pairwise-monotonicity has not been used. A close look at Sasakis proofs for Step 2 reveals that this is where weak pairwise-monotonicity is heavily used. Even though the core is a weakly pairwise-monotonic solution on the class of solvable problems, the strength of weak pairwise-monotonicity as a property on the class of solvable one-sided problems is different from its strength on the class of two-sided problems. The main difference is that in Sasakis two-sided assignment model, any pairwise-monotonic transformation of a characteristic function (see the definition of weak pairwise-monotonicity) leads to another two-sided problem and, therefore, to solvability. However, for solvable one-sided problems, a small pairwise-monotonic transformation can transform a solvable one-sided problem into a one-sided problem with an empty core. Thus, for problems on the boundary of the class of solvable one-sided problems, weak pairwise-monotonicity cannot be used in the same way as Sasaki (1995) does because it would lead outside the class of solvable one-sided problems. Whether a counterpart of Sasakis (1995) characterization of the core holds on the class of solvable one-sided problems is an open question.
We conclude with an example that shows that for the class of solvable problems, changing the value of a couple (i, j) might change the set of core outcomes quite drastically. In particular, the solvable problem is one on the boundary of the class of solvable problems for which a direct adaptation of Sasakis proof Step 2 does not work (for instance, the pairwise-monotonic transformation from to transforms a solvable problem to one with an empty core).
Example 7 (Changes of the core when the value of a couple changes) Let N = {1, 2, 3}
and (0, 1). Consider the following characteristic functions: such that (1, 2) =
2, (1, 3) = 1, (2, 3) = 1, such that (1, 2) = 2, (1, 3) = 1, (2, 3) = 1,
and such that (1, 2) = 2, (1, 3) = 1, (2, 3) = 1 + . Then, for the
corresponding problems = (N, ), = (N, ), and = (N, ), we have S( ) = {(, u) | = (2, 1, 3) and u = (1 + , 1 , 0) for [0, ]}, S( ) =
{(, u) | = (2, 1, 3) and u = (1, 1, 0)}, and S( ) = .
For the solvable problem in Example 7, there is a unique optimal matching and an innite number of payoff vectors associated with it; therefore, |S( )| = . Fur
thermore, the innite cardinality is maintained for small changes of the characteristic function. Without introducing the formal definitions here, we state that the problem is in the interior of the set of solvable problems. In general, one can show that a
123
Consistency in one-sided assignment problems 429
problem is in the interior of the set of solvable problems whenever the core contains an innite set of payoff vectors.
For the solvable problem in Example7 there is a unique optimal matching and a unique payoff vector; therefore |S( )| = 1. Furthermore, small changes of the
characteristic function (e.g., as represented by or for small ), change the core: either from a nite set to an innite set (if is changed to ) or from a nite set to an empty set (if is changed to ). More generally, one can show that a problem is on the boundary of the set of solvable one-sided problems whenever the core consists of a unique payoff vector (and thus, a nite outcome set).
Any problem that is not solvable, e.g., in Example 7, is outside of the set of solvable problems.
We conjecture, that if Sasakis (1995, Theorems 2 and 4) characterizations hold on the class of solvable one-sided problems, the proof techniques for the interior and the boundary of the class differ.
Acknowledgements We thank a
gatay Kay, William Thomson, an anonymous referee, and an associate editor for helpful comments. We thank the Netherlands Organisation for Scientic Research (NWO) for its support under grant VIDI-452-06-013.
Open Access This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
A Appendix: Proof of Theorem 2
Let N be a solvable problem. Then, ( ) S( ). We prove that ( ) S( ),
i.e., we show that (, u) S( ) implies (, u) ( ).
Step 1: Intuitively, we start from and a stable outcome (with a maximal number of dummy agents) and then add a new agent n. We extend the characteristic function such that each incumbent obtains together with n a value equal to the payoff of the incumbent prior to ns arrival. We require the payoff of an incumbent paired with n to be kept invariant. We extend each optimal matching with n being either single or part of a dummy pair together with a formerly single incumbent.
Formally, let (, u) S( ). We will not work with matching directly but with
a matching D A (possibly D A = ) that has a maximal number of dummy agents;
therefore, the only possible difference between D A and is that some dummy agents
for D A are single at , i.e., C(D A) C() and S() \ S(D A) D A(, D A)
and there exists no matching
such that C(
) C(), S() \ S(
) D A(,
),
)| > |D A(, D A)|. Note that (D A, u) S( ) and that at D A, at
most one agent is single: if more than one agent is single, then D A is not optimal for
(two single agents have a positive value) or it does not match the maximal number of dummy agents (two single agents have value 0). In the remainder of the proof, we distinguish the two Cases (a) S(D A) = {d} and (b) S(D A) = .
Let n
N
and |D A(,
\N and N = N {n}. For each i N, let (i, n) = ui = ui and
for each (i, j) P(N), (i, j) = (i, j). Let = (N, ). For Case (a), let
123
430 B. Klaus, A. Nichifor
be such that for each i N\{d}, (i) = D A(i), (d) = d, and (n) = n, and such that for each i N\{d},
(i) = D A(i) and
(d) = n. For Case (b),
let be such that for each i N, (i) = D A(i) and (n) = n. Hence, (a)
S() = {d, n} and S(
) = and (b) S() = {n}. Upon the arrival of the new
agent n, no blocking pair is created when extending matching to matching . Hence, (a) (, u), (
, u) S( ) and (b) (, u) S( ).
Step 2: Next, starting from , we construct as follows: we increase by the value of each couple at that does not include agent n, and we distribute the benets equally between the two members of a couple.
Formally, for Case (a), for each (i, j) C(D A),6 [(i, j) = (i, j) + , ui =
ui + 2, and uj = uj + 2], (d, n) = (d, n), and ud = un = 0. For each
(i, j) P(N)\C(D A), (i, j) = (i, j). For Case (b), for each (i, j) C() =
C(D A), [(i, j) = (i, j) + , ui = ui + 2, and uj = uj + 2] and un = 0. For
each (i, j) P(N) \ C(), (i, j) = (i, j).
Let = (N, ). Because the change in couples values does not create any
blocking pair, it follows that (a) (, u), (
, u) S( ) and (b) (, u) S( ). Hence, (a) {,
} OM( ) and (b) {} OM( ). Note that (a)
D A( , ) = and D A( ,
) = {d, n} and (b) D A( , ) = . Claim 1 (a) OM( ) = {,
} and (b) OM( ) = {}.
Let M(N) with (a) = ,
or (b) = . Since for (a) and (b)
(, u) S( ), OM( ). By construction,
(i, j) (i, j) = (i, j) (i, j) + |C(D A)| and (4) (i, j) (i, j) = (i, j) (i, j) + |C(D A) C( )| . (5)
Observe that
|C(D A) C( )| |C(D A)|. (6)
By construction of D A, (a) |C(D A)| =
Hence, if |C(D A) C( )| = |C(D A)|,7 then C( ) = C(D A) = C() and
S( ) = S(). Consequently, = , a contradiction. Thus, (6) is strict, which
taken together with (4) and (5) yields (i, j) (i, j) > (i, j) (i, j). Hence,
(a) OM( ) = {,
} and (b) OM( ) = {}.
are the only optimal matchings for and (b) is the only optimal matching for . However, there might be innitely many payoff vectors associated with these optimal matching(s) (Sotomayor 2003, Theorem 1).
Claim 2 Let (,) S( ). Then, for each i N, | i ui| 2.
6 Note that for Case (a), C(D A) = C() = C(
)\{(d, n)}.
7 Recall that in Case (a), we also assume = .
By Claim 1, (a) and
|N|2
2 or (b) |C(D A)| =
|N|1
2 .
123
Consistency in one-sided assignment problems 431
For Case (a), S() = {d, n},d = ud = 0, andn = un = 0. Hence, | d ud| = | n un| = 0. For Case (b), S() = {n} andn = un = 0. Hence, | n un| = 0.
Now consider couples payoffs. Recall that compared to , in , the value of each couple is increased by . Intuitively, we show that any payoff renegotiation within each pair is bounded by , as any attempt of a matched agent to negotiate a payoff in excess of would induce his partner to leave the couple in favor of a partnership with agent n. Formally, let (i, j) C().
Case 1i ui < 2
Theni < ui 2 = ui = ui. By construction, for each i N, (i, n) = ui. Thus,
(i, n) forms a blocking pair, and (,) / S( ).
Case 2i ui > 2
Since OM( ), for any (i, j) C(),i + j = ui + uj. Theni ui =
uj j >
2 . Thus, j uj < 2 and similarly as in Case 1, it follows that
(,) / S( ).
In Case (a), we have in addition (,) S( ) if and only if (
,) S( ).
Step 3: By assumption, ( ) S( ). Thus, S( ) ( ) = . For Case (a),
assume that (
,) S( )( ). Then, by invariance with respect to unmatching
dummy pairs, (,) S( )( ). Hence, for both cases (a) and (b), there exists
(,) S( ) ( ). By Claim 2, for each i N, | i ui| 2. Letting 0,
for each i N, | i ui| 0 and ui ui. By continuity, (, u) ( ). Note
that for each N N such that (N) = N, |N = , and (|N , u|N ) = (D A, u).
By consistency, (|N , u|N ) ( |N ). Thus, (D A, u) ( ). Since (, u) F( ),
by invariance with respect to unmatching dummy pairs, (, u) ( ).
B Appendix: Proof of Theorem 3
We slightly modify the model of Sect. 2 by extending the definition of a characteristic function to allow for variable reservation values, i.e., for any N N
a function : P(N)
R+ is a characteristic function for N. In particular,
we now do not require that for each agent i N, the reservation value (i, i) is
xed at 0.
Let N be a solvable problem. Then, ( ) S( ). We prove that
( ) S( ), i.e., we show that (, u) S( ) implies (, u) ( ).
Step 1: Let (, u) S( ). Let n
\ N and N = N {n}. For each i N,
let (i, n) = ui = ui and for each (i, j) P(N), (i, j) = (i, j). Let
= (N, ). Let be such that for each i N, (i) = (i) and (n) = n.
Upon the arrival of the new agent n, no blocking pair is created when extending matching to matching . Hence, (, u) S( ).
N
123
432 B. Klaus, A. Nichifor
Step 2: For each (i, j) C(), (i, j) = (i, j) + , ui = ui + 2, and
uj = uj + 2, and for each i S(), (i, j) = ui =
2 .8 For each (i, j)
P(N) \ C(), (i, j) = (i, j). Let = (N, ). Because the change in
agents values does not create any new blocking pairs, it follows that (, u) S( ).
Claim 1 is the unique optimal matching for , i.e., OM( ) = {}.
Let M(N) with = . Since (, u) S( ), OM( ). By
construction,
(i, j)
(i, j) =
(i, j) =
|C() C( )| |C()| and |S() S( )| |S()|. (9)
If |S() S( )| = |S()| and |C() C( )| = |C()|, then S( ) = S()
and C( ) = C(). Consequently, = , a contradiction. Thus, at least one
of the inequalities in (9) is strict, which taken together with (7) and (8) yields (i, j) (i, j) > (i, j) (i, j). Hence, OM( ) = {}.
By Claim 1, is the unique optimal matching for .
Claim 2 Let (,) S( ). Then, for each i N, | i ui| 2.
For each i S(),i = ui = 0. Hence, | i ui| = 0. Let (i, j) C(). Case 1i ui < 2
Then,i < ui 2 = ui = ui. By construction, for each i N, (i, n) = ui. Thus,
(i, n) forms a blocking pair, and (,) / S( ).
Case 2i ui > 2
Since OM( ), for any (i, j) C(),i + j = ui + uj. Then, ui ui = uj j >
2 . Thus, j uj < 2 and similarly as in Case 1, it
follows that (,) / S( ).
Step 3: By assumption, ( ) S( ). Thus, S( ) ( ) = , i.e., there exists
(,) S( ) ( ). By Claim2, for each i N, | i ui| 2. Letting 0,
for each i N, | i ui| 0 and ui ui. By continuity, (, u) ( ).
Note that N N such that (N) = N, |N = , and (|N , u|N ) = (, u). By
consistency, (|N , u|N ) ( |N ). Hence, (, u) ( ).
8 Note that we increase the reservation values of single agents at this is only possible if we change the assignment model to allow reservation values to vary.
(i, j) + |C()| + |S()|
2 and (7)
(i, j) + |C() C( )| + |S() S( )|
2. (8)
Observe that
123
Consistency in one-sided assignment problems 433
References
Eriksson K, Karlander J (2001) Stable outcomes of the roommate game with transferable utility. Int J GameTheory 29:555569
Gale D, Shapley LS (1962) College admissions and the stability of marriage. Am Math Mon 69:915 Roth AE, Sotomayor MAO (1990) Two-sided matching: a study in game-theoretic modeling and analysis.
Cambridge University Press, Cambridge
Sasaki H (1995) Consistency and monotonicity in assignment problems. Int J Game Theory 24:373397 Shapley L, Shubik M (1972) The assignment game I: the core. Int J Game Theory 1:111130 Sotomayor M (2003) Some further remark on the core structure of the assignment game. Math Soc Sci
46(3):261265
Sotomayor M (2005) On the core of the one-sided assignment game. MimeoTalman DJJ, Yang Z (2008) A model of partnership formation. Center Discussion Paper Series No. 2008-103 Thomson W (2009) Consistent allocation rules. Monograph (forthcoming)
Toda M (2005) Axiomatization of the core of assignment games. Games Econ Behav 53:248261
123
Springer-Verlag 2010