On some balanced, totally balanced and submodular delivery games

This paper studies a class of delivery problems associated with the Chinese postman problem and a corresponding class of delivery games. A delivery problem in this class is determined by a connected graph, a cost function defined on its edges and a special chosen vertex in that graph which will be referred to as the post office. It is assumed that the edges in the graph are owned by different individuals and the delivery game is concerned with the allocation of the traveling costs incurred by the server, who starts at the post office and is expected to traverse all edges in the graph before returning to the post office. A graph G is called Chinese postman-submodular, or, for short, CP-submodular (CP-totally balanced, CP-balanced, respectively) if for each delivery problem in which G is the underlying graph the associated delivery game is submodular (totally balanced, balanced, respectively). For undirected graphs we prove that CP-submodular graphs and CP-totally balanced graphs are weakly cyclic graphs and conversely. An undirected graph is shown to be CP-balanced if and only if it is a weakly Euler graph. For directed graphs, CP-submodular graphs can be characterized by directed weakly cyclic graphs. Further, it is proven that any strongly connected directed graph is CP-balanced. For mixed graphs it is shown that a graph is CP-submodular if and only if it is a mixed weakly cyclic graph. Finally, we note that undirected, directed and mixed weakly cyclic graphs can be recognized in linear time. Received May 20, 1997 / Revised version received August 18, 1998?Published online June 11, 1999     

Dual representation of convex sets of probability measures on totally bounded spaces

Convex sets of probability measures, frequently encountered in probability theory and statistics, can be transparently analyzed by means of dual representations in a function space. This paper introduces totally bounded spaces, whose structure is defined by a set of bounded real-valued functions, as a general framework for studying such representations. The reinterpretation of classical theorems in this framework clarifies the role of compactness and leads to simple existence criteria. Applications include results on the existence of probability measures satisfying given sets of conditions and an equivalence of consistent preferences and families of probability measures. Moreover, countable additivity of probabilities is seen to be a consequence of elementary consistency assumptions.     

Separated totally convex spaces

In this paper we define for every totally convex space a suitable topology, the radial topology. We prove that a morphism in the category TC^sep of separated totally convex spaces is an epimorphism if and only if its image is dense in the radial topology, and that TC^sep is the full subcategory of TC generated by its Hausdorff objects. These results remain valid for finitely totally convex spaces when the radial topology is replaced by the distance-radial topology.Dedicated to Karl Stein     

A polymatroid associated with convex games

A cooperative game with side payments is called convex if its characteristic function is supermodular. We define a polymatroid with the characteristic function of the convex game, and investigate some properties of a partition of the players equivalent to the principal partition of the polymatroid as well as a partial order among the elements of the partition. The partition and partial order reflects players' interdependences and one-way dependences respectively. The critical value in the polymatroid theory is related to the minimum amount of reasonable requirement between coalitions at the time of their amalgamation. Also shown is an application to the problem of oligopoly.     

Characterizations of totally balanced matrices

A (0,1)-matrix is totally balanced if it does not contain as a submatrix the incidence matrix of any cycle of length at least 3. Several alternative characterizations of these matrices are presented. These characterizations follow from properties of strongly chordal graphs, studied by Farber, and maximal totally balanced matrices, studied by Anstee. Using these characterizations, efficient recognition algorithms for totally balanced matrices are presented. In addition, a new completion algorithm for building a maximal totally balanced matrix from an arbitrary totally balanced matrix follows from these results.     

A representation of convex semilinear sets

If F is an ordered field, a subset of n-space over F is said to be semilinear just in case it is a finite Boolean combination of translates of closed halfspaces, where a closed halfspace is the set of all points obeying a homogeneous weak linear inequality with coefficients from F. Andradas, Rubio, and Vélez have shown that closed (open) convex semilinear sets are finite intersections of translates of closed (open) halfspaces (an open halfspace is defined as before, but with a strict inequality). This paper represents arbitrary convex semilinear sets in a manner analogous to that of Andradas, Rubio, and Vélez.     

Cores of convex games

The core of ann-person game is the set of feasible outcomes that cannot be improved upon by any coalition of players. A convex game is defined as one that is based on a convex set function. In this paper it is shown that the core of a convex game is not empty and that it has an especially regular structure. It is further shown that certain other cooperative solution concepts are related in a simple way to the core: The value of a convex game is the center of gravity of the extreme points of the core, and the von Neumann-Morgenstern stable set solution of a convex game is unique and coincides with the core.     

Strongly balanced cooperative games

Kaneko/Wooders (1982) derived a list of necessary and sufficient conditions for a partitioning game to have a nonempty core regardless of the payoff functions of its effective coalitions. The main purpose of our paper is to provide a graph-theoretical characterization of this family of games whose associated hypergraphs we callstrongly balanced: we show that the strong balancedness condition is equivalent to thenormality of the hypergraph, which is a type ofcoloring property (Lovasz (1972)). We also study interesting economic examples ofcommunication andassignment games and provide direct proofs that their associated hypergraphs are strongly balanced.We wish to thank two anonymous referees of this journal for their useful comments and suggestions. The previous version of this paper was written while the authors were visiting Department of Economics, University of Bonn. The financial support of Sonderfor-schungsbereich 303 is gratefully acknowledged.     

Epimorphisms of separated totally convex spaces

We give characterizations of the epimorphisms in the categories of open and separated totally convex and (pre)separated absolutely convex spaces.     

On convex optimization without convex representation

We consider the convex optimization problem P:min_x {f(x) : x ? K}{{\rm {\bf P}}:{\rm min}_{\rm {\bf x}} \{f({\rm {\bf x}})\,:\,{\rm {\bf x}}\in{\rm {\bf K}}\}} where f is convex continuously differentiable, and K ì \mathbb Rⁿ{{\rm {\bf K}}\subset{\mathbb R}^n} is a compact convex set with representation {x ? \mathbb Rⁿ : g_j(x) 3 0, j = 1,?,m}{\{{\rm {\bf x}}\in{\mathbb R}^n\,:\,g_j({\rm {\bf x}})\geq0, j = 1,\ldots,m\}} for some continuously differentiable functions (g _j ). We discuss the case where the g _j ’s are not all concave (in contrast with convex programming where they all are). In particular, even if the g _j are not concave, we consider the log-barrier function f_m{\phi_\mu} with parameter μ, associated with P, usually defined for concave functions (g _j ). We then show that any limit point of any sequence (x_m) ì K{({\rm {\bf x}}_\mu)\subset{\rm {\bf K}}} of stationary points of f_m, m? 0{\phi_\mu, \mu \to 0} , is a Karush–Kuhn–Tucker point of problem P and a global minimizer of f on K.     

A constrained egalitarian solution for convex multi-choice games

This paper deals with a constrained egalitarian solution for convex multi-choice games named the d value. It is proved that the d value of a convex multi-choice game belongs to the precore, Lorenz dominates each other element of the precore and possesses a population monotonicity property regarding players’ participation levels. Furthermore, an axiomatic characterization is given where a specific consistency property plays an important role.     

Online balanced graph avoidance games

We introduce and study online balanced coloring games on the random graph process. The game is played by a player we call Painter. Edges of the complete graph with n vertices are introduced two at a time, in a random order. For each pair of edges, Painter immediately and irrevocably chooses one of the two possibilities to color one of them red and the other one blue. His goal is to avoid creating a monochromatic copy of a small fixed graph F for as long as possible.We show that the duration of the game is determined by a threshold function m_H=m_H(n) for certain graph-theoretic structures, e.g., cycles. That is, for every graph H in this family, Painter will asymptotically almost surely (a.a.s.) lose the game after m=ω(m_H) edge pairs in the process. On the other hand, there exists an essentially optimal strategy: if the game lasts for m=o(m_H) moves, Painter can a.a.s. successfully avoid monochromatic copies of H. Our attempt is to determine the threshold function for several classes of graphs.     

Totally balanced combinatorial optimization games

Combinatorial optimization games deal with cooperative games for which the value of every subset of players is obtained by solving a combinatorial optimization problem on the resources collectively owned by this subset. A solution of the game is in the core if no subset of players is able to gain advantage by breaking away from this collective decision of all players. The game is totally balanced if and only if the core is non-empty for every induced subgame of it.?We study the total balancedness of several combinatorial optimization games in this paper. For a class of the partition game [5], we have a complete characterization for the total balancedness. For the packing and covering games [3], we completely clarify the relationship between the related primal/dual linear programs for the corresponding games to be totally balanced. Our work opens up the question of fully characterizing the combinatorial structures of totally balanced packing and covering games, for which we present some interesting examples: the totally balanced matching, vertex cover, and minimum coloring games. Received: November 5, 1998 / Accepted: September 8, 1999?Published online February 23, 2000     

Combinatorial representation and convex dimension of convex geometries

We develop a representation theory for convex geometries and meet distributive lattices in the spirit of Birkhoff's theorem characterizing distributive lattices. The results imply that every convex geometry on a set X has a canonical representation as a poset labelled by elements of X. These results are related to recent work of Korte and Lovász on antimatroids. We also compute the convex dimension of a convex geometry.Supported in part by NSF grant no. DMS-8501948.     

On ε-cores of balanced games

The present note considers a balanced game without side payments with a continuum of players. The nonemptiness of theε-core for some classes of such games is established.     

Strong equilibria in claim games corresponding to convex games

This paper deals with a specific aspect of the problem of coalition formation in a situation described by a TU-game. First, we define a very simple normal form game which models the process of coalition formation. To define the payoff functions of the players we use an allocation rule for TU-games. The main objective of this paper is ascertain what conditions of the allocation rule lead to the grand coalition being a strong equilibrium of the normal form game, when the original TU-game is convex. Received January 1996/Revised version December 1996/Final version May 1997     

Various characterizations of convex fuzzy games

This note enlarges the literature on convex fuzzy games with new characterizing properties of such games besides the increasing average marginal return property, namely: the monotonicity of the first partial derivatives, the directional convexity and forC ²-functions the non-negativity of the second order partial derivatives.