On the existence of extremal cones and comparative probability orderings

We study the recently discovered phenomenon [Conder, M. D. E., & Slinko, A. M. (2004). A counterexample to Fishburn's conjecture. Journal of Mathematical Psychology, 48(6), 425-431] of existence of comparative probability orderings on finite sets that violate the Fishburn hypothesis [Fishburn, P. C. (1996). Finite linear qualitative probability. Journal of Mathematical Psychology, 40, 64-77; Fishburn, P. C. (1997). Failure of cancellation conditions for additive linear orders. Journal of Combinatorial Designs, 5, 353-365]—we call such orderings and the discrete cones associated with them extremal. Conder and Slinko constructed an extremal discrete cone on a set of n=7 elements and showed that no extremal cones exist on a set of n?6 elements. In this paper we construct an extremal cone on a finite set of prime cardinality p if p satisfies a certain number theoretical condition. This condition has been computationally checked to hold for 1725 of the 1842 primes between 132 and 16,000, hence for all these primes extremal cones exist.     

Archimedean qualitative probabilities

Necessary and sufficient conditions for the existence of a probability measure agreeing with a weak order on an algebra of events are given. In the case of a countable algebra they consist of an extension of Kraft, Pratt, and Seidenberg's (1959. Annals of Mathematical Statistics, 38, 780–786) additivity condition through the requirement of an Archimedean property. In the case of a σ-algebra and a σ-additive agreeing probability, Villegas' (1964. Annals of Mathematical Statistics, 35, 1787–1796) monotone continuity condition, which becomes necessary, is merely added to them.     

Utility of extension of functional equations—when possible

Jean-Claude Falmagne observed in 1981 [On a recurrent misuse of classical functional equation result. Journal of Mathematical Psychology, 23, 190-193] that, even under regularity assumptions, not all solutions of the functional equation k(s+t)=k(s)+k(t), important in many fields, also in the theory of choice, are of the form k(s)=Cs. This is certainly so when the domain of the equation (the set of (s,t) for which the equation is satisfied) is finite. We mention an example showing that this can happen even on some infinite, open, connected sets (open regions). The more general equations k(s+t)=?(s)+n(t) and k(s+t)=m(s)n(t), called Pexider equations, have been completely solved on R². In case they are assumed valid only on an open region, they have been extended to R² and solved that way (the latter if k is not constant). In this paper their common generalization

k(s+t)=?(s)+m(s)n(t)     

Nondecomposable conjoint measurement for bisymmetric structures

This paper discusses two “nondecomposable” conjoint measurement representations for an asymmetric binary relation ? on a product set A × X, namely (a, x) ? (b, y) iff f₁(a) + g₁(a)g₂(x) > f₁(b) + g₁(b)g₂(y), and (a, x) ? (b, y) iff f₁(a) + f₂(x) + g₁(a)g₂(x) > f₁(b) + f₂(y) + g₁(b)g₂(y). Difficulties in developing axioms for ? on A × X which imply these representations in a general formulation have led to their examination from the standpoint of bisymmetric structures based on applications of a binary operation to A × X. Depending on context, the binary operation may refer to concatenation, extensive or intensive averaging, gambles based on an uncertain chance event, or to some other interpretable process. Independence axioms which are necessary and sufficient for the special representations within the context of bisymmetric structures are presented.     

Lexicographic additive differences

Several authors have identified sets of axioms for a preference relation ? on a two-factor set A × X which imply that ? can be represented by specific types of numerical structures. Perhaps the two best-known of these are the additive representation, for which there are real valued functions f_A on A and f_X on X such that (a, x) ? (b, y) if and only if f_A(a) + f_X(x) > f_A(b) + f_X(y), and the lexicographic representation which, with A as the dominant factor, has (a, x) ? (b, y) if and only if f_A(a) > f_A(b) or {f_A(a) = f_A(b) and f_X(x) > f_X(y)}. Recently, Duncan Luce has combined the additive and lexicographic notions in a model for which A is the dominant factor if the difference between a and b is sufficiently large but which adheres to the additive representation when the difference between a and b lies within what might be referred to as a lexicographic threshold. The present paper specifies axioms for ? which lead to a numerical model which also has a lexicographic component but whose local tradeoff structure is governed by the additive-difference model instead of the additive model. Although the additive-difference model includes the additive model as a special case, the new lexicographic additive-difference model is not more general than Luce's model since the former has a “constant” lexicographic threshold whereas Luce's model has a “variable” lexicographic threshold. Realizations of the new model range from the completely lexicographic representation to the regular additive-difference model with no genuine lexicographic component. Axioms for the latter model are obtained from the general axioms with one slight modification.     

A locus problem involving the three-dimensional city-block metric

In connection with multidimensional scaling, representations have been considered of the form abDcd ← ?(f(a), f(b)) ≦ ?(f(c), f(d)), for all a, b, c, d ∈ A, where A is a nonvoid finite set, D is a four-place relation on A, f is a function from A into Euclidean n-space, $\text{R}{}^{\mathrm{n}}$, and ? is a metric in $\text{R}{}^{\mathrm{n}}$. For particular metrics there exist finite universal axiomatizations which are necessary and sufficient for the above representation. On the other hand, it is known that no such axiomatizations can be given for either the supremum metric or the ordinary Euclidean metric. Methods for showing this apply easily to the city-block metrics in $\text{R}{}^1$ and $\text{R}{}^2$. This article describes a computer-aided verification of a locus result which shows the impossibility of finite universal axiomatizability for the case of the city-block metric in $\text{R}{}^3$. The result was obtained by dealing with 21,780 cases, each of which involved a set of 10 equations in 12 unknowns along with a related set of inequalities.     

Maximization of sums of quotients of quadratic forms and some generalizations

Monotonically convergent algorithms are described for maximizing six (constrained) functions of vectors x, or matricesX with columns x₁, ..., x _r . These functions are h₁(x)= _k (xA _kx)(xC _kx)^–1, H₁(X)= _k tr (XA _k X)(XC _k X)^–1, h₁(X)= _{k l} (x _l A _kx _l ) (x _l C _kx _l )^–1 withX constrained to be columnwise orthonormal, h₂(x)= _k (xA _kx)²(xC _kx)^–1 subject to xx=1, H₂(X)= _k tr(XA _kX)(XA_kX)(XC_kX)^–1 subject toXX=I, and h₂(X)= _{k l} (x _l A _kx _l )² (x _l C _kX _l )^–1 subject toXX=I. In these functions the matricesC _k are assumed to be positive definite. The matricesA _k can be arbitrary square matrices. The general formulation of the functions and the algorithms allows for application of the algorithms in various problems that arise in multivariate analysis. Several applications of the general algorithms are given. Specifically, algorithms are given for reciprocal principal components analysis, binormamin rotation, generalized discriminant analysis, variants of generalized principal components analysis, simple structure rotation for one of the latter variants, and set component analysis. For most of these methods the algorithms appear to be new, for the others the existing algorithms turn out to be special cases of the newly derived general algorithms.This research has been made possible by a fellowship from the Royal Netherlands Academy of Arts and Sciences to the author. The author is obliged to Jos ten Berge for stimulating this research and for helpful comments on an earlier version of this paper.     

Finite axiomatization for some intermediate logics

LetN. be the set of all natural numbers (except zero), and letD _n ^* = {k ∈N ∶k|n} ∪ {0} wherek¦n if and only ifn=k.x f or somex∈N. Then, an ordered setD _n ^* = 〈D _n ^* , ? _n , wherex? _ny iffx¦y for anyx, y∈D _n ^* , can easily be seen to be a pseudo-boolean algebra. In [5], V.A. Jankov has proved that the class of algebras {D _n ^* ∶n∈B}, whereB =,{k ∈N∶ ? \(\mathop \exists \limits_{n \in N} \) (n > 1 ≧n ² k)is finitely axiomatizable. The present paper aims at showing that the class of all algebras {D _n ^* ∶n∈B} is also finitely axiomatizable. First, we prove that an intermediate logic defined as follows: $$LD = Cn(INT \cup \{ p_3 \vee [p_3 \to (p_1 \to p_2 ) \vee (p_2 \to p_1 )]\} )$$ finitely approximatizable. Then, defining, after Kripke, a model as a non-empty ordered setH = 〈K, ?〉, and making use of the set of formulas true in this model, we show that any finite strongly compact pseudo-boolean algebra ? is identical with. the set of formulas true in the Kripke modelH _B = 〈P(?), ?〉 (whereP(?) stands for the family of all prime filters in the algebra ?). Furthermore, the concept of a structure of divisors is defined, and the structure is shown to beH D _n ^* = 〈P (D _n ^* ), ?〉for anyn∈N. Finally, it is proved that for any strongly compact pseudo-boolean algebraU satisfying the axiomp ₃∨ [p ₃→(p₁→p₂)∨(p₂→p₁)] there is a structure of divisorsD _* ⁿ such that it is possible to define a strong homomorphism froomiH D _n ^* ontoH D _U . Exploiting, among others, this property, it turns out to be relatively easy to show that \(LD = \mathop \cap \limits_{n \in N} E(\mathfrak{D}_n^* )\) .     

Analyzing proximity matrices: The assessment of internal variation in combinatorial structure

A data analysis strategy is discussed for evaluating the degree to which a subset D of a larger object set S satisfies a particular algebraic property. Based on a set measure f(D) and a proximity function on S × S, two separate evaluation tasks, referred to as confirmatory and exploratory, are considered. In a confirmatory task the subset D is identified a priori and f(D) is compared against the distribution of f(·) over all subsets containing the same number of objects. The exploratory task, on the other hand, treats f(·) as an objective function to be optimized over all subsets of a given size. Examples of these two notions include the assessment of symmetry, cluster compactness, and the extent to which D satisfies the error-free conditions for a hierarchical model or a unidimensional scale.     

Binary choice probabilities: on the varieties of stochastic transitivity

Let {P_λ} denote the family of decisiveness relations {$\text{P}{}_{\mathrm{\lambda }}\text{:}\text{1}\text{2}\text{≤ λ < 1}$} with aP_λb if and only if P(a,b) > λ, where P is a binary choice probability function. Families in which all decisiveness relations are of the same type, such as all strict partial orders or all semiorders, are characterized by stochastic transitivity conditions. The conditions used for this purpose differ in various ways from the traditional forms of strong, moderate, and weak stochastic transitivity. The family {P_λ} is then examined from the viewpoint of interval representation models, the most general of which is aP_λb if and only if I(a, λ) > I(b, λ), where the I's are real intervals with I(a, λ) > I(b, λ) if and only if the first interval is completely to the right of the second. With I(a, λ) = [f(a, λ), f(a, λ) + σ(a, λ)], the specializations of the interval model that are discussed include those where the location function f (for left end-points) depends only on the set A of alternatives or stimuli and where the length function σ depends only on A or on λ or neither.     

An approximation of theK outN reliability of a test,and a scoring procedure for determining which items an examinee knows

Consider any scoring procedure for determining whether an examinee knows the answer to a test item. Letx _i = 1 if a correct decision is made about whether the examinee knows the ith item; otherwisex _i = 0. Thek out ofn reliability of a test isρ _k = Pr (Σx _i ≥k). That is,ρ _k is the probability of making at leastk correct decisions for a typical (randomly sampled) examinee. This paper proposes an approximation ofρ _k that can be estimated with an answer-until-correct test. The paper also suggests a scoring procedure that might be used whenρ _k is judged to be too small under a conventional scoring rule where it is decided an examinee knows if and only if the correct response is given.     

Resolution of Algebraic Systems of Equations in the Variety of Cyclic Post Algebras

There is a constructive method to define a structure of simple k-cyclic Post algebra of order p, L _p,k , on a given finite field F(p ^k ), and conversely. There exists an interpretation ??₁ of the variety ${\mathcal{V}(L_{p,k})}$ generated by L _p,k into the variety ${\mathcal{V}(F(p^k))}$ generated by F(p ^k ) and an interpretation ??₂ of ${\mathcal{V}(F(p^k))}$ into ${\mathcal{V}(L_{p,k})}$ such that ??₂??₁(B) =  B for every ${B \in \mathcal{V}(L_{p,k})}$ and ??₁??₂(R) =  R for every ${R \in \mathcal{V}(F(p^k))}$ . In this paper we show how we can solve an algebraic system of equations over an arbitrary cyclic Post algebra of order p, p prime, using the above interpretation, Gröbner bases and algorithms programmed in Maple.     

On the functional form of partial masking functions in psychoacoustics

Partial masking of pure tones is often investigated in terms of matching functions which record the intensity φ(x, n) of an unmasked tone which matches, in perceived loudness, a tone of intensity x embedded in a flat, broadband noise of intensity n. Empirically, the following property of “shift invariance” is observed to hold for these matching functions: φ(λx, λ^θn) = λφ(x, n), for any λ > 0, and some θ < 1. In the context of the model $\text{φ(x, n) = F}{}_0\text{[}\text{g}{}_0\text{(x)}\text{(h}{}_0\text{(x) + k}{}_0\text{(n))}\text{]}$ which expresses the idea that the effect of a noise mask is to control the gain of a pure tone signal in a multiplicative fashion, shift invariance proves to be an extremely powerful theoretical constraint. Specifically, we show that only two parametric families of functions (F₀, g₀, h₀, k₀) are possible candidates for interpolating empirical data. These two parametric families are given by the following expressions: $\text{φ}{}_1\text{(x, n) = A(}\text{x}{}^{\mathrm{\alpha }}\text{(x}{}^{\mathrm{\alpha \prime }}\text{+ Kn}{}^{\mathrm{<mtext>\alpha \prime </mtext><mtext>\theta </mtext>}}\text{)}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>(\alpha \; ?\; \alpha \prime )</mtext>}}$, $\text{φ}{}_2\text{(x, n) = A[x}{}^{\mathrm{\alpha }}\text{(x}{}^{\mathrm{\alpha \prime }}\text{? Kn}{}^{\mathrm{<mtext>\alpha \prime </mtext><mtext>\theta </mtext>}}\text{)]}{}^{\mathrm{<mtext>1</mtext><mtext>(\alpha \; +\; \alpha \prime )</mtext>}}$. Both of these expressions are in good agreement with a large array of partial masking data.     

Classification of concatenation measurement structures according to scale type

A relational structure is said to be of scale type (M,N) iff M is the largest degree of homogeneity and N the least degree of uniqueness (Narens, 1981a, Narens, 1981b) of its automorphism group.Roberts (in Proceedings of the first Hoboken Symposium on graph theory, New York: Wiley, 1984; in Proceedings of the fifth international conference on graph theory and its applications, New York: Wiley, 1984) has shown that such a structure on the reals is either ordinal or M is less than the order of at least one defining relation (Theorem 1.2). A scheme for characterizing N is outlined in Theorem 1.3. The remainder of the paper studies the scale type of concatenation structures 〈X, ?, ° 〉, where ? is a total ordering and ° is a monotonic operation. Section 2 establishes that for concatenation structures with M>0 and N<∞ the only scale types are (1,1), (1,2), and (2,2), and the structures for the last two are always idempotent. Section 3 is concerned with such structures on the real numbers (i.e., candidates for representations), and it uses general results of Narens for real relational structures of scale type (M, M) (Theorem 3.1) and of Alper (Journal of Mathematical Psychology, 1985, 29, 73–81) for scale type (1, 2) (Theorem 3.2). For M>0, concatenation structures are all isomorphic to numerical ones for which the operation can be written $\text{x°y = yf(}\text{x}\text{y}\text{)}$, where f is strictly increasing and $\text{f(x)}\text{x}$ is strictly decreasing (unit structures). The equation f(x^?)=f(x)^? is satisfied for all x as follows: for and only for ? = 1 in the (1,1) case; for and only for ?=kⁿ, k > 0 fixed, and n ranging over the integers, in the (1, 2) case; and for all ?>0 in the (2, 2) case (Theorems 3.9, 3.12, and 3.13). Section 4 examines relations between concatenation catenation and conjoint structures, including the operation induced on one component by the ordering of a conjoint structure and the concept of an operation on one component being distributive in a conjoint structure. The results, which are mainly of interest in proving other results, are mostly formulated in terms of the set of right translations of the induced operation. In Section 5 we consider the existence of representations of concatenation structures. The case of positive ones was dealt with earlier (Narens & Luce (Journal of Pure & Applied Algebra27, 1983, 197–233). For idempotent ones, closure, density, solvability, and Archimedean are shown to be sufficient (Theorem 5.1). The rest of the section is concerned with incomplete results having to do with the representation of cases with M>0. A variety of special conditions, many suggested by the conjoint equivalent of a concatenation structure, are studied in Section 6. The major result (Theorem 6.4) is that most of these concepts are equivalent to bisymmetry for idempotent structures that are closed, dense, solvable, and Dedekind complete. This result is important in Section 7, which is devoted to a general theory of scale type (2, 2) for the utility of gambles. The representation is a generalization of the usual SEU model which embodies a distinctly bounded form of rationality; by the results of Section 6 it reduces to the fully rational SEU model when rationality is extended beyond the simplest equivalences. Theorem 7.3 establishes that under plausible smoothness conditions, the ratio scale case does not introduce anything different from the (2, 2) case. It is shown that this theory is closely related to, but somewhat more general, than Kahneman and Tversky's (Econometrica47, 1979, 263–291) prospect theory.     

The general psychophysical differential equation: A comparison of three specifications

The general psychophysical differential equation, dy/dx = W₂(y)/W₁(x), with the solution y = f(x), where x and y are subjective variables and W₁ and W₂ their subjective Weber functions, is (a) compared with a corresponding functional equation, and (b) studied from a stochastic point of view by error calculus, Methods for evaluating and handling divergences are proposed and illustrated for a number of combinations of Weber functions. It is shown that either the differential: and the functional equations have the same solution or the difference between the solutions is negligible compared to empirical scatter. The error calculus gives the same result: either no error at all or a negligible one.     

On a functional equation related to Thurstone models

If f and g are nonvanishing characteristic functions the functional equation g(s)g(t)g(?s ? t) = f(as)f(at)f(?as ? at) implies g(s) = e^ibsf(as), i.e., f and g corresponding to probability distributions of the same type. It is shown here that when f and g are allowed to vanish this equation also has solutions in which f and g correspond to distributions of different types. The practical implication is that there are nonequivalent. Thurstone models which cannot be discriminated by any choice experiment with three objects.     

Satisfiability Decay along Conjunctions of Pseudo-Random Clauses

k-SAT is a fundamental constraint satisfaction problem. It involvesS(m), the satisfaction set of the conjunction of m clauses,each clause a disjunction of k literals. The problem has manytheoretical, algorithmic and practical aspects. When the clauses are chosen at random it is anticipated (butnot fully proven) that, as the density parameter m/n (n thenumber of variables) grows, the transition of S(m) to beingempty, is abrupt: It has a "sharp threshold", with probability1 – o(1). In this article we replace the random ensemble analysis by apseudo-random one: Derive the decay rule for individual sequencesof clauses, subject to combinatorial conditions, which in turnhold with probability 1 – o(1). This is carried out under the big relaxation that k is not constantbut k = log n , or even r log log n . Then the decay of S isslow, "near-perfect" (like a radioactive decay), which entailssharp thresholds for the transition-time of S below any givenlevel, down to S = .     

On linear classifications under varying choice probabilities

The paper deals with certain problems connected with the assumption that choice probabilities p_s(x, y) depend on the subject s. A set of postulates is given, which implies the existence of sequences of “classification standards”, i.e., sequences {z_j} such that whenever we have 0 < p_s0(x, z_i) < 1 for some s₀ and i, then p_s(z_i+k, x) = p_s(x, z_i?k) = 1 for all s, and k ≥ 1. Elements of any such sequence {z_j} can serve as boundaries between successive categories of classification based on the following rule: Assign x to jth category if you feel it is “to the right” of z_j and “to the left” of z_j+1. Under the condition stated above this rule is unambiguous, and the resulting classification has the property that every element is assigned to one of the two neighboring categories, regardless who performs the classification.Next, the postulates are enriched so as to imply the existence of “tightest” among such sequences {z_j}, hence leading to a classification with largest number of categories.     

Generalized procrustes analysis

SupposeP _i ⁽ⁱ⁾ (i = 1, 2, ...,m, j = 1, 2, ...,n) give the locations ofmn points inp-dimensional space. Collectively these may be regarded asm configurations, or scalings, each ofn points inp-dimensions. The problem is investigated of translating, rotating, reflecting and scaling them configurations to minimize the goodness-of-fit criterion Σ _i=1 ^m Σ _i=1 ⁿ Δ²(P _j ⁽ⁱ⁾ G _i ), whereG _i is the centroid of them pointsP _i ⁽ⁱ⁾ (i = 1, 2, ...,m). The rotated positions of each configuration may be regarded as individual analyses with the centroid configuration representing a consensus, and this relationship with individual scaling analysis is discussed. A computational technique is given, the results of which can be summarized in analysis of variance form. The special casem = 2 corresponds to Classical Procrustes analysis but the choice of criterion that fits each configuration to the common centroid configuration avoids difficulties that arise when one set is fitted to the other, regarded as fixed.