Mathematics of Plott choice functions

Abstract

This paper is devoted to the study of mathematical structures related to the class of choice functions satisfying the path independence property (Plott functions). The set of Plott functions has a natural lattice structure. We describe join-irreducible and meet-irreducible elements of this lattice. We introduce a convex structure on the set of simple words and show that Plott functions are in a natural one-to-one correspondence with convex subsets of simple words. In particular, this correspondence is compatible with the lattice structures on both sets. All these structures and relations are functorially dependent on a change of base sets.

Introduction

The concept of path independent choice functions was introduced and coined by Plott (1973), and we call these choice functions Plott functions. Although it should be noted that the idea to consider such functions was first proposed by Afriat. Plott considered the concept of “path independence” of a choice function as a means of weakening the condition of rationality in a manner which preserves one of the key properties of rational choice, namely, that choice over any subset should be independent of the way the alternatives were initially divided up to consideration. He considered the associativity law as the mathematical structure underlying path independence concepts. Our purpose is to show that mathematics related to Plott functions is much richer.²

The paper's aim is twofold. The first one is to study the lattice PF(X) of the Plott choice functions on a given (finite) set of alternatives X. Specifically, choice functions defined on the same set X, can be compared by their “size”: f≤g if f(A)⊂g(A) for any A⊂X.³ It turns out that the set PF(X) endowed with this partial order is a lattice. Any element of a lattice can be represented as the join of join-irreducible elements and as the meet of meet-irreducible elements. We describe the irreducible Plott functions of both types and, for any Plott function, we characterize the set of all meet-irreducible functions which dominate this Plott function and the set of join-irreducibles which are dominated by this function (see Proposition 4, Example 5). We found that meet-irreducible Plott functions are exactly the so-called circuit functions. Join-irreducible Plott functions are the so-called linear Plott functions.

Linear Plott functions correspond to linear orders on (subsets of) X. It is convenient to “code” them by simple words (that is, by words over the alphabet X without repeating letters). The set SW(X) of simple words has a natural tree-like order. Moreover, the set SW(X) has a natural convex structure. Given a subset S of SW(X), one can form (with the help of shuffles) its convex hull co(S). Roughly speaking, the convex space SW(X) resembles the positive orthant ${\mathbb{R}}_{+}^X$. In this language, Plott functions correspond to convex subsets of SW(X) and vice versa (Theorem 3). The meet of Plott functions corresponds to the intersection of convex subsets, and the join corresponds to the convex hull of the union. Convex sets for circuit functions resemble semispaces and Theorem 1 is an analogy of Minkowski's theorem on a representation of a convex polytope as the intersection of semispaces. Note also that the convex space SW(X) has the following basic property of conventional convexity: a set is convex if and only if it contains the convex hull of any pair of its points.

The second task is to find relations between the lattices PF(X) and PF(Y) for different sets X and Y. More precisely, we consider three transformations (functors): the direct image (from X to Y), the inverse image (from Y to X), and the weak direct image (again from X to Y).

The direct image commutes with the join and transforms linear Plott functions into linear Plott functions. The inverse image commutes with both the meet and the join.⁴ Therefore, it has the right conjugate operator (a functor) ϕ_! (we call it the weak direct image) transforming Plott functions on X into Plott functions on Y. In contrast to the direct image, the weak direct image commutes with the meet and transforms circuit functions into circuit functions. Moreover, for a surjective mapping, it transforms rational Plott functions into rational ones.⁵

Any rational choice function is a Plott function, but, of course, not vise versa. Thus, Plott functions generalize rational choice functions. However, this is not a mere generalization, it is a very natural one. Specifically, almost all natural constructions for choice functions like the union, the direct and inverse images, take us outside of the class of rational choice functions. The class of Plott functions constitute the minimal extension of the class of rational choice functions for which all these operations become well defined. (The situation is similar to an extension of rational numbers to real numbers, or to adding points at infinity in projective geometry, or to introducing ideals in algebra.) However, the rational choice functions still play an important role. Firstly, any Plott function has a natural rational envelope. Secondly, any Plott function is the join of special rational (namely, linear) functions. Thirdly, although meet-irreducible (circuit) functions are not rational, they represent a natural generalization of “elementary” rational functions. Last but not the least, any Plott function has a canonical representation as the direct image of some rational Plott function. (Using for that lifting to a super-set resembles Riemann's idea of many-sheeted covering of Riemann sphere or the “espace étalé” of a sheaf.)

On the other hand, the functoriality of Plott functions and many abovementioned operations remain true for more general closure operators. The corresponding formalism will be presented in a separate paper.

Summing up the main ideas of the paper, one may say that the notion of a Plott function, which has origins in mathematical economics, is one of the fundamental mathematical notions and generalizes the notion of a topology (or a partially ordered set). Thus, it is worthwhile to apply to Plott functions general–mathematical notions and tools conventional for topological spaces, bundles, sheaves, algebraic varieties and schemes, etc.

We should say at once, that several principal notions and results which are developed in our paper have appeared in the literature, although sometimes in another language and not always in proper form. For example, the theorems about join and meet representations were announced in either form by Malishevski (Aizerman and Malishevski, 1981, Aizerman and Aleskerov, 1995). The notion of convex mixture of (complete) simple words can be found in Duchet (1987) (under the name compatibility) or in Chameni-Nembua (1990) (under the name quasi-unimodality). We thank B. Monjardet for drawing our attention to these papers. As to the functoriality, we should mention a pioneering paper (Litvakov, 1980) where the notion of the direct image (under the name graph-multiple structure) was used implicitly for rationalization of a choice function. Later on, this notion (under the name homomorphism for surjective mappings) appeared in the theory of antimatroids and convex geometries (see Korte et al., 1991). We borrow from there the language of simple words.

The paper is organized as follows. In Section 2, we consider general choice functions, define the lattice structure and the localization operation. Plott functions appear in Section 3 in which we give examples, define lattice operations, and introduce the notion of Plottization of a choice function. We also recall the well-known decomposition of path independence as the conjugation of the Heredity and Outcast properties. In Section 4, we give a theorem on the meet-representation of a Plott function by circuit functions. In Section 5, we give a dual join-representation of a Plott function by linear Plott functions. We also show that linear Plott functions on a set X are in a natural one-to-one correspondence with simple words over the alphabet X. This correspondence allows to associate to any Plott function f a subset Bas(f) of the set SW(X) of simple words. In Section 6, we introduce and study a convex structure in the set SW(X). We show that a Plott function is nothing but a convex set in SW(X).

In Section 7, we define the operations of direct image, inverse image, and full direct image of choice functions. In Section 8, we show that direct image sends Plott functions on X into Plott functions Y. The direct image is used in the next section for constructing the canonical rationalization of Plott functions. We study properties of the inverse image, which is the right conjugate to the direct image within the set of Plott functions, in Section 10. Translation into our language of the main result in Kashiwabara et al. (2004)⁶ reads as that any Plott function is an inverse image of a shelling function. The weak direct image, a right conjugate to the inverse image, is studied in Section 11. In particular, we show that the weak direct image transforms any circuit function into a circuit function and any rational function into a rational function.