Chapter 10 - Subset choice

In this chapter you will learn how to use computer simulations as a theoretical tool, namely to analyze the consequences different formalizations of verbal theories. To reach that goal, you will also learn how to read an implementation of formal theory in Scala mathlib (Blokpoel, 2024). At the end of this chapter, you will be able to use (adapt and run) the provided simulation code to compare three formal models of subset chocie. You will be able to test your intuitions about the theory and derive qualitative differences between them.

We pick up the conversation between Verbal and Formal from Chapter 5 - Subset Choice. Formal is very excited to share the computer simulations they implemented of the theoretical models Formal and Verbal created (this illustration is inspired by van Rooij and Blokpoel, 2020). Formal has some suggestions on how to use the simulations, which they explain to Verbal.

If you jumped here directly from Chapter 5 - Subset choice you may find it helpful to first read Chapter 9 - Scala and mathlib to learn how to read (and write) Scala code using the mathlib library. In addition to the default mathlib library, the simulation code on this page includes supporting code which we explain first.

Supporting code

Running simulations requires input instances as specified by the theoretical model. While we could code input by hand, that is a lot of work. The benefit of using computer simulations is that with some clever coding we can automatically generate input. To that end, Formal has written supporting code. Supporting code is often written specifically for a domain. For example, a simulation of Coherence would require different support code.

For now, it is not important that you know how to write support code. However, in order to explore and adapt the code that Formal has provided, being able to use support code is recommended. Let’s explore some examples.

The theoretical models for selecting invitees (subset choice) take as input sets of persons and a function that for pairs of persons returns if they like eachother or not. The support code helps us generate these parts of the input.

Persons

A particular person is identified by their name, and can be defined by using Person(name: String). This function takes a string as input and returns a Person object with the given name:

import mathlibrepo.selectinginvitees._

Person("Paola")

Persons with the same name are considered to be the same individual.

import mathlibrepo.selectinginvitees._

val person1 = Person("Paola")
val person2 = Person("Paola")

person1 == person2

We can also generate random persons. Their names are randomly selected from a predefined list with 100 names based on the Diverse Name Generator (Maura, Williams & Peng Lee, 2023). Running the code below multiple times will generate different persons.

import mathlibrepo.selectinginvitees._

Person.random

We can also generate groups of n random individuals.

import mathlibrepo.selectinginvitees._

Person.randomGroup(5)

These functions will help us create sets of persons. We can then use mathlib to work with these sets as expected. For example, we can create a set of random persons \(P\), randomly take 2 persons who are liked \(L\), and create a set of persons who are disliked \(D=P \setminus L\):

import mathlibrepo.selectinginvitees._
import mathlib.set.SetTheory._

val persons = Person.randomGroup(5)
val personsLiked = persons.take(2)            // Take 2 people from persons.
val personsDisliked = persons \ personsLiked

personsLiked
personsDisliked
persons

Like-function

The final support code Formal provided is used to create like relationships between persons. In the formal model this function is defined as \(like: P\times P \rightarrow \{true,false\}\). After discussing with a colleague (see Exercise 4.4 in Chapter 5), Formal recognized that the like function was intended to exclude reflection (i.e., self-liking) and is symmetrical \(like(a,b)=like(b,a)\) (i.e., it formalizes like or dislike eachother).The formalizations in this chapter are updated with these properties.

One could specify a like relationship manually. Simply create persons, store them in values so we can refer to them and then use likes or dislikes to create like relationships.

import mathlibrepo.selectinginvitees._

val sanghan   = Person("Sanghan")
val youngJu   = Person("Young Ju")
val greny     = Person("Greny")

sanghan likes youngJu
sanghan dislikes greny
youngJu dislikes greny

Specifying a complete like function for a set of persons, however, will be quite a chore: for each pair you need to explicate if \(a\) likes \(b\) and vice versa. For \(10\) persons, that is a list of \(10 \cdot 10=100\) likes. Support functions help us here.

When given an incomplete list of like relationships, we can complete it this into a complete like function by assuming that any non-specified relationship is a dislike. Use the support function .deriveLikeFunction(partialLikes: Set[Likes]) on a set of persons to create a like function for which the domain consists of all pairs of persons (including \((a,b)\), \((b,a)\) and \(a,a\)). It will complete partialLikes by assuming non-specified relationships are dislikes.

The html function is used to draw a graph of the like function. This graph is specified in the DOT language and can be generated using the .toDotString(like) helper function transforms persons and a like function to graph figures.

import mathlibrepo.selectinginvitees._


val sanghan   = Person("Sanghan")
val youngJu   = Person("Young Ju")
val greny     = Person("Greny")

val persons = Set(sanghan, youngJu, greny)
val partialLikings = Set(sanghan likes youngJu, youngJu likes greny, youngJu dislikes sanghan)

def like = persons.deriveLikeFunction(partialLikings)

List(
  like(sanghan, youngJu),
  like(sanghan, greny),
  like(youngJu, greny)
)


html"<img src=\"https://quickchart.io/graphviz?layout=circo&graph=${persons.toDotString(like)}\" />"

While this approach is useful to manually explore small examples, it still is a lot of manual work. Wouldn’t it be nice if we can generate a complete like function randomly? Use the support function .randomLikeFunction(probability: Double) on a set of persons to create a random like function. For each pair (including \((a,b)\), \((b,a)\) and \(a,a\)), it generates false with probability equal to the ratio or true otherwise.

import mathlibrepo.selectinginvitees._

val sanghan   = Person("Sanghan")
val youngJu   = Person("Young Ju")
val greny     = Person("Greny")

val persons = Set(sanghan, youngJu, greny)

def like = persons.randomLikeFunction(0.7)

List(
  like(sanghan, youngJu),
  like(sanghan, greny),
  like(youngJu, greny)
)

html"<img src=\"https://quickchart.io/graphviz?layout=circo&graph=${persons.toDotString(like)}\" />"

A final example to illustrate how to generate a random input instance. An alternative visualization is used to indicate which persons are liked by the host or not. Note that generating a visualization graph with many persons will not display properly or potentially crash your browser due to the many relationships.

import mathlibrepo.selectinginvitees._
import mathlib.set.SetTheory._

val persons = Person.randomGroup(5)
val personsLiked = persons.take(2)
val personsDisliked = persons \ personsLiked

def like = persons.randomLikeFunction(0.7)

html"<img src=\"https://quickchart.io/graphviz?layout=circo&graph=${persons.toDotString(personsLiked, personsDisliked, like)}\" />"

Simulating Selecting Invitees

In this section we cover how to simulate Selecting invitees (version 4, 5 and 6) . You will learn how to read Scala mathlib simulation code and how it relates to the formalization. We go through Selecting invitees (version 4) step by step, after which you can explore versions 5 and 6 yourself. To make the code more readable, we use names in the code that are more descriptive than the single letters used in math (see Table 1).

⊕Table 1: the mapping from math notation to Scala code.

Selecting invitees (version 4)
Input: A set \(P\), subsets \(L \subseteq P\) and \(D \subseteq P\) with \(L \cap D = \emptyset\) and \(L \cup D = P\), a function \(like: P \times P \rightarrow \{true, false\}\), and a threshold value \(k\).
Output: \(G \subseteq P\) such that \(|G\cap D| \leq k\) and \(|X| + |G|\) is maximized (where \(X = \{p_i,p_j \in G~|~like(p_i,p_j) = true \wedge i\neq j\}\)).

Let’s see how this formalization translates to simulation code. The formalization is implemented in the si4 function, all of the input (\(P\), \(L\), \(D\), \(like\) and \(k\)) is listed as an argument of the function. The type of the output also needs to be defined. In this case the output is a subset \(G\subseteq P\) of persons, translating to the type Set[Person].

def si4(
  persons: Set[Person],
  personsLiked: Set[Person],
  personsDisliked: Set[Person],
  like: (Person, Person) => Boolean,
  k: Int
): Set[Person]

The input in the formalization is subject to a few constraints. We check those constraints in the code and stop the program with an informative error message when the constraints are not met.

// Input must satisfy these constraints, otherwise error.
require(personsLiked <= persons,
        "personsLiked must be a subset of persons")
require(personsDisliked <= persons,
        "personsDisliked must be a subset of persons")
require(personsLiked /\ personsDisliked == Set.empty,
        "personsLiked intersect personsDisliked must be emtpy")
require(personsLiked \/ personsDisliked == persons,
        "personsLiked union personsLiked must equal persons")

The output is defined using two properties. To define output using the set builder we write two functions that compute these properties. First, the host wants to invite at most \(k\) people they dislike \(|G \cap D|\leq k\). The following function returns a Boolean if a given (sub)set of people does not have this property.

// Specify that invitees is valid if |G /\ D| <= k.
def atMostKDislikes(invitees: Set[Person]): Boolean =
  (invitees /\ personsDisliked).size <= k

Second, the formalization states that the number of invited pairs that like each other plus the number of invited people \(|X| + |G|\) is maximal. This is an optimality condition. The next function computes for a given (sub)set of people, the set \(X\) and returns an integer corresponding to \(|X| + |G|\).

⊕The .tupled function transforms a function with \(n\) arguments into a function with 1 argument, where that argument is an \(n\)-tuple. This is needed when applying a function on a set of tuples such as invitees.uniquePairs that correspond to the arguments of that function.

// Specify the optimality condition.
def xg(invitees: Set[Person]): Int = {
  // The number of unique pairs that like eachother.
  val x = { invitees.uniquePairs | like.tupled }.size
  // The number of total invitees.
  val g = invitees.size
  x + g
}

Finally, we specify the set of possible valid outputs. Remember that for any given formalization multiple possible outputs may exist that satisfy the output conditions. Below, we consider all possible subsets of people, i.e., the powerset \(\mathcal{P}(P)\). Any \(G\in\mathcal{P}(P)\) is a subset of people \(G\subseteq P\). From this set of sets we build a set of sets of people that satisfy \(|G \cap D|\leq k\) using atMostKDislikes and the optimality condition \(\arg\max_{|X|+|G|}\) using argMax(xg).

val invitees = { powerset(persons) | atMostKDislikes _ }.argMax(xg)

To complete the implementation, we need to output one valid solution if any exist. If multiple possible solutions exist, we return one at random. Minimally one solution will always exist, namely the empty set, so we can safely ask for a random one.

// Return a (valid) set of invitees at random.
invitees.random.get

This completes the implementation of Selecting Invitees (version 4) . Now we need to create some input for which si4 can evaluate the output.

import mathlibrepo.selectinginvitees._
import mathlib.set.SetTheory._

val group = Person.randomGroup(10)    // Generate random group
val personsLiked = group.take(5)      // The first 5 are liked
val personsDisliked = group.drop(5)   // The rest is disliked

def like = group.randomLikeFunction(.7) // Autogenerate random like relations

html"<img src=\"https://quickchart.io/graphviz?layout=circo&graph=${group.toDotString(personsLiked, personsDisliked, like)}\" />"

def si4(
  persons: Set[Person],
  personsLiked: Set[Person],
  personsDisliked: Set[Person],
  like: (Person, Person) => Boolean,
  k: Int
): Set[Person] = {
  // Input must satisfy these constraints, otherwise error.
  require(personsLiked <= persons,
          "personsLiked must be a subset of persons")
  require(personsDisliked <= persons,
          "personsDisliked must be a subset of persons")
  require(personsLiked /\ personsDisliked == Set.empty,
          "personsLiked intersect personsDisliked must be emtpy")
  require(personsLiked \/ personsDisliked == persons,
          "personsLiked union personsLiked must equal persons")

  // Specify that invitees is valid if |G /\ D| <= k.
  def atMostKDislikes(invitees: Set[Person]): Boolean =
    (invitees /\ personsDisliked).size <= k

  // Specify the optimality condition.
  def xg(invitees: Set[Person]): Int = {
    // The number of unique pairs that like eachother.
    val x = { invitees.uniquePairs | like.tupled }.size
    // The number of total invitees.
    val g = invitees.size
    x + g
  }

  val invitees = { powerset(persons) | atMostKDislikes _ }.argMax(xg)

  // Return a (valid) set of invitees at random.
  invitees.random.get

}

si4(
  persons = group,
  personsLiked,
  personsDisliked,
  like,
  k = 2
)

Keep in mind that the search space grows exponentially with the size of \(P\). If your computer crashes or is taking a long time, you are probably trying to simulate for large (\(>10\)) groups.

From here on, you are free to explore the implementations of Selecting Invitees (versions 5 and 6) on your own. Try simulating some inputs to get a feeling for the differences between the three formalizations. You can even change the simulation code if you want. Perhaps try implementing any of the other versions? After simulating the three models individually, we provide a sandbox for you to compare their behaviour directly.

Selecting invitees (version 5)
Input: A set \(P\), subsets \(L \subseteq P\) and \(D \subseteq P\) with \(L \cap D = \emptyset\) and \(L \cup D = P\), and a function \(like: P \times P \rightarrow \{true, false\}\).
Output: \(G \subseteq P\) such that \(|G\cap L| + |X| + |G|\) is maximized (where \(X = \{p_i,p_j \in G\}~|~like(p_i,p_j) = true \wedge i\neq j\}\)).

import mathlibrepo.selectinginvitees._
import mathlib.set.SetTheory._

def si5(
  persons: Set[Person],
  personsLiked: Set[Person],
  personsDisliked: Set[Person],
  like: (Person, Person) => Boolean
): Set[Person] = {

  // Input must satisfy these constraints, otherwise error.
  require(personsLiked <= persons,
          "personsLiked must be a subset of persons")
  require(personsDisliked <= persons,
          "personsDisliked must be a subset of persons")
  require(personsLiked /\ personsDisliked == Set.empty,
          "personsLiked intersect personsDisliked must be emtpy")
  require(personsLiked \/ personsDisliked == persons,
          "personsLiked union personsLiked must equal persons")

  // Specify the optimality condition.
  def gl_x_g(invitees: Set[Person]): Int = {
    // The number of invitees the host likes.
    val gl = (invitees /\ personsLiked).size
    // The number of unique pairs that like eachother.
    val x = { invitees.uniquePairs | like.tupled }.size
    // The number of total invitees.
    val g  = invitees.size
    gl + x + g
  }

  val invitees = powerset(persons).argMax(gl_x_g)

  // Return a (valid) set of invitees at random.
  invitees.random.get
}

val group = Person.randomGroup(10)    // Generate random group
val personsLiked = group.take(5)      // The first 5 are liked
val personsDisliked = group.drop(5)   // The rest is disliked

def like = group.randomLikeFunction(.7) // Autogenerate random like relations

html"<img src=\"https://quickchart.io/graphviz?layout=circo&graph=${group.toDotString(personsLiked, personsDisliked, like)}\" />"

si5(
  persons = group,
  personsLiked,
  personsDisliked,
  like
)

Selecting invitees (version 6)
Input: A set \(P\), subsets \(L \subseteq P\) and \(D \subseteq P\) with \(L \cap D = \emptyset\) and \(L \cup D = P\), a function \(like: P \times P \rightarrow \{true, false\}\), and a threshold value \(k\).
Output: \(G \subseteq P\) such that \(|Y| \leq k\) and \(|G\cap L|+|G|\) is maximized (where \(Y = \{p_i,p_j \in G\}~|~like(p_i,p_j) = false \wedge i\neq j \}\)).

import mathlibrepo.selectinginvitees._
import mathlib.set.SetTheory._

def si6(
  persons: Set[Person],
  personsLiked: Set[Person],
  personsDisliked: Set[Person],
  like: (Person, Person) => Boolean,
  k: Int
): Set[Person] = {
  // Input must satisfy these constraints, otherwise error.
  require(personsLiked <= persons,
          "personsLiked must be a subset of persons")
  require(personsDisliked <= persons,
          "personsDisliked must be a subset of persons")
  require(personsLiked /\ personsDisliked == Set.empty,
          "personsLiked intersect personsDisliked must be emtpy")
  require(personsLiked \/ personsDisliked == persons,
          "personsLiked union personsLiked must equal persons")

	// Specify that invitees is valid if |Y| <= k.
  def atMostKPairDislikes(invitees: Set[Person]): Boolean = {
    { invitees.uniquePairs | like.tupled }.size <= k
  }

  // Specify the optimality condition.
  def gl_g(invitees: Set[Person]): Int = {
    // The number of invitees the host likes.
    val gl = (invitees /\ personsLiked).size
    // The number of total invitees.
    val g  = invitees.size
    gl + g
  }

  val invitees = { powerset(persons) | atMostKPairDislikes _ }.argMax(gl_g)

  // Return a (valid) set of invitees at random.
  invitees.random.get
}

val group = Person.randomGroup(10)    // Generate random group
val personsLiked = group.take(5)      // The first 5 are liked
val personsDisliked = group.drop(5)   // The rest is disliked

def like = group.randomLikeFunction(.7) // Autogenerate random like relations

html"<img src=\"https://quickchart.io/graphviz?layout=circo&graph=${group.toDotString(personsLiked, personsDisliked, like)}\" />"

si6(
  persons = group,
  personsLiked,
  personsDisliked,
  like,
  k = 2
)

Analyzing and comparing formalizations

Simulations are a useful theoretical tool to uncover consequences of formalization choices, especially those that are hard to derive mathematically. Looking at single input instances of single formalizations is not very informative and wouldn’t be worth the effort of coding. Let’s see what we can learn about the three versions of Selecting Invitees by comparing them to eachother across many inputs. We follow the example questions from Chapter 8.

First we ask: Are these formalizations truly different, or are they equivalent? We can run the simulation for all three versions on the same input to compare their output. To prevent redundant copying, the implementations can be found in SelectingInvitees.si4(.), SelectingInvitees.si5(.) and SelectingInvitees.si6(.).

import mathlibrepo.selectinginvitees._
import mathlib.set.SetTheory._

val group = Person.randomGroup(10)    // Generate random group
val personsLiked = group.take(5)      // The first 5 are liked
val personsDisliked = group.drop(5)   // The rest is disliked

def like = group.randomLikeFunction(.7) // Autogenerate random like relations

val k = 2

html"<img src=\"https://quickchart.io/graphviz?layout=circo&graph=${group.toDotString(personsLiked, personsDisliked, like)}\" />"

val si4out = SelectingInvitees.si4(group, personsLiked, personsDisliked, like, k)
val si5out = SelectingInvitees.si5(group, personsLiked, personsDisliked, like)
val si6out = SelectingInvitees.si6(group, personsLiked, personsDisliked, like, k)

html"SI4: ${si4out.mkString("\t")}"
html"SI5: ${si5out.mkString("\t")}"
html"SI6: ${si6out.mkString("\t")}"

For some inputs the formalizations might be equivalent, but for many others they are not. Next, try to answer the question: How would you be able tell different formalizations apart in terms of the input-output mappings they theorize? Finally the hard work will pay off, because you can use simulations to do this. The code below consists of three steps: (1) generate a set of inputs, (2) compute for all inputs the corresponding output using si4, si5 and si6, (3) perform data analysis and plotting.

For Step 1 and 3 some additional (helper) code is introduced. Step 1 introduces code that generates input using the same helper functions we’ve already seen, but at a larger scale (i.e., more inputs) and by giving control over input properties. This is the constrained input generator (see Chapter 9). In Step 3, we perform an example analysis of the simulation data.

import mathlibrepo.selectinginvitees._
import mathlib.set.SetTheory._

val inputs = Input.generate(
  groupSize         = 6,
  likeDislikeRatios = Set(0, 0.22, 0.66, 1.0),
  pairLikeRatios    = Set(0, 0.22, 0.66, 1.0),
  ks                = Set(0, 0.22, 0.66, 1.0),
  sampleSize        = 1
)

val io4 = inputs.map(input => input -> SelectingInvitees.si4(
  input.group,
  input.personsLiked,
  input.personsDisliked,
  input.like,
  input.k
))
val io5 = inputs.map(input => input -> SelectingInvitees.si5(
  input.group,
  input.personsLiked,
  input.personsDisliked,
  input.like
))
val io6 = inputs.map(input => input -> SelectingInvitees.si6(
  input.group,
  input.personsLiked,
  input.personsDisliked,
  input.like,
  input.k
))

def analysis1(io: (Input, Set[Person])): (Double, Double) = {
  val input      = io._1
  val output     = io._2
  val nrLikes    = input.group.uniquePairs.count(input.like.tupled)
  val nrDislikes = input.group.uniquePairs.count(!input.like.tupled(_))
  val ldRatio    = nrLikes.toDouble / nrDislikes
  val size       = output.size.doubleValue
  (ldRatio, size)
}

val data4A1: List[(Double, Double)] = io4 map {
  case (i: Input, o: Set[Person]) => analysis1(i, o)
}
val data5A1: List[(Double, Double)] = io5 map {
  case (i: Input, o: Set[Person]) => analysis1(i, o)
}
val data6A1: List[(Double, Double)] = io6 map {
  case (i: Input, o: Set[Person]) => analysis1(i, o)
}

val data4string1 = Analyses.scatterDataToString(data4A1, "SI4")
val data5string1 = Analyses.scatterDataToString(data5A1, "SI5")
val data6string1 = Analyses.scatterDataToString(data6A1, "SI6")

html"<img src=\"https://quickchart.io/chart?c={type:'scatter',data:{datasets:[$data4string1,$data5string1,$data6string1]},options:{scales:{xAxes:[{scaleLabel:{display: true,labelString:'like/dislike ratio'}}],yAxes:[{scaleLabel:{display:true,labelString:'size'}}]}}}\" />"

import mathlibrepo.selectinginvitees._
import mathlib.set.SetTheory._

val inputs = Input.generate(
  groupSize         = 6,
  likeDislikeRatios = Set(0, 0.22, 0.66, 1.0),
  pairLikeRatios    = Set(0, 0.22, 0.66, 1.0),
  ks                = Set(0, 0.22, 0.66, 1.0),
  sampleSize        = 1
)

val io4 = inputs.map(input => input -> SelectingInvitees.si4(
  input.group,
  input.personsLiked,
  input.personsDisliked,
  input.like,
  input.k
))
val io5 = inputs.map(input => input -> SelectingInvitees.si5(
  input.group,
  input.personsLiked,
  input.personsDisliked,
  input.like
))
val io6 = inputs.map(input => input -> SelectingInvitees.si6(
  input.group,
  input.personsLiked,
  input.personsDisliked,
  input.like,
  input.k
))

def analysis2(io: (Input, Set[Person])): (Double, Double) = {
  val input      = io._1
  val output     = io._2
  val nrLikes    = input.group.uniquePairs.count(input.like.tupled)
  val nrDislikes = input.group.uniquePairs.count(!input.like.tupled(_))
  val ldRatio    = nrLikes.toDouble / nrDislikes
  val avgLikes   = output.uniquePairs.count(input.like.tupled)
  (ldRatio, avgLikes)
}

val data4A1: List[(Double, Double)] = io4 map {
  case (i: Input, o: Set[Person]) => analysis2(i, o)
}
val data5A1: List[(Double, Double)] = io5 map {
  case (i: Input, o: Set[Person]) => analysis2(i, o)
}
val data6A1: List[(Double, Double)] = io6 map {
  case (i: Input, o: Set[Person]) => analysis2(i, o)
}

val data4string1 = Analyses.scatterDataToString(data4A1, "SI4")
val data5string1 = Analyses.scatterDataToString(data5A1, "SI5")
val data6string1 = Analyses.scatterDataToString(data6A1, "SI6")

html"<img src=\"https://quickchart.io/chart?c={type:'scatter',data:{datasets:[$data4string1,$data5string1,$data6string1]},options:{scales:{xAxes:[{scaleLabel:{display: true,labelString:'like/dislike ratio'}}],yAxes:[{scaleLabel:{display:true,labelString:'average likes'}}]}}}\" />"

The analysis and plotting functionality within the online Scala environment is quite limited. If you want to explore the simulations more extensively consider running the simulations in a dedicated Scala development environment. You can download the code from the mathlib-repo repository.

References

Blokpoel, Mark (2024). mathlib: A Scala package for readable, verifiable and sustainable simulations of formal theory. Journal of Open Source Software, 9(99), 6049, https://doi.org/10.21105/joss.06049

O’Leary, Maura, Williams, Rainey, & Peng Lee, Mario (2023). The Diverse Names Generator: An App for Decreasing Bias and Promoting Inclusion. In Proceedings of the Linguistic Society of America 8(1): 5541. https://doi.org/10.3765/plsa.v8i1.5541.

van Rooij, Iris, & Baggio, Giosuè (2021). Theory before the test: How to build high-verisimilitude explanatory theories in psychological science. Perspectives on Psychological Science, 16(4) 682–697.

van Rooij, I., & Blokpoel, M. (2020). Formalizing verbal theories: A tutorial by dialogue. Social Psychology 51(5), 285-298. https://doi.org/10.1027/1864-9335/a000428