CD生产函数与CES生产函数的几点比较

本文对ＣＤ生产函数与ＣＥＳ生产函数进行了几个方面的比较分析，以便于实际运用中的选择。     

On the Lovász theta function and some variants

The Lovász theta function of a graph is a well-known upper bound on the stability number. It can be computed efficiently by solving a semidefinite program (SDP). Actually, one can solve either of two SDPs, one due to Lovász and the other to Grötschel et al. The former SDP is often thought to be preferable computationally, since it has fewer variables and constraints. We derive some new results on these two equivalent SDPs. The surprising result is that, if we weaken the SDPs by aggregating constraints, or strengthen them by adding cutting planes, the equivalence breaks down. In particular, the Grötschel et al. scheme typically yields a stronger bound than the Lovász one.     

On Extracting Maximum Stable Sets in Perfect Graphs Using Lovász's Theta Function

We study the maximum stable set problem. For a given graph, we establish several transformations among feasible solutions of different formulations of Lovász's theta function. We propose reductions from feasible solutions corresponding to a graph to those corresponding to its induced subgraphs. We develop an efficient, polynomial-time algorithm to extract a maximum stable set in a perfect graph using the theta function. Our algorithm iteratively transforms an approximate solution of the semidefinite formulation of the theta function into an approximate solution of another formulation, which is then used to identify a vertex that belongs to a maximum stable set. The subgraph induced by that vertex and its neighbors is removed and the same procedure is repeated on successively smaller graphs. We establish that solving the theta problem up to an adaptively chosen, fairly rough accuracy suffices in order for the algorithm to work properly. Furthermore, our algorithm successfully employs a warm-start strategy to recompute the theta function on smaller subgraphs. Computational results demonstrate that our algorithm can efficiently extract maximum stable sets in comparable time it takes to solve the theta problem on the original graph to optimality. This work was supported in part by NSF through CAREER Grant DMI-0237415. Part of this work was performed while the first author was at the Department of Applied Mathematics and Statisticsat Stony Brook University, Stony Brook, NY, USA.     

Matrix approach to dual similar associated consistency for the Shapley value

In terms of the similarity of matrices, by combining the dual operator and the linear mapping with respect to Hamiache’s associated game on the game space, the Shapley value for TU-games is axiomatized as the unique value verifying dual similar associated consistency, continuity, and the inessential game property.     

含有时滞的CES生产函数的资产投资模型解的稳定性

研究含有非局部和时滞边界条件的投资控制模型在解的存在唯一性基础上,讨论了模型解的稳定性,得到解的渐进稳定性.     

On the neutral stability of mixed strategies in asymmetric contests

Although a mixed strategy can never be evolutionary stable in a truly asymmetric contest, examples show that mixed strategies can satisfy the weaker criterion of neutral stability. This paper shows that such examples are rare, and, generically, a mixed strategy is unstable. We apply our result to the battle of the sexes between males and females over the raising of offspring.     

Characterizations ofk-Convex Games

The paper deals with the class of k-convex n-person transferable utility games which has clear affinities to the well-known class of convex n-person TU-games. Five new characterizations of a k-convex n-person game are presented in terms of the following key notions:(1) the unanimity coordinates, as determined by the algebraic representation of the game with respect to the particular basis consisting of all n-person unanimity games; (2) the second order partial derivatives of Owen's multilinear extension of the game; (3) the coremembership of the adjusted marginal worth vectors of the game (taking into account even or odd orderings of players); (4) a min-modular decomposition of an appropriately chosen cover-game (the decomposition of which is based on the adjusted marginal worth vectors of the initial game); (5) the concavity of the Lovász extension of the associated cover-game     

Evolutionary dynamics of the spatial Prisoner’s Dilemma with self-inhibition

In this paper we study the influence of interventions on self-interactions in a spatial Prisoner’s Dilemma on a two-dimensional grid with periodic boundary conditions and synchronous updating of the dynamics. We investigate two different types of self-interaction modifications. The first type (FSIP) is deterministic, effecting each self-interaction of a player by a constant factor, whereas the second type (PSIP) performs a probabilistic interventions. Both types of interventions lead to a reduction of the payoff of the players and, hence, represent inhibiting effects. We find that a constant but moderate reduction of self-interactions has a very beneficial effect on the evolution of cooperators in the population, whereas probabilistic interventions on self-interactions are in general counter productive for the coexistence of the two different strategies.     

Combinatorial Groupoids,Cubical Complexes,and the Lovász Conjecture

This paper lays the foundation for a theory of combinatorial groupoids that allows us to use concepts like “holonomy”, “parallel transport”, “bundles”, “combinatorial curvature”, etc. in the context of simplicial (polyhedral) complexes, posets, graphs, polytopes and other combinatorial objects. We introduce a new, holonomy-type invariant for cubical complexes, leading to a combinatorial “Theorema Egregium” for cubical complexes that are non-embeddable into cubical lattices. Parallel transport of Hom-complexes and maps is used as a tool to extend Babson–Kozlov–Lovász graph coloring results to more general statements about nondegenerate maps (colorings) of simplicial complexes and graphs. The author was supported by grants 144014 and 144026 of the Serbian Ministry of Science and Technology.     

Semidefinite programming relaxations for graph coloring and maximal clique problems

The semidefinite programming formulation of the Lovász theta number does not only give one of the best polynomial simultaneous bounds on the chromatic number χ(G) or the clique number ω(G) of a graph, but also leads to heuristics for graph coloring and extracting large cliques. This semidefinite programming formulation can be tightened toward either χ(G) or ω(G) by adding several types of cutting planes. We explore several such strengthenings, and show that some of them can be computed with the same effort as the theta number. We also investigate computational simplifications for graphs with rich automorphism groups. Partial support by the EU project Algorithmic Discrete Optimization (ADONET), MRTN-CT-2003-504438, is gratefully acknowledged.     

An application of the Lovász–Schrijver <Emphasis Type="Italic">M</Emphasis>(<Emphasis Type="Italic">K</Emphasis>, <Emphasis Type="Italic">K</Emphasis>) operator to the stable set problem

Although the lift-and-project operators of Lovász and Schrijver have been the subject of intense study, their M(K, K) operator has received little attention. We consider an application of this operator to the stable set problem. We begin with an initial linear programming (LP) relaxation consisting of clique and non-negativity inequalities, and then apply the operator to obtain a stronger extended LP relaxation. We discuss theoretical properties of the resulting relaxation, describe the issues that must be overcome to obtain an effective practical implementation, and give extensive computational results. Remarkably, the upper bounds obtained are sometimes stronger than those obtained with semidefinite programming techniques.      

On a dynamic fractional game

Consider a two-person zero-sum game constructed by a dynamic fractional form. We establish the upper value as well as the lower value of a dynamic fractional game, and prove that the dual gap is equal to zero under certain conditions. It is also established that the saddle point function exists in the fractional game system under certain conditions so that the equilibrium point exists in this game system.     

Dynamics of a single species evolutionary model with Allee effects

We investigate the evolutionary outcomes of a single species population subject to Allee effects within the framework of a continuous strategy evolutionary game theory (EGT) model. Our model assumes a single trait creates a phenotypic trade-off between carrying capacity (i.e., competition) and predator evasion ability following a Gaussian distribution. This assumption contributes to one of our interesting findings that evolution prevents extinction even when population exhibits strong Allee effects. However, the extinction equilibrium can be an ESS under some special distributions of anti-predation phenotypes. The ratio of variation in competition and anti-predation phenotypes plays an important role in determining global dynamics of our EGT model: (a) evolution may suppress strong Allee effects for large values of this ratio; (b) evolution may preserve strong Allee effects for small values of this ratio by generating a low density evolutionary stable strategy (ESS) equilibrium which can serve as a potential Allee threshold; and (c) intermediate values of this ratio can result in multiple ESS equilibria.     

Copositive programming motivated bounds on the stability and the chromatic numbers

The Lovász theta number of a graph G can be viewed as a semidefinite programming relaxation of the stability number of G. It has recently been shown that a copositive strengthening of this semidefinite program in fact equals the stability number of G. We introduce a related strengthening of the Lovász theta number toward the chromatic number of G, which is shown to be equal to the fractional chromatic number of G. Solving copositive programs is NP-hard. This motivates the study of tractable approximations of the copositive cone. We investigate the Parrilo hierarchy to approximate this cone and provide computational simplifications for the approximation of the chromatic number of vertex transitive graphs. We provide some computational results indicating that the Lovász theta number can be strengthened significantly toward the fractional chromatic number of G on some Hamming graphs. Partial support by the EU project Algorithmic Discrete Optimization (ADONET), MRTN-CT-2003-504438, is gratefully acknowledged.     

The Shapley value for arbitrary families of coalitions

We address the problem of finding a suitable definition of a value similar to that of Shapley’s, when the games are defined on a subfamily of coalitions with no structure. We present two frameworks: one based on the familiar efficiency, linearity and null player axioms, and the other on linearity and the behavior on unanimity games. We give several properties and examples in each case, and give necessary and sufficient conditions on the family of coalitions for the approaches to coincide.     

An algorithm of evolutionarily stable strategies for the single-population evolutionary game

In this paper, we study the single-population evolutionary game and construct an algorithm to find evolutionarily stable strategies. Finally, by an example, we illuminate the computing process of algorithm.