Inequality in population weights,majority threshold and the inversion probability in the case of three states

Two-tier voting systems are prone to majority inversions, when the outcome of an election is not backed by a majority of popular vote. We study the inversion probability in a model with two candidates, three states and uniformly distributed fractions of supporters for each candidate. We show that the inversion probability in a two-tier voting system with three states eventually decreases with a majority threshold in the states and increases with the inequality in the size distribution of the states.     

A simple “market value” bargaining model for weighted voting games: characterization and limit theorems

We offer a bargaining model for weighted voting games that is a close relative of the nucleolus and the kernel. We look for a set of weights that preserves winning coalitions that has the property of minimizing the difference between the weight of the smallest and the weight of the largest Minimum Winning Coalition. We claim that such a set of weights provides an a priori measure of a weighted voter’s bribeworthiness or market value. After introducing our model, we provide a characterization result for this model and show its links to other bargaining model approaches in the literature. Then we offer some limit results showing that, with certain reasonable conditions on the distributions of weights, as the size of the voting body increases, the values of bribeworthiness we calculate will approach both the weights themselves and the Banzhaf scores for the weighted voting game. We also show that, even for relatively small groups using weighted voting, such as the membership of the European Council of Ministers (and its predecessors) 1958–2003, similarities among the usual a priori power scores, bribeworthiness/market value, and the weights themselves, will be quite strong.     

The fraction of large random trees representing a given Boolean function in implicational logic

We consider the logical system of Boolean expressions built on the single connector of implication and on positive literals. Assuming all expressions of a given size to be equally likely, we prove that we can define a probability distribution on the set of Boolean functions expressible in this system. Then we show how to approximate the probability of a function f when the number of variables grows to infinity, and that this asymptotic probability has a simple expression in terms of the complexity of f. We also prove that most expressions computing any given function in this system are “simple”, in a sense that we make precise. The probability of all read‐once functions of a given complexity is also evaluated in this model. At last, using the same techniques, the relation between the probability of a function and its complexity is also obtained when random expressions are drawn according to a critical branching process. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Cooperative oligopoly games with boundedly rational firms

We analyze cooperative Cournot games with boundedly rational firms. Due to cognitive constraints, the members of a coalition cannot accurately predict the coalitional structure of the non-members. Thus, they compute their value using simple heuristics. In particular, they assign various non-equilibrium probability distributions over the outsiders’ set of partitions. We construct the characteristic function of a coalition in such an environment and we analyze the core of the corresponding games. We show that the core is non-empty provided the number of firms in the market is sufficiently large. Moreover, we show that if two distributions over the set of partitions are related via first-order dominance, then the core of the game under the dominated distribution is a subset of the core under the dominant distribution.     

Accusation probabilities in Tardos codes: beyond the Gaussian approximation

We study the probability distribution of user accusations in the q-ary Tardos fingerprinting system under the Marking Assumption, in the restricted digit model. In particular, we look at the applicability of the so-called Gaussian approximation, which states that accusation probabilities tend to the normal distribution when the fingerprinting code is long. We introduce a novel parametrization of the attack strategy which enables a significant speedup of numerical evaluations. We set up a method, based on power series expansions, to systematically compute the probability of accusing innocent users. The ‘small parameter’ in the power series is 1/m, where m is the code length. We use our method to semi-analytically study the performance of the Tardos code against majority voting and interleaving attacks. The bias function ‘shape’ parameter k{{\kappa}} strongly influences the distance between the actual probabilities and the asymptotic Gaussian curve. The impact on the collusion-resilience of the code is shown. For some realistic parameter values, the false accusation probability is even lower than the Gaussian approximation predicts.     

An informational distance for estimating the faithfulness of a possibility distribution,viewed as a family of probability distributions,with respect to data

An acknowledged interpretation of possibility distributions in quantitative possibility theory is in terms of families of probabilities that are upper and lower bounded by the associated possibility and necessity measures. This paper proposes an informational distance function for possibility distributions that agrees with the above-mentioned view of possibility theory in the continuous and in the discrete cases. Especially, we show that, given a set of data following a probability distribution, the optimal possibility distribution with respect to our informational distance is the distribution obtained as the result of the probability-possibility transformation that agrees with the maximal specificity principle. It is also shown that when the optimal distribution is not available due to representation bias, maximizing this possibilistic informational distance provides more faithful results than approximating the probability distribution and then applying the probability-possibility transformation. We show that maximizing the possibilistic informational distance is equivalent to minimizing the squared distance to the unknown optimal possibility distribution. Two advantages of the proposed informational distance function is that (i) it does not require the knowledge of the shape of the probability distribution that underlies the data, and (ii) it amounts to sum up the elementary terms corresponding to the informational distance between the considered possibility distribution and each piece of data. We detail the particular case of triangular and trapezoidal possibility distributions and we show that any unimodal unknown probability distribution can be faithfully upper approximated by a triangular distribution obtained by optimizing the possibilistic informational distance.     

Binomial Moments of the Distance Distribution and the Probability of Undetected Error

In [1] K. A. S. Abdel-Ghaffar derives a lower bound on the probability of undetected error for unrestricted codes. The proof relies implicitly on the binomial moments of the distance distribution of the code. We use the fact that these moments count the size of subcodes of the code to give a very simple proof of the bound in Abdel by showing that it is essentially equivalent to the Singleton bound. This proof reveals connections of the probability of undetected error to the rank generating function of the code and to related polynomials (Whitney function, Tutte polynomial, and higher weight enumerators). We also discuss some improvements of this bound.Finally, we analyze asymptotics. We show that an upper bound on the undetected error exponent that corresponds to the bound of Abdel improves known bounds on this function.     

The distribution semantics for normal programs with function symbols

The distribution semantics integrates logic programming and probability theory using a possible worlds approach. Its intuitiveness and simplicity have made it the most widely used semantics for probabilistic logic programming, with successful applications in many domains. When the program has function symbols, the semantics was defined for special cases: either the program has to be definite or the queries must have a finite number of finite explanations. In this paper we show that it is possible to define the semantics for all programs. We also show that this definition coincides with that of Sato and Kameya on positive programs. Moreover, we highlight possible approaches for inference, both exact and approximate.     

Voting Power in the Governance of the International Monetary Fund

In general in an organisation whose system of governance involves weighted voting, a member's weight in terms of the number of votes and the formal power it represents differ. Power indices provide a means of analysing this difference. The paper uses new algorithms for computing power indices for large games. Three analyses are carried out: (1) the distribution of Banzhaf voting power among members in 1999; the results show that the United States has considerably more power over ordinary decisions than its weight of 17% but that the use of special supermajorities limits its power; (2) the effect of varying the majority requirement on the power of the IMF to act and the powers of members to prevent and initiate action (Coleman indices); the results show the effect of supermajorities severely limits the power to act and therefore renders the voting system ineffective in democratic terms, also the sovereignty of the United States within the IMF is effectively limited to just the power of veto; (3) the paper proposes the determination of the weights instrumentally by means of an iterative algorithm to give the required power distribution; this would be a useful procedure for determining appropriate changes in weights consequent on changes to individual countries' quotas; this is applied to the 1999 data. Policy recommendations are, first, that the IMF use only simple majority voting, and discontinue using special supermajorities, and, second, allocate voting weight instrumentally using power indices.     

Likelihood-based belief function: Justification and some extensions to low-quality data

Given a parametric statistical model, evidential methods of statistical inference aim at constructing a belief function on the parameter space from observations. The two main approaches are Dempster's method, which regards the observed variable as a function of the parameter and an auxiliary variable with known probability distribution, and the likelihood-based approach, which considers the relative likelihood as the contour function of a consonant belief function. In this paper, we revisit the latter approach and prove that it can be derived from three basic principles: the likelihood principle, compatibility with Bayes' rule and the minimal commitment principle. We then show how this method can be extended to handle low-quality data. Two cases are considered: observations that are only partially relevant to the population of interest, and data acquired through an imperfect observation process.     

Properties of consistent voting systems

We consider exactly and strongly consistent voting functions where the alternative set is the set of real numbers and each person's preference ordering is determined by a utility function ¦x?x^*¦ wherex ^* is his most preferred alternative. We prove that a voting function which is continuous, anonymous, weakly Pareto, and strongly and exactly consistent must coincide with a class of generalized medians studied byMoulin [1978]. Thus, such a function is actually strategyproof. The continuity assumption can be weakened a little, but we give an example of a noncontinuous function which is strongly and exactly consistent, anonymous, and weakly Pareto, but is not strategyproof.     

Canonical representation of conditionally specified multivariate discrete distributions

Most work on conditionally specified distributions has focused on approaches that operate on the probability space, and the constraints on the probability space often make the study of their properties challenging. We propose decomposing both the joint and conditional discrete distributions into characterizing sets of canonical interactions, and we prove that certain interactions of a joint distribution are shared with its conditional distributions. This invariance opens the door for checking the compatibility between conditional distributions involving the same set of variables. We formulate necessary and sufficient conditions for the existence and uniqueness of discrete conditional models, and we show how a joint distribution can be easily computed from the pool of interactions collected from the conditional distributions. Hence, the methods can be used to calculate the exact distribution of a Gibbs sampler. Furthermore, issues such as how near compatibility can be reconciled are also discussed. Using mixed parametrization, we show that the proposed approach is based on the canonical parameters, while the conventional approaches are based on the mean parameters. Our advantage is partly due to the invariance that holds only for the canonical parameters.     

Delay analysis of a two-class batch-service queue with class-dependent variable server capacity

In this paper, we analyse the delay of a random customer in a two-class batch-service queueing model with variable server capacity, where all customers are accommodated in a common single-server first-come-first-served queue. The server can only process customers that belong to the same class, so that the size of a batch is determined by the length of a sequence of same-class customers. This type of batch server can be found in telecommunications systems and production environments. We first determine the steady state partial probability generating function of the queue occupancy at customer arrival epochs. Using a spectral decomposition technique, we obtain the steady state probability generating function of the delay of a random customer. We also show that the distribution of the delay of a random customer corresponds to a phase-type distribution. Finally, some numerical examples are given that provide further insight in the impact of asymmetry and variance in the arrival process on the number of customers in the system and the delay of a random customer.     

Some properties of a two-parameter family of poisson distributions of orderk

We study the problem of simulating the process of detecting a weighted sum of independent Poisson random variables. We investigate the properties of the resulting compound Poisson distribution: the analytic form of the probability function and recursion formulas for computing it, moments and semi-invariants, asymptotics of the distribution, and recursion relations for the derivatives with respect to the parameters. We give the results of model computations showing the set structure of the distribution. One figure. Bibliography: 8 titles. Translated fromProblemy Matematicheskoi Fiziki, 1998, pp. 46–54.     

On Boolean functions with the sum of every two of them being bent

A set of Boolean functions is called a bent set if the sum of any two distinct members is a bent function. We show that any bent set yields a homogeneous system of linked symmetric designs with the same design parameters as those systems derived from Kerdock sets. Further we observe that there are bent sets of size equal to the square root of the Kerdock set size which consist of Boolean functions with arbitrary degrees.     

离散时间马氏决策过程的首达目标准则

本文考虑可数状态离散时间马氏决策过程的首达目标模型的风险概率准则.优化的准则是最小化系统首次到达目标状态集的时间不超过某阈值的风险概率.首先建立最优方程并且证明最优值函数和最优方程的解对应,然后讨论了最优策略的一些性质,并进一步给出了最优平稳策略存在的条件,最后用一个例子说明我们的结果.     

Multiround Unconditionally Secure Authentication

Authentication codes are used to protect communication against a malicious adversary. In this paper we investigate unconditionally secure multiround authentication schemes. In a multiround scheme a message is authenticated by passing back and forth several codewords between the sender and receiver. We define a multiround authentication model and show how to calculate the probability of a successful attack for this model. We prove the security for a 3-round scheme and give a construction for the 3-round scheme based on Reed-Solomom codes. This construction has a very small key size for even extremely large messages. Furthermore, a secure scheme for an arbitrary number of rounds is given. We give a new upper bound for the keys size of an n-round scheme.     

Discrete time Markov chains with interval probabilities

The parameters of Markov chain models are often not known precisely. Instead of ignoring this problem, a better way to cope with it is to incorporate the imprecision into the models. This has become possible with the development of models of imprecise probabilities, such as the interval probability model. In this paper we discuss some modelling approaches which range from simple probability intervals to the general interval probability models and further to the models allowing completely general convex sets of probabilities. The basic idea is that precisely known initial distributions and transition matrices are replaced by imprecise ones, which effectively means that sets of possible candidates are considered. Consequently, sets of possible results are obtained and represented using similar imprecise probability models.We first set up the model and then show how to perform calculations of the distributions corresponding to the consecutive steps of a Markov chain. We present several approaches to such calculations and compare them with respect to the accuracy of the results. Next we consider a generalisation of the concept of regularity and study the convergence of regular imprecise Markov chains. We also give some numerical examples to compare different approaches to calculations of the sets of probabilities.     

Asymptotic Properties of a Nonparametric Regression Function Estimator with Randomly Truncated Data

In this paper, we define a new kernel estimator of the regression function under a left truncation model. We establish the pointwise and uniform strong consistency over a compact set and give a rate of convergence of the estimate. The pointwise asymptotic normality of the estimate is also given. Some simulations are given to show the asymptotic behavior of the estimate in different cases. The distribution function and the covariable’s density are also estimated.     

A Practical Algorithm for Computing a Subadditive Dual Function for Set Partitioning

Recently, a new algorithm for computing an optimal subadditive dual function to an integer program has been proposed. In this paper we show how to apply the algorithm to the set partitioning problem. We give several enhancements to the algorithm and we report computational experiments. The results show that it is tractable to obtain an optimal subadditive function for small and medium size problems. To the best of our knowledge this is the first work that reports computational experiments on computing an optimal subadditive dual function.