On the population monotonicity of independent set games

An independent set game is a cooperative game dealing with profit sharing in the maximum independent set problem. A population monotonic allocation scheme is a rule specifying how to share the profit of each coalition among its participants such that every participant is better off when the coalition expands. In this paper, we provide a necessary and sufficient characterization for independent set games admitting population monotonic allocation schemes. Moreover, our characterization can be verified efficiently.     

6元素集合上T0拓扑总数的计算

文中证明了有限预序集与有限偏序集的一些性质,并基于有限集上的拓扑和其上预序的一一对应关系,利用这些性质通过对极小元和极大元个数进行分类讨论,以一种有别于计算机算法而又容易理解的计算方法得出6元素集合上的T₀拓扑总数为130023.     

Finding normal solutions in piecewise linear programming

Letf: ⁿ (–, ] be a convex polyhedral function. We show that if any standard active set method for quadratic programming (QP) findsx(t)= arg min _x ¦x¦²/2+t f(x) for somet> 0, then its final working set defines a simple equality QP subproblem, whose Lagrange multiplier can be used both for testing ift is large enough forx(t) to coincide with the normal minimizer off, and for increasingt otherwise. The QP subproblem may easily be solved via the matrix factorizations used for findingx(t). This opens up the way for efficient implementations. We also give finite methods for computing the whole trajectory {x(t)} _t 0, minimizingf over an ellipsoid, and choosing penalty parameters inL ₁QP methods for strictly convex QP.This research was supported by the State Committee for Scientific Research under Grant 8S50502206.     

Near-perfect matrices

A 0, 1 matrixA isnear-perfect if the integer hull of the polyhedron {x0: Ax } can be obtained by adding one extra (rank) constraint. We show that in general, such matrices arise as the cliquenode incidence matrices of graphs. We give a colouring-like characterization of the corresponding class of near-perfect graphs which shows that one need only check integrality of a certain linear program for each 0, 1, 2-valued objective function. This in contrast with perfect matrices where it is sufficient to check 0, 1-valued objective functions. We also make the following conjecture: a graph is near-perfect if and only if sequentially lifting any rank inequality associated with a minimally imperfect graph results in the rank inequality for the whole graph. We show that the conjecture is implied by the Strong Perfect Graph Conjecture. (It is also shown to hold for graphs with no stable set of size eleven.) Our results are used to strengthen (and give a new proof of) a theorem of Padberg. This results in a new characterization of minimally imperfect graphs: a graph is minimally imperfect if and only if both the graph and its complement are near-perfect.The research has partially been done when the author visited Mathematic Centrum, CWI, Amsterdam, The Netherlands.     

The diagnonal multivariate natural exponential families and their classification

A natural exponential family (NEF)F in ? ⁿ ,n>1, is said to be diagonal if there existn functions,a ₁,...,a _n , on some intervals of ?, such that the covariance matrixV _F (m) ofF has diagonal (a ₁(m ₁),...,a _n (m _n )), for allm=(m ₁,...,m _n ) in the mean domain ofF. The familyF is also said to be irreducible if it is not the product of two independent NEFs in ? ^k and ? ^n-k , for somek=1,...,n?1. This paper shows that there are only six types of irreducible diagonal NEFs in ? ⁿ , that we call normal, Poisson, multinomial, negative multinomial, gamma, and hybrid. These types, with the exception of the latter two, correspond to distributions well established in the literature. This study is motivated by the following question: IfF is an NEF in ? ⁿ , under what conditions is its projectionp(F) in ? ^k , underp(x ₁,...,x _n )∶=(x ₁,...,x _k ),k=1,...,n?1, still an NEF in ? ^k ? The answer turns out to be rather predictable. It is the case if, and only if, the principalk×k submatrix ofV _F (m ₁,...,m _n ) does not depend on (m _k+1,...,m _n ).     

Banach spaces that admit support sets

It is shown that the existence of a closed convex set all of whose points are properly supported in a Banach space is equivalent to the existence of a certain type of uncountable ordered one-sided biorthogonal system. Under the continuum hypothesis, we deduce that this notion is weaker than the existence of an uncountable biorthogonal system.

     

Impossibility of a Certain Cyclotomic Equation with Applicationsto Difference Sets

Under certain conditions, we show the nonexistence ofan element in the p-th cyclotomicfield over , that satisfies . As applications, we establish the nonexistence ofsome difference sets and affine difference sets.     

Countable network weight and multiplication of Borel sets

A space Borel multiplies with a space if each Borel set of is a member of the -algebra in generated by Borel rectangles. We show that a regular space Borel multiplies with every regular space if and only if has a countable network. We give an example of a Hausdorff space with a countable network which fails to Borel multiply with any non-separable metric space. In passing, we obtain a characterization of those spaces which Borel multiply with the space of countable ordinals, and an internal necessary and sufficient condition for to Borel multiply with every metric space.

     

Stochastic dominance with nonadditive probabilities

Choquet expected utility which uses capacities (i.e. nonadditive probability measures) in place of-additive probability measures has been introduced to decision making under uncertainty to cope with observed effects of ambiguity aversion like the Ellsberg paradox. In this paper we present necessary and sufficient conditions for stochastic dominance between capacities (i.e. the expected utility with respect to one capacity exceeds that with respect to the other one for a given class of utility functions). One wide class of conditions refers to probability inequalities on certain families of sets. To yield another general class of conditions we present sufficient conditions for the existence of a probability measureP with f dC= f dP for all increasing functionsf whenC is a given capacity. Examples includen-th degree stochastic dominance on the reals and many cases of so-called set dominance. Finally, applications to decision making are given including anticipated utility with unknown distortion function.