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.     

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.     

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.     

An evolution model of behavior and nash equilibria in game interactions

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

An assignment problem for a parallel queueing system with two heterogeneous servers

In this paper, we consider an optimization problem for a parallel queueing system with two heterogeneous servers. Each server has its own queue and customers arrive at each queue according to independent Poisson processes. Each service time is independent and exponentially distributed. When a customer arrives at queue 1, the customers in queue 1 can be transferred to queue 2 by paying an assignment cost which is proportional to the number of moved customers. Holding cost is a function of the pair of queue lengths of the two servers. Our objective is to minimize the expected total discounted cost. We use the dynamic programming approach for this problem. Considering the pair of queue lengths as a state space, we show that the optimal policy has a switch over structure under some conditions on the holding cost.     

The infinite time horizon dynamic pricing problem with multi-unit demand

This paper studies a dynamic pricing problem for a monopolist selling multiple identical items to potential buyers arriving over time, where the time horizon is infinite, the goods are imperishable and the buyers’ arrival follows a renewal process. Each potential buyer has some private information about his purchasing will, and this private information is unknown to the seller and therefore characterized as a random variable in this paper. Thus, the buyers may have multi-unit demand. Meanwhile, the seller needs to determine the optimal posted price such that his expected discounted revenue is maximized. This problem is formulated as a stochastic dynamic programming in this paper and then how to obtain the solution is explored. A numerical study shows that the optimal posted price performs better than that of optimal fixed price, and this advantage becomes obvious as the interest rate and/or the number of initial items increases.     

The value of competitive information in forecasting FMCG retail product sales and the variable selection problem

Sales forecasting at the UPC level is important for retailers to manage inventory. In this paper, we propose more effective methods to forecast retail UPC sales by incorporating competitive information including prices and promotions. The impact of these competitive marketing activities on the sales of the focal product has been extensively documented. However, competitive information has been surprisingly overlooked by previous studies in forecasting UPC sales, probably because of the problem of too many competitive explanatory variables. That is, each FMCG product category typically contains a large number of UPCs and is consequently associated with a large number of competitive explanatory variables. Under such a circumstance, time series models can easily become over-fitted and thus generate poor forecasting results.