1. Biró P., F. Klijn, and S. Pápai (2022): 'Balanced Exchange in a Multi-Unit Shapley-Scarf Market,' Barcelona School of Economics Working Paper 1342
Abstract: We study markets in which each agent is endowed with multiple units of an indivisible and agent-specific good. Monetary compensations are not possible. An outcome of a market is given by a circulation which consists of a balanced exchange of goods. Agents only have (responsive) preferences over the bundles they receive.
We prove that for general capacity configurations there is no circulation rule that satisfies individual rationality, Pareto-efficiency, and strategy-proofness. We characterize the (so-called irreducible) capacity configurations for which the three properties are compatible, and show that in this case the Circulation Top Trading Cycle (cTTC) rule is the unique rule that satisfies all three properties. We also explore the incentive and efficiency properties of the cTTC rule for general capacity configurations and provide a characterization of the rule for lexicographic preferences.
Next, we introduce and study the family of so-called Segmented Trading Cycle (STC) rules. These rules are obtained by first distributing agents' endowments over a number of different smaller markets (the market segments), then applying the standard Top Trading Cycle algorithm within each market segment separately, and finally lumping together the induced circulations. We show that STC rules are individually rational, strategy-proof, and nonbossy. Even though STC rules do not satisfy group-strategy-proofness in general, they do satisfy weaker notions of group-strategy-proofness. For irreducible capacity configurations the family of STC rules collapses to the cTTC rule which then is also group-strategy-proof. Finally, we characterize one particularly interesting STC rule by means of top unanimity and self-enforcing group-strategy-proofness.
Full paper: working paper
64. Klaus B., F. Klijn, and S. Özbilen (2025): 'Core Stability and Strategy-Proofness in Hedonic Coalition Formation Problems with Friend-Oriented Preferences,' Games and Economic Behavior, 154, 16-52
Abstract: We study hedonic coalition formation problems with friend-oriented preferences; that is, each agent has preferences over his coalitions based on a partition of the set of agents, except himself, into "friends" and "enemies" such that (E) adding an enemy makes him strictly worse off and (F) adding a friend together with a set of enemies makes him strictly better off. Friend-oriented preferences induce a so-called friendship graph where vertices are agents and directed edges point to friends.
We show that the partition associated with the strongly connected components (SCC) of the friendship graph is in the strict core. We then prove that the SCC mechanism, which assigns the SCC partition to each hedonic coalition formation problem with friend-oriented preferences, satisfies a strong group incentive compatibility property: group strategy-proofness. Our main result is that on any "rich" subdomain of friend-oriented preferences, the SCC mechanism is the only mechanism that satisfies core stability and strategy-proofness.
Full paper: publisher, previous working paper
63. Klaus B., F. Klijn, and J. Sethuraman (2025): 'A Characterization of the Top-Trading-Cycles Mechanism for Housing Markets via Respecting-Improvement,' Economics Letters, 247, 112145
Abstract: We provide the first characterization of the prominent top-trading-cycles (TTC) mechanism in the Shapley-Scarf housing market model (Shapley and Scarf, 1974) that uses respecting-improvement. Specifically, we show that for strict preferences, the TTC mechanism is the unique mechanism satisfying pair-efficiency, respecting-improvement, and strategy-proofness.
Full paper: publisher, previous working paper
62. Klijn F., M. Mdaghri Alaoui, and M. Vorsatz (2025): 'Online Academic Exams: Does Multiplicity of Exam Versions Mitigate Cheating?,' International Review of Economics Education, 48, 100305
Abstract: We study academic integrity in a final exam of a game theory course with 463 undergraduate students at a major Spanish university. The exam is an unproctored online multiple-choice exam without backtracking. A key characteristic is that for each (type of) problem, groups of students receive different versions. Moreover, each problem version is assigned to one subgroup during one stage of the exam and to another subgroup during an immediately consecutive later stage. Thus, we can exploit grade points and timestamps to study students' academic integrity. We observe a significant decrease in completion time at each later stage; however, surprisingly, there is no corresponding impact on average grade points. The precise number of different versions does not seem to have an effect on either variable. Our findings thus suggest that employing a limited number of distinct problem versions (as few as two) can diminish cheating effectiveness in online exams.
Full paper: publisher, previous working paper
61. Klaus B. and F. Klijn (2024): 'Minimal-Access Rights in School Choice and the Deferred Acceptance Mechanism,' Mathematics of Operations Research, 49, 1487-1501
Abstract: A classical school choice problem consists of a set of schools with priorities over students and a set of students with preferences over schools. Schools' priorities are often based on multiple criteria, e.g., merit-based test scores as well as minimal-access rights (siblings attending the school, students' proximity to the school, etc.). Traditionally, minimal-access rights are incorporated into priorities by always giving minimal-access students higher priority over non-minimal-access students. However, stability based on such adjusted priorities can be considered unfair because a minimal-access student may be admitted to a popular school while another student with higher merit-score but without minimal-access right is rejected, even though the former minimal-access student could easily attend another of her minimal-access schools.
We therefore weaken stability to minimal-access stability: minimal-access rights only promote access to at most one minimal-access school. Apart from minimal-access stability, we also would want a school choice mechanism to satisfy strategy-proofness and minimal-access monotonicity, i.e., additional minimal-access rights for a student do not harm her. Our main result is that the student-proposing deferred acceptance mechanism is the only mechanism that satisfies minimal-access stability, strategy-proofness, and minimal-access monotonicity. Since this mechanism is in fact stable, our result can be interpreted as an impossibility result: fairer outcomes that are made possible by the weaker property of minimal-access stability are incompatible with strategy-proofness and minimal-access monotonicity.
Full paper: publisher, previous working paper
60. Feng D., B. Klaus, and F. Klijn (2024): 'Characterizing the Typewise Top-Trading-Cycles Mechanism for Multiple-Type Housing Markets,' Games and Economic Behavior, 146, 234-254
Abstract: We consider the generalization of the classical Shapley and Scarf housing market model (Shapley and Scarf, 1974) to so-called multiple-type housing markets (Moulin, 1995). Throughout the paper, we focus on strict preferences. When preferences are separable, the prominent solution for these markets is the typewise top-trading-cycles (tTTC) mechanism.
We first show that for lexicographic preferences, a mechanism is unanimous (or onto), individually rational, strategy-proof, and non-bossy if and only if it is the tTTC mechanism. Second, we obtain a corresponding characterization for separable preferences. We obtain additional characterizations when replacing [strategy-proofness and non-bossiness] with self-enforcing group (or pairwise) strategy-proofness. Finally, we show that for strict preferences, there is no mechanism satisfying unanimity, individual rationality, and strategy-proofness. We obtain further impossibility results for strict preferences based on weakening unanimity to ontoness and on extending the tTTC solution.
Our characterizations of the tTTC mechanism constitute the first characterizations of an extension of the prominent top-trading-cycles (TTC) mechanism to multiple-type housing markets.
Full paper: publisher, previous working paper
59. Biró P., F. Klijn, X. Klimentova, and A. Viana (2024): 'Shapley-Scarf Housing Markets: Respecting Improvement, Integer Programming, and Kidney Exchange,' Mathematics of Operations Research, 49, 1938-1972
Abstract: In a housing market of Shapley and Scarf (1974), each agent is endowed with one indivisible object and has preferences over all objects. An allocation of the objects is in the (strong) core if there exists no (weakly) blocking coalition. We show that for strict preferences the unique strong core allocation "respects improvement": if an agent's object becomes more desirable for some other agents, then the agent's allotment in the unique strong core allocation weakly improves. We extend this result to weak preferences for both the strong core (conditional on non-emptiness) and the set of competitive allocations (using probabilistic allocations and stochastic dominance). There are no counterparts of the latter two results in the two-sided matching literature. We provide examples to show how our results break down when there is a bound on the length of exchange cycles.
Respecting improvements is an important property for applications of the housing markets model such as kidney exchange: it incentivises each patient to bring the best possible set of donors to the market. We conduct computer simulations using markets that resemble the pools of kidney exchange programmes. We compare the game-theoretical solutions with current techniques (maximum size and maximum weight allocations) in terms of violations of the respecting improvement property. We find that game-theoretical solutions fare much better at respecting improvements, even when exchange cycles are bounded, and they do so at a low efficiency cost. As a stepping-stone for our simulations, we provide novel integer programming formulations for computing core, competitive, and strong core allocations.
Full paper: publisher, previous working paper
58. Alcalde-Unzu J., F. Klijn, and M. Vorsatz (2023): 'Constrained School Choice: An Experimental QRE Analysis,' Social Choice and Welfare, 61, 587-624
Abstract: The theoretical literature on public school choice proposes centralized mechanisms that assign children to schools on the basis of parents' preferences and the priorities children have for different schools. The related experimental literature analyzes in detail how various mechanisms fare in terms of welfare and stability of the resulting matchings, yet often provides only aggregate statistics of the individual behavior that leads to these outcomes (i.e., the degree to which subjects tell the truth in the induced simultaneous move game). In this paper, we show that the quantal response equilibrium (QRE) adequately describes individual behavior and the resulting matching in three constrained problems for which the immediate acceptance mechanism and the student-optimal stable mechanism coincide. Specifically, the comparative statics of the logit-QRE with risk-neutral and expected-payoff-maximizing agents capture the directional changes of subject behavior and the prevalence of the different stable matchings when cardinal payoffs (i.e., relative preference intensities) are modified in the experiment.
Full paper: publisher, previous working paper
57. Biró P., F. Klijn, and S. Pápai (2022): 'Serial Rules in a Multi-Unit Shapley-Scarf Market,' Games and Economic Behavior, 136, 428-453
Abstract: We study generalized Shapley-Scarf exchange markets where each agent is endowed with multiple units of an indivisible and agent-specific good and monetary compensations are not possible. An outcome is given by a circulation which consists of a balanced exchange of goods. We focus on circulation rules that only require as input ordinal preference rankings of individual goods, and agents are assumed to have responsive preferences over bundles of goods. We study the properties of serial dictatorship rules which allow agents to choose either a single good or an entire bundle sequentially, according to a fixed ordering of the agents. We also introduce and explore extensions of these serial dictatorship rules that ensure individual rationality. The paper analyzes the normative and incentive properties of these four families of serial dictatorships and also shows that the individually rational extensions can be implemented with efficient graph algorithms.
Full paper: publisher, previous working paper
56. Klijn F., M. Mdaghri Alaoui, and M. Vorsatz (2022): 'Academic Integrity in On-line Exams: Evidence from a Randomized Field Experiment,' Journal of Economic Psychology, 93, 102555
Abstract: We study academic integrity in a final exam of a compulsory course with almost 500 undergraduate students at a major Spanish university. Confinement and university closure due to Covid-19 took place by the end of the last lecture week. As a consequence, the usual classroom exam was turned into an unproctored on-line multiple-choice exam without backtracking. We exploit the different orders of exam problems and detailed data with timestamps to study students' academic integrity. First, taking the average over questions that were part of both earlier and later "rounds," we find that the number of correct answers to questions in the later round was 7.7% higher than in the earlier round. Second, the average completion time of questions in the later round was 18.1% shorter than in the earlier round. Third, a mere reminder of the university's code of ethics, which was sent to a subgroup halfway through the exam, did not affect cheating levels.
Full paper: publisher, previous working paper
55. Jaramillo P., Ç. Kayı, and F. Klijn (2021): 'School Choice: Nash Implementation of Stable Matchings through Rank-Priority Mechanisms,' Journal of Mathematical Economics, 95, 102496
Abstract: We consider school choice problems (Abdulkadiroğlu and Sönmez, 2003) where students are assigned to public schools through a centralized assignment mechanism. We study the family of so-called rank-priority mechanisms, each of which is induced by an order of rank-priority pairs. Following the corresponding order of pairs, at each step a rank-priority mechanism considers a rank-priority pair and matches an available student to an unfilled school if the student and the school rank and prioritize each other in accordance with the rank-priority pair. The Boston or immediate acceptance mechanism is a particular rank-priority mechanism. Our first main result is a characterization of the subfamily of rank-priority mechanisms that Nash implement the set of stable matchings (Theorem 1). Our second main result is a strong impossibility result: under incomplete information, no rank-priority mechanism implements the set of stable matchings (Theorem 2).
Full paper: publisher, previous working paper
54. Klijn F., M. Walzl, and C. Kah (2021): 'Almost Mutually Best in Matching Markets: Rank Gaps and Size of the Core,' Social Choice and Welfare, 57, 797-816
Abstract: This paper studies the one-to-one two-sided marriage model (Gale and Shapley, 1962). If agents' preferences exhibit mutually best (i.e., each agent is most preferred by her/his most preferred matching partner), there is a unique stable matching without rank gaps (i.e., in each matched pair the agents assign one another the same rank). We study in how far this result is robust for matching markets that are "close'' to mutually best. Without a restriction on preference profiles, we find that natural "distances'' to mutually best neither bound the size of the core nor the rank gaps at stable matchings. However, for matching markets that satisfy horizontal heterogeneity, "local'' distances to mutually best provide bounds for the size of the core and the rank gaps at stable matchings.
Full paper: publisher, previous working paper
53. Klijn F., J. Pais and M. Vorsatz (2020): 'Improving Schools through School Choice: An Experimental Study of Deferred Acceptance,' Economics Letters, 186, 108853
Abstract: In the context of school choice, we experimentally study the student-optimal stable mechanism where subjects take the role of students and schools are passive. Specifically, we study if a school can be better off when it unambiguously improves in the students' true preferences and its (theoretic) student-optimal stable match remains the same or gets worse. Using first-order stochastic dominance to evaluate the schools' distributions over their actual matches, we find that schools' welfare almost always changes in the same direction as the change of the student-optimal stable matching, i.e., incentives to improve school quality are nearly idle.
Full paper: publisher, previous working paper
52. Klijn F., J. Pais and M. Vorsatz (2019): 'Static versus Dynamic Deferred Acceptance in School Choice: Theory and Experiment,' Games and Economic Behavior, 113, 147-163
Abstract: In the context of school choice, we experimentally study how behavior and outcomes are affected when, instead of submitting rankings in the student-proposing or school-proposing deferred acceptance (DA) mechanism, students make decisions dynamically, going through the steps of the underlying algorithms. Our main results show that, contrary to theory, (a) in the dynamic student-proposing DA mechanism, students propose to schools respecting the order of their true preferences slightly more often than in its static version while, (b) in the dynamic school-proposing DA mechanism, students react to proposals by always respecting the order and not accepting schools in the tail of their true preferences more often than in the corresponding static version. As a consequence, the dynamic mechanisms outperform their static counterparts in what stability and average payoffs are concerned. In the aggregate, the dynamic school-proposing DA mechanism is the best performing mechanism.
Full paper: publisher, previous working paper
51. Jaramillo P., Ç. Kayı, and F. Klijn (2019): 'The Core of Roommate Problems: Size and Rank-Fairness within Matched Pairs,' International Journal of Game Theory, 48, 157-179
Abstract: This paper deals with roommate problems (Gale and Shapley, 1962) that are solvable, i.e., have a non-empty core (set of stable matchings). We study rank-fairness within pairs of stable matchings and the size of the core by means of maximal and average rank gaps. We provide upper bounds in terms of maximal and average disagreements in the agents' rankings. Finally, we show that most of our bounds are tight.
Full paper: publisher, previous working paper
50. Braat J., H. Hamers, F. Klijn and M. Slikker (2019): 'A Selfish Allocation Heuristic in Scheduling: Equilibrium and Inefficiency Bound Analysis,' European Journal of Operational Research, 273, 634-645
Abstract: For single decision maker optimization problems that lack time efficient algorithms to determine the optimum, there is a need for heuristics. In the context of coordinated production planning, the seminal paper of Graham (1969) provided a performance analysis of heuristics and obtained a bound in relation to the centralized optimum. This paper introduces a framework that includes a performance analysis of a so-called equilibrium heuristic in the setting of multiple decision maker problems. The framework consists of three steps: a heuristic for each player that leads to a strategy profile, the verification that this strategy profile is a Nash equilibrium, and finally a worst case cost analysis to obtain a bound on the performance of the heuristic in terms of the aggregate cost in the obtained Nash equilibrium in relation to the centralized optimum. We implement our general framework in a setting of sequencing situations with selfish agents, multiple identical machines, and the sum of completion times as cost criterion. We provide a tight upper bound for the performance of our equilibrium heuristic. Simulations show that the equilibrium heuristic generally performs much better than the derived tight upper bound. Finally, the relation with the price of anarchy is discussed.
Full paper: publisher, previous working paper
49. Hamers H., F. Klijn and M. Slikker (2019): 'Implementation of Optimal Schedules in Outsourcing with Identical Suppliers,' Mathematical Methods of Operations Research, 89, 173-187
Abstract: This paper deals with decentralized decision-making situations in which firms outsource production orders to multiple identical suppliers. Each firm aims to minimize the sum of its completion times. We study whether a central authority can install a mechanism such that strategic interaction leads to a socially optimal schedule. For the case of single demand the shortest-first mechanism implements optimal schedules in Nash equilibrium. We show that for the general case there exists no anonymous mechanism that implements optimal schedules in correlated equilibrium.
Full paper: publisher, previous working paper
48. Klijn F. (2019): 'Constrained Allocation of Projects to Heterogeneous Workers with Preferences over Peers,' B.E. Journal of Theoretical Economics, 19, 20170038
Abstract: We study the problem of allocating projects to heterogeneous workers. The simultaneous execution of multiple projects imposes constraints across project teams. Each worker has preferences over the combinations of projects in which he can potentially participate and his team members in any of these projects. We propose a revelation mechanism that is Pareto-efficient and group strategy-proof (Theorem 1). We also identify two preference domains on which the mechanism is strongly group strategy-proof (Theorem 2). Our results subsume results by Monte and Tumennasan (2013) and Kamiyama (2013).
Full paper: publisher, previous working paper
47. Klaus B. and F. Klijn (2017): 'Non-Revelation Mechanisms for Many-to-Many Matching: Equilibria versus Stability,' Games and Economic Behavior, 104, 222-229
Abstract: We study many-to-many matching markets in which agents from a set A are matched to agents from a disjoint set B through a two-stage non-revelation mechanism. In the first stage, A-agents, who are endowed with a quota that describes the maximal number of agents they can be matched to, simultaneously make proposals to the B-agents. In the second stage, B-agents sequentially, and respecting the quota, choose and match to available A-proposers. We study the subgame perfect Nash equilibria of the induced game. We prove that stable matchings are equilibrium outcomes if all A-agents' preferences are substitutable. We also show that the implementation of the set of stable matchings is closely related to the quotas of the A-agents. In particular, implementation holds when A-agents' preferences are substitutable and their quotas are non-binding.
Full paper: publisher, previous working paper
46. Klijn F. and M. Vorsatz (2017): 'Outsourcing with Identical Suppliers and Shortest-First Policy: A Laboratory Experiment,' Theory and Decision, 82, 597-615
Abstract: We study experimentally in the laboratory two 2-player games that mimic a decentralized decision-making situation in which firms repeatedly outsource production orders to multiple identical suppliers. The first game has a unique (inefficient) equilibrium in mixed strategies, while the second game has two (efficient) equilibria in pure strategies and an infinite number of (inefficient) equilibria in mixed strategies. In both games, the optimal social costs can also be obtained via dominated strategies. We find that only in the second game subjects manage to reach an efficient outcome more often when matched in fixed pairs than when randomly rematched each round. Surprisingly, this is because subjects coordinate on dominated strategies (and not an efficient pure strategy equilibrium). We show theoretically that preferences for efficiency cannot explain our experimental results. Inequality aversion, on the other hand, cannot be rejected.
Full paper: publisher, previous working paper
45. Klaus B. and F. Klijn (2016): 'Equilibria of Deferred Acceptance with Complete Lists,' Economics Letters, 144, 98-101
Abstract: We study the structure of the set of (Nash) equilibria of a deferred acceptance game with complete lists: for a given marriage market with complete lists, men propose to women truthfully while women can accept or reject proposals strategically throughout the deferred-acceptance algorithm. Zhou (1991) studied this game and showed that a matching that is stable with respect to the true preferences can be supported by some preference profile (possibly a non-equilibrium one) if and only if it can be supported by an equilibrium as well. In particular, this result implies the existence of equilibria since the men-optimal stable matching is supported by true preferences and hence an equilibrium outcome. We answer an open question Zhou posed by showing that there need not exist an equilibrium matching that weakly dominates all other equilibrium matchings from the women's point of view (Theorem 2).
Full paper: publisher, previous working paper
44. Klijn F., J. Pais, and M. Vorsatz (2016): 'Affirmative Action through Minority Reserves: An Experimental Study on School Choice,' Economics Letters, 139, 72-75
Abstract: Minority reserves are an affirmative action policy proposed by Hafalir et al. (2013) in the context of school choice. In a laboratory experiment, we find that adding minority reserves to the GS and TTC mechanisms has positive effects on stability but is quite disappointing in terms of efficiency. Also GS induces higher rates of truth-telling by minority students and thus outclasses TTC.
Full paper: publisher, previous working paper
43. Klijn F. and A. Yazici (2014): 'A Many-to-Many Rural Hospital Theorem,' Journal of Mathematical Economics, 54(1), 63-73
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: publisher, previous working paper
42. Jaramillo P., Ç. Kayı, and F. Klijn (2014): 'Asymmetrically Fair Rules for an Indivisible Good Problem with a Budget Constraint,' Social Choice and Welfare, 43(3), 603-633
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,' Social Choice and Welfare, 42(4), 793-811
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, addendum
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: 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), 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: publisher, previous 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: 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), 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: 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), 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: 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, 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: publisher, previous 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: publisher, previous 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: publisher, previous 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: publisher, previous 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: publisher, previous 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: publisher, previous 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: 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, 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: publisher, previous 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: publisher, previous 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: publisher, previous 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: 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, 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: 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, 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: 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, 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: 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, 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: 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. 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: publisher, previous 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: publisher, previous 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: publisher, previous 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: 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, 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: 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, 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: publisher, previous 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