How to play the one-lie Rényi-Ulam game

The one-lie Rényi-Ulam liar game is a two-player perfect information zero-sum game, lasting q rounds, on the set [n]?{1,…,n}. In each round Paul chooses a subset A⊆[n] and Carole either assigns one lie to each element of A or to each element of [n]?A. Paul wins the original (resp. pathological) game if after q rounds there is at most one (resp. at least one) element with one or fewer lies. We exhibit a simple, unified, optimal strategy for Paul to follow in both games, and use this to determine which player can win for all q,n and for both games.     

The Rényi–Ulam pathological liar game with a fixed number of lies

The q-round Rényi–Ulam pathological liar game with k lies on the set [n]{1,…,n} is a 2-player perfect information zero sum game. In each round Paul chooses a subset A[n] and Carole either assigns 1 lie to each element of A or to each element of [n]A. Paul wins if after q rounds there is at least one element with k or fewer lies. The game is dual to the original Rényi–Ulam liar game for which the winning condition is that at most one element has k or fewer lies. Define to be the minimum n such that Paul can win the q-round pathological liar game with k lies and initial set [n]. For fixed k we prove that is within an absolute constant (depending only on k) of the sphere bound, ; this is already known to hold for the original Rényi–Ulam liar game due to a result of J. Spencer.     

面积定理推广

本文把单位国外ｍ叶半纯函数的面积定理，推广到只假定函数在无穷有ｍ级极点情形．并给出面积大于零的充要条件．     

Definition and properties of cooperative equilibria in a two-player game of infinite duration

A two-player multistage game, with an infinite number of stages is considered. The concepts of overtaking and weakly overtaking payoff sequences are introduced. The class of strategies considered consists of memory strategies, which are based on the past history of the control and the initial state from where the game has been played. Weak equilibria are defined in this class of strategies. It is then shown how such equilibria can be constructed by composing into a trigger strategy a nominal cooperative control sequence and two threat strategies representing the announced retaliation by each player in the case where the other player does not play according to the nominal control. When the threats consists of a feedback equilibrium pair, the resulting cooperative equilibrium is perfect. Another result shows that, if each player can use a most effective threat based on a saddle-point feedback strategy, then any weak equilibrium in the class of memory strategies is in some sense related to this particular kind of equilibrium in the class of trigger strategies.Dedicated to G. LeitmannThis research was supported by SSHRC Grant No. 410-81-0722 and FCAC Grant No. EQ-428 to the first author. This research has also been made possible by a financial support from the University of Puerto Rico.     

The Sprague-Grundy function of the game Euclid

We show that the Sprague-Grundy function of the game Euclid is given by g(x,y)=⌊|y/x-x/y|⌋ for x,y≥1.     

The game chromatic index of wheels

We prove that the game chromatic index of n-wheels is n for n≥6.     

A note on Buczolich's solution of the Weil gradient problem: a construction based on an infinite game

Summary Using an infinite game approach we reprove Buczolich's result that there exists a differentiable function f such that ∇f(0) = 0 and |∇ f |≧1 a.e.     

The semireactive bargaining set of a cooperative game

The semireactive bargaining set, a solution for cooperative games, is introduced. This solution is in general a subsolution of the bargaining set and a supersolution of the reactive bargaining set. However, on various classes of transferable utility games the semireactive and the reactive bargaining set coincide. The semireactive prebargaining set on TU games can be axiomatized by one-person rationality, the reduced game property, a weak version of the converse reduced game property with respect to subgrand coalitions, and subgrand stability. Furthermore, it is shown that there is a suitable weakening of subgrand stability, which allows to characterize the prebargaining set. Replacing the reduced game by the imputation saving reduced game and employing individual rationality as an additional axiom yields characterizations of both, the bargaining set and the semireactive bargaining set. Received September 2000/Revised version June 2001     

The Shapley value for the probability game

The main goal of this paper is to introduce the probability game. On one hand, we analyze the Shapley value by providing an axiomatic characterization. We propose the so-called independent fairness property, meaning that for any two players, the player with larger individual value gets a larger portion of the total benefit. On the other, we use the Shapley value for studying the profitability of merging two agents.     

A bargaining game model for measuring performance of two-stage network structures

Data envelopment analysis (DEA) is a method for measuring the efficiency of peer decision making units (DMUs), where the internal structures of DMUs are treated as a black-box. Recently DEA has been extended to examine the efficiency of DMUs that have two-stage network structures or processes, where all the outputs from the first stage are intermediate measures that make up the inputs to the second stage. The resulting two-stage DEA model not only provides an overall efficiency score for the entire process, but also yields an efficiency score for each of the individual stages. The current paper develops a Nash bargaining game model to measure the performance of DMUs that have a two-stage structure. Under Nash bargaining theory, the two stages are viewed as players and the DEA efficiency model is a cooperative game model. It is shown that when only one intermediate measure exists between the two stages, our newly developed Nash bargaining game approach yields the same results as applying the standard DEA approach to each stage separately. Two real world data sets are used to demonstrate our bargaining game model.     

位置参数分布族中Fiducial分布与后验分布的关系

本文考虑本质位置参数分布族中,参数的Fiducial分布与后验分布的等同问题．首先讨论了如何给出Fiducial分布,分析结果表明以分布函数形式给出Fiducial分布要比密度函数形式合理,同时,证明了所给的Fiducial分布具有频率性质．然后,研究在参数受到单侧限制时,Fiducial分布与后验分布等同的问题,给出的充要条件是分布族为指数分布族,此时,先验分布是一个广义先验分布,它不能被Lebesgue测度控制．最后,证明了在参数限制在一个有限区间内时,Fiducial分布与任何先验(包括广义先验分布)下的后验分布不等同．     

具随机折现的博弈期权定价问题

对具随机折现的博弈期权定价问题进行了研究,在满足一个可积性条件的情况下,借用过份函数等工具给出了期权价格的表达式和买卖双方的最优停止策略.对于不满足可积性条件的情况,推广了相关文献的结果,并给出了τ＊存在的条件.最后给出了一个例子.     

The pairwise egalitarian solution for the assignment game

In this note we consider the pairwise egalitarian solution (Sánchez-Soriano, 2003) on the domain of assignment games and study its relation with the core. Strengthening the dominant diagonal condition (Solymosi and Raghavan, 2001), we introduce k-dominant diagonal assignment games (k≥1), analyzing for which values of k the pairwise egalitarian solution fulfills the standards of fairness represented by the Lorenz domination and the kernel. We also characterize the Thompson’s fair division point (Thompson, 1981) for arbitrary assignment games.     

Online sum-paintability: The slow-coloring game

The slow-coloring game is played by Lister and Painter on a graph $G$. On each round, Lister marks a nonempty subset $M$ of the uncolored vertices, scoring $\left|M\right|$ points. Painter then gives a color to a subset of $M$ that is independent in $G$. The game ends when all vertices are colored. Painter and Lister want to minimize and maximize the total score, respectively. The best score that each player can guarantee is the sum-color cost of $G$, written $\stackrel{?}{s}\left(G\right)$. The game is an online variant of online sum list coloring.We prove $\frac{\left|V\left(G\right)\right|}{2\alpha \left(G\right)}+\frac{1}{2}\le \frac{\stackrel{?}{s}\left(G\right)}{\left|V\left(G\right)\right|}\le max\left\{\frac{\left|V\left(H\right)\right|}{\alpha \left(H\right)}:H?G\right\}$, where $\alpha \left(G\right)$ is the independence number, and we study when equality holds in the bounds. We compute $\stackrel{?}{s}\left(G\right)$ for graphs with $\alpha \left(G\right)=2$. Among $n$-vertex trees, we prove that $\stackrel{?}{s}$ is minimized by the star and maximized by the path. We also study $\stackrel{?}{s}\left(K_{r,s}\right)$.     

Tensor roots of isomorphisms and weak limits of transformations

We prove that two transformations S and T are isomorphic if their Cartesian squares are isomorphic, under the assumption that the sequence of powers of T converges weakly to a polynomial.     

The Orlicz-Pettis theorem for topological Riesz spaces

A finitely additive vector measure from a -ring to a Riesz space is countably additive (exhaustive) for all Hausdorff Lebesgue topologies on the range space, or for none of them. In particular, subseries convergent series are the same for all Hausdorff Lebesgue topologies on a Riesz space.

     

Schmidt's game, badly approximable matrices and fractals

We prove that for every M,N∈N, if τ is a Borel, finite, absolutely friendly measure supported on a compact subset K of RMN, then K∩BA(M,N) is a winning set in Schmidt's game sense played on K, where BA(M,N) is the set of badly approximable M×N matrices. As an immediate consequence we have the following application. If K is the attractor of an irreducible finite family of contracting similarity maps of RMN satisfying the open set condition (the Cantor's ternary set, Koch's curve and Sierpinski's gasket to name a few known examples), then

dimK=dimK∩BA(M,N).