Sufficient conditions for existence of extrema in linear programming

It is shown that, on a closed convex subset X of a real Hausdorff locally convex space E, a continuous linear functional x′ on E has an extremum at an extreme point of X, provided X contains no line and X ∩ (x′)^?1 (λ₀) is non-empty and weakly compact for some real λ₀. It is also shown that any weakly locally compact closed convex subset of E that contains no line is the sum of its asymptotic cone and the closed convex hull of its extreme points.     

Involutory decomposition of a group and twisted subsets with few involutions

A subset K of some group C is called twisted if 1 ∈ K and x, y ∈ K implies that xy ^?1 x belongs to K. We use the concept of twisted subset to investigate and generalize the concept of involutory decomposition of a group. A group is said to admit involutory decomposition if it contains some involution such that the group is the product of the centralizer of the involution and the set of elements inverted by the involution. We study the twisted subsets with at most one involution. We prove that if a twisted subset has no involutions at all then it generates a subgroup of odd order.     

An efficient algorithm for voting sequences

The chaos theorems show that given almost any alternatives x and y, there exists voting sequence from x to y. However, proofs of such results have been purely existential; that is, there is no algorithm by which such a voting path can be constructed. In this paper, we present such an algorithm for one standard example. Furthermore, it is shown that the algorithm has the property that the voting sequence involves the fewest possible number of steps.     

Multivalued social choice functions and strategic manipulation with counterthreats

In this paper, we examine the manipulability properties of social decision rules which select a non-empty subset of the set of alternatives. Assuming that if an individual prefers x to y, then he prefers the outcome set {x, y} to {y}, and also {x} to {x, y}, we show that a wide class of scf's which allow ties even in pairwise choice violates one of the weakest notions of strategyproofness — a single individual can profitably misrepresent his preferences, even when he takes into account the possibility of countercoalitions. This class of scf's also violates exact consistency — no equilibrium situation gives the same outcome set as the ‘true profile’.     

Inverted orders for monotone scoring rules

When each of n judges ranks a set A of m objects from best to worst, and s=(s₁,…,s_m) is a decreasing sequence of real numbers, the collective ranking determined by s orders the objects in A according to their total scores. The total score of x equals s_p times the number of judges who rank x in pth place, summed over p.For normalization purposes, let S_m denote the set of all decreasing s=(s₁,…,s_m) for which s_{m ? 1}=1 and s_m=0. Given any m ? 3, we show firstthat if s and s′ in S_m are not identical, then some profile of judges' rankings yields a linear collective order for s′ that is the reverse or dual of the linear collective order for s.We then consider reversals in collective rankings when one object is removed from A. Suppose s is in S_m and t is in S_{m ? 1}, with m ≥ 3. A simple constructive proof shows that there is a profile of judges' rankings on A which yields a collective linear order for s such that, when any pre-specified object in A is removed, t yields the reverse ranking on the remaining m ? 1 objects. More detailed results are derived for m=3, and shown to depend on the nature of s=(s₁, 1, 0). In particular, the sum-of-ranks procedure with s₁=2 permits fewer reversals than any other s₁>1.     

Classifying efficient alternatives in SMAA using cross confidence factors

Stochastic multicriteria acceptability analysis (SMAA) is a family of methods for aiding multicriteria group decision making. These methods are based on exploring the weight space in order to describe the preferences that make each alternative the most preferred one. The main results of the analysis are rank acceptability indices, central weight vectors and confidence factors for different alternatives. The rank acceptability indices describe the variety of different preferences resulting in a certain rank for an alternative; the central weight vectors represent the typical preferences favouring each alternative; and the confidence factors measure whether the criteria data are sufficiently accurate for making an informed decision.In some cases, when the problem involves a large number of efficient alternatives, the analysis may fail to discriminate between them. This situation is revealed by low confidence factors. In this paper we develop cross confidence factors, which are based on computing confidence factors for alternatives using each other’s central weight vectors. The cross confidence factors can be used for classifying efficient alternatives into sets of similar and competing alternatives. These sets are related to the concept of reference sets in Data Envelopment Analysis (DEA), but generalized for stochastic models. Forming these sets is useful when trying to identify one or more most preferred alternatives, or suitable compromise alternatives. The reference sets can also be used for evaluating whether criteria need to be measured more accurately, and at which alternatives the measurements should be focused. This may cause considerable savings in measurement costs. We demonstrate the use of the cross confidence factors and reference sets using a real-life example.     

Dictators on blocks: Generalizations of social choice impossibility theorems

This paper extends impossibility theorems of Arrow and others to cases in which social comparisons between alternatives in a set X of social alternatives may be made only for each pair {x, y} in a certain subset of distinct pairs taken from X. With E the set of pairs within which social comparisons may be made, G = (X, E) is an undirected graph without loops. The social comparison between x and y for {x, y} ∈ E is to be based on the preferences of individuals in a finite society S. Each individual is presumed to prefer x to y or prefer y to x (not both) for every {x, y} ∈ E and may hold any preference relation that does not cycle in G. A profile is an assignment of one such relation to each individual in S. The paper examines binary social comparison procedures which map each profile into a social preference relation over the pairs in E, subject to x socially preferred to y whenever {x, y} ∈ E and everyone in S prefers x to y. Individual i ∈ S is a dictator [weak dictator] on {x, y} ∈ E iff x is socially preferred to y [x ranks as high as y socially] whenever i prefers x to y, and similarly with x and y interchanged, regardless of the preferences of the other individuals in S. An individual is a dictator [weak dictator] on a subgraph of G iff he is a dictator [weak dictator] on every edge in the subgraph. Under each of three ordering conditions on social preferences, there is a dictator or weak dictator on every block of G which has three or more points, different blocks can have different dictators, and bridges in E need not have dictators.     

The complexity of nonrepetitive coloring

A coloring of a graph is nonrepetitive if the graph contains no path that has a color pattern of the form xx (where x is a sequence of colors). We show that determining whether a particular coloring of a graph is nonrepetitive is coNP-hard, even if the number of colors is limited to four. The problem becomes fixed-parameter tractable, if we only exclude colorings xx up to a fixed length k of x.     

Ordinal definable subsets of singular cardinals

A remarkable result by Shelah states that if κ is a singular strong limit cardinal of uncountable cofinality, then there is a subset x of κ such that HOD_x contains the power set of κ. We develop a version of diagonal extender-based supercompact Prikry forcing, and use it to show that singular cardinals of countable cofinality do not in general have this property, and in fact it is consistent that for some singular strong limit cardinal κ of countable cofinality κ⁺ is supercompact in HOD_x for all x ? κ.     

Condorcet winner configurations of linear networks

We consider the problem of locating a fixed number of facilities along a line to serve n players. We model this problem as a cooperative game and assume that any locational configuration can be eventually disrupted through a strict majority of players voting for an alternative configuration. A solution of such a voting location problem is called a Condorcet winner configuration. In this article, we state three necessary and one sufficient condition for a configuration to be a Condorcet winner. Consequently, we propose a fast algorithm which enables us to verify whether a given configuration is a Condorcet winner, and can be efficiently used also for computing the (potentially empty) set of all Condorcet winner configurations.     

Denjoy-Wolff theorems, Hilbert metric nonexpansive maps and reproduction-decimation operators

Let K be a closed cone with nonempty interior in a Banach space X. Suppose that is order-preserving and homogeneous of degree one. Let be a continuous, homogeneous of degree one map such that q(x)>0 for all x∈K?{0}. Let T(x)=f(x)/q(f(x)). We give conditions on the cone K and the map f which imply that there is a convex subset of ∂K which contains the omega limit set ω(x;T) for every x∈intK. We show that these conditions are satisfied by reproduction-decimation operators. We also prove that ω(x;T)⊂∂K for a class of operator-valued means.     

On the parity of the partition function

Let N be the set of all positive integers and D a subset of N. Let p(D,n) be the number of partitions of n with parts in D and let |D(x)| denote the number of elements of D not exceeding x. It is proved that if D is an infinite subset of N such that p(D,n) is even for all n?n₀, then |D(x)|?logx/log2−logn₀/log2. Moreover, if D is an infinite subset of N such that p(D,n) is odd for all n?n₀ and , then |D(x)|?logx/log2−logn₀/log2. These lower bounds are essentially the best possible.     

Romanoff theorem in a sparse set

Let A be any subset of positive integers,and P the set of all positive primes.Two of our results are:(a) the number of positive integers which are less than x and can be represented as 2k + p(resp.p-2k) with k ∈ A and p ∈ P is more than 0.03A(log x/log 2)π(x) for all sufficiently large x;(b) the number of positive integers which are less than x and can be represented as 2q + p with p,q ∈ P is(1 + o(1))π(log x/log 2)π(x).Four related open problems and one conjecture are posed.     

Tightness games with bounded finite selections

For a topological space X and a point x ∈ X, consider the following game—related to the property of X being countably tight at x. In each inning n ∈ ω, the first player chooses a set A _n that clusters at x, and then the second player picks a point a _n ∈ A _n ; the second player is the winner if and only if \(x \in \overline {\left\{ {{a_n}:n \in \omega } \right\}} \).In this work, we study variations of this game in which the second player is allowed to choose finitely many points per inning rather than one, but in which the number of points they are allowed to choose in each inning has been fixed in advance. Surprisingly, if the number of points allowed per inning is the same throughout the play, then all of the games obtained in this fashion are distinct. We also show that a new game is obtained if the number of points the second player is allowed to pick increases at each inning.     

Monochromatic sinks in nearly transitive arc-colored tournaments

Let T be the set of all arc-colored tournaments, with any number of colors, that contain no rainbow 3-cycles, i.e., no 3-cycles whose three arcs are colored with three distinct colors. We prove that if T∈T and if each strong component of T is a single vertex or isomorphic to an upset tournament, then T contains a monochromatic sink. We also prove that if T∈T and T contains a vertex x such that T−x is transitive, then T contains a monochromatic sink. The latter result is best possible in the sense that, for each n≥5, there exists an n-tournament T such that (T−x)−y is transitive for some two distinct vertices x and y in T, and T can be arc-colored with five colors such that T∈T, but T contains no monochromatic sink.     

A distributed social choice protocol for combinatorial domains

In this paper, we study the problem of collective decision-making over combinatorial domains, where the set of possible alternatives is a Cartesian product of (finite) domain values for each of a given set of variables, and these variables are not preferentially independent. Due to the large alternative space, most common rules for social choice cannot be directly applied to compute a winner. In this paper, we introduce a distributed protocol for collective decision-making in combinatorial domains, which enjoys the following desirable properties: (i) the final decision chosen is guaranteed to be a Smith member; (ii) it enables distributed decision-making and works under incomplete information settings, i.e., the agents are not required to reveal their preferences explicitly; (iii) it significantly reduces the amount of dominance testings (individual outcome comparisons) that each agent needs to conduct, as well as the number of pairwise comparisons; (iv) it is sufficiently general and does not restrict the choice of preference representation languages.     

Algebraic function fields with small class number

It is proved that there is no congruence function field of genus 4 over GF(2) which has no prime of degree less than 4 and precisely one prime of degree 4. This shows the nonexistence of function fields of genus 4 with class number one and gives an example of an isogeny class of abelian varieties which contains no jacobian. It is shown that, up to isomorphism, there are two congruence function fields of genus 3 with class number one. It follows that there are seven nonisomorphic function fields of genus different from zero with class number one. Congruence function fields with class number 2 are fully classified. Finally, it is proved that there are eight imaginary quadratic function fields $\text{F}\text{K(x)}$ for which the integral closure of K[x] in F has class number 2.     

A multiple criteria ranking method based on game cross-evaluation approach

The application of Data Envelopment Analysis (DEA) as an alternative multiple criteria decision making (MCDM) tool has been gaining more attentions in the literatures. Doyle (Organ. Behav. Hum. Decis. Process. 62(1):87?C100, 1995) presents a method of multi-attribute choice based on an application of DEA. In the first part of his method, the straightforward DEA is considered as an idealized process of self-evaluation in which each alternative weighs the attributes in order to maximize its own score (or desirability) relative to the other alternatives. Then, in the second step, each alternative applies its own DEA-derived best weights to each of the other alternatives (i.e., cross-evaluation), then the average of the cross-evaluations that get placed on an alternative is taken as an index of its overall score. In some cases of multiple criteria decision making, direct or indirect competitions exist among the alternatives, while the factor of competition is usually ignored in most of MCDM settings. This paper proposes an approach to evaluate and rank alternatives in MCDM via an extension of DEA method, namely DEA game cross-efficiency model in Liang, Wu, Cook and Zhu (Oper. Res. 56(5):1278?C1288, 2008b), in which each alternative is viewed as a player who seeks to maximize its own score (or desirability), under the condition that the cross-evaluation scores of each of other alternatives does not deteriorate. The game cross-evaluation score is obtained when the alternative??s own maximized scores are averaged. The obtained game cross-evaluation scores are unique and constitute a Nash equilibrium point. Therefore, the results and rankings based upon game cross-evaluation score analysis are more reliable and will benefit the decision makers.     

A characterization of fuzzy subgroups

An ordinary subgroup of a group G is (1) a subset of G, (2) closed under the group operation. In a fuzzy subgroup it is precisely these two notions that lose their deterministic character. A fuzzy subgroup μ of a group (G,·) associates with each group element a number, the larger the number the more certainly that element belongs to the fuzzy subgroup. The closure property is captured by the inequality μ(x · y)?T(μ(x), μ(y)). In A. Rosenfeld's original definition, T was the function ‘minimum’. However, any t-norm T provides a meaningful generalization of the closure property. Two classes of fuzzy subgroups are investigated. The fuzzy subgroups in one class are subgroup generated, those in the other are function generated. Each fuzzy subgroup in these classes satisfies the above inequality with T given by T(a, b) = max(a + b ?1, 0). While the two classes look different, each fuzzy subgroup in either is isomorphic to one in the other. It is shown that a fuzzy subgroup satisfies the above inequality with $\text{T =}\text{‘minimum’}$ if and only if it is subgroup generated of a very special type. Finally, these notions are applied to some abstract pattern recognition problems.     

Short effective intervals containing primes

We prove that every interval ]x(1−Δ⁻¹),x] contains a prime number with Δ=28314000 and provided x?10726905041. The proof combines analytical, sieve and algorithmical methods.