
Publications
42. Jaramillo P., Ç. Kayı, and F. Klijn (2014): 'Asymmetrically Fair Rules for an Indivisible Good Problem with a Budget Constraint,' forthcoming in Social Choice and Welfare
Abstract: We study a
particular restitution problem where there is an indivisible good (land
or property) over which two agents have rights: the dispossessed agent
and the owner. A third party, possibly the government, seeks to resolve
the situation by assigning rights to one and compensate the other. There
is also a maximum amount of money available for the compensation. We
characterize a family of asymmetrically fair rules that are immune to
strategic behavior, guarantee minimal welfare levels for the agents, and
satisfy the budget constraint.
Full paper: publisher, previous working paper
41. Jaramillo P., Ç. Kayı, and F. Klijn (2014): 'On the Exhaustiveness of Truncation and Dropping Strategies in ManytoMany Matching Markets,' forthcoming in Social Choice and Welfare
Abstract: We consider
twosided manytomany matching markets in which each worker may work
for multiple firms and each firm may hire multiple workers. We study
individual and group manipulations in centralized markets that employ
(pairwise) stable mechanisms and that require participants to submit
rank order lists of agents on the other side of the market. We are
interested in simple preference manipulations that have been reported
and studied in empirical and theoretical work: truncation strategies,
which are the lists obtained by removing a tail of least preferred
partners from a preference list, and the more general dropping
strategies, which are the lists obtained by only removing partners from a
preference list (i.e., no reshuffling). We study when
truncation/dropping strategies are exhaustive for a group of agents on
the same side of the market, i.e., when each match resulting from
preference manipulations can be replicated or improved upon by some
truncation/dropping strategies. We prove that for each stable mechanism,
dropping strategies are exhaustive for each group of agents on the same
side of the market (Theorem 1), i.e., independently of the quotas.
Then, we show that for each stable mechanism, truncation strategies are
exhaustive for each agent with quota 1 (Theorem 2). Finally, we show
that this result cannot be extended neither to individual manipulations
when the agent's quota is larger than 1 (even when all other agents'
quotas equal 1  Example 1), nor to group manipulations (even when all
quotas equal 1  Example 2).
Full paper: publisher, previous working paper
40. Jaramillo P., Ç. Kayı, and F. Klijn (2013): 'Equilibria under Deferred Acceptance: Dropping Strategies, Filled Positions, and Welfare,' Games and Economic Behavior, 82(1), 693701
Abstract: We
study manytoone matching markets where hospitals have responsive
preferences over students. We study the game induced by the
studentoptimal stable matching mechanism. We assume that students play
their weakly dominant strategy of truthtelling. Roth and Sotomayor
(1990) showed that equilibrium outcomes can be unstable. We prove that
any stable matching is obtained in some equilibrium. We also show that
the exhaustive class of dropping strategies does not necessarily
generate the full set of equilibrium outcomes. Finally, we find that the
'rural hospital theorem' cannot be extended to the set of equilibrium
outcomes and that welfare levels are in general unrelated to the set of
stable matchings. Two important consequences are that, contrary to
onetoone matching markets, (a) filled positions depend on the
equilibrium that is reached and (b) welfare levels are not bounded by
the optimal stable matchings (with respect to the true preferences).
Full paper: publisher, previous working paper
39. Klijn F., J. Pais, and M. Vorsatz (2013): 'Preference Intensities and
Risk Aversion in School Choice: A Laboratory Experiment,' Experimental Economics, 16(1), 122
Abstract:
We experimentally investigate in the laboratory prominent mechanisms
that are employed in school choice programs to assign students to public
schools and study how individual behavior is influenced by preference
intensities and risk aversion. Our main results show that (a) the
GaleShapley mechanism is more robust to changes in cardinal preferences
than the Boston mechanism independently of whether individuals can
submit a complete or only a restricted ranking of the schools and (b)
subjects with a higher degree of risk aversion are more likely to play
"safer'' strategies under the GaleShapley but not under the Boston
mechanism. Both results have important implications for enrollment
planning and the possible protection risk averse agents seek. Full paper: publisher, previous working paper
38. Klaus B. and F. Klijn (2013): 'Local and Global
Consistency Properties for Student Placement,' Journal of Mathematical Economics, 49(3), 222229
Abstract:
In the
context of resource allocation on the basis of priorities, Ergin (2002)
identifies
a necessary and sufficient condition on the priority structure such that
the
studentoptimal stable mechanism satisfies a consistency principle.
Ergin
(2002) formulates consistency as a local property based on a fixed
population
of agents and fixed resources  we refer to this condition as local
consistency and to his condition on the priority structure as local
acyclicity.
We identify a related but stronger necessary and sufficient condition
(unit
acyclicity) on the priority structure such that the studentoptimal
stable
mechanism satisfies a more standard global consistency property. Next,
we provide necessary and sufficient conditions for the studentoptimal
stable mechanism to satisfy converse consistency principles. We identify
a
necessary and sufficient condition (local shiftfreeness) on the
priority
structure such that the studentoptimal stable mechanism satisfies local
converse consistency. Interestingly, local acyclicity implies local
shiftfreeness and hence the studentoptimal stable mechanisms more
frequently
satisfies local converse consistency than local consistency. Finally, in
order
for the studentoptimal stable mechanisms to be globally conversely
consistent,
one again has to impose unit acyclicity on the priority structure.
Hence, unit
acyclicity is a necessary and sufficient condition on the priority
structure
for the studentoptimal stable mechanism to satisfy global consistency
or
global converse consistency.
Full paper: publisher, previous working paper
37. Biró P. and F. Klijn (2013): 'Matching with Couples: A Multidisciplinary Survey,' International Game Theory Review, 15, 118
Abstract: This survey deals with twosided matching markets where one set of agents (workers/residents) has to be matched with another set of agents (firms/hospitals). We first give a short overview of a selection of classical results. Then, we review recent contributions to a complex and representative case of matching with complementarities, namely matching markets with couples. We discuss contributions from computer scientists, economists, and game theorists. Full paper: publisher, previous working paper
36. Ashlagi
I. and F. Klijn (2012): 'Manipulability
in Matching Markets: Conflict and Coincidence of Interests,' Social Choice and Welfare, 39(1), 2333
Abstract: We study
comparative statics of manipulations by women in the menproposing deferred
acceptance mechanism in the twosided onetoone marriage market. We prove that
if a group of women weakly successfully manipulates or employs truncation
strategies, then all other women weakly benefit and all men are weakly harmed.
We show that our results do not appropriately generalize to the manytoone
college admissions model.
Full paper: publisher, previous working paper
35. Klaus B., F. Klijn, and M. Walzl (2011): 'Farsighted
Stability for Roommate Markets,' Journal of Public
Economic Theory, 13(6), 921933
Abstract: We study
farsighted stability for roommate markets. We show that a matching for a
roommate market indirectly dominates another matching if and only if no
blocking pair of the former is matched in the latter (Proposition 1). Using
this characterization of indirect dominance, we investigate von
NeumannMorgenstern farsightedly stable sets. We show that a singleton is von
NeumannMorgenstern farsightedly stable if and only if the matching is stable
(Theorem 1). We also present a roommate market without a von
NeumannMorgenstern farsightedly stable set (Example 1) and a roommate market
with a nonsingleton von NeumannMorgenstern farsightedly stable set (Example
2).
Full paper:
publisher, previous working paper
34. Klijn F. (2011): 'On the Consistency of Deferred Acceptance when Priorities are Acceptant Substitutable,' Mathematical Social Sciences, 62(2), 101103
Abstract: In the context of resource allocation on the basis of responsive priorities, Ergin (2002) identifies a necessary and sufficient condition for the deferred acceptance rule to satisfy a consistency principle. In this note we extend this result to the domain of substitutable priorities, complementing results of Kojima and Manea (2010) and Kumano (2009). Full paper:
publisher, previous working paper, clarification
33. Calsamiglia C., G. Haeringer, and F. Klijn (2011): 'A
Comment On: School Choice: An Experimental Study,' Journal of Economic
Theory, 146(1), 392396
Abstract: We show
that one of the main results in Chen and Sönmez (2006, 2008) does no longer
hold when the number of recombinations is sufficiently increased to obtain
reliable conclusions. No school choice mechanism is significantly superior in
terms of efficiency.
Full paper: publisher,
previous working paper
32. Klaus B., F. Klijn, and M. Walzl (2010): 'Farsighted
House Allocation,' Journal of Mathematical Economics, 46(5),
817824
Abstract: In this note we
study von NeumannMorgenstern farsightedly stable sets for Shapley and Scarf
(1974) housing markets. Kawasaki
(2008) shows that the set of competitive allocations coincides with the unique
von NeumannMorgenstern stable set based on a farsighted version of
antisymmetric weak dominance (cf., Wako, 1999). We demonstrate that the set of
competitive allocations also coincides with the unique von NeumannMorgenstern
stable set based on a farsighted version of strong dominance (cf., Roth and
Postlewaite, 1977) if no individual is indifferent between his endowment and
the endowment of someone else.
Full paper: publisher,
previous working paper
31. Klaus B., F. Klijn, and M. Walzl (2010): 'Stochastic
Stability for Roommate Markets,' Journal of Economic Theory,
145(6), 22182240
Abstract: We
show that for any roommate market the set of stochastically stable matchings
coincides with the set of absorbing matchings. This implies that whenever the
core is nonempty (e.g., for marriage markets), a matching is in the core if
and only if it is stochastically stable, i.e., stochastic stability is a
characteristic of the core. Several solution concepts have been proposed to
extend the core to all roommate markets (including those with an empty core).
An important implication of our results is that the set of absorbing matchings
is the only solution concept that is core consistent and shares the stochastic
stability characteristic with the core.
Full paper: publisher,
previous working paper
30. Calsamiglia C., G. Haeringer, and F. Klijn (2010):
'Constrained School Choice: An Experimental Study,' American Economic
Review, 100(4), 18601874
Abstract: The literature
on school choice assumes that families can submit a preference list over all
the schools they want to be assigned to. However, in many reallife instances
families are only allowed to submit a list containing a limited number of
schools. Subjects' incentives are drastically affected, as more individuals
manipulate their preferences. Including a safety school in the constrained list
explains most manipulations. Competitiveness across schools play an important
role. Constraining choices increases segregation and affects the stability and
efficiency of the final allocation. Remarkably, the constraint reduces
significantly the proportion of subjects playing a dominated strategy.
Full paper: publisher, previous working paper
29. Klaus B. and F. Klijn (2010): 'Smith and Rawls
Share a Room: Stability and Medians,' Social Choice and Welfare,
35(4), 647667
Abstract: We consider
onetoone matching (roommate) problems in which agents (students) can either
be matched as pairs or remain single. The aim of this paper is twofold. First,
we review a key result for roommate problems (the "lonely wolf"
theorem) for which we provide a concise and elementary proof. Second, and
related to the title of this paper, we show how the often incompatible concepts
of stability (represented by the political economist Adam Smith) and fairness
(represented by the political philosopher John Rawls) can be reconciled for
roommate problems.
Full paper: publisher,
previous working paper
28. Haeringer G. and F. Klijn (2009):
'Constrained School Choice,' Journal of Economic Theory, 144(5),
19211947
Abstract: Recently,
several school districts in the US
have adopted or consider adopting the StudentOptimal Stable mechanism or the
Top Trading Cycles mechanism to assign children to public schools. There is
evidence that for school districts that employ (variants of) the socalled Boston mechanism the
transition would lead to efficiency gains. The first two mechanisms are
strategyproof, but in practice student assignment procedures typically impede
a student to submit a preference list that contains all his acceptable schools.
We study the preference revelation game where students can only declare up to a
fixed number of schools to be acceptable. We focus on the stability and
efficiency of the Nash equilibrium outcomes. Our main results identify rather
stringent necessary and sufficient conditions on the priorities to guarantee
stability or efficiency of either of the two mechanisms. This stands in sharp
contrast with the Boston mechanism which has
been abandoned in many US
school districts but nevertheless yields stable Nash equilibrium outcomes.
Full paper: publisher,
previous
working paper, longer
previous working paper (with additional proofs)
27. Hamers H., F. Klijn, M. Slikker, and B. van Velzen
(2009): 'A Cooperative Approach to Queue Allocation of Indivisible Objects,' International
Game Theory Review, 11(2), 215227
Abstract: We consider the
allocation of a finite number of indivisible objects to the same number of
agents according to an exogenously given queue. We assume that the agents
collaborate in order to achieve an efficient outcome for society. We allow for
sidepayments and provide a method for obtaining stable outcomes.
Full paper: publisher, previous working paper
26. Klaus B. and F. Klijn (2009): 'Employment by
Lotto Revisited,' International Game Theory Review, 11(2),
181198
Abstract: We study
employment by lotto (Aldershof et al., 1999), a procedurally fair matching algorithm
for the socalled stable marriage problem. We complement Aldershof et al.'s
(1999) analysis in two ways. First, we give an alternative and intuitive
description of employment by lotto in terms of a probabilistic serial
dictatorship on the set of stable matchings. Second, we show that Aldershof et
al.'s (1999) conjectures are correct for small matching markets but not
necessarily correct for large matching markets.
Full paper: publisher, previous working paper
25. Klaus B., F. Klijn, and T. Nakamura (2009):
'Corrigendum: Stable Matchings and Preferences of Couples,' Journal of
Economic Theory, 144(5), 22272233
Abstract: We
correct an omission in the definition of the domain of weakly responsive
preferences introduced in Klaus and Klijn (2005) or KK05 for short. The proof
of the existence of stable matchings (KK05, Theorem 3.3) and a maximal domain
result (KK05, Theorem 3.5) are adjusted accordingly.
Full paper: publisher, previous working paper
24. Klijn F. (2008): 'Mechanism
Design in School Choice: Some Lessons in a Nutshell,' Boletín de la
Sociedad de Estadística e Investigación Operativa, 24(3), 1122
Abstract: This
paper deals with school choice as an application of matching theory. Although
the use of matching theory for the design and study of school choice mechanisms
is rather recent, some of its tools were already successfully employed in
several other markets, the most noticeable being the labor market for medical
doctors in the US. I first briefly describe the problems that some US school
districts had, and why and how economic engineering has contributed a lot to
the improvement of school choice programs. Then, I will review and interpret a
selection of the most recent developments and results.
Full paper: publisher, previous working paper
23. Klaus B., F. Klijn, and J. Massó (2007): 'Some
Things Couples Always Wanted to Know about Stable Matchings (but were afraid to
ask),' Review of Economic Design, 11, 175184
Abstract: In this
note we study the new National Resident Matching Program (NRMP) algorithm in
the US
market for physicians. We report on two potential problems that concern the
presence of couples, a feature explicitly incorporated in the new NRMP
algorithm (cf. Roth and Peranson, 1999). First, we show that the new
NRMP algorithm may not find an existing stable matching, even when couples'
preferences are 'responsive,' i.e., when Gale and Shapley's (1962)
deferred acceptance algorithm (on which the old NRMP algorithm is based) is
applicable. Second, we demonstrate that the new NRMP algorithm may also be
manipulated by couples acting as singles.
For a step by step description of the execution of the APCA algorithm for
examples 3.1 and 3.2 click here.
Full paper: publisher, previous working paper
22. Klaus B. and F. Klijn (2007): 'Fair and Efficient
Student Placement with Couples,' International Journal of Game Theory,
36, 177207
Abstract: We
study situations of allocating positions to students based on priorities. An
example is the assignment of medical students to hospital residencies on the
basis of entrance exams. For markets without couples, e.g., for undergraduate
student placement, acyclicity is a necessary and sufficient condition for the
existence of a fair and efficient placement mechanism (Ergin, 2002). We show
that in the presence of couples acyclicity is still necessary, but not
sufficient. A second necessary condition is prioritytogetherness of couples. A
priority structure that satisfies both necessary conditions is called ptacyclic.
For student placement problems where all quotas are equal to one we
characterize ptacyclicity and show that it is a sufficient condition for the
existence of a fair and efficient placement mechanism. If in addition to
ptacyclicity we require reallocation and vacancyfairness for couples, the
socalled dictatorbidictator placement mechanism is the unique fair and
efficient placement mechanism. Finally, for general student placement problems,
we show that ptacyclicity may not be sufficient for the existence of a fair
and efficient placement mechanism. We identify a sufficient condition such that
the socalled sequential placement mechanism produces a fair and efficient
allocation.
Full paper: publisher, previous working paper
21. Klaus B. and F. Klijn (2007): 'Corrigendum to ''On
Randomized Matching Mechanisms'' [Economic Theory 8(1996)377381],' Economic
Theory, 32, 411416
Abstract: Ma
(1996) studied the random order mechanism, a matching mechanism suggested by
Roth and Vande Vate (1990) for marriage markets. By means of an example he
showed that the random order mechanism does not always reach all stable
matchings. Although Ma's (1996) result is true, we show that the probability
distribution he presented  and therefore the proof of his Claim 2  is not
correct. The mistake in the calculations by Ma (1996) is due to the fact that
even though the example looks very symmetric, some of the calculations are not
as ''symmetric."
Full paper: publisher, previous working paper
20. Klaus B. and F. Klijn (2007): 'Paths to Stability for
Matching Markets with Couples,' Games and Economic Behavior, 58,
154171
Abstract: We
study twosided matching markets with couples and show that for a natural
preference domain for couples, the domain of weakly responsive preferences,
stable outcomes can always be reached by means of decentralized decision
making. Starting from an arbitrary matching, we construct a path of matchings obtained
from `satisfying' blocking coalitions that yields a stable matching. Hence, we
establish a generalization of Roth and Vande Vate's (1990) result on path
convergence to stability for decentralized singles markets. Furthermore, we
show that when stable matchings exist, but preferences are not weakly
responsive, for some initial matchings there may not exist any path obtained
from `satisfying' blocking coalitions that yields a stable matching.
Full paper: publisher, previous working paper
19. Klaus B. and F. Klijn (2006): 'Median Stable Matching
for College Admissions,' International Journal of Game Theory,
34, 111
Abstract: We
give a simple and concise proof that socalled generalized median stable
matchings are welldefined for college admissions problems. Furthermore, we
discuss the fairness properties of median stable matchings and conclude with
two illustrative examples of college admissions markets, the lattices of stable
matchings, and the corresponding generalized median stable matchings.
Full paper: publisher, previous working paper
18. Klijn F. and E. Sánchez
(2006): 'Sequencing Games without Initial Order,' Mathematical Methods of
Operations Research, 63, 5362
Abstract: In this
note we study uncertainty sequencing situations, i.e., 1machine
sequencing situations in which no initial order is specified. We associate
cooperative games with these sequencing situations, study their core, and
provide links with the classic sequencing games introduced by Curiel et al.
(1989). Moreover, we propose and characterize two simple cost allocation rules
for uncertainty sequencing situations with equal processing times.
Full paper: publisher, previous working paper
17. Klaus B. and F. Klijn (2006): 'Procedurally Fair and
Stable Matching,' Economic Theory, 27, 431447
Abstract: We motivate
procedural fairness for matching mechanisms and study two procedurally fair and
stable mechanisms: employment by lotto (Aldershof et al., 1999) and the random
order mechanism (Roth and Vande Vate, 1990, Ma, 1996). For both mechanisms we
give various examples of probability distributions on the set of stable
matchings and discuss properties that differentiate employment by lotto and the
random order mechanism. Finally, we consider an adjustment of the random order
mechanism, the equitable random order mechanism, that combines aspects of
procedural and ''endstate'' fairness.
Full paper: publisher, previous working paper
16. Hamers H., F. Klijn, and B. van Velzen (2005): 'On
the Convexity of Precedence Sequencing Games,' Annals of Operations
Research, 137, 161175
Abstract: In this
paper we study a class of cooperative sequencing games that arise from
onemachine sequencing situations in which chain precedence relations are
imposed on the jobs. It is shown that these sequencing games are convex.
Full paper: publisher, previous
working paper
15. Klaus B. and F. Klijn (2005): 'Stable Matchings and
Preferences of Couples,' Journal of Economic Theory, 121, 75106
Abstract: Couples
looking for jobs in the same labor market may cause instabilities. We determine
a natural preference domain, the domain of weakly responsive preferences, that
guarantees stability. Under a restricted unemployment aversion condition we
show that this domain is maximal for the existence of stable matchings. We
illustrate how small deviations from (weak) responsiveness, that model the wish
of couples to be closer together, cause instability, even when we use a weaker
stability notion that excludes myopic blocking. Our remaining results deal with
various properties of the set of stable matchings for ``responsive couples
markets,'' viz., optimality, filled positions, and manipulation.
For a short corrigendum to this paper, see publication #25.
Full paper: publisher, previous
working paper
14. Klijn F. and M. Slikker (2005): 'Distribution Center
Consolidation Games,' Operations Research Letters, 33, 285288
Abstract: We study
the locationinventory model as introduced by Teo et al. (2001) to analyze the
impact of consolidation of distribution centers on facility and inventory
costs. We extend their result on profitability of consolidation. We associate a
cooperative game with each locationinventory situation and prove that this
game has a nonempty core for identical and independent demand processes. This
illustrates that consolidation does not only lower joint costs (which was shown
by Teo et al. (2001)), but it allows for a stable division of the minimal costs
as well.
Full paper: publisher, previous working paper
13. FiestrasJaneiro G., F. Klijn, and E.
Sánchez (2004): 'Manipulation of Optimal Matchings via Predonation
of Endowment,' Mathematical Social Sciences, 47, 295312
Abstract: In
this paper we answer a question posed by Sertel and ÖzkalSanver (2002) on the
manipulability of optimal matching rules in matching problems with endowments.
We characterize the classes of consumption rules under which optimal matching
rules can be manipulated via predonation of endowment.
Full paper: publisher, previous working paper
12. Hamers H., F. Klijn, T. Solymosi, S. Tijs, and D.
Vermeulen (2003): 'On the Nucleolus of Neighbor Games,' European Journal
of Operational Research, 146, 118
Abstract: Assignment
games are wellknown problems in practice. We mention house markets, job
markets, and production planning. The games of interest in this paper, the
neighbor games, arise from a special class of assignment problems. We focus on
the nucleolus (Schmeidler (1969)), one of the most prominent core solutions. A
core solution is interesting with respect to neighbor games because it divides
the profit of an optimal matching in a stable manner. This paper establishes a
polynomial bounded algorithm of quadratic order in the number of players for
calculating the nucleolus of neighbor games.
Full paper: publisher, previous working paper
11. Klijn F., D. Vermeulen, H. Hamers, T. Solymosi, S.
Tijs, and J.P. Villar (2003): 'Neighbor Games and the Leximax Solution,' Mathematical
Methods of Operations Research, 58, 191208
Abstract: Neighbor
games arise from certain matching or sequencing situations in which only some
specific pairs of players can obtain a positive gain. As a consequence, the
class of neighbor games is the intersection of the class of assignment games
(cf. Shapley and Shubik (1972)) and the class of component additive games
(Curiel et al. (1994)). We first present some elementary features of neighbor
games. After that we provide a polynomially bounded algorithm of order p^3 for
calculating the leximax solution of neighbor games, where p is the number of
players. The leximax solution, introduced by Arin and Iñarra (1997), is an
egalitarian solution that equals the core allocation that minimizes the maximum
satisfaction among all players. A nice feature of the algorithm is that it can
be visualized by pictures, showing the process of adjusting and fixing the
payoffs of the players.
Full paper: publisher, previous working paper
10. Klijn F. and J. Massó (2003): 'Weak Stability and a
Bargaining Set for the Marriage Model,' Games and Economic Behavior,
42, 91100
Abstract: In
this note we introduce weak stability, a relaxation of the concept of stability
for the marriage model (cf. Gale and Shapley (1962)) by assuming that the
agents are no longer myopic in choosing a blocking pair. The new concept is
based on threats within blocking pairs: an individually rational matching is
weakly stable if for every blocking pair one of the members can find a more
attractive partner with whom he forms another blocking pair for the original
matching. Our main result is that under the assumption of strict preferences,
the set of weakly stable and weakly efficient matchings coincides with the
bargaining set of Zhou (1994) for this context.
Full paper: publisher, previous working paper
9. Calleja P., P. Borm, H. Hamers, F. Klijn, and M.
Slikker (2002): 'On a New Class of Parallel Sequencing Situations and Related
Games,' Annals of Operations Research, 109, 265277
Abstract: This
paper considers a special class of sequencing situations with two parallel
machines in which each agent has precisely two jobs to be processed, one on
each machine. The costs of an agent depend linearly on the final completion
time of his jobs. We describe a procedure that provides an optimal processing
order of the jobs. Furthermore, we study cooperative games arising from these
sequencing situations. Our main result is balancedness of these games.
Full paper: publisher, previous
working paper
8. Curiel
I., H. Hamers, and F. Klijn (2002):
'Sequencing Games: A Survey,' in: P. Borm and H. Peters (eds.), Chapters in
Game Theory: in Honor of Stef Tijs, pp. 2750. Kluwer Academic Publishers, Boston
Abstract: This
paper gives an overview of the start and the main developments in the research
area that studies the interaction between sequencing situations and cooperative
game theory. It focuses on results related to balancedness and convexity of
sequencing games.
Full paper: publisher, previous working paper
7. Hamers H., F. Klijn, T. Solymosi, S. Tijs, and J.P.
Villar (2002): 'Assignment Games satisfy the CoMaproperty,' Games and Economic
Behavior, 38, 231239
Abstract: A balanced
game satisfies the CoMaproperty if and only if the extreme points of its core
are marginal vectors. Hence, the core of a game that satisfies the
CoMaproperty is the convex hull of the marginal vectors that are in the core.
In this note, we prove that assignment games (cf. Shapley and Shubik (1972))
satisfy the CoMaproperty.
Full paper: publisher, previous working paper
6. Klijn F., M. Slikker, and S.
Tijs (2001): 'A Dual Egalitarian Solution,' Economics
Bulletin, vol 3., no. 10, 18
Abstract: In
this note we introduce an egalitarian solution, called the dual egalitarian
solution, that is the natural counterpart of the egalitarian solution of Dutta
and Ray (1989). We prove among others, that for a convex game the egalitarian
solution coincides with the dual egalitarian solution for its dual concave
game.
Full paper: publisher
5. Klijn F., S. Tijs, and H. Hamers (2000):
'Balancedness of Permutation Games and Envyfree Allocations in Indivisible Good
Economies,' Economics Letters, 69, 323326
Abstract: Permutation
games are cooperative games that are induced by situations in which n agents
all have one job to be processed and one machine on which each job can be
processed. Tijs et al. (1984} used the Birkhoffvon Neumann theorem on
doubly stochastic matrices to prove the total balancedness of permutation
games. Curiel and Tijs (1986) gave another proof, using an equilibrium
existence theorem of Gale (1984) for a discrete exchange economy with money. In
this note, we provide another proof, which, in contrast to the proofs mentioned
above, does not rely on deep mathematical theorems. We invoke the existence
result of envyfree allocations in quasilinear economies (cf. Klijn (2000)) to
construct a core allocation by relating the core conditions with the properties
of envyfreeness and Paretoefficiency.
Full paper: publisher, previous working paper
4. Klijn F. (2000): 'An Algorithm for Envyfree
Allocations in an Economy with Indivisible Objects and Money,' Social
Choice and Welfare, 17, 201216
Abstract: Envyfree
allocations are allocations in which every agent likes his own bundle at least
as well as that of anyone else (cf. Foley (1967)). In other words, an
allocation is envyfree if and only if no individual wishes to trade with
anyone else. In this paper, we study envyfree allocations for economies with
indivisible objects, quasilinear utility functions, and an amount of money. We
give a polynomially bounded algorithm for finding envyfree allocations. The
algorithm consists of two intuitive procedures, viz., a sidepayment procedure
(that changes the sidepayments) and a permutation procedure (that changes the
assignment of the objects to the agents). We use graphs to visualize the
procedures. It is shown that connectedness of the graphs characterizes the
extreme points of the polytopes of sidepayments corresponding with envyfree
allocations.
Full paper: publisher, previous working paper
3. Klijn F., M. Slikker, S. Tijs, and J. Zarzuelo
(2000): 'The Egalitarian Solution for Convex Games: Some
Characterizations,' Mathematical Social Sciences, 40,
111121
Abstract: The
egalitarian solution for TUgames as introduced by Dutta and Ray (1989) is
studied. Five characterizations of the restriction of this solution to the
class of convex games are given. They all involve a stability property due to
the concept of the equal division core from Selten (1972) and all but the third
characterization involve a property restricting maximum payoffs. The first two
characterizations use in addition efficiency and the reduced game properties of
Hart and MasColell (1989) and Davis
and Maschler (1965), respectively. The fourth and fifth characterization only
need in addition weak variants of the reduced game properties mentioned above.
The third characterization involves besides the stability condition, efficiency
and a new consistency property.
Full paper: publisher, previous working paper
2. Hamers H., F. Klijn, and J. Suijs (1999): 'On the
Balancedness of Multiple Machine Sequencing Games,' European Journal of
Operational Research, 119, 678691
Abstract: In
this paper we study msequencing games that arise from sequencing situations
with m parallel and identical machines. These msequencing games, which involve
n players, give rise to mmachine games, which involve m players. Here, n
corresponds to the number of jobs in an msequencing situation, and m
corresponds to the number of machines in the same msequencing situation. We
prove that an msequencing game is balanced if and only if the corresponding
mmachine game is balanced. Furthermore, it is shown that msequencing games
are balanced if m=1,2. Finally, if m>2, balancedness is established for two
special classes of msequencing games.
Full paper: publisher, previous working paper
1. Klijn F., M. Slikker, and J. Zarzuelo (1999):
'Characterizations of a MultiChoice Value,' International Journal of
Game Theory, 28, 521532
Abstract: A
multichoice game is a generalization of a cooperative game in which each
player has several activity levels. We study the extended Shapley value as
proposed by Derks and Peters (1993). Van den Nouweland (1993) provided a
characterization that is an extension of Young's (1985) characterization of the
Shapley value. Here we provide four other characterizations, one of which is
the analogue of Shapley's (1953) original characterization. The three other
characterizations are inspired by Myerson's (1980) characterization of the
Shapley value using balanced contributions.
Full paper: publisher, previous working paper
Working Papers
2. Hamers H., F. Klijn and M. Slikker (2013): 'Price of Anarchy in Sequencing Situations and the Impossibility to Coordinate,' Barcelona GSE Working Paper 709
Abstract: Scheduling jobs of decentralized decision makers that are in competition will usually lead to cost inefficiencies. This cost inefficiency is studied using the Price of Anarchy (PoA), i.e., the ratio between the worst Nash equilibrium cost and the cost attained at the centralized optimum. First, we provide a tight upperbound for the PoA that depends on the number of machines involved. Second, we show that it is impossible to design a scheduledbased coordinating mechanism in which a Nash equilibrium enforces the centralized or first best optimum. Finally, by simulations we illustrate that on average the PoA is relatively small with respect to the established tight upperbound.
Full paper: working paper
1. Klijn F. and A. Yazici (2012): 'A
ManytoMany 'Rural Hospital Theorem',' Barcelona GSE Working Paper 567
Abstract: We show that the full version of the socalled "rural hospital theorem" generalizes to manytomany matching problems where agents on both sides of the problem have substitutable and weakly separable preferences. We reinforce our result by showing that when agents' preferences satisfy substitutability, the domain of weakly separable preferences is also maximal for the rural hospital theorem to hold.
Full paper: working paper

