On the lattice structure of the set of stable matchings for a many-to-one model ∗

For the many-to-one matching model with firms having substitutable and q-separable preferences we propose two very natural binary operations that together with the unanimous partial ordering of the workers endow the set of stable matchings with a lattice structure. We also exhibit examples in which, under this restricted domain of firms' preferences, the classical binary operations may not even be matching     

Sequentially compatible payoffs and the core in TU-games

In the context of cooperative TU-games, we introduce a recursive procedure to distribute the surplus of cooperation when there is an exogenous ordering among the set of players N. In each step of the process, using a given notion of reduced games, an upper and a lower bound for the payoff to the player at issue are required. Sequentially compatible payoffs are defined as those allocation vectors that meet these recursive bounds. For a family of reduction operations, the behavior of this new solution concept is analyzed. For any ordering of N, the core of the game turns out to be the set of sequentially compatible payoffs when the Davis–Maschler reduced games are used. Finally, we study which reduction operations give an advantage to the first player in the ordering.     

A simple procedure to obtain the extreme core allocations of an assignment market

Given an assignment market, we introduce a set of vectors, one for each possible ordering on the player set, which we name the max-payoff vectors. Each one of these vectors is obtained recursively only making use of the assignment matrix. Those max-payoff vectors that are efficient turn out to give the extreme core allocations of the market. When the assignment game has a large core, all the max-payoff vectors are extreme core allocations.     

Egalitarian solutions in the core

In this paper we define the Lorenz stable set, a subset of the core consisting of the allocations that are not Lorenz dominated by any other allocation of the core. We introduce the leximin stable allocation, which is derived from the application of the Rawlsian criterion on the core. We also define and axiomatize the egalitarian core, a set of core allocations for which no transfer from a rich player to a poor player is possible without violating the core restrictions. We find an inclusive relation of the leximin stable allocation and of the Lorenz stable set into the egalitarian core. Received: October 1999/Final version: July 2001     

Full ordering in the Shorrocks mobility sense of the semiring of monotone doubly stochastic matrices

In this paper, we investigate the ordering on a semiring of monotone doubly stochastic transition matrices in Shorrocks’ sense. We identify a class of an equilibrium index of mobility that induces the full ordering in a semiring, while this ordering is compatible with Dardanoni’s partial ordering on a set of monotone primitive irreducible doubly stochastic matrices.     

Mathematical morphology on bipolar fuzzy sets: general algebraic framework

In many domains of information processing, bipolarity is a core feature to be considered: positive information represents what is possible or preferred, while negative information represents what is forbidden or surely false. If the information is moreover endowed with vagueness and imprecision, as is the case for instance in spatial information processing, then bipolar fuzzy sets constitute an appropriate knowledge representation framework. In this paper, we focus on mathematical morphology as a tool to handle such information and reason on it. Applying mathematical morphology to bipolar fuzzy sets requires defining an appropriate lattice. We extend previous work based on specific partial orderings to any partial ordering leading to a complete lattice. We address the case of algebraic operations and of operations based on a structuring element, and show that they have good properties for any partial ordering, and that they can be useful for processing in particular spatial information, but also other types of bipolar information such as preferences and constraints. Particular cases using Pareto and lexicographic orderings are illustrated. Operations derived from fuzzy bipolar erosion and dilation are proposed as well.     

Evaluation and Incremental Determination of Almost Optimal Allocations of Resources

The problem of allocating resources to activities with strictly concave return functions is considered; the objective function to be maximized is the sum of the returns from each activity. It is demonstrated that any set of feasible allocations can be used to obtain an explicit upper bound of the optimal value of this function. The upper bound is used to check that a numerically fast incremental procedure produces almost optimal allocations. A conservative solution of the allocation problem is generated by successively incrementing allocations with the greatest marginal returns; practical allocations are obtained from the conservative allocations by a method resulting in a reduction of the number of nonzero allocations and a simultaneous increase of the value of the objective function.     

Resource location games

In this paper, we introduce and analyze resource location games. We show core non-emptiness by providing a set of intuitive core allocations, called Resource-Profit allocations. In addition, we present a sufficient condition for which the core and the set of Resource-Profit allocations coincide. Finally, we provide an example showing that when the sufficient condition is not satisfied, the coincidence is not guaranteed.     

Weighted allocation rules for standard fixed tree games

In this paper we consider standard fixed tree games, for which each vertex unequal to the root is inhabited by exactly one player. We present two weighted allocation rules, the weighted down-home allocation and the weighted neighbour-home allocation, both inspired by the painting story in Maschler et al. (1995) . We show, in a constructive way, that the core equals both the set of weighted down-home allocations and the set of weighted neighbour allocations. Since every weighted down-home allocation specifies a weighted Shapley value (Kalai and Samet (1988)) in a natural way, and vice versa, our results provide an alternative proof of the fact that the core of a standard fixed tree game equals the set of weighted Shapley values. The class of weighted neighbour allocations is a generalization of the nucleolus, in the sense that the latter is in this class as the special member where players have all equal weights.     

On extensions of the core and the anticore of transferable utility games

We consider several related set extensions of the core and the anticore of games with transferable utility. An efficient allocation is undominated if it cannot be improved, in a specific way, by sidepayments changing the allocation or the game. The set of all such allocations is called the undominated set, and we show that it consists of finitely many polytopes with a core-like structure. One of these polytopes is the $L_1$ -center, consisting of all efficient allocations that minimize the sum of the absolute values of the excesses. The excess Pareto optimal set contains the allocations that are Pareto optimal in the set obtained by ordering the sums of the absolute values of the excesses of coalitions and the absolute values of the excesses of their complements. The $L_1$ -center is contained in the excess Pareto optimal set, which in turn is contained in the undominated set. For three-person games all these sets coincide. These three sets also coincide with the core for balanced games and with the anticore for antibalanced games. We study properties of these sets and provide characterizations in terms of balanced collections of coalitions. We also propose a single-valued selection from the excess Pareto optimal set, the min-prenucleolus, which is defined as the prenucleolus of the minimum of a game and its dual.     

The extensional ordering of the sequential functionals

We investigate the extensional ordering of the sequential functionals of finite types, with a focus on when the sequential functionals of a given type form a directed complete partial ordering, and on when a finite sequential functional will be the nontrivial least upper bound of an infinite chain of sequential functionals. We offer a full characterization for finite functionals of pure types.     

Multi-commodity rationing problems with maxmin payoffs

We address a multi-dimensional extension of standard rationing problems in which several commodities have to be shared among a set of agents who exhibit maxmin preferences on the results they obtain. In this context we investigate efficiency and introduce a property of stability which is supported on a transferable utility game. We also propose a procedure to construct rules for obtaining stable allocations for the special case where all commodities have the same weight.     

Fuzzy Optimization Problems Based on Ordering Cones

The solution concepts of the fuzzy optimization problems using ordering cone (convex cone) are proposed in this paper. We introduce an equivalence relation to partition the set of all fuzzy numbers into the equivalence classes. We then prove that this set of equivalence classes turns into a real vector space under the settings of vector addition and scalar multiplication. The notions of ordering cone and partial ordering on a vector space are essentially equivalent. Therefore, the optimality notions in the set of equivalence classes (in fact, a real vector space) can be naturally elicited by using the similar concept of Pareto optimal solution in vector optimization problems. Given an optimization problem with fuzzy coefficients, we introduce its corresponding (usual) optimization problem. Finally, we prove that the optimal solutions of its corresponding optimization problem are the Pareto optimal solutions of the original optimization problem with fuzzy coefficients.     

Ordinal arithmetic and \Sigma_{1}-elementarity

We will introduce a partial ordering on the class of ordinals which will serve as a foundation for an approach to ordinal notations for formal systems of set theory and second-order arithmetic. In this paper we use to provide a new characterization of the ubiquitous ordinal . Received: 18 August 1997     

On the contracts between doctors and rural hospitals

We prove that the set of doctors assigned to a hospital with unfilled positions is the same in all stable allocations for a many-to-one matching model with contracts where all hospitals have q-separable preferences. However, the characteristics of the relationships among these agents may differ from one stable allocation to another.     

The Hirsch Conjecture for the fractional stable set polytope

The edge formulation of the stable set problem is defined by two-variable constraints, one for each edge of a graph \(G\) , expressing the simple condition that two adjacent nodes cannot belong to a stable set. We study the fractional stable set polytope, i.e. the polytope defined by the linear relaxation of the edge formulation. Even if this polytope is a weak approximation of the stable set polytope, its simple geometrical structure provides deep theoretical insight as well as interesting algorithmic opportunities. Exploiting a graphic characterization of the bases, we first redefine pivots in terms of simple graphic operations, that turn a given basis into an adjacent one. These results lead us to prove that the combinatorial diameter of the fractional stable set polytope is at most the number of nodes of the given graph. As a corollary, the Hirsch bound holds for this class of polytopes.     

Cournot–Walras equilibrium as a subgame perfect equilibrium

In this paper, we investigate the problem of the strategic foundation of the Cournot–Walras equilibrium approach. To this end, we respecify à la Cournot–Walras the mixed version of a model of simultaneous, noncooperative exchange, originally proposed by Lloyd S. Shapley. We show, through an example, that the set of the Cournot–Walras equilibrium allocations of this respecification does not coincide with the set of the Cournot–Nash equilibrium allocations of the mixed version of the original Shapley’s model. As the nonequivalence, in a one-stage setting, can be explained by the intrinsic two-stage nature of the Cournot–Walras equilibrium concept, we are led to consider a further reformulation of the Shapley’s model as a two-stage game, where the atoms move in the first stage and the atomless sector moves in the second stage. Our main result shows that the set of the Cournot–Walras equilibrium allocations coincides with a specific set of subgame perfect equilibrium allocations of this two-stage game, which we call the set of the Pseudo–Markov perfect equilibrium allocations. We would like to thank Pierpaolo Battigalli, Marcellino Gaudenzi, and an anonymous referee for their comments and suggestions.     

Quadratic model for allocating operational budget in public and nonprofit organizations

We develop a quadratic model for allocating operational budgets in public and nonprofit organizations. The allocations for each organizational unit have lower and upper bounds. The objective function is to minimize the weighted sum of the quadratic deviations of each allocation from its bounds. The optimal allocations are mostly around the midpoint between the bounds. A simple algorithm is presented to derive the solution. The new quadratic model is compared to the familiar linear model for budget allocation, which almost always, provides extreme allocations on the bounds: for some units on the upper bound, while for others, on the lower bound. We perform sensitivity analyses, and resolve special cases of the model with closed form solution. Moreover, we show various properties of the quadratic budget allocation model and prove that its fairness index is higher than that of the linear model. The model, with its variants, was actually used for allocating budgets in various university setups; some examples are presented here.