Optimization Problem on Permutations with Linear-Fractional Objective Function: Properties of the Set of Admissible Solutions

We consider an optimization problem on permutations with a linear-fractional objective function. We investigate the properties of the domain of admissible solutions of the problem.     

运输问题的合作对策求解方法

产地间或销地间往往存在竞争,在这种情况下,使用运输问题最优化方法是不合理的。因此,从个体理性的视角提出运输问题的合作对策求解方法,方法将运输问题看作是一个博弈问题,各个产地或销地是博弈的局中人,求解其纳什均衡与纳什讨价还价解。在此基础上,说明了运输问题的非合作形式是一个指派问题,并证明指派问题的最优解是一个纳什均衡点。接着,通过实验验证运输问题的最优解是一个纳什讨价还价解,满足产地或销地的自身利益。在此基础上,针对纳什讨价还价解不唯一的问题,从决策者的视角给出最大可能激励成本的计算方法。最后,为弥补纳什讨价还价解不唯一及纳什讨价还价解不允许出现子联盟的缺陷,给出运输收益分配或成本分摊的Shapely值计算方法。     

A New Class of Wilf-Equivalent Permutations

For about 10 years, the classification up to Wilf equivalence of permutation patterns was thought completed up to length 6. In this paper, we establish a new class of Wilf-equivalent permutation patterns, namely, (n – 1, n – 2, n, ) (n – 2, n, n – 1, ) for any S _{n –3}. In particular, at level n = 6, this result includes the only missing equivalence (546213) (465213), and for n = 7 it completes the classification of permutation patterns by settling all remaining cases in S ₇.     

A Probabilistic-Numerical Approximation for an Obstacle Problem Arising in Game Theory

We investigate a two-player zero-sum stochastic differential game in which one of the players has more information on the game than his opponent. We show how to construct numerical schemes for the value function of this game, which is given by the solution of a quasilinear partial differential equation with obstacle.     

风险的动态定量和一个相关的随机对策问题

本文讨论不完全市场中股票收益率不确定时的动态风险度量问题和一个相关的随机对策问题。该动态风险度量可表示为一个随机最优控制问题的值函数,以倒向随机微分方程为工具我们给出了最优目标具有的形式,并给出随机对策问题上值与下值相等的充分条件和鞍点的存在性。     

Collinear Points in Permutations

Consider the following problem: how many collinear triples of points must a transversal of have? This question is connected with venerable issues in discrete geometry. We show that the answer, for n prime, is between (n − 1)/4 and (n − 1)/2, and consider an analogous question for collinear quadruples. We conjecture that the upper bound is the truth and suggest several other interesting problems in this area.Received August 29, 2004     

Adjacent q-Cycles in Permutations

We introduce a new permutation statistic, namely, the number of cycles of length q consisting of consecutive integers, and consider the distribution of this statistic among the permutations of {1, 2, . . . , n}. We determine explicit formulas, recurrence relations, and ordinary and exponential generating functions. A generalization to more than one fixed length is also considered.     

Pattern Avoidance in Multiset Permutations: Bijective Proof

It is well-known that the number of permutations of n letters that avoid a pattern τ of 3 letters is independent of τ. In this note we provide bijective proof that the same result holds for permutations of a multiset. Received August 16, 2006     

制造企业产品质量问题的信号博弈模型

基于制造企业产品质量信息不对称的特点,以制造企业和客户作为博弈方,以客户服务水平作为产品质量信号,建立信号博弈模型,分析信号博弈的三种贝叶斯均衡及其条件,得出了信息不对称情况下制造企业和客户的应对策略.     

Pattern Avoidance in Poset Permutations

We extend the concept of pattern avoidance in permutations on a totally ordered set to pattern avoidance in permutations on partially ordered sets. The number of permutations on P that avoid the pattern p is denoted A v _P (p). We extend a proof of Simion and Schmidt to show that A v _P (132)=A v _P (123) for any poset P, and we exactly classify the posets for which equality holds.     

基于博弈论的小煤矿安全问题分析

安全事故频繁发生是我国小煤矿的现状和特点.文章从小煤矿的内部管理、政府监管及矿工举报三个方面入手,分析了小煤矿安全监管体系中由于行为原因而引起的问题,从而建立了小煤矿安全监管体系中基于监管部门、小煤矿及矿工三方之间的两两博弈模型.并根据博弈模型的纳什均衡解得出能使三方达到均衡并可加强安全监管的几点政策建议.     

基于博弈理论的大学生考试作弊问题分析

考试作弊已经成为一种社会不良现象,在考试过程中,学生、监考与巡考构成了一个复杂的博弈体系.首先针对100名来自不同大学各个年级的同学进行相关网上问卷调查,客观真实的得出影响作弊行为的相关因素,随后利用完全信息静态博弈理论、建立学生与学生、学生与监考、监考与巡考之间的博弈模型,寻找混合策略纳什均衡;利用演化博弈理论,建立学生与学生之间的动态复制方程来找出系统进化向不良状态演化原因,最终基于原因针对性的改进大学生考试制度.     

VC-Dimension of Sets of Permutations

VC-dimension of a set of permutations to be the maximal k such that there exist distinct that appear in A in all possible linear orders, that is, every linear order of is equivalent to the standard order of for at least one permutation . In other words, the VC-dimension of A is the maximal k such that for some the restriction of A to contains all possible linear orders. This is analogous to the VC-dimension of a set of strings. Our main result is that there exists a universal constant C such that any set of permutations with VC-dimension 2 is of size . This is analogous to Sauer's lemma for the case of VC-dimension 2. One corollary of our main result is that any acyclic set of linear orders of is of size , (a set A of linear orders on is called acyclic if no 3 elements appear in A in all 3 orders (i,j,k), (k,i,j) and (j,k,i)). The size of the largest acyclic set of linear orders has interested researchers for many years because it is the largest number of linear orders of n alternatives such that the following is always satisfied: if each one of a set of voters chooses one of these orders as his preference then the majority relation between each two alternatives is transitive. Received August 6, 1998     

Polyominoes Determined by Permutations: Enumeration via Bijections

A permutominide is a set of cells in the plane satisfying special connectivity constraints and uniquely defined by a pair of permutations. It naturally generalizes the concept of permutomino, recently investigated by several authors and from different points of view [1, 2, 4, 6, 7]. In this paper, using bijective methods, we determine the enumeration of various classes of convex permutominides, including, parallelogram, directed convex, convex, and row convex permutominides. As a corollary we have a bijective proof for the number of convex permutominoes, which was still an open problem.     

A Game Related to the Number of Hides Game

In this paper, we study a discrete search game on an array of N ordered cells, with two players having opposite goals: player I (searcher) and player II (hider). Player II has to hide q objects at consecutive cells and player I can search p consecutive cells. The payoff to player I is the number of objects found by him. In some situations, the players need to adopt sophisticated strategies if they are to act optimally.