The paper aims at not only counting how many basic choice functions exist on a finite set of alternatives (all, non-empty, single-element valued) but shows how to do this with the help of Formal Concept Analysis. Moreover, we introduce the contextual representation of a choice function by considering the formal context of its map from 2 to 2 . We also characterise these contexts as nominal scales of a certain size and build a lattice of all choice functions with their help. Last but not least, we study the asymptotic behaviour of those obtained and new counting formulas that do not have a closed form.
Choice Theory is formalised with the help of Order Theory [
In this paper, inspired by earlier works on choice functions and Lattice Theory [
The previous work of Monjardet and Raderanirina [
Other related works on FCA and Choice Theory include learning individual and collective preferences [11], enchaining consensus voting procedures [12], for example, in consensus clustering [13], studying games on concept lattices [14, 15], and attribute ranking in formal concepts with Shapley values [16].
The paper is organised as follows. In Section 2 we give basic definitions from FCA and for considered families of choice functions. Section 3 contains our main results split in three subsections on the proposed conceptual representation of choice functions, three counting formulas, and their asymptotic behaviour, respectively. The last section concludes the paper.
We recall several definitions from Formal Concept Analysis [ 7], an applied branch of modern Lattice Theory. We reproduce basic definitions from our tutorial [ 17], for more details see also textbook [18].
A formal context = (, , ) consists of two sets and and a relation between and . The elements of are called the objects and the elements of are called the attributes of the context. The notation or (, ) ∈ means that the object has attribute .
A special type of context defined on any set is used in the next section: the nominal scale ℕ ∶= (, , =) .
For ⊆ and ⊆ , let ′ ∶= { ∈ ∣ (, ) ∈ ′ ∶= { ∈ ∣ (, ) ∈ for all ∈ } for all ∈ }.
These operators are called derivation operators or concept-forming operators for = (, , ) .
Proposition 1. Let (, , ) be a formal context, for subsets , 1, 2 ⊆ and ⊆ we have 1. 1 ⊆ 2 ⇒ ′2 ⊆ ′1 (antimonotony of ′), 2. 1 ⊆ 2 ⇒ ′1′ ⊆ ′2′ (monotony of ′′), 3. ⊆ ′′ (extensity of ′′), 4. ′ = ′′′ (hence, ⁗ = ″, i.e. idempotency of ′′), 5. ( 1 ∪ 2)′ = ′1 ∩ ′2, Similar properties hold for subsets of attributes.
Note that traditionally {} ′ and {} ′ are written as ′ and ′ for brevity.
For = (, , ) , the operators (⋅)″ ∶ 2 → 2 , (⋅)″ ∶ 2 → 2 are closure operators, i.e. idempotent, extensive, and monotone.
A formal concept of a formal context = (, , ) is a pair (, ) with ⊆ , ⊆ , ′ = and ′ = . The sets and are called the extent and the intent of the formal concept (, ) , respectively. The subconcept-superconcept relation is given by ( 1, 1) ≤ ( 2, 2)if 1 ⊆ 2 ( 2 ⊆ 1).
The set of all formal concepts of a context together with the order relation ≤ forms a complete lattice called the concept lattice of and denoted by () .
A choice function on a set is defined as map ∶ 2 → 2 such that () ⊆ (intensity property).
In what follows, we adopt terminology from [
The set of all single-valued functions ̂contains ̂such that |( ̂)| = 1 for all ∈ .
Let us form the context representing a choice function as follows ∶= (, , ) with ∶= 2 , ∶= 2 , ⊆ 2 × 2 , where for ∈ , ∈ , if () = . It is clear that the domain of , () , is , while () ⊆ .
Contexts representing non-empty and single-valued functions are denoted + ∶= ( , , +) and ̂ ∶= ( , , ̂), respectively, where + ⟺ +() = and for the last context ̂ ⟺ (̂)= and || = 1 .
Proposition 2. Let ∈ , + ∈ +, ∈̂ ̂and || = , then the concept lattices of = (2 , 2 , ), + = ( , , +)and ̂ = ( , , ̂)are isomorphic to the lattices of nominal scales = ([], [], =) 1 where = | ( )| for ∈ {, +, } ̂and 1) 1 ≤ ≤ 2 , 2) ≤ ≤ 2 − 1, and 3) = , respectively.
Proof. 1) () may vary from {∅} set to 2 , which means that the number of ∈ 2 such that ′ ≠ ∅ varies from 1 to 2 . Equality 2) follows from the condition ∀ ∈ ∶ || = 1 ⇒ ′ = {} (by intensity of () ). Equality 3) follows from the previous condition and condition ∀ ∈ ∃ ∈ ∶ ′ = {} ∧ ∈ .
The interpretation of concepts in such lattices is straightforward. Let ∈ = 2 , then ( ′, ) contains the image as the intent and its preimage ′ (or the fibre −1({}) , the set all of sets that mapped to {} ) as the extent. Note that {} ″ = {} and there are no other concepts than ( ′, ) , (, ′)and ( ′, ) .
The following example is inspired by our previous work on how university entrants are choosing their departments [19]. 1We use [] for {1, 2, … , } Example 1. Let us consider a set
with three alternatives 1 (Computer Science faculty), 2
(Mathematical faculty), and 3 (Faculty of Economics). It is known that if an individual has
preferences represented by a binary relation , then they can be rationalised by a choice function
under certain conditions [
∅ 1 2 3 1, 2 1, 3 2, 3 1, 2, 3 ∅ × × 1 × × 2 × 3 2 3 3
2
, , ,
, 1 1 2
1
3 , × ×
×
1, 2}) = { 1, 2}. When only a single faculty out of the last two is available, she chooses it. However, when only the faculty of Economics is ofered, she refuses and probably takes a year gap (it might be a very pity that there is no choice among the favourite faculties). However, when educational tracks for mathematics and economics are compared, she might decide to apply both. So, the choices might seem to be not fully rational (in terms of common sense), but they are in line with the definition of (⋅) .
The line diagram of the corresponding concept lattice ( ) on the left in Fig. 1 is drawn in Concept Explorer. We use the so-called reduced labelling when nodes (representing concepts) are labelled with object names when objects are first time added to the extent of a concept (when we go from the bottom concept to the topmost one) and attribute names when attributes are first time added to the intent of a concept (when we go in top-to-bottom direction). Note that we use shorthand , , and in the attribute labels (the latter denote choices on all alternative subsets), and 1, 2, and 3 in the object labels (the latter denote the subsets of all the alternatives).
Note that our attributes are sets of alternatives and { 3}, { 1, 3}, and { 1, 2, 3} can be eliminated from the without afecting the lattice structure. The obtained concept lattice is isomorphic to the so-called diamond lattice 5.
The lattice of a choice function can be defined via point-wise intersection and union. Let us order objects of = 2 first by their cardinality and lexicographically for sets of equal cardinality such that 0 = ∅, … , 2 −1 = . Now, every choice function is represented by its point-wise vector of images () = (
⋃ 0′, ⋃ 1′, … , ⋃ 2′ −1)2. Note that 0′ = {∅}.
For the example in Fig. 1, we have () = (∅, { 1}, { 2}, ∅, { 1, 2}, { 1}, { 2, 3}, { 1, 2}). 2we use ⋃ as a set unfolding operation since ′ = { } and ( ) ≡ ⋃ ′
For two functions 1 and 2, the supremum and infimum of their point-wise vectors of images ( 1) = (⋃ 01, ⋃ 11, … , ⋃ 2 −1)and ( 1 2) = (⋃ 02, ⋃ 12, … , ⋃ 2 −1) 2 (primes are taken in the respective contexts) are defined as follows: ( ( 1)⋁ ( 1)⋀ ( 2) = (⋃ 1 ∪ ⋃ 2 ) 2= 0−1, 2) = (⋃ 1 ∩ ⋃ 2 ) 2= 0−1 . ( ̂2) ⟺
⋃ 1 ⊆ ⋃ 2 for ∈ [2 − 1]).
Their existence is guaranteed by set intersection and union on images of choice functions. , then triple () = ( ( ),
⋁, ⋀)3 forms a lattice with 0 = (∅ )2= 0−1 and 1 = (∅, {1}, … , []) , while = ( ( +),⋀) is an upper-semilattice and = ( ( )̂,≤) forms an antichain with respect to the point-wise set inclusion of components ≤ (∀ ̂1, ̂2 ∈ ̂∶( ̂1) ≤ Let us prove the following proposition on the cardinality of , +, ̂ where || = . Proposition 3.
| +| = ∏(2 − 1)( ) | | = 22 −1 =1 |̂ | = ∏
( ) =1 (1) (2) (3) 2 −1 . ( ) = {() ∣ ∈ }
Note that (1) and (2) have been proven in [20] according to [
Proof. 1) Let us consider 1 = (∅, {1}, … , []) it corresponds to = (2 , 2 , ), where ( ) = for ⊆
and ∶==. For each other choice function, () variants and the choice of each row is independent (we are ready for the product rule). which means that ⋃ ′ ⊆ ⋃ , where ′ is taken in the . Thus each row of has |2⋃ | is below 1 in the lattice ( ) 2 −1
∏ 2| ⋃ | = =0 ∏ 2 ⊆ | | = ∏ 2 ( )
=0 The last step is due to the presence of each set of size ( ) times. The sum ∑ ( ) equals
=0 Formula | | Counting sequences for | +|, | |, and |̂ | up to = 5
OEIS sequence
– https://oeis.org/A229333 1 1 1 2 3 2 3 189 24
4 26254935 20736
5 392654823152462915625 309586821120 2) Now, we are not allowed to consider ⋃ = ∅, which implies subtraction of 1 (i.e. 2 − 1) when counting variants for the choice of a row in the context + = ( , , + ⊆). Here so 0 (also 0) is excluded and the product starts with = 1 . 3) Here, compared to the previous case, since we can choose only single-element sets among , 2 − 1 is simply replaced by .
Note that Monjardet and Raderanirina [
We also note that the beginning values by equations 1 and 3 are listed in OEIS: see integer sequences https://oeis.org/A061301 and https://oeis.org/A229333, respectively.
Before we go to the asymptotic analysis, let us also list some beginning values of these sequences by equations 1–3 in Table 1.
The values represented by equations 2 and 3 have no closed-form formulas but are smaller than the size of the whole space of choice functions. Our goal here is to figure out their asymptotic behaviour to better understand how the sizes of the posets, | +|, | |, and |̂ |, interrelated.
log2 | +| = 2 −1 + (2 −1/2) Proof. Let us apply log2 to the product (2).
The first sum equals ( 1), while the second is more laborious since it has no closed form. Since log2 ≤ − 1 for all > 0 , we obtain
=1
∑ ( ) log2(1 − 1/2 ) ≤ ∑ ( )(−1/2 ) = −( ) + 1 3 do better with the lower bound if pull out the maximal binomial coeficient, i.e. the middle (or central) binomial coeficient.
=1
⌊/2⌋ ∞ =1
∏(1 − ) is the Euler function [22], and ()∞ and (; ) ∞ are -Pochhammer symbols [23].
The variable term ( ⌊/2⌋ ) is (2 −1/2) since for even , we have (/2 ) = Proof. From the proof of the previous proposition it follows that
(1/2) √2/⋅2 −1/2 ≤ ∏(1 − 1 )( ) ≤ 2−( 23 ) +1 where (1/2) ≈ 0.2888.
When tends to ∞, both sides tend to 0, and since no terms of the partial product are zeros, the whole product is said to diverge to zero [26, 27].
Proposition 5. →∞ | | = ∏(1 −
2 1 )( ) diverges to zero.
=1 ∑ ( ) log2 ≥ ⌊/2⌋−1 ∑ =1 ( ) log2 + ∑ =⌊/2⌋
( ) log2 2 ≥ ∑ =⌊/2⌋
( ) log2 2 ≥ log2 |̂ | = Θ(2 log2 ) . 12 log2 ≤ log2 |̂ | ≤ 22 log2 for all > 0 .
We can pull out the largest value that log2 takes Proof. To prove the statement we need to show that there are constants 1, 2 > 0, such that log2 |̂ | = ∑ ( ) log2 ≤ log2 ∑ ( ) = (2 − 1)log2 .
For the lower bound we can split the sum into two parts as follows:
4. Conclusion
−1
=0
=1
−1
=0
and the remaining term is
∑ ( ) log2(1 − /) ≤ −
Monjardet and Raderanirina [
For example, the lattice of choice functions satisfying hereditary axiom has size |(
( −1 ) , where is the -th Dedekind number [
We hope to continue this work on combinatorial properties of choice functions with FCA tools for their representation and counting and perform asymptotic analysis (if necessary).
This study was implemented in the Basic Research Program’s framework at HSE University.
We would like to thank the anonymous reviewers for relevant suggestions and the OEIS maintainers. We also would like to thank Lev P. Shibasov and Fuad T. Aleskerov for the inspirational lectures on Analysis and Choice Theory, respectively. Last but not least, we are grateful to Dmitry V. Vinogradov for useful remarks on the notation.
The last result can be sharpened to log2 |̂ | = 2 log2 (1 + (1/ 2) ). By changing to ∑( )log2 = ∑( )log2( − ) and pull out log2 , which gives us the term
Choice and Welfare 23 (2004) 349–382. doi:10.1007/s00355- 003- 0251- 9. [3] C. Boutilier, I. Caragiannis, S. Haber, T. Lu, A. D. Procaccia, O. Shefet, Optimal Social
Choice Functions, Artif. Intell. 227 (2015) 190–213. doi:10.1016/j.artint.2015.06.003. [4] G. Pigozzi, A. Tsoukiàs, P. Viappiani, Preferences in artificial intelligence, Annals of Mathematics and Artificial Intelligence 77 (2016) 361–401. doi: 10.1007/s10472-015-9475-5. [5] H. Moulin, Choice functions over a finite set: A summary, Social Choice and Welfare 2 (1985) 147–160. doi:10.1007/BF00437315. [6] M. Aizerman, F. Aleskerov, Voting operators in the space of choice functions, Mathematical
Social Sciences 11 (1986) 201–242. [7] B. Ganter, R. Wille, Formal Concept Analysis - Mathematical Foundations, Springer, 1999.
doi:10.1007/978-3-642-59830-2. [8] A. Revenko, S. O. Kuznetsov, Attribute exploration of properties of functions on sets,
Fundam. Informaticae 115 (2012) 377–394. doi:10.3233/FI-2012-660. [9] A. Revenko, S. O. Kuznetsov, Attribute exploration of properties of functions on ordered sets, in: M. Kryszkiewicz, S. A. Obiedkov (Eds.), Proceedings of the 7th International Conference on Concept Lattices and Their Applications, Sevilla, Spain, October 19-21, 2010, volume 672 of CEUR Workshop Proceedings, CEUR-WS.org, 2010, pp. 313–324. URL: https://ceur-ws.org/Vol-672/paper28.pdf. [10] B. Ganter, Attribute exploration with background knowledge, Theoretical Computer
Science 217 (1999) 215–233. doi:10.1016/S0304-3975(98)00271-0, oRDAL’96. [11] S. Obiedkov, Parameterized ceteris paribus preferences over atomic conjunctions under conservative semantics, Theoretical Computer Science 658 (2017) 375–390. doi:10.1016/ j.tcs.2016.01.035. [12] F. Domenach, A. Tayari, Implications of Axiomatic Consensus Properties, in: B. Lausen, D. Van den Poel, A. Ultsch (Eds.), Algorithms from and for Nature and Life, Springer International Publishing, Cham, 2013, pp. 59–67. [13] A. Bocharov, D. Gnatyshak, D. I. Ignatov, B. G. Mirkin, A. Shestakov, A lattice-based consensus clustering algorithm, in: M. Huchard, S. O. Kuznetsov (Eds.), Proc. of CLA 2016, volume 1624 of CEUR Workshop Proceedings, CEUR-WS.org, 2016, pp. 45–56. URL: https://ceur-ws.org/Vol-1624/paper4.pdf. [14] U. Faigle, M. Grabisch, A. Jiménez-Losada, M. Ordóñez, Games on concept lattices: Shapley value and core, Discrete Applied Mathematics 198 (2016) 29–47. doi:https://doi.org/ 10.1016/j.dam.2015.08.004. [15] K. Maafa, L. Nourine, M. S. Radjef, Algorithms for computing the Shapley value of cooperative games on lattices, Discret. Appl. Math. 249 (2018) 91–105. doi:10.1016/j. dam.2018.03.022. [16] D. I. Ignatov, L. Kwuida, On Shapley value interpretability in concept-based learning with formal concept analysis, Ann. Math. Artif. Intell. 90 (2022) 1197–1222. doi:10.1007/ s10472-022-09817-y. [17] D. I. Ignatov, Introduction to formal concept analysis and its applications in information retrieval and related fields, in: P. Braslavski, N. Karpov, M. Worring, Y. Volkovich, D. I. Ignatov (Eds.), RuSSIR 2014, volume 505 of Communications in Computer and Information Science, Springer, 2014, pp. 42–141. doi:10.1007/978-3-319-25485-2\_3. [18] B. Ganter, S. A. Obiedkov, Conceptual Exploration, Springer, 2016. doi:10.1007/ 978-3-662-49291-8. [19] N. Romashkin, D. I. Ignatov, E. Kolotova, How university entrants are choosing their department? mining of university admission process with FCA taxonomies, in: M. Pechenizkiy, T. Calders, C. Conati, S. Ventura, C. Romero, J. C. Stamper (Eds.), Proceedings of the 4th International Conference on Educational Data Mining, Eindhoven, The Netherlands, July 6-8, 2011, www.educationaldatamining.org, 2011, pp. 229–234. URL: http://educationaldatamining.org/EDM2011/wp-content/uploads/proc/edm2011_ paper31_short_Romashkin.pdf. [20] V. Raderanirina, Treillis et agrégation de familles de Moore et de fonctions de choix, These de doctorat Université Paris 1 (2001). [21] F. Echenique, Counting combinatorial choice rules, Games and Economic Behavior 58 (2007) 231–245. URL: https://www.sciencedirect.com/science/article/pii/ S0899825606000431. doi:https://doi.org/10.1016/j.geb.2006.03.009. [22] E. W. Weisstein, Euler Function, From MathWorld–A Wolfram Web Resource, 2023. URL: https://mathworld.wolfram.com/EulerFunction.html. [23] B. C. Berndt, q-Series and Theta-Functions, Springer New York, New York, NY, 1991, pp.
11–86. doi:10.1007/978- 1- 4612- 0965- 2\_2. [24] D. E. Knuth, I. Vardi, R. Richberg, 6581. The Asymptotic Expansion of the Middle Binomial Coeficient, The American Mathematical Monthly 97 (1990) 626–630. URL: http://www. jstor.org/stable/2324649. [25] Z.-H. Sun, Inequalities for binomial coeficients, 2013. arXiv:1310.0353. [26] B. P. Demidovich, Problems in Mathematical Analysis, American First Edition ed., Mir
Publishers, 1989. [27] H. Jefreys, B. Jefreys, Methods of Mathematical Physics, Cambridge Mathematical Library, 3 ed., Cambridge University Press, 1999. doi:10.1017/CBO9781139168489. [28] C. Jäkel, A computation of the ninth Dedekind Number, 2023. arXiv:2304.00895.