Game theory with translucent players

A traditional assumption in game theory is that players are opaque to one another—if a player changes strategies, then this change in strategies does not affect the choice of other players’ strategies. In many situations this is an unrealistic assumption. We develop a framework for reasoning about games where the players may be translucent to one another; in particular, a player may believe that if she were to change strategies, then the other player would also change strategies. Translucent players may achieve significantly more efficient outcomes than opaque ones. Our main result is a characterization of strategies consistent with appropriate analogues of common belief of rationality. Common Counterfactual Belief of Rationality (CCBR) holds if (1) everyone is rational, (2) everyone counterfactually believes that everyone else is rational (i.e., all players i believe that everyone else would still be rational even if i were to switch strategies), (3) everyone counterfactually believes that everyone else is rational, and counterfactually believes that everyone else is rational, and so on. CCBR characterizes the set of strategies surviving iterated removal of minimax-dominated strategies, where a strategy \(\sigma \) for player i is minimax dominated by \(\sigma '\) if the worst-case payoff for i using \(\sigma '\) is better than the best possible payoff using \(\sigma \).     

General Theorem on a Finite Support of Mixed Strategy in the Theory of Zero-Sum Games

A theorem related to the theory of zero-sum games is proved. Rather general assumptions on the payoff function are found that are sufficient for an optimal strategy of one of the players to be chosen in the class of mixed strategies concentrated in at most m + 1 points if the opponent chooses a pure strategy in a finite-dimensional convex compact set and m is its dimension. This theorem generalizes results of several authors, starting from Bohnenblust, Karlin, and Shapley (1950).     

Stabilizing network bargaining games by blocking players

Cooperative matching games (Shapley and Shubik) and Network bargaining games (Kleinberg and Tardos) are games described by an undirected graph, where the vertices represent players. An important role in such games is played by stable graphs, that are graphs whose set of inessential vertices (those that are exposed by at least one maximum matching) are pairwise non adjacent. In fact, stable graphs characterize instances of such games that admit the existence of stable outcomes. In this paper, we focus on stabilizing instances of the above games by blocking as few players as possible. Formally, given a graph G we want to find a minimum cardinality set of vertices such that its removal from G yields a stable graph. We give a combinatorial polynomial-time algorithm for this problem, and develop approximation algorithms for some NP-hard weighted variants, where each vertex has an associated non-negative weight. Our approximation algorithms are LP-based, and we show that our analysis are almost tight by giving suitable lower bounds on the integrality gap of the used LP relaxations.     

Brochette percolation

We study bond percolation on the square lattice with one-dimensional inhomogeneities. Inhomogeneities are introduced in the following way: A vertical column on the square lattice is the set of vertical edges that project to the same vertex on Z. Select vertical columns at random independently with a given positive probability. Keep (respectively remove) vertical edges in the selected columns, with probability p (respectively 1?p). All horizontal edges and vertical edges lying in unselected columns are kept (respectively removed) with probability q (respectively 1 ? q). We show that, if p > p_c(Z²) (the critical point for homogeneous Bernoulli bond percolation), then q can be taken strictly smaller than p_c(Z²) in such a way that the probability that the origin percolates is still positive.     

A <Emphasis Type="Italic">q</Emphasis>-player impartial avoidance game for generating finite groups

We study a q-player variation of the impartial avoidance game introduced by Anderson and Harary, where q is a prime. The game is played by the q players taking turns selecting previously-unselected elements of a finite group. The losing player is the one who selects an element that causes the set of jointly-selected elements to be a generating set for the group, with the previous player winning. We introduce a ranking system for the other players to prevent coalitions. We describe the winning strategy for these games on cyclic, nilpotent, dihedral, and dicyclic groups.     

Additive properties of product sets in the field $$ \mathbb{F}_{p^2 } $$

For given positive integer n and ε > 0 we consider an arbitrary nonempty subset A of a field consisting of p ² elements such that its cardinality exceeds p ^2/n?ε . We study the possibility to represent an arbitrary element of the field as a sum of at most N(n, ε) elements from the nth degree of the set A. An upper estimate for the number N(n, ε) is obtained when it is possible.     

Uniform approximation of continuous functions by probability functions of Boolean bases

Random Boolean expressions obtained by random and independent substitution of the constants 1, 0 with probabilities p, 1 ? p, respectively, into random non-iterated formulas over a given basis are considered. The limit of the probability of appearance of expressions with the value 1 under unrestricted growth of the complexity of expressions, which is called the probability function, is considered. It is shown that for an arbitrary continuous function f(p) mapping the segment [0, 1] into itself there exists a sequence of bases whose probability functions uniformly approximate the function f(p) on the segment [0, 1].     

Disentangling price,risk and model risk: V&amp;R measures

We propose a method to assess the intrinsic risk carried by a financial position X when the agent faces uncertainty about the pricing rule assigning its present value. Our approach is inspired by a new interpretation of the quasiconvex duality in a Knightian setting, where a family of probability measures replaces the single reference probability and is then applied to value financial positions. Diametrically, our construction of Value and Risk measures is based on the selection of a basket of claims to test the reliability of models. We compare a random payoff X with a given class of derivatives written on X, and use these derivatives to “test” the pricing measures. We further introduce and study a general class of Value and Risk measures \( R(p,X,\mathbb {P})\) that describes the additional capital that is required to make X acceptable under a probability \(\mathbb {P}\) and given the initial price p paid to acquire X.     

Games with a permission structure - A survey on generalizations and applications

In the field of cooperative games with restricted cooperation, various restrictions on coalition formation are studied. The most studied restrictions are those that arise from restricted communication and hierarchies. This survey discusses several models of hierarchy restrictions and their relation with communication restrictions. In the literature, there are results on game properties, Harsanyi dividends, core stability, and various solutions that generalize existing solutions for TU-games. In this survey, we mainly focus on axiomatizations of the Shapley value in different models of games with a hierarchically structured player set, and their applications. Not only do these axiomatizations provide insight in the Shapley value for these models, but also by considering the types of axioms that characterize the Shapley value, we learn more about different network structures. A central model of games with hierarchies is that of games with a permission structure where players in a cooperative transferable utility game are part of a permission structure in the sense that there are players that need permission from other players before they are allowed to cooperate. This permission structure is represented by a directed graph. Generalizations of this model are, for example, games on antimatroids, and games with a local permission structure. Besides discussing these generalizations, we briefly discuss some applications, in particular auction games and hierarchically structured firms.     

Independence numbers of random subgraphs of a distance graph

We consider the so-called distance graph G(n, 3, 1), whose vertices can be identified with three-element subsets of the set {1, 2,..., n}, two vertices being joined by an edge if and only if the corresponding subsets have exactly one common element. We study some properties of random subgraphs of G(n, 3, 1) in the Erd?s–Rényi model, in which each edge is included in the subgraph with some given probability p independently of the other edges. We find the asymptotics of the independence number of a random subgraph of G(n, 3, 1).     

Security games on matroids

Two players, the Defender and the Attacker play the following game. A matroid \(M=(S,\mathcal {I})\), a weight function \(d:S\rightarrow \mathbb {R}^+\) and a cost function \(c:S\rightarrow \mathbb {R}\) are given. The Defender chooses a base B of the matroid M and the Attacker chooses an element \(s\in S\) of the ground set. In all cases, the Attacker pays the Defender the cost of attack c(s). Besides that, if \(s\in B\) then the Defender pays the Attacker the amount d(s); if, on the other hand, \(s\notin B\) then there is no further payoff. Special cases of this two-player, zero-sum game were considered and solved in various security-related applications. In this paper we show that it is also possible to compute Nash-equilibrium mixed strategies for both players in strongly polynomial time in the above general matroid setting. We also consider a further generalization where common bases of two matroids are chosen by the Defender and apply this to define and efficiently compute a new reliability metric on digraphs.     

On Degrees of Growth of Finitely Generated Groups

We prove that for an arbitrary function ρ of subexponential growth there exists a group G of intermediate growth whose growth function satisfies the inequality v _G,S (n) ? ρ(n) for all n. For every prime p, one can take G to be a p-group; one can also take a torsion-free group G. We also discuss some generalizations of this assertion.     

Unit-sphere games

This paper introduces a class of games, called unit-sphere games, in which strategies are real vectors with unit 2-norms (or, on a unit-sphere). As a result, they should no longer be interpreted as probability distributions over actions, but rather be thought of as allocations of one unit of resource to actions and the payoff effect on each action is proportional to the square root of the amount of resource allocated to that action. The new definition generates a number of interesting consequences. We first characterize the sufficient and necessary condition under which a two-player unit-sphere game has a Nash equilibrium. The characterization reduces solving a unit-sphere game to finding all eigenvalues and eigenvectors of the product matrix of individual payoff matrices. For any unit-sphere game with non-negative payoff matrices, there always exists a unique Nash equilibrium; furthermore, the unique equilibrium is efficiently reachable via Cournot adjustment. In addition, we show that any equilibrium in positive unit-sphere games corresponds to approximate equilibria in the corresponding normal-form games. Analogous but weaker results are obtained in n-player unit-sphere games.     

Optimal Linear Bernoulli Factories for Small Mean Problems

Suppose a coin with unknown probability p of heads can be flipped as often as desired. A Bernoulli factory for a function f is an algorithm that uses flips of the coin together with auxiliary randomness to flip a single coin with probability f(p) of heads. Applications include perfect sampling from the stationary distribution of certain regenerative processes. When f is analytic, the problem can be reduced to a Bernoulli factory of the form f(p) = C p for constant C. Presented here is a new algorithm that for small values of C p, requires roughly only C coin flips. From information theoretic considerations, this is also conjectured to be (to first order) the minimum number of flips needed by any such algorithm. For large values of C p, the new algorithm can also be used to build a new Bernoulli factory that uses only 80 % of the expected coin flips of the older method. In addition, the new method also applies to the more general problem of a linear multivariate Bernoulli factory, where there are k coins, the kth coin has unknown probability p _k of heads, and the goal is to simulate a coin flip with probability C ₁ p ₁+? + C _k p _k of heads.     

Sharp Weak Type Inequalities for Fractional Integral Operators

Suppose that d≥1 is an integer, α∈(0,d) is a fixed parameter and let I _α be the fractional integral operator associated with d-dimensional Walsh-Fourier series on (0,1] ^d . Let p, q be arbitrary numbers satisfying the conditions 1≤p<d/α and 1/q=1/p?α/d. We determine the optimal constant K, which depends on α, d and p, such that for any f∈L ^p ((0,1] ^d ) we have

$$ ||I_{\alpha } f||_{L^{q,\infty }((0,1]^{d})}\leq K||f||_{L^{p}((0,1]^{d})}. $$

In fact, we shall prove this inequality in the more general context of probability spaces equipped with a regular tree-like structures. This allows us to obtain this result also for non-integer dimension. The proof exploits a certain modification of the so-called Bellman function method and appropriate interpolation-type arguments. We also present a sharp weighted weak-type bound for I _α , which can be regarded as a version of the Muckenhoupt-Wheeden conjecture for fractional integral operators.

     

Some related paradoxes of queuing theory: new cases and a unifying explanation

In this paper, we study a number of closely related paradoxes of queuing theory, each of which is based on the intuitive notion that the level of congestion in a queuing system should be directly related to the stochastic variability of the arrival process and the service times. In contrast to such an expectation, it has previously been shown that, in all H _k /G/1 queues, PW (the steady-state probability that a customer has to wait for service) decreases when the service-time becomes more variable. An analagous result has also been proved for p_loss (the steady-state probability that a customer is lost) in all H_k/G/1 loss systems. Such theoretical results can be seen, in this paper, to be part of a much broader scheme of paradoxical behaviour which covers a wide range of queuing systems. The main aim of this paper is to provide a unifying explanation for these kinds of behaviour. Using an analysis based on a simple, approximate model, we show that, for an arbitrary set of n GI/G_k/1 loss systems (k=1,..., n), if the interarrival-time distribution is fixed and ‘does not differ too greatly’ from the exponential distribution, and if the n systems are ordered in terms of their p_loss values, then the order that results whenever c_A<1 is the exact reverse of the order that results whenever c_A>1, where c_A is the coefficient of variation of the interarrival time. An important part of the analysis is the insensitivity of the p_loss value in an M/G/1 loss system to the choice of service-time distribution, for a given traffic intensity. The analysis is easily generalised to other queuing systems for which similar insensitivity results hold. Numerical results are presented for paradoxical behaviour of the following quantities in the steady state: p_loss in the GI/G/1 loss system; PW and W _q (the expected queuing time of customers) in the GI/G/1 queue; and p_K (the probability that all K machines are in the failed state) in the GI/G/r machine interference model. Two of these examples of paradoxical behaviour have not previously been reported in the literature. Additional cases are also discussed.     

A New Method of Approximating the Probability of Matching Common Words in Multiple Random Sequences

In this paper we consider R independent sequences of length T formed by independent, not necessarily uniformly distributed letters drawn from a finite alphabet. We first develop a new and efficient method of calculating the expectation \(\mathbb{E}(N_{R}) = \mathbb{E}(N_{R}(m,T))\) of the number of distinct words of length m, N _R (m, T), which are common to R such sequences. We then consider the case of four uniformly distributed letters. We determine a b _R ?=?b _R (m, T)?≥?0 such that the interval \([\mathbb{E}(N_{R}) - b_{R}; \mathbb{E}(N_{R})]\) contains the probability p _R ?=??(N _R ?≥?1) that there exists a word of length m common to the R sequences. We show that \(b_{R} \approx 0.07\mathbb{E}(N_{R})\) if R?=?3 and \(b_{R} \leq 0.05 \mathbb{E}(N_{R})\) if R?≥?4. Thus, for unusual common words, i.e. such that p _R is small, E(N _R ) provides a very accurate approximation of this probability. We then compare numerically the intervals \([\mathbb{E}(N_{R})-b_{R}, \mathbb{E}(N_{R})]\) with former approximations of p _R provided by Karlin and Ost (Ann Probab 16:535–563, 1988) and Naus and Sheng (Bull Math Biol 59(3):483–495, 1997).     

Algorithmic tests and randomness with respect to a class of measures

This paper offers some new results on randomness with respect to classes of measures, along with a didactic exposition of their context based on results that appeared elsewhere. We start with the reformulation of the Martin-Löf definition of randomness (with respect to computable measures) in terms of randomness deficiency functions. A formula that expresses the randomness deficiency in terms of prefix complexity is given (in two forms). Some approaches that go in another direction (from deficiency to complexity) are considered. The notion of Bernoulli randomness (independent coin tosses for an asymmetric coin with some probability p of head) is defined. It is shown that a sequence is Bernoulli if it is random with respect to some Bernoulli measure B _p . A notion of “uniform test” for Bernoulli sequences is introduced which allows a quantitative strengthening of this result. Uniform tests are then generalized to arbitrary measures. Bernoulli measures B _p have the important property that p can be recovered from each random sequence of B _p . The paper studies some important consequences of this orthogonality property (as well as most other questions mentioned above) also in the more general setting of constructive metric spaces.     

Algorithms with high order convergence speed for blind source extraction

A rigorous convergence analysis for the fixed point ICA algorithm of Hyvärinen and Oja is provided and a generalization of it involving cumulants of an arbitrary order is presented. We consider a specific optimization problem OP(p), p>3, integer, arising from a Blind Source Extraction problem (BSE) and prove that every local maximum of OP(p) is a solution of (BSE) in sense that it extracts one source signal from a linear mixture of unknown statistically independent signals. An algorithm for solving OP(p) is constructed, which has a rate of convergence p?1.