The assignment game I: The core

The assignment game is a model for a two-sided market in which a product that comes in large, indivisible units (e.g., houses, cars, etc.) is exchanged for money, and in which each participant either supplies or demands exactly one unit. The units need not be alike, and the same unit may have different values to different participants. It is shown here that the outcomes in thecore of such a game — i.e., those that cannot be improved upon by any subset of players — are the solutions of a certain linear programming problem dual to the optimal assignment problem, and that these outcomes correspond exactly to the price-lists that competitively balance supply and demand. The geometric structure of the core is then described and interpreted in economic terms, with explicit attention given to the special case (familiar in the classic literature) in which there is no product differentiation — i.e., in which the units are interchangeable. Finally, a critique of the core solution reveals an insensitivity to some of the bargaining possibilities inherent in the situation, and indicates that further analysis would be desirable using other game-theoretic solution concepts.     

The stochastic generalised assignment problem with Bernoulli demands

This paper deals with the Stochastic Generalised Assignment problem. It presents several models for the special case when demands are independent and Bernoulli distributed. Each model designs an assignment structure before the demands are known. Two policies are considered to handle infeasibilities in particular instances of the demands vector. Model performances are compared under both policies.     

Core and competitive equilibria with indivisibilities

The paper presents a model of an exchange economy with indivisible goods and money. There are a finite number of agents, each one initially endowed with a certain amount of money and at most one indivisible good. Each agent is assumed to have no use for more than one indivisible good. It is proved that the core of the economy is nonempty. If utility functions are increasing in money, and if the initial resources in money are in some sense “sufficient” the core allocations coincide with the competitive equilibrium allocations. With restrictions on the set of feasible allocations, the same model is used to prove the existence of stable solutions in the generalized “marriage problem”. However it is shown that, even if money enters the model, these solutions cannot generally be obtained as competitive equilibria.     

The equilibria of a multiple objective game

For a multiple objective game, we introduce its cooperative, non-cooperative, hybrid and quasi-hybrid solution concepts and prove their existence. JEL #: C70, C71, C72The author is indebted to Truman Bewley, Pradeep Dubey, Zhimin Huang, Tatsuro Ichiishi, David Pearce, Herbert E. Scarf, Lloyd Shapley, Martin Shubik, Lin Zhou and the Editor and an anonymous referee ofThe International Journal of Game Theory for their valuable dicussions and suggestions. The support of the 1990–91 Anderson Prize Fellowship from the Cowles Foundation for Research in Economics at Yale University is also appreciated.     

Financial market equilibria with heterogeneous agents: CAPM and market segmentation

We consider a single-period financial market model with normally distributed returns and heterogeneous agents. Specifically, some investors are classical expected utility maximizers whereas some others follow cumulative prospect theory. Using well-known functional forms for the preferences, we analytically prove that a Security Market Line Theorem holds. This implies that capital asset pricing model is a necessary (though not sufficient) requirement in equilibria with positive prices. We prove that equilibria may not exist and we give explicit sufficient conditions for an equilibrium to exist. To circumvent the complexity arising from the interaction of heterogeneous agents, we propose a segmented-market equilibrium model where segmentation is endogenously determined.     

Set-valued cooperative games with fuzzy payoffs. The fuzzy assignment game

In this paper we study cooperative games with fuzzy payoffs. The main advantage of the approach presented is the incorporation into the analysis of the problem of ambiguity inherent in many real-world collective decision situations. We propose extensions of core concepts which maintain the fuzzy nature of allocations, and lead to a more satisfactory study of the problem within the fuzzy context. Finally, we illustrate the extended core concepts and the approach to obtain the corresponding allocations through the analysis of assignment games with uncertain profits.     

The pairwise egalitarian solution for the assignment game

In this note we consider the pairwise egalitarian solution (Sánchez-Soriano, 2003) on the domain of assignment games and study its relation with the core. Strengthening the dominant diagonal condition (Solymosi and Raghavan, 2001), we introduce k-dominant diagonal assignment games (k≥1), analyzing for which values of k the pairwise egalitarian solution fulfills the standards of fairness represented by the Lorenz domination and the kernel. We also characterize the Thompson’s fair division point (Thompson, 1981) for arbitrary assignment games.     

The core of a further m-sided assignment game

A further generalization of the Shapley-Shubik housing market is considered in which there are m types of individuals instead of two. This is different from the generalization of Quint. These games can have empty cores.     

Strong equilibria of a repeated game with randomized strategies

A version of Aumann's (1976) model of a repeated game with randomized strategies is studied. The pure strategy set of each player is assumed to be a compact metric spacnd complexities due to the information structures are explicitly handled. It is shown that one can extend Aumann's argument to this setup and still prove the Aumann Proposition on equivalence of the β-core of a one-shot game with correlated strategies and the strong equilibrium utility allocations of the associated repeated game with randomized strategies. To this extended version of the Aumann Proposition, the author's theorem for nonemptiness of the β-core with correlated strategies is applicable, so this version is non-vacuous.     

Pure-strategy Nash equilibria in an advertising game with interference

Two manufacturers produce substitutable goods for a homogeneous market. The advertising efforts of the two manufacturers determine the demand for the goods and interfere negatively with each other. The demand of each good is a piecewise linear function of the product goodwill, and the latter is a linear function of advertising efforts. In a game with two competing profit-maximizing manufacturers who have access to a set of several advertising media, the pure-strategy Nash equilibria are characterized and their existence is shown.     

Bargaining on whales: A differential game model with pareto optimal equilibria

A two-country differential game model of whaling is used for analysing a dynamic bargaining problem. At a given initial time, the two countries may either continue on a noncooperative mood of play characterized by an open-loop Nash-equilibrium, or negotiate a bargaining solution which we define as the Kalaï-Smorodinsky solution. The cooperative solution calls for a restraint in the whaling efforts which leaves a temptation to cheat for any player. The model shows how, by announcing a credible threat, namely to make whaling an ‘open-access’ fishery, a country can eliminate this temptation to cheat and transform the cooperative solution into an equilibrium.     

Generalized three-sided assignment markets: core consistency and competitive prices

A generalization of the classical three-sided assignment market is considered, where value is generated by pairs or triplets of agents belonging to different sectors, as well as by individuals. For these markets we represent the situation that arises when some agents leave the market with some payoff by means of a generalization of Owen (Ann Econ Stat 25–26:71–79, 1992) derived market. Consistency with respect to the derived market, together with singleness best and individual anti-monotonicity, axiomatically characterize the core for these generalized three-sided assignment markets. When one sector is formed by buyers and the other by two different type of sellers, we show that the core coincides with the set of competitive equilibrium payoff vectors.     

The Manne-Chao-Wilson algorithm for computing competitive equilibria: A modified version and its implementation

We present a modification of the Manne-Chao-Wilson algorithm for computing competitive equilibria and discuss some of its convergence properties. Numerical experiments involving models with up to 100 price responsive agents are provided.This research has been partially supported by the Belgian Department for Science Policy. We are indebted to Alan Manne for helpful comments; all errors and shortcomings are ours.     

Monotone and bounded interval equilibria in a coordination game with information aggregation

We analyze how private learning in a class of games with common stochastic payoffs affects the form of equilibria, and how properties such as player welfare and the extent of strategic miscoordination relate across monotone and non-monotone equilibria. Researchers typically focus on monotone equilibria. We provide conditions under which non-monotone equilibria also exist, where players attempt to coordinate to obtain the stochastic payoff whenever signals are in a bounded interval. In bounded interval equilibria (BIE), an endogenous fear of miscoordination discourages players from coordinating to obtain the stochastic payoff when their signals suggest coordination is most beneficial. In contrast to monotone equilibria, expected payoffs from successful coordination in BIE are lower than the ex-ante expected payoff from ignoring signals and always trying to coordinate to obtain the stochastic payoff. We show that BIE only exist when, absent private information, the game would be a coordination game.     

Analysis of job assignment with batch arrivals among heterogeneous servers

We revisit the problem of job assignment to multiple heterogeneous servers in parallel. The system under consideration, however, has a few unique features. Specifically, repair jobs arrive to the queueing system in batches according to a Poisson process. In addition, servers are heterogeneous and the service time distributions of the individual servers are general. The objective is to optimally assign each job within a batch arrival to minimize the long-run average number of jobs in the entire system. We focus on the class of static assignment policies where jobs are routed to servers upon arrival according to pre-determined probabilities. We solve the model analytically and derive the structural properties of the optimal static assignment. We show that when the traffic is below a certain threshold, it is better to not assign any jobs to slower servers. As traffic increases (either due to an increase in job arrival rate or batch size), more slower servers will be utilized. We give an explicit formula for computing the threshold. Finally we compare and evaluate the performance of the static assignment policy to two dynamic policies, specifically the shortest expected completion policy and the shortest queue policy.     

一类博弈排序问题的纳什均衡存在性证明

研究机器带有激活费用的博弈排序问题. 机器集由两类组成: 一类是速度为1、 激活费用为B的k_1台同型机; 另一类是速度为a(>1)、激活费用为aB的k_2台同型机, 其中k_1与k_2是任意正整数. 工件作为``局中人", 其目的是极小化自身的费用, 工件的费用是由其所在机器的负载和其所承担的激活费用组成, 其中工件承担的激活费用与工件的加工时间成正比. 针对不同的情况, 设计不同的算法, 并证明各算法得到的排序都是纳什均衡.     

An evolution model of behavior and nash equilibria in game interactions

Translated from Programmnoe Obespechenie i Modeli Sistemnogo Analiza, pp. 71–78, 1991.