Construction of a maximal stable bridge in games with simple motions on the plane

It is known that the solvability set (the maximal stable bridge) in a zero-sum differential game with simple motions, fixed terminal time, geometric constraints on the controls of the first and second players, and convex terminal set can be constructed by means of a program absorption operator. In this case, a backward procedure for the construction of t-sections of the solvability set does not need any additional partition times. We establish the same property for a game with simple motions, polygonal terminal set (which is generally nonconvex), and polygonal constraints on the players’ controls on the plane. In the particular case of a convex terminal set, the operator used in the paper coincides with the program absorption operator.     

Sufficient conditions for unique stable sets in three agent pillage games

Pillage games (Jordan, 2006a) have two features that make them richer than cooperative games in either characteristic or partition function form: they allow power externalities between coalitions; they allow resources to contribute to coalitions’ power as well as to their utility. Extending von Neumann and Morgenstern’s analysis of three agent games in characteristic function form to anonymous pillage games, we characterise the core for any number of agents; for three agents, all anonymous pillage games with an empty core represent the same dominance relation. When a stable set exists, and the game also satisfies a continuity and a responsiveness axiom, it is unique and contains no more than 15 elements, a tight bound. By contrast, stable sets in three agent games in characteristic or partition function form may not be unique, and may contain continua. Finally, we provide an algorithm for computing the stable set, and can easily decide non-existence. Thus, in addition to offering attractive modelling possibilities, pillage games seem well behaved and analytically tractable, overcoming a difficulty that has long impeded use of cooperative game theory’s flexibility.     

Comparing partitions of two sets of units based on the same variables

We propose a procedure based on a latent variable model for the comparison of two partitions of different units described by the same set of variables. The null hypothesis here is that the two partitions come from the same underlying mixture model. We define a method of “projecting” partitions using a supervised classification method: once one partition is taken as a reference; the individuals of the second data set are allocated to the clusters of the reference partition; it gives two partitions of the same units of the second data set: the original and the projected one and we evaluate their difference by usual measures of association. The empirical distributions of the association measures are derived by simulation.     

Computational complexity of stable partitions with B-preferences

Consider a special stable partition problem in which the player's preferences over sets to which she could belong are identical with her preferences over the most attractive member of a set and in case of indifference the set of smaller cardinality is preferred. If the preferences of all players over other (individual) players are strict, a strongly stable and a stable partition always exists. However, if ties are present, we show that both the existence problems are NP-complete. These results are very similar to what is known for the stable roommates problem. Received: July 2000/Revised: October 2002 RID="*" ID="*"  This work was supported by the Slovak Agency for Science, contract #1/7465/20 “Combinatorial Structures and Complexity of Algorithms”.     

Combinatorial optimization with 2-joins

A 2-join is an edge cutset that naturally appears in decomposition of several classes of graphs closed under taking induced subgraphs, such as perfect graphs and claw-free graphs. In this paper we construct combinatorial polynomial time algorithms for finding a maximum weighted clique, a maximum weighted stable set and an optimal coloring for a class of perfect graphs decomposable by 2-joins: the class of perfect graphs that do not have a balanced skew partition, a 2-join in the complement, nor a homogeneous pair. The techniques we develop are general enough to be easily applied to finding a maximum weighted stable set for another class of graphs known to be decomposable by 2-joins, namely the class of even-hole-free graphs that do not have a star cutset.We also give a simple class of graphs decomposable by 2-joins into bipartite graphs and line graphs, and for which finding a maximum stable set is NP-hard. This shows that having holes all of the same parity gives essential properties for the use of 2-joins in computing stable sets.     

The Potts model representation and a Robinson–Schensted correspondence for the partition algebra

We construct a correspondence between the set of partitions of a finite set M and the set of pairs of walks to the same vertex on a graph giving the Bratteli diagram of the partition algebra on M. This is the precise analogue of the correspondence between the set of permutations of a finite set and the set of pairs of Young tableaux of the same shape, called the Robinson–Schensted correspondence.     

Equistarable Graphs and Counterexamples to Three Conjectures on Equistable Graphs

Equistable graphs are graphs admitting positive weights on vertices such that a subset of vertices is a maximal stable set if and only if it is of total weight 1. Strongly equistable graphs are graphs such that for every and every nonempty subset T of vertices that is not a maximal stable set, there exist positive vertex weights assigning weight 1 to every maximal stable set such that the total weight of T does not equal c . General partition graphs are the intersection graphs of set systems over a finite ground set U such that every maximal stable set of the graph corresponds to a partition of U . General partition graphs are exactly the graphs every edge of which is contained in a strong clique. In 1994, Mahadev, Peled, and Sun proved that every strongly equistable graph is equistable, and conjectured that the converse holds as well. In 2009, Orlin proved that every general partition graph is equistable, and conjectured that the converse holds as well. Orlin's conjecture, if true, would imply the conjecture due to Mahadev, Peled, and Sun. An “intermediate” conjecture, posed by Miklavi? and Milani? in 2011, states that every equistable graph has a strong clique. The above conjectures have been verified for several graph classes. We introduce the notion of equistarable graphs and based on it construct counterexamples to all three conjectures within the class of complements of line graphs of triangle‐free graphs. We also show that not all strongly equistable graphs are general partition.     

Farsighted stable sets in Hotelling’s location games

We apply the farsighted stable set to two versions of Hotelling’s location games: one with a linear market and another with a circular market. It is shown that there always exists a farsighted stable set in both games, which consists of location profiles that yield equal payoff to all players. This stable set contains location profiles that reflect minimum differentiation as well as those profiles that reflect local monopoly. These results are in contrast to those obtained in the literature that use some variant of Nash equilibrium. While this stable set is unique when the number of players is two, uniqueness no longer holds for both models when the number of players is at least three.     

Individual and group stability in neutral restrictions of hedonic games

We consider a class of coalition formation games called hedonic games, i.e., games in which the utility of a player is completely determined by the coalition that the player belongs to. We first define the class of subset-additive hedonic games and show that they have the same representation power as the class of hedonic games. We then define a restriction of subset-additive hedonic games that we call subset-neutral hedonic games and generalize a result by Bogomolnaia and Jackson (2002) by showing the existence of a Nash stable partition and an individually stable partition in such games. We also consider neutrally anonymous hedonic games and show that they form a subclass of the subset-additive hedonic games. Finally, we show the existence of a core stable partition that is also individually stable in neutrally anonymous hedonic games by exhibiting an algorithm to compute such a partition.     

Stability in coalition formation games

In the context of coalition formation games a player evaluates a partition on the basis of the set she belongs to. For this evaluation to be possible, players are supposed to have preferences over sets to which they could belong. In this paper, we suggest two extensions of preferences over individuals to preferences over sets. For the first one, derived from the most preferred member of a set, it is shown that a strict core partition always exists if the original preferences are strict and a simple algorithm for the computation of one strict core partition is derived. This algorithm turns out to be strategy proof. The second extension, based on the least preferred member of a set, produces solutions very similar to those for the stable roommates problem. Received August 1998/Final version June 20, 2000     

The shrinking principle and the axiom of choice

The axiom of choice is equivalent to the shrinking principle: every indexed cover of a set has a refinement with the same index set which is a partition. A simple and direct proof of this equivalence is given within an elementary fragment of constructive Zermelo–Fraenkel set theory. Variants of the shrinking principle are discussed, and it is related to a similar but different principle formulated by Vaught.     

On Tutte polynomial expansion formulas in perspectives of matroids and oriented matroids

We introduce the active partition of the ground set of an oriented matroid perspective (or morphism, or quotient, or strong map) on a linearly ordered ground set. The reorientations obtained by arbitrarily reorienting parts of the active partition share the same active partition. This yields an equivalence relation for the set of reorientations of an oriented matroid perspective, whose classes are enumerated by coefficients of the Tutte polynomial, and a remarkable partition of the set of reorientations into Boolean lattices, from which we get a short direct proof of a 4-variable expansion formula for the Tutte polynomial in terms of orientation activities. This formula was given in the last unpublished preprint by Michel Las Vergnas; the above equivalence relation and notion of active partition generalize a former construction in oriented matroids by Michel Las Vergnas and the author; and the possibility of such a proof technique in perspectives was announced in the aforementioned preprint. We also briefly highlight how the 5-variable expansion of the Tutte polynomial in terms of subset activities in matroid perspectives comes in a similar way from the known partition of the power set of the ground set into Boolean lattices related to subset activities (and we complete the proof with a property which was missing in the literature). In particular, the paper applies to matroids and oriented matroids on a linearly ordered ground set, and applies to graph and directed graph homomorphisms on a linearly ordered edge-set.     

The shrinking principle and the axiom of choice

The axiom of choice is equivalent to the shrinking principle: every indexed cover of a set has a refinement with the same index set which is a partition. A simple and direct proof of this equivalence is given within an elementary fragment of constructive Zermelo–Fraenkel set theory. Variants of the shrinking principle are discussed, and it is related to a similar but different principle formulated by Vaught.     

On the relationship between Shapley and Owen values

Owen value is an extension of Shapley value for cooperative games when a particular coalition structure or partition of the set of players is considered in addition. In this paper, we will obtain the Shapley value as an average of Owen values over each set of the same kind of coalition structures, i.e., coalition structures with equal number of sets sharing the same size.     

The extended serial correspondence on a rich preference domain

We study the problem of assigning objects to a set of agents. We focus on probabilistic solutions that only take agents’ preferences over objects as input. Importantly, agents may be indifferent among several objects. The “extended serial correspondence” is proposed by Katta and Sethuraman (J Econ Theory 131:231–250, 2006) to solve this problem. As a follow-up to Liu and Pycia (Ordinal efficiency, fairness, and incentives in large markets. Mimeo, 2012) who introduce the notion of profiles with “full support”, we work with two interesting classes of preference profiles: profiles that (i) have rich support on a partition or (ii) are single-peaked with rich support on a partition. For each profile in these classes, an assignment matrix is selected by the extended serial correspondence if and only if it is sd-efficient and sd envy-free. We also provide an asymptotic result.     

Group technology in production management: The short horizon planning level

We consider a set of parts divided into subsets called part types, determined in such a way that the parts belonging to the same part type are manufactured using the same sequence of tasks (i.e. the same working process). We are looking for a partition of the set of part types into subsets called part families, and for a partition of the set of tasks into subsets called production subsystems defined as follows: (1) the number of part families and the number of production subsystems are equal, (2) one (one only one) production subsystem corresponds to each part family, (3) one (and only one) part family corresponds to each production subsystem, (4) the previous partitions minimize the number of tasks performed in a production subsystem different from that which corresponds to the part family containing the part involved. We give a fast algorithm which leads to a good solution depending on the initial set of part families. We also propose an algorithm to find a ‘good’ initial set of part families.     

The rank of the endomorphism monoid of a uniform partition

The rank of a semigroup is the cardinality of a smallest generating set. In this paper we compute the rank of the endomorphism monoid of a non-trivial uniform partition of a finite set, that is, the semigroup of those transformations of a finite set that leave a non-trivial uniform partition invariant. That involves proving that the rank of a wreath product of two symmetric groups is two and then use the fact that the endomorphism monoid of a partition is isomorphic to a wreath product of two full transformation semigroups. The calculation of the rank of these semigroups solves an open question.     

基于属性约简的分类及其应用

约简是粗糙集用于数据分析的重要方法和手段,也是粗糙集理论的核心内容之一.论域U上的等价关系可以确定U的划分,U上的不可区分关系是等价关系.利用不可区分关系定义信息系统的划分协调集及划分约简集,而且证明了划分约简集的判定定理,并将其应用于实际分类问题.     

Asymptotics of pattern avoidance in the Klazar set partition and permutation-tuple settings

We consider asymptotics of set partition pattern avoidance in the sense of Klazar. Our main result derives the asymptotics of the number of set partitions avoiding a given set partition within an exponential factor, which leads to a classification of possible growth rates of set partition pattern classes. We further define a notion of permutation-tuple avoidance, which generalizes notions of Aldred et al. and the usual permutation pattern setting, and similarly determine the number of permutation-tuples avoiding a given tuple to within an exponential factor. We note a seeming connection to previous results on hereditary properties of labelled graphs, prompting the question of if there is a generalization to ordered graphs.     

Edge Coloring of Split Graphs

A split graph is a graph whose vertex set admits a partition into a stable set and a clique. The chromatic indexes for some subsets of split graphs, such as split graphs with odd maximum degree and split-indifference graphs, are known. However, for the general class, the problem remains unsolved. This paper presents new results about the classification problem for split graphs as a contribution in the direction of solving the entire problem for this class.