On the core of linear production games

An economic production game is treated, in which players pool resources to produce finished goods which can be sold at a given market price. The production process is linear, so that the characteristic function can be obtained by solving linear programs. Duality theory of linear programming is used to obtain equilibrium price vectors and to prove the non-emptiness of the core. Under replication, it is shown that, in the non-degenerate case, the core converges finitely to the set of competitive equilibria; a counter-example shows that this is not true in the degenerate case (i.e., only convergence in the limit can be guaranteed).     

Stable multi-skill workforce assignments

This paper analyzes stability in multi-skill workforce assignments of technicians and jobs. In our stability analysis, we extend the notion of blocking pairs as stated in the Marriage model of Gale-Shapley to the multi-skill workforce assignment. It is shown that finding stable assignments is NP-hard. A special case turns out to be solvable in polynomial time. For the general case, we give a characterization of the set of stable assignments by means of linear inequalities involving binary variables. We propose an integer programming (IP) model to construct optimal stable assignments with several objectives. In the computational results, we observe that it is easier to attain stability in instances with easy jobs and we consider a range of instances to show how fast the solution time increases. Open questions and further directions are discussed in the conclusion section.     

Network capacity management under competition

We consider capacity management games between airlines who transport passengers over a joint airline network. Passengers are likely to purchase alternative tickets of the same class from competing airlines if they do not get tickets from their preferred airlines. We propose a Nash and a generalized Nash game model to address the competitive network revenue management problem. These two models are based on well-known deterministic linear programming and probabilistic nonlinear programming approximations for the non-competitive network capacity management problem. We prove the existence of a Nash equilibrium for both games and investigate the uniqueness of a Nash equilibrium for the Nash game. We provide some further uniqueness and comparative statics analysis when the network is reduced to a single-leg flight structure with two products. The comparative statics analysis reveals some useful insights on how Nash equilibrium booking limits change monotonically in the prices of products. Our numerical results indicate that airlines can generate higher and more stable revenues from a booking scheme that is based on the combination of the partitioned booking-limit policy and the generalized Nash game model. The results also show that this booking scheme is robust irrespective of which booking scheme the competitor takes.     

考虑决策单元竞争合作动态变化的DEA博弈交叉效率方法

利用DEA方法进行相对效率评估时,决策单元通常需要考虑多重目标,且随着目标的变化,决策单元间竞争合作状态也会发生动态变化。传统竞合模型虽然考虑了决策单元间竞争与合作同时存在的现象,但忽视了竞争合作关系动态变化的过程。本文以竞争合作对策为切入点,将多目标规划中的优先因子引入传统DEA博弈交叉效率模型中,提出了带有优先等级的多目标DEA博弈交叉效率模型,即动态竞合博弈交叉效率模型。该模型充分体现了不同目标下决策单元间竞争合作关系的动态变化,其焦点由传统竞合模型对多重最优权重现象的改善,转向对最优效率得分的直接寻找。利用DEA动态竞合博弈交叉效率模型,本文对环境污染约束下2014年长三角地区制造业投入产出绩效进行了客观的评估。分析结果表明:DEA动态竞合博弈交叉效率模型收敛速度优于传统DEA博弈交叉效率模型,其交叉效率得分收敛于唯一的纳什均衡点;不同目标重要性的差异程度,对最终排名结果不产生明显影响,不需要确切指出。     

A new reformulation-linearization technique for bilinear programming problems

This paper is concerned with the development of an algorithm for general bilinear programming problems. Such problems find numerous applications in economics and game theory, location theory, nonlinear multi-commodity network flows, dynamic assignment and production, and various risk management problems. The proposed approach develops a new Reformulation-Linearization Technique (RLT) for this problem, and imbeds it within a provably convergent branch-and-bound algorithm. The method first reformulates the problem by constructing a set of nonnegative variable factors using the problem constraints, and suitably multiplies combinations of these factors with the original problem constraints to generate additional valid nonlinear constraints. The resulting nonlinear program is subsequently linearized by defining a new set of variables, one for each nonlinear term. This RLT process yields a linear programming problem whose optimal value provides a tight lower bound on the optimal value to the bilinear programming problem. Various implementation schemes and constraint generation procedures are investigated for the purpose of further tightening the resulting linearization. The lower bound thus produced theoretically dominates, and practically is far tighter, than that obtained by using convex envelopes over hyper-rectangles. In fact, for some special cases, this process is shown to yield an exact linear programming representation. For the associated branch-and-bound algorithm, various admissible branching schemes are discussed, including one in which branching is performed by partitioning the intervals for only one set of variables x or y, whichever are fewer in number. Computational experience is provided to demonstrate the viability of the algorithm. For a large number of test problems from the literature, the initial bounding linear program itself solves the underlying bilinear programming problem.This paper was presented at the II. IIASA Workshop on Global Optimization, Sopron (Hungary), December 9–14, 1990.     

Nondominated Nash points: application of biobjective mixed integer programming

We study the connection between biobjective mixed integer linear programming and normal form games with two players. We first investigate computing Nash equilibria of normal form games with two players using single-objective mixed integer linear programming. Then, we define the concept of efficient (Pareto optimal) Nash equilibria. This concept is precisely equivalent to the concept of efficient solutions in multi-objective optimization, where the solutions are Nash equilibria. We prove that the set of all points in the payoff (or objective) space of a normal form game with two players corresponding to the utilities of players in an efficient Nash equilibrium, the so-called nondominated Nash points, is finite. We demonstrate that biobjective mixed integer linear programming, where the utility of each player is an objective function, can be used to compute the set of nondominated Nash points. Finally, we illustrate how the nondominated Nash points can be used to determine the disagreement point of a bargaining problem.     

Price subsidies and guaranteed buys of a new technology

We consider a problem of a government that wishes to stimulate the adoption of a new technology in order to replace an older, environmentally less desirable, technology. The new technology is manufactured by a monopolist firm which has learning-by-doing in its production process. The firm sells the new product to both private households and government institutions and wishes to determine an optimal pricing policy. The government has at its disposal two instruments: subsidizing the consumer price and making purchases of the new technology from the firm. We assume profit maximization on the part of the firm. The government wishes to maximize the cumulative number of units of the new technology sold to private households by the terminal date of the government program. The problem is set up as a Stackelberg differential game in which we identify an open-loop equilibrium, supposing that the government can credibly precommit to its subsidy and buying program.     

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.     

不同博弈框架下多竞争零售商的双渠道供应链定价决策研究

在Bertrand竞争、Stackelberg竞争及集中决策下,研究由单制造商与多竞争零售商组成的双渠道供应链的定价决策问题。运用两阶段优化技术、博弈论及矩阵论,讨论了多竞争零售商与单制造商在价格方面相互竞争的问题,给出不同市场竞争模式及集中决策下供应链成员的博弈均衡解。对比不同博弈框架及集中决策下供应链成员的定价决策,通过数值实验分析了价格敏感度及零售商个数对最优定价决策和最大利润影响,给出一些管理学理论与见解,为双渠道供应链中各成员的管理者制定最优决策提供理论支持。     

Finding Robust Global Optimal Values of Bilevel Polynomial Programs with Uncertain Linear Constraints

This paper studies a bilevel polynomial program involving box data uncertainties in both its linear constraint set and its lower-level optimization problem. We show that the robust global optimal value of the uncertain bilevel polynomial program is the limit of a sequence of values of Lasserre-type hierarchy of semidefinite linear programming relaxations. This is done by first transforming the uncertain bilevel polynomial program into a single-level non-convex polynomial program using a dual characterization of the solution of the lower-level program and then employing the powerful Putinar’s Positivstellensatz of semi-algebraic geometry. We provide a numerical example to show how the robust global optimal value of the uncertain bilevel polynomial program can be calculated by solving a semidefinite programming problem using the MATLAB toolbox YALMIP.     

The inverse optimal value problem

This paper considers the following inverse optimization problem: given a linear program, a desired optimal objective value, and a set of feasible cost vectors, determine a cost vector such that the corresponding optimal objective value of the linear program is closest to the desired value. The above problem, referred here as the inverse optimal value problem, is significantly different from standard inverse optimization problems that involve determining a cost vector for a linear program such that a pre-specified solution vector is optimal. In this paper, we show that the inverse optimal value problem is NP-hard in general. We identify conditions under which the problem reduces to a concave maximization or a concave minimization problem. We provide sufficient conditions under which the associated concave minimization problem and, correspondingly, the inverse optimal value problem is polynomially solvable. For the case when the set of feasible cost vectors is polyhedral, we describe an algorithm for the inverse optimal value problem based on solving linear and bilinear programming problems. Some preliminary computational experience is reported.Mathematics Subject Classification (1999):49N45, 90C05, 90C25, 90C26, 90C31, 90C60Acknowledgement This research has been supported in part by the National Science Foundation under CAREER Award DMII-0133943. The authors thank two anonymous reviewers for valuable comments.     

An extended assignment problem considering multiple inputs and outputs

The existing assignment problems for assigning n jobs to n individuals are limited to the considerations of cost or profit incurred by each possible assignment. However, in real applications, various inputs and outputs are usually concerned in an assignment problem, such as a general decision-making problem. This paper develops a procedure for resolving assignment problems with multiple incommensurate inputs and outputs for each possible assignment. The concept of the relative efficiency in using various resources, instead of cost or profit, is adopted for each possible assignment of the problem. Data envelopment analysis (DEA) is employed in this paper to measure the efficiency of one assignment relative to that of the others according to a set of decision-making units. A composite efficiency index, consisting of two kinds of relative efficiencies under different comparison bases, is defined to serve as the performance measurement of each possible assignment in the problem formulation. A mathematical programming model for the extended assignment problem is proposed, which is then expressed as a classical integer linear programming model to determine the assignments with the maximum efficiency. A numerical example is used to demonstrate the approach.     

Continuity and Uniqueness of Equilibria for Linear Exchange Economies

The purpose of this paper is to study the continuity and uniqueness properties of equilibria for linear exchange economies. We characterize the sets of utility vectors and initial endowments for which the equilibrium price is unique and respectively the set for which the equilibrium allocation is unique. We show that the equilibrium allocation correspondence is continuous with respect to the initial endowments and we characterize the set of full measure where the equilibrium allocation correspondence with respect to the initial endowments and utility vectors is continuous.     

Hybrid subgames and copycat games in a pulsing model of advertising competition

Two recent papers,^6,7 introduced the game of pulsing competition (PC) in advertising together with its related subgames of alternating pulsing competition (APC) and matching pulsing competition (MPC) for a duopoly. Following a game theoretic approach in conjunction with a continuous Lanchester model, the above authors basically concluded that when at least one of the response functions is convex, generalising monopolistic advertising pulsation results to a competitive setting might not be adequate. This paper expands the scope of the PC game by incorporating in its structure for the first time in the literature, two versions of a hybrid pulsing competition (HPC) subgame. The article compares the payoffs of the four alternative subgames and provides an analytical solution of a special case of the PC game. In addition, the article also introduces for the first time a variant of the PC game designated by ‘the copycat advertising game’ and shows analytically that for such a game the policy of constant advertising spending over time is optimal for both firms irrespective of the shape of their advertising response functions. The paper illustrates at its end how to solve numerically the expanded PC game in its general form using linear programming and how to derive a solution for a copycat advertising game.     

A note on oligopoly exploitation of common-pool renewable resources

This note derives the linear Feedback Nash equilibrium of a differential oligopoly game of exploitation of a common-pool renewable resource, and compares and contrasts it with social optimum. The case of regulated entry by means of a license fee is also considered. Two main results are derived. First, the steady-state oligopoly price can be increasing in the (exogenously given) number of firms. Second, an optimal license fee exists that induces the (endogenously given) number of firms to behave efficiently.     

Equilibrium structures of two supply chains with price and displayed-quantity competition

This paper studies the equilibrium structure of two competing supply chains, each of which consists of one manufacturer and one retailer who faces the demand influenced by price and displayed quantity. Each chain has two structure options: integration or decentralization. Under linear demand, we present the optimal pricing/displayed quantity of all members in the two chains under possible structures: two integrated chains (II), two decentralized chains (DD), and one integrated chain and one decentralized chain (ID or DI). We then analyse the impact of the intensities of price and displayed-quantity competition on the equilibrium structure of two supply chains. The results show that both price and displayed-quantity competition intensities influence significantly the equilibrium structure. Moreover, under certain specific conditions, both price and displayed-quantity competition can have the two chains fall into the prisoner’s dilemma and play a game of chicken as well.     

On the manipulability of competitive equilibrium rules in many-to-many buyer–seller markets

We analyze the manipulability of competitive equilibrium allocation rules for the simplest many-to-many extension of Shapley and Shubik’s (Int J Game Theory 1:111–130, 1972) assignment game. First, we show that if an agent has a quota of one, then she does not have an incentive to manipulate any competitive equilibrium rule that gives her her most preferred competitive equilibrium payoff when she reports truthfully. In particular, this result extends to the one-to-many (respectively, many-to-one) models the Non-Manipulability Theorem of the buyers (respectively, sellers), proven by Demange (Strategyproofness in the assignment market game. École Polytechnique, Laboratoire d’Économetrie, Paris, 1982), Leonard (J Polit Econ 91:461–479, 1983), and Demange and Gale (Econometrica 55:873–888, 1985) for the assignment game. Second, we prove a “General Manipulability Theorem” that implies and generalizes two “folk theorems” for the assignment game, the Manipulability Theorem and the General Impossibility Theorem, never proven before. For the one-to-one case, this result provides a sort of converse of the Non-Manipulability Theorem.     

A two-person non-zero-sum game model of the world oil market

The world oil market is modelled as a two-person non-zero-sum game in normal form with each player having a continuum of strategies. The two players are the oil importing nations (OPIC) and the oil exporting nations (OPEC). The game is solved in the noncooperative sense using the equilibrium point solution concept due to Nash. The Nash equilibrium point solution yields an analytic expression for the optimal price per barrel of oil for OPEC and the optimal level of imports of oil for OPIC assuming noncooperation between the players. The cooperative solution to the game is also investigated using the von Neumann-Morgenstern negotiation set solution and Nash's bargaining point solution. Again, we give analytic expressions for the optimal price of a barrel of oil and the optimal level of imports of oil assuming that the players cooperate (negotiate, bargain, etc., for a binding agreement) in arriving at a solution.     

Eigenvalue Multiplicity Estimate in Semidefinite Programming

A semidefinite programming problem is a mathematical program in which the objective function is linear in the unknowns and the constraint set is defined by a linear matrix inequality. This problem is nonlinear, nondifferentiable, but convex. It covers several standard problems (such as linear and quadratic programming) and has many applications in engineering. Typically, the optimal eigenvalue multiplicity associated with a linear matrix inequality is larger than one. Algorithms based on prior knowledge of the optimal eigenvalue multiplicity for solving the underlying problem have been shown to be efficient. In this paper, we propose a scheme to estimate the optimal eigenvalue multiplicity from points close to the solution. With some mild assumptions, it is shown that there exists an open neighborhood around the minimizer so that our scheme applied to any point in the neighborhood will always give the correct optimal eigenvalue multiplicity. We then show how to incorporate this result into a generalization of an existing local method for solving the semidefinite programming problem. Finally, a numerical example is included to illustrate the results.