Prosperity properties of TU-games

An important open problem in the theory of TU-games is to determine whether a game has a stable core (Von Neumann-Morgenstern solution (1944)). This seems to be a rather difficult combinatorial problem. There are many sufficient conditions for core-stability. Convexity is probably the best known of these properties. Other properties implying stability of the core are subconvexity and largeness of the core (two properties introduced by Sharkey (1982)) and a property that we have baptized extendability and is introduced by Kikuta and Shapley (1986). These last three properties have a feature in common: if we start with an arbitrary TU-game and increase only the value of the grand coalition, these properties arise at some moment and are kept if we go on with increasing the value of the grand coalition. We call such properties prosperity properties. In this paper we investigate the relations between several prosperity properties and their relation with core-stability. By counter examples we show that all the prosperity properties we consider are different. Received: June 1998/Revised version: December 1998     

A sufficiency condition for coalitive pareto-optimal solutions

In ak-player, nonzero-sum differential game, there exists the possibility that a group of players will form a coalition and work together. If allk players form the coalition, the criterion usually chosen is Pareto optimality whereas, if the coalition consists of only one player, a minmax or Nash equilibrium solution is sought.In this paper, games with coalitions of more than one but less thank players are considered. Coalitive Pareto optimality is chosen as the criterion. Sufficient conditions are presented for coalitive Pareto-optimal solutions, and the results are illustrated with an example.     

Coalitional unanimity versus strategy-proofness in coalition formation problems

This paper examines coalition formation problems from the viewpoint of mechanism design. We consider the case where (i) the list of feasible coalitions (those coalitions which are permitted to form) is given in advance; and (ii) each individual’s preference is a ranking over those feasible coalitions which include this individual. We are interested in requiring the mechanism to guarantee each coalition the “right” of forming that coalition at least when every member of the coalition ranks the coalition at the top. We name this property coalitional unanimity. We examine the compatibility between coalitional unanimity and incentive requirements, and prove that if the mechanism is strategy-proof and respects coalitional unanimity, then for each preference profile, there exists at most one strictly core stable partition, and the mechanism chooses such a partition whenever available. Further, the mechanism is coalition strategy-proof and respects coalitional unanimity if, and only if, the strictly core stable partition uniquely exists for every preference profile.     

Stability in coalition formation games

In the context of coalition formation games a player evaluates a partition on the basis of the set she belongs to. For this evaluation to be possible, players are supposed to have preferences over sets to which they could belong. In this paper, we suggest two extensions of preferences over individuals to preferences over sets. For the first one, derived from the most preferred member of a set, it is shown that a strict core partition always exists if the original preferences are strict and a simple algorithm for the computation of one strict core partition is derived. This algorithm turns out to be strategy proof. The second extension, based on the least preferred member of a set, produces solutions very similar to those for the stable roommates problem. Received August 1998/Final version June 20, 2000     

The consistent Shapley value for hyperplane games

A new value is defined for n-person hyperplane games, i.e., non-sidepayment cooperative games, such that for each coalition, the Pareto optimal set is linear. This is a generalization of the Shapley value for side-payment games. It is shown that this value is consistent in the sense that the payoff in a given game is related to payoffs in reduced games (obtained by excluding some players) in such a way that corrections demanded by coalitions of a fixed size are cancelled out. Moreover, this is the only consistent value which satisfies Pareto optimality (for the grand coalition), symmetry and covariancy with respect to utility changes of scales. It can be reached by players who start from an arbitrary Pareto optimal payoff vector and make successive adjustments.     

Noncooperative formation of coalitions in hedonic games

We study a bargaining procedure of coalition formation in the class of hedonic games, where players’ preferences depend solely on the coalition they belong to. We provide an example of nonexistence of a pure strategy stationary perfect equilibrium, and a necessary and sufficient condition for existence. We show that when the game is totally stable (the game and all its restrictions have a nonempty core), there always exists a no-delay equilibrium generating core outcomes. Other equilibria exhibiting delay or resulting in unstable outcomes can also exist. If the core of the hedonic game and its restrictions always consist of a single point, we show that the bargaining game admits a unique stationary perfect equilibrium, resulting in the immediate formation of the core coalition structure.     

Characterization of the core in full domain marriage problems

In this paper, we study the core of two-sided, one-to-one matching problems. First, in a model in which agents have strict preferences over their potential mates and are allowed to remain single, we characterize the core as the unique solution that satisfies individual rationality, Pareto optimality, gender fairness, consistency, and converse consistency. Next, in a model that relaxes the constraint that agents have strict preferences over their potential mates, we show that no solution exists that satisfies Pareto optimality, anonymity, and converse consistency. In this full domain, we characterize the core by individual rationality, weak Pareto optimality, monotonicity, gender fairness, consistency, and converse consistency.     

Cores and large cores when population varies

In a TU cooperative game with populationN, a monotonic core allocation allocates each surplusv (S) among the agents of coalitionS in such a way that agenti's share never decreases when the coalition to which he belongs expands.We investigate the property of largeness (Sharkey [1982]) for monotonic cores. We show the following result. Given a convex TU game and an upper bound on each agent' share in each coalition containing him, if the upper bound depends only upon the size of the coalition and varies monotonically as the size increases, then there exists a monotonic core allocation meeting this system of upper bounds. We apply this result to the provision of a public good problem.     

Shapley mappings and the cumulative value for n-person games with fuzzy coalitions

In this paper we prove existence and uniqueness of the so-called Shapley mapping, which is a solution concept for a class of n-person games with fuzzy coalitions whose elements are defined by the specific structure of their characteristic functions. The Shapley mapping, when it exists, associates to each fuzzy coalition in the game an allocation of the coalitional worth satisfying the efficiency, the symmetry, and the null-player conditions. It determines a “cumulative value” that is the “sum” of all coalitional allocations for whose computation we provide an explicit formula.     

A Note on the Private Core and Coalitional Fairness under Asymmetric Information

We study relations among Walrasian expectations allocations, coalitional fair allocations and the private core of economies with uncertainty and asymmetric information. Our analysis covers finite exchange models, as well as models of mixed markets consisting of some large traders and an ocean of small traders. The adopted notion of coalitional fairness requires that: 1. Under a “c-fair” allocation, no coalition could benefit from achieving the net trade of some other disjoint coalition; 2. Coalition bargaining takes place without information sharing among agents. We introduce a notion of restricted Walrasian expectations allocation and examine its relations with c-fairness.     

On the core of cost-revenue games: Minimum cost spanning tree games with revenues

In this paper, we analyze cost sharing problems arising from a general service by explicitly taking into account the generated revenues. To this cost-revenue sharing problem, we associate a cooperative game with transferable utility, called cost-revenue game. By considering cooperation among the agents using the general service, the value of a coalition is defined as the maximum net revenues that the coalition may obtain by means of cooperation. As a result, a coalition may profit from not allowing all its members to get the service that generates the revenues. We focus on the study of the core of cost-revenue games. Under the assumption that cooperation among the members of the grand coalition grants the use of the service under consideration to all its members, it is shown that a cost-revenue game has a nonempty core for any vector of revenues if, and only if, the dual game of the cost game has a large core. Using this result, we investigate minimum cost spanning tree games with revenues. We show that if every connection cost can take only two values (low or high cost), then, the corresponding minimum cost spanning tree game with revenues has a nonempty core. Furthermore, we provide an example of a minimum cost spanning tree game with revenues with an empty core where every connection cost can take only one of three values (low, medium, or high cost).     

Nash equilibrium based fairness

There are several approaches of sharing resources among users. There is a noncooperative approach wherein each user strives to maximize its own utility. The most common optimality notion is then the Nash equilibrium. Nash equilibria are generally Pareto inefficient. On the other hand, we consider a Nash equilibrium to be fair as it is defined in a context of fair competition without coalitions (such as cartels and syndicates). We show a general framework of systems wherein there exists a Pareto optimal allocation that is Pareto superior to an inefficient Nash equilibrium. We consider this Pareto optimum to be ??Nash equilibrium based fair.?? We further define a ??Nash proportionately fair?? Pareto optimum. We then provide conditions for the existence of a Pareto-optimal allocation that is, truly or most closely, proportional to a Nash equilibrium. As examples that fit in the above framework, we consider noncooperative flow-control problems in communication networks, for which we show the conditions on the existence of Nash-proportionately fair Pareto optimal allocations.     

On the core of multiple longest traveling salesman games

In this paper we introduce multiple longest traveling salesman (MLTS) games. An MLTS game arises from a network in which a salesman has to visit each node (player) precisely once, except to his home location, in such an order that maximizes the total reward. First it is shown that the value of a coalition of an MLTS game is determined by taking the maximum of suitable combinations of one and two person coalitions. Secondly it is shown that MLTS games with five or less players have a nonempty core. However, a six player MLTS game may have an empty core. For the special instance in which the reward between a pair of nodes is equal to 0 or 1, we provide relations between the structure of the core and the underlying network.     

Stochastic Optimization over a Pareto Set Associated with a Stochastic Multi-Objective Optimization Problem

We deal with the problem of minimizing the expectation of a real valued random function over the weakly Pareto or Pareto set associated with a Stochastic Multi-objective Optimization Problem, whose objectives are expectations of random functions. Assuming that the closed form of these expectations is difficult to obtain, we apply the Sample Average Approximation method in order to approach this problem. We prove that the Hausdorff–Pompeiu distance between the weakly Pareto sets associated with the Sample Average Approximation problem and the true weakly Pareto set converges to zero almost surely as the sample size goes to infinity, assuming that our Stochastic Multi-objective Optimization Problem is strictly convex. Then we show that every cluster point of any sequence of optimal solutions of the Sample Average Approximation problems is almost surely a true optimal solution. To handle also the non-convex case, we assume that the real objective to be minimized over the Pareto set depends on the expectations of the objectives of the Stochastic Optimization Problem, i.e. we optimize over the image space of the Stochastic Optimization Problem. Then, without any convexity hypothesis, we obtain the same type of results for the Pareto sets in the image spaces. Thus we show that the sequence of optimal values of the Sample Average Approximation problems converges almost surely to the true optimal value as the sample size goes to infinity.     

The core of an economy with multilateral environmental externalities

When environmental externalities are international — i.e. transfrontier — they most often are multilateral and embody public good characteristics. Improving upon inefficient laissez-faire equilibria requires voluntary cooperation for which the game-theoretic core concept provides optimal outcomes that have interesting properties against free riding. To define the core, however, the characteristic function of the game associated with the economy (which specifies the payoff achievable by each possible coalition of players—here, the countries) must also reflect in each case the behavior of the players which are not members of the coalition. This has been for a long time a disputed issue in the theory of the core of economies with externalities. Among the several assumptions that can be made as to this behaviour, a plausible one is defined in this paper, for which it is shown that the core of the game is nonempty. The proof is constructive in the sense that it exhibits a strategy (specifying an explicit coordinated abatement policy and including financial transfers) that has the desired property of nondomination by any proper coalition of countries, given the assumed behavior of the other countries. This strategy is also shown to have an equilibrium interpretation in the economic model.     

Hedonic coalition formation games: A new stability notion

This paper studies hedonic coalition formation games where each player’s preferences rely only upon the members of her coalition. A new stability notion under free exit-free entry membership rights, referred to as strong Nash stability, is introduced which is stronger than both core and Nash stabilities studied earlier in the literature. Strong Nash stability has an analogue in non-cooperative games and it is the strongest stability notion appropriate to the context of hedonic coalition formation games. The weak top-choice property is introduced and shown to be sufficient for the existence of a strongly Nash stable partition. It is also shown that descending separable preferences guarantee the existence of a strongly Nash stable partition. Strong Nash stability under different membership rights is also studied.     

基于Choquet积分形式的模糊联盟核心

在具有联盟结构的合作对策中,针对局中人以某种程度参与到合作中的情况,研究了模糊联盟结构的合作对策的收益分配问题。首先,定义了具有模糊联盟结构的合作对策及相关概念。其次,定义了Choquet积分形式的模糊联盟核心,提出了该核心与联盟核心之间的关系,对于强凸联盟对策,证明Choquet积分形式的模糊Owen值属于其所对应的模糊联盟核心。最后通过算例,对该分配模型的可行性进行分析。     

基于群体共识的农村土地流转优化决策方法

农村土地流转涉及到政府部门的心理预期和承包企业的利益参照点。如果两者不能达成共识,很难达到农村土地流转帕累托改善。本文主要研究这两方流转主体在群体演化博弈中累积的共识达成过程,及其对现有土地效率的优化机制作用规律。在考虑双方异质性累积前景预期值的基础上,利用模拟仿真研究政府和企业之间的博弈演化过程,发现在双方心理预期均获得满足的条件下,群体能够达成共识,农村土地流转效率最高。     

Welfare and stability in senior matching markets

We consider matching markets at a senior level, where workers are assigned to firms at an unstable matching—the status-quo—which might not be Pareto efficient. It might also be that none of the matchings Pareto superior to the status-quo are Core stable. We propose two weakenings of Core stability: status-quo stability and weakened stability, and the respective mechanisms which lead any status-quo to matchings meeting the stability requirements above mentioned. The first one is inspired by the Top trading cycle and Deferred Acceptance procedures, the other one belongs to the family of Branch and Bound algorithms. The last procedure finds a core stable matching in many-to-one markets whenever it exists, dispensing with the assumption of substitutability.     

Stable profit sharing in a patent licensing game: general bargaining outcomes

By considering coalition structures formed by an external licensor of a patented technology and oligopolistic firms, we investigate licensing agreements that can be reached as bargaining outcomes under those coalition structures. The following results hold in a generalized patent licensing game. The core for a coalition structure is always empty, unless the grand coalition forms. We give a necessary and sufficient condition for the nonemptiness of the core (for the grand coalition). If the number of licensees that maximizes licensees’ total surplus is greater than the number of existing non-licensees, each symmetric bargaining set for a coalition structure is a singleton, and the optimal number of licensees that maximizes the licensor’s revenue is uniquely determined. The authors wish to thank the chief editor, anonymous referees, and participants in the 10th DC (Japan), the 3rd ICMA, and the 17th Stony Brook conference for helpful comments and suggestions. Thanks are extended to Ryo Kawasaki for editing English. They are partially supported by the MEXT Grant-in-Aid for 21 Century COE Program, Grant-in-Aid 18730517 (Watanabe), and Grant-in-Aid 16310107 (Muto).