Convex multi-choice games: Characterizations and monotonic allocation schemes

This paper focuses on new characterizations of convex multi-choice games using the notions of exactness and superadditivity. Furthermore, level-increase monotonic allocation schemes (limas) on the class of convex multi-choice games are introduced and studied. It turns out that each element of the Weber set of such a game is extendable to a limas, and the (total) Shapley value for multi-choice games generates a limas for each convex multi-choice game.     

Minimal ellipsoids and their duals

It is proved that “most” convex bodies in IE ^d touch the boundaries of their minimal circumscribed and their maximal inscribed ellipsoids in preciselyd(d+3)/2 points. A version of the former result shows that for “most” compact sets in IE ^d the corresponding optimal designs, i.e. probability measures with a certain extremal property, are concentrated ond(d+1)/2 points.     

The average tree solution for multi-choice forest games

In this article we study cooperative multi-choice games with limited cooperation possibilities, represented by an undirected forest on the player set. Players in the game can cooperate if they are connected in the forest. We introduce a new (single-valued) solution concept which is a generalization of the average tree solution defined and characterized by Herings et?al. (Games Econ. Behav. 62:77?C92, 2008) for TU-games played on a forest. Our solution is characterized by component efficiency, component fairness and independence on the greatest activity level. It belongs to the precore of a restricted multi-choice game whenever the underlying multi-choice game is superadditive and isotone. We also link our solution with the hierarchical outcomes (Demange in J. Polit. Econ. 112:754?C778, 2004) of some particular TU-games played on trees. Finally, we propose two possible economic applications of our average tree solution.     

The convex dimension of a graph

The convex dimension of a graph G=(V,E) is the smallest dimension d for which G admits an injective map f:V?R^d of its vertices into d-space, such that the barycenters of the images of the edges of G are in convex position. The strong convex dimension of G is the smallest d for which G admits a map as above such that the images of the vertices of G are also in convex position. In this paper we study the convex and strong convex dimensions of graphs.     

Polyhedral Embeddings of Cayley Graphs

When is a Cayley graph the graph of a convex d-polytope? We show that while this is not always the case, some interesting finite groups have this property.     

Cutting the Same Fraction of Several Measures

We study some measure partition problems: Cut the same positive fraction of d+1 measures in ? ^d with a hyperplane or find a convex subset of ? ^d on which d+1 given measures have the same prescribed value. For both problems positive answers are given under some additional assumptions.     

Existence and convergence theorems for generalized hybrid mappings in uniformly convex metric spaces

In this paper, we show a relationship between strictly convexity of type (I) and (II) defined by Takahashi and Talman, and we prove that any uniformly convex metric space is strictly convex of type (II). Continuity of the convex structure is also shown on a compact domain. Then, we prove the existence of a minimum point of a convex, lower semicontinuous and d-coercive function defined on a nonempty closed convex subset of a complete uniformly convex metric space. By using this property, we prove fixed point theorems for (α, β)-generalized hybrid mappings in uniformly convex metric spaces. Using this result, we also obtain a common fixed point theorem for a countable commutative family of (α, β)-generalized hybrid mappings in uniformly convex metric spaces. Finally, we establish strong convergence of a Mann type iteration to a fixed point of (α, β)-generalized hybrid mapping in a uniformly convex metric space without assuming continuity of convex structure. Our results can be applied to obtain the existence and convergence theorems for (α, β)-generalized hybrid mappings in Hilbert spaces, uniformly convex Banach spaces and CAT(0) spaces.     

Distances Between Poisson k -Flats

The distances between flats of a Poisson k-flat process in the d-dimensional Euclidean space with k?<?d/2 are discussed. Continuing an approach originally due to Rolf Schneider, the number of pairs of flats having distance less than a given threshold and midpoint in a fixed compact and convex set is considered. For a family of increasing convex subsets, the asymptotic variance is computed and a central limit theorem with an explicit rate of convergence is proven. Moreover, the asymptotic distribution of the m-th smallest distance between two flats is investigated and it is shown that the ordered distances form asymptotically after suitable rescaling an inhomogeneous Poisson point process on the positive real half-axis. A similar result with a homogeneous limiting process is derived for distances around a fixed, strictly positive value. Our proofs rely on recent findings based on the Wiener–Itô chaos decomposition and the Malliavin–Stein method.     

Sufficient Conditions and Duality for a Class of Multiobjective Fractional Programming Problems with Higher-Order (F,α,ρ,d)-Convexity

In this paper, a class of multiobjective fractional programming problems (denoted by (MFP)) is considered. First, the concept of higher-order (F,α,ρ,d)-convexity of a function f:C→R with respect to the differentiable function φ:R ⁿ ×R ⁿ →R is introduced, where C is an open convex set in R ⁿ and α:C×C→R ₊?{0} is a positive value function. And an important property, which the ratio of higher-order (F,α,ρ,d)-convex functions is also higher-order (F,α ^′,ρ ^′,d ^′)-convex, is proved. Under the higher-order (F,α,ρ,d)-convexity assumptions, an alternative theorem is also given. Then, some sufficient conditions characterizing properly (or weakly) efficient solutions of (MFP) are obtained from the above property and alternative theorem. Finally, a class of dual problems is formulated and appropriate duality theorems are proved.     

Polyhedral studies on the convex recoloring problem

A coloring of the vertices of a graph G is convex if, for each assigned color d, the vertices with color d induce a connected subgraph of G. We address the convex recoloring problem, defined as follows. Given a graph G and a coloring of its vertices, recolor a minimum number of vertices of G, so that the resulting coloring is convex. This problem is known to be NP-hard even when G is a path. We show an integer programming formulation for the weighted version of this problem on arbitrary graphs, and then specialize it for trees. We study the facial structure of the polytope defined as the convex hull of the integer points satisfying the restrictions of the proposed ILP formulation, present several classes of facet-defining inequalities and discuss separation algorithms.     

On multi-choice TU games arising from replica of economies

In this paper we derive a multi-choice TU game from r-replica of exchange economy with continuous, concave and monetary utility functions, and prove that the cores of the games converge to a subset of the set of Edgeworth equilibria of exchange economy as r approaches to infinity. We prove that the dominance core of each balanced multi-choice TU game, where each player has identical activity level r, coincides with the dominance core of its corresponding r-replica of exchange economy. We also give an extension of the concept of the cover of the game proposed by Shapley and Shubik (J Econ Theory 1: 9-25, 1969) to multi-choice TU games and derive some sufficient conditions for the nonemptyness of the core of multi-choice TU game by using the relationship among replica economies, multi-choice TU games and their covers.     

Reduced convex bodies in Euclidean space—A survey

A convex body R in Euclidean space E^d is called reduced if the minimal width Δ(K) of each convex body K⊂R different from R is smaller than Δ(R). This definition yields a class of convex bodies which contains the class of complete sets, i.e., the family of bodies of constant width. Other obvious examples in E² are regular odd-gons. We know a relatively large amount on reduced convex bodies in E². Besides theorems which permit us to understand the shape of their boundaries, we have estimates of the diameter, perimeter and area. For d≥3 we do not even have tools which permit us to recognize what the boundary of R looks like. The class of reduced convex bodies has interesting applications. We present the current state of knowledge about reduced convex bodies in E^d, recall some striking related research problems, and put a few new questions.     

Contractivity of Wasserstein metrics and asymptotic profiles for scalar conservation laws

The aim of this paper is to analyze contractivity properties of Wasserstein-type metrics for one-dimensional scalar conservation laws with nonnegative, L^∞ and compactly supported initial data and its implications on the long time asymptotics. The flux is assumed to be convex and without any growth condition at the zero state. We propose a time-parameterized family of functions as intermediate asymptotics and prove the solutions, after a time-depending scaling, converge toward this family in the d_∞-Wasserstein metric. This asymptotic behavior relies on the aforementioned contraction property for conservation laws in the space of probability densities metrized with the d_∞-Wasserstein distance. Finally, we also give asymptotic profiles for initial data whose distributional derivative is a probability measure.     

Kirchberger-type theorems for separation by convex domains

We say that a convex set K in ? ^d strictly separates the set A from the set B if A ? int(K) and B ? cl K = ø. The well-known Theorem of Kirchberger states the following. If A and B are finite sets in ? ^d with the property that for every T ? A?B of cardinality at most d + 2, there is a half space strictly separating T ? A and T ? B, then there is a half space strictly separating A and B. In short, we say that the strict separation number of the family of half spaces in ? ^d is d + 2.In this note we investigate the problem of strict separation of two finite sets by the family of positive homothetic (resp., similar) copies of a closed, convex set. We prove Kirchberger-type theorems for the family of positive homothets of planar convex sets and for the family of homothets of certain polyhedral sets. Moreover, we provide examples that show that, for certain convex sets, the family of positive homothets (resp., the family of similar copies) has a large strict separation number, in some cases, infinity. Finally, we examine how our results translate to the setting of non-strict separation.     

Billiards in convex bodies with acute angles

In this paper we investigate the existence of closed billiard trajectories in not necessarily smooth convex bodies. In particular, we show that if a body K ? R^d has the property that the tangent cone of every non-smooth point q ? ?K is acute (in a certain sense), then there is a closed billiard trajectory in K.     

On the multiple Borsuk numbers of sets

The Borsuk number of a set S of diameter d > 0 in Euclidean n-space is the smallest value of m such that S can be partitioned into m sets of diameters less than d. Our aim is to generalize this notion in the following way: The k -fold Borsuk number of such a set S is the smallest value of m such that there is a k-fold cover of S with m sets of diameters less than d. In this paper we characterize the k-fold Borsuk numbers of sets in the Euclidean plane, give bounds for those of centrally symmetric sets, smooth bodies and convex bodies of constant width, and examine them for finite point sets in the Euclidean 3-space.     

On the covering index of convex bodies

Covering a convex body by its homothets is a classical notion in discrete geometry that has resulted in a number of interesting and long-standing problems. Swanepoel introduced the covering parameter of a convex body as a means of quantifying its covering properties. In this paper, we introduce two relatives of the covering parameter called covering index and weak covering index, which upper bound well-studied quantities like the illumination number, the illumination parameter and the covering parameter of a convex body. Intuitively, the two indices measure how well a convex body can be covered by a relatively small number of homothets having the same relatively small homothety ratio. We show that the covering index is a lower semicontinuous functional on the Banach-Mazur space of convex bodies. We further show that the affine d-cubes minimize the covering index in any dimension d, while circular disks maximize it in the plane. Furthermore, the covering index satisfies a nice compatibility with the operations of direct vector sum and vector sum. In fact, we obtain an exact formula for the covering index of a direct vector sum of convex bodies that works in infinitely many instances. This together with a minimization property can be used to determine the covering index of infinitely many convex bodies. As the name suggests, the weak covering index loses some of the important properties of the covering index. Finally, we obtain upper bounds on the covering and weak covering index.     

Convex polytopes whose projection bodies and difference sets are polars

In a paper by the author and B. Weissbach it was proved that the projection body and the difference set of ad-simplex (d≥2) are polars. Obviously, ford=2 a convex domain has this property if and only if its difference set is bounded by a so-called Radon curve. A natural question emerges about further classes of convex bodies inR ^d (d≥3) inducing the mentioned polarity. The aim of this paper is to show that a convexd-polytope (d≥3) is a simplex if and only if its projection body and its difference set are polars.     

On a cone covering problem

Given a set of polyhedral cones C₁,…,Ck⊂Rd, and a convex set D, does the union of these cones cover the set D? In this paper we consider the computational complexity of this problem for various cases such as whether the cones are defined by extreme rays or facets, and whether D is the entire Rd or a given linear subspace Rt. As a consequence, we show that it is coNP-complete to decide if the union of a given set of convex polytopes is convex, thus answering a question of Bemporad, Fukuda and Torrisi.     

Group actions and Helly's theorem

We describe a connection between the combinatorics of generators for certain groups and the combinatorics of Helly's 1913 theorem on convex sets. We use this connection to prove fixed point theorems for actions of these groups on nonpositively curved metric spaces. These results are encoded in a property that we introduce called “property FAr”, which reduces to Serre's property FA when r=1. The method applies to S-arithmetic groups in higher Q-rank, to simplex reflection groups (including some nonarithmetic ones), and to higher rank Chevalley groups over polynomial and other rings (for example SLn(Z[x₁,…,xd]), n>2).