Concavity and efficient points of discrete distributions in probabilistic programming

We consider stochastic programming problems with probabilistic constraints involving integer-valued random variables. The concept of a p-efficient point of a probability distribution is used to derive various equivalent problem formulations. Next we introduce the concept of r-concave discrete probability distributions and analyse its relevance for problems under consideration. These notions are used to derive lower and upper bounds for the optimal value of probabilistically constrained stochastic programming problems with discrete random variables. The results are illustrated with numerical examples. Received: October 1998 / Accepted: June 2000?Published online October 18, 2000     

Characterizing and decomposing classes of threshold,split, and bipartite graphs via 1-Sperner hypergraphs

A hypergraph is said to be 1-Sperner if for every two hyperedges the smallest of their two set differences is of size one. We present several applications of $1$-Sperner hypergraphs to graphs. First, we consider several ways of associating hypergraphs to graphs, namely, vertex cover, clique, independent set, dominating set, and closed neighborhood hypergraphs. For each of them, we characterize graphs yielding $1$-Sperner hypergraphs. These results give new characterizations of threshold and domishold graphs. Second, we apply a characterization of $1$-Sperner hypergraphs to derive decomposition theorems for two classes of split graphs, a class of bipartite graphs, and a class of cobipartite graphs. These decomposition theorems, based on certain matrix partitions, lead to new classes of graphs of bounded clique-width and new polynomially solvable cases of three basic domination problems: domination, total domination, and connected domination.     

Risk measurement and risk-averse control of partially observable discrete-time Markov systems

We consider risk measurement in controlled partially observable Markov processes in discrete time. We introduce a new concept of conditional stochastic time consistency and we derive the structure of risk measures enjoying this property. We prove that they can be represented by a collection of static law invariant risk measures on the space of function of the observable part of the state. We also derive the corresponding dynamic programming equations. Finally we illustrate the results on a machine deterioration problem.     

Comments on a Simplified Form of Block-Iterative Operator Splitting,and an Asynchronous Algorithm Resembling the Multi-block Alternating Direction Method of Multipliers

This note gives an improved version of the proof of Proposition 4.2 in “A Simplified Form of Block-Iterative Operator Splitting, and an Asynchronous Algorithm Resembling the Multi-block Alternating Direction Method of Multipliers,” Journal of Optimization Theory and Applications 173(1): 155–182 (2017).     

Multivariate value at risk and related topics

Multivariate Value at Risk, or MVaR, is defined as the quantile set of a multivariate probability distribution. It has already been introduced and used in the literature under the name of p-Level Efficient Points, or pLEP’s, or briefly p-efficient points. Some of the topics connected with it are surveyed: discrete convexity, algorithmic generation, relation to logconcavity. A related notion: Multivariate Conditional Value at Risk, or MCVaR, is also introduced and some of its properties are explored. Finally, optimization problems, based on these notions, are presented and discussed, from the point of view of convexity and algorithmic solution.     

A convex programming-based algorithm for mean payoff stochastic games with perfect information

We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph \(G = (V, E)\), with local rewards \(r{:}\,E \rightarrow \mathbb {Z}\), and three types of positions: black \(V_B\), white \(V_W\), and random \(V_R\) forming a partition of V. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, even when \(|V_R|=0\). In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial solvability. In this short note, we show that BWR-games can be solved via convex programming in pseudo-polynomial time if the number of random positions is a constant.     

A nested family of $$\varvec{}$$-total effective rewards for positional games

We consider Gillette’s two-person zero-sum stochastic games with perfect information. For each \(k \in \mathbb {N}=\{0,1,\ldots \}\) we introduce an effective reward function, called k-total. For \(k = 0\) and 1 this function is known as mean payoff and total reward, respectively. We restrict our attention to the deterministic case. For all k, we prove the existence of a saddle point which can be realized by uniformly optimal pure stationary strategies. We also demonstrate that k-total reward games can be embedded into \((k+1)\)-total reward games.     

Comprehensive vs. comprehensible classifiers in logical analysis of data

The main objective of this paper is to compare the classification accuracy provided by large, comprehensive collections of patterns (rules) derived from archives of past observations, with that provided by small, comprehensible collections of patterns. This comparison is carried out here on the basis of an empirical study, using several publicly available data sets. The results of this study show that the use of comprehensive collections allows a slight increase of classification accuracy, and that the “cost of comprehensibility” is small.