Papers (w/ abstracts)




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 Many-to-Many Matching Markets,' forthcoming in Social Choice and Welfare


Abstract: We consider two-sided many-to-many 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), 693-701


Abstract: We study many-to-one matching markets where hospitals have responsive preferences over students. We study the game induced by the student-optimal stable matching mechanism. We assume that students play their weakly dominant strategy of truth-telling. 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 one-to-one 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), 1-22


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 Gale-Shapley 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 Gale-Shapley 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), 222-229


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 student-optimal 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 student-optimal stable mechanism satisfies a more standard global consistency property. Next, we provide necessary and sufficient conditions for the student-optimal stable mechanism to satisfy converse consistency principles. We identify a necessary and sufficient condition (local shift-freeness) on the priority structure such that the student-optimal stable mechanism satisfies local converse consistency. Interestingly, local acyclicity implies local shift-freeness and hence the student-optimal stable mechanisms more frequently satisfies local converse consistency than local consistency. Finally, in order for the student-optimal 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 student-optimal 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, 1-18


Abstract: This survey deals with two-sided 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), 23-33


Abstract: We study comparative statics of manipulations by women in the men-proposing deferred acceptance mechanism in the two-sided one-to-one 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 many-to-one 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), 921-933


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 Neumann-Morgenstern farsightedly stable sets. We show that a singleton is von Neumann-Morgenstern farsightedly stable if and only if the matching is stable (Theorem 1). We also present a roommate market without a von Neumann-Morgenstern farsightedly stable set (Example 1) and a roommate market with a non-singleton von Neumann-Morgenstern 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), 101-103


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: 
publisherprevious 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), 392-396


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), 817-824


Abstract: In this note we study von Neumann-Morgenstern farsightedly stable sets for Shapley and Scarf (1974) housing markets. Kawasaki (2008) shows that the set of competitive allocations coincides with the unique von Neumann-Morgenstern 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 Neumann-Morgenstern 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), 2218-2240


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 non-empty (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), 1860-1874


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 real-life 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), 647-667


Abstract: We consider one-to-one 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), 1921-1947


Abstract: Recently, several school districts in the US have adopted or consider adopting the Student-Optimal 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 so-called Boston mechanism the transition would lead to efficiency gains. The first two mechanisms are strategy-proof, 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), 215-227


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 side-payments and provide a method for obtaining stable outcomes.
Full paper: publisherprevious working paper


 

26. Klaus B. and F. Klijn (2009): 'Employment by Lotto Revisited,' International Game Theory Review, 11(2), 181-198


Abstract: We study employment by lotto (Aldershof et al., 1999), a procedurally fair matching algorithm for the so-called 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: publisherprevious working paper


 

25. Klaus B., F. Klijn, and T. Nakamura (2009): 'Corrigendum: Stable Matchings and Preferences of Couples,' Journal of Economic Theory, 144(5), 2227-2233


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: publisherprevious 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), 11-22


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: publisherprevious 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, 175-184


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: publisherprevious working paper


 

22. Klaus B. and F. Klijn (2007): 'Fair and Efficient Student Placement with Couples,' International Journal of Game Theory, 36, 177-207


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 priority-togetherness of couples. A priority structure that satisfies both necessary conditions is called pt-acyclic. For student placement problems where all quotas are equal to one we characterize pt-acyclicity and show that it is a sufficient condition for the existence of a fair and efficient placement mechanism. If in addition to pt-acyclicity we require reallocation- and vacancy-fairness for couples, the so-called dictator-bidictator placement mechanism is the unique fair and efficient placement mechanism. Finally, for general student placement problems, we show that pt-acyclicity may not be sufficient for the existence of a fair and efficient placement mechanism. We identify a sufficient condition such that the so-called sequential placement mechanism produces a fair and efficient allocation.
Full paper: publisherprevious working paper


 

21. Klaus B. and F. Klijn (2007): 'Corrigendum to ''On Randomized Matching Mechanisms'' [Economic Theory 8(1996)377-381],' Economic Theory, 32, 411-416


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: publisherprevious working paper


 

20. Klaus B. and F. Klijn (2007): 'Paths to Stability for Matching Markets with Couples,' Games and Economic Behavior, 58, 154-171


Abstract: We study two-sided 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: publisherprevious working paper


 

19. Klaus B. and F. Klijn (2006): 'Median Stable Matching for College Admissions,' International Journal of Game Theory, 34, 1-11


Abstract: We give a simple and concise proof that so-called generalized median stable matchings are well-defined 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: publisherprevious working paper


 

18. Klijn F. and E. Sánchez (2006): 'Sequencing Games without Initial Order,' Mathematical Methods of Operations Research, 63, 53-62


Abstract: In this note we study uncertainty sequencing situations, i.e., 1-machine 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: publisherprevious working paper


 

17. Klaus B. and F. Klijn (2006): 'Procedurally Fair and Stable Matching,' Economic Theory, 27, 431-447


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: publisherprevious working paper


 

16. Hamers H., F. Klijn, and B. van Velzen (2005): 'On the Convexity of Precedence Sequencing Games,' Annals of Operations Research, 137, 161-175


Abstract: In this paper we study a class of cooperative sequencing games that arise from one-machine sequencing situations in which chain precedence relations are imposed on the jobs. It is shown that these sequencing games are convex.
Full paper: 
publisherprevious working paper


 

15. Klaus B. and F. Klijn (2005): 'Stable Matchings and Preferences of Couples,' Journal of Economic Theory, 121, 75-106


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: 
publisherprevious working paper


 

14. Klijn F. and M. Slikker (2005): 'Distribution Center Consolidation Games,' Operations Research Letters, 33, 285-288


Abstract: We study the location-inventory 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 location-inventory situation and prove that this game has a non-empty 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: publisherprevious working paper


 

13. Fiestras-Janeiro G., F. Klijn, and E. Sánchez (2004): 'Manipulation of Optimal Matchings via Predonation of Endowment,' Mathematical Social Sciences, 47, 295-312


Abstract: In this paper we answer a question posed by Sertel and Özkal-Sanver (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: publisherprevious 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, 1-18


Abstract: Assignment games are well-known 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: publisherprevious 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, 191-208


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: publisherprevious working paper


 

10. Klijn F. and J. Massó (2003): 'Weak Stability and a Bargaining Set for the Marriage Model,' Games and Economic Behavior, 42, 91-100


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: publisherprevious 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, 265-277


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: 
publisherprevious 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. 27-50. 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: publisherprevious working paper


 

7. Hamers H., F. Klijn, T. Solymosi, S. Tijs, and J.P. Villar (2002): 'Assignment Games satisfy the CoMa-property,' Games and Economic Behavior, 38, 231-239


Abstract: A balanced game satisfies the CoMa-property if and only if the extreme points of its core are marginal vectors. Hence, the core of a game that satisfies the CoMa-property 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 CoMa-property.
Full paper: publisherprevious working paper


 

6. Klijn F., M. Slikker, and S. Tijs (2001): 'A Dual Egalitarian Solution,' Economics Bulletin, vol 3., no. 10, 1-8


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 Envy-free Allocations in Indivisible Good Economies,' Economics Letters, 69, 323-326


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 Birkhoff-von 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 envy-free allocations in quasi-linear economies (cf. Klijn (2000)) to construct a core allocation by relating the core conditions with the properties of envy-freeness and Pareto-efficiency.
Full paper: publisherprevious working paper


 

4. Klijn F. (2000): 'An Algorithm for Envy-free Allocations in an Economy with Indivisible Objects and Money,' Social Choice and Welfare, 17, 201-216


Abstract: Envy-free 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 envy-free if and only if no individual wishes to trade with anyone else. In this paper, we study envy-free allocations for economies with indivisible objects, quasi-linear utility functions, and an amount of money. We give a polynomially bounded algorithm for finding envy-free 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 envy-free allocations.
Full paper: publisherprevious 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, 111-121


Abstract: The egalitarian solution for TU-games 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 Mas-Colell (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: publisherprevious 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, 678-691


Abstract: In this paper we study m-sequencing games that arise from sequencing situations with m parallel and identical machines. These m-sequencing games, which involve n players, give rise to m-machine games, which involve m players. Here, n corresponds to the number of jobs in an m-sequencing situation, and m corresponds to the number of machines in the same m-sequencing situation. We prove that an m-sequencing game is balanced if and only if the corresponding m-machine game is balanced. Furthermore, it is shown that m-sequencing games are balanced if m=1,2. Finally, if m>2, balancedness is established for two special classes of m-sequencing games.
Full paper: publisherprevious working paper


 

1. Klijn F., M. Slikker, and J. Zarzuelo (1999): 'Characterizations of a Multi-Choice Value,' International Journal of Game Theory, 28, 521-532


Abstract: A multi-choice 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 scheduled-based 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 Many-to-Many 'Rural Hospital Theorem',' Barcelona GSE Working Paper 567


Abstract: We show that the full version of the so-called "rural hospital theorem" generalizes to many-to-many 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








Comments