Solutions for non-negatively weighted TU games derived from extension operators

We suggest two alternatives to the Lovász-Shapley value for non-negatively weighted TU games, the dual Lovász-Shapley value and the Shapley² value. Whereas the former is based on the Lovász extension operator for TU games, the latter two are based on extension operators that share certain economically plausible properties with the Lovász extension operator, the dual Lovász extension operator and the Shapley extension operator, respectively.     

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 the asymptotic convergence to mixed equilibria in 2×2 asymmetric games

We analyse the stability properties of mixed equilibria in 2×2 asymmetric games under evolutionary dynamics. With the standard replicator dynamics these equilibria are stable but not asymptotically stable. We modified the replicator dynamics by introducing players of two types: myopies — like in the standard replicator dynamics — and best responders. The behaviour of the latter is described by a continuos time version of the best reply dynamics. Asymptotic convergence under theModified Replicator Dynamics is proved by identifying a strictly decreasing Ljapunov function. We argue that the finding has important implications to justify the use of economic models with mixed strategy 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.     

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 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.     

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     

On Minty-variational inequalities and evolutionary stable states of generalized monotone games

In this note, we emphasize the role played by Minty variational inequalities in evolutionary game theory for studying neutrally and evolutionary stable states of nonlinear population games. This connection allows deriving new results on the sets of neutrally stable and evolutionary stable states for generalized monotone games as well as stability results for the replicator dynamics.     

On the subdifferential of a submodular function

The author recently introduced a concept of a subdifferential of a submodular function defined on a distributive lattice. Each subdifferential is an unbounded polyhedron. In the present paper we determine the set of all the extreme points and rays of each subdifferential and show the relationship between subdifferentials of a submodular function and subdifferentials, in an ordinary sense of convex analysis, of Lovász's extension of the submodular function. Furthermore, for a modular function on a distributive lattice we give an algorithm for determining which subdifferential contains a given vector and finding a nonnegative linear combination of extreme vectors of the subdifferential which expresses the given vector minus the unique extreme point of the subdifferential.     

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.     

Dynamic stability in symmetric extensive form games

Dynamic stability under the replicator dynamic of evolutionary game theory is investigated for certain symmetric extensive form games whose subgame structure exhibits a high degree of decomposability. It is shown that a pervasive equilibrium strategy is locally asymptotically stable (l.a.s.) if and only if it is given by backwards induction applied to the l.a.s. pervasive equilibria of the subgames and their corresponding truncations. That is, this dynamic backwards induction procedure provides a rational basis on which to predict the evolutionary outcome of the replicator dynamic for these symmetric games.     

A note on near‐optimal coloring of shift hypergraphs

As shown in the original work on the Lovász Local Lemma due to Erd?s & Lovász (Infinite and Finite Sets, 1975), a basic application of the Local Lemma answers an infinitary coloring question of Strauss, showing that given any integer set S, the integers may be k‐colored so that S and all its translates meet every color. The quantitative bounds here were improved by Alon, Kriz & Nesetril (Studia Scientiarum Mathematicarum Hungarica, 1995). We obtain an asymptotically optimal bound in this note, using the technique of iteratively applying the Lovász Local Lemma in order to prune dependencies. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 53–56, 2016     

Forbidden subgraphs and the König–Egerváry property

The matching number of a graph is the maximum size of a set of vertex-disjoint edges. The transversal number is the minimum number of vertices needed to meet every edge. A graph has the König–Egerváry property  if its matching number equals its transversal number. Lovász proved a characterization of graphs having the König–Egerváry property by means of forbidden subgraphs within graphs with a perfect matching. Korach, Nguyen, and Peis proposed an extension of Lovász’s result to a characterization of all graphs having the König–Egerváry property in terms of forbidden configurations (which are certain arrangements of a subgraph and a maximum matching). In this work, we prove a characterization of graphs having the König–Egerváry property by means of forbidden subgraphs which is a strengthened version of the characterization by Korach et al. Using our characterization of graphs with the König–Egerváry property, we also prove a forbidden subgraph characterization for the class of edge-perfect graphs.     

Chip-Firing,Antimatroids, and Polyhedra

Starting from the chip-firing game of Björner and Lovász we consider a generalization to vector addition systems that still admit algebraic structures as sandpile group or sandpile monoid. Every such vector addition language yields an antimatroid. We show that conversely every antimatroid can be represented this way. The inclusion order on the feasible sets of an antimatroid is an upper locally distributive lattice. We characterize polyhedra, which carry an upper locally distributive structure and show that they can be modelled by chip-firing games with gains and losses. At the end we point out a connection to a membership problem discussed by Korte and Lovász.     

Maximum stable set formulations and heuristics based on continuous optimization

 The stability number α(G) for a given graph G is the size of a maximum stable set in G. The Lovász theta number provides an upper bound on α(G) and can be computed in polynomial time as the optimal value of the Lovász semidefinite program. In this paper, we show that restricting the matrix variable in the Lovász semidefinite program to be rank-one and rank-two, respectively, yields a pair of continuous, nonlinear optimization problems each having the global optimal value α(G). We propose heuristics for obtaining large stable sets in G based on these new formulations and present computational results indicating the effectiveness of the heuristics. Received: December 13, 2000 / Accepted: September 3, 2002 Published online: December 19, 2002 RID="★" ID="★" Computational results reported in this paper were obtained on an SGI Origin2000 computer at Rice University acquired in part with support from NSF Grant DMS-9872009. Key Words. maximum stable set – maximum clique – minimum vertex cover – semidefinite program – semidefinite relaxation – continuous optimization heuristics – nonlinear programming Mathematics Subject Classification (2000): 90C06, 90C27, 90C30     

Evolutionary and asymptotic stability in symmetric multi-player games

We provide a classification of symmetric three-player games with two strategies and investigate evolutionary and asymptotic stability (in the replicator dynamics) of their Nash equilibria. We discuss similarities and differences between two-player and multi-player games. In particular, we construct examples which exhibit a novel behavior not found in two-player games.Received October 2001/Revised May 2003     

An edge-coloration theorem for bipartite graphs with applications

An edge-coloration theorem for bipartite graphs, announced in [4], is proved from which some well-known theorems due to König [5] and the author [2, 3] are deduced. The theorem is further applied to prove the “dual” of a theorem due to Lovász [6].     

On Lovász’ lattice reduction and the nearest lattice point problem

Answering a question of Vera Sós, we show how Lovász’ lattice reduction can be used to find a point of a given lattice, nearest within a factor ofc ^d (c = const.) to a given point in R ^d . We prove that each of two straightforward fast heuristic procedures achieves this goal when applied to a lattice given by a Lovász-reduced basis. The verification of one of them requires proving a geometric feature of Lovász-reduced bases: ac ₁ ^d lower bound on the angle between any member of the basis and the hyperplane generated by the other members, wherec ₁ = √2/3. As an application, we obtain a solution to the nonhomogeneous simultaneous diophantine approximation problem, optimal within a factor ofC ^d . In another application, we improve the Grötschel-Lovász-Schrijver version of H. W. Lenstra’s integer linear programming algorithm. The algorithms, when applied to rational input vectors, run in polynomial time.     

On a class of operator equations arising in infinite dimensional replicator dynamics

We introduce a class of infinite dimensional replicator dynamics for the study of equilibrium selection in non-cooperative games and study their properties. Examples from economic theory are provided.