Skip to contents

A dirichlet_tree object represents a Dirichlet-tree distribution on ballots. By specifying the tree structure for the ranked ballots, the Dirichlet-tree is initialized with the same prior structure described by Everest et al. (2022) . There are methods provided for observing data (to obtain a posterior distribution) along with methods to sample election outcomes and sets of ballots from the posterior predictive distribution.

Format

An R6Class generator object.

References

Everest F, Blom M, Stark PB, Stuckey PJ, Teague V, Vukcevic D (2023). “Ballot-Polling Audits of Instant-Runoff Voting Elections with a Dirichlet-Tree Model.” In Computer Security. ESORICS 2022 International Workshops, 525--540. ISBN 978-3-031-25460-4. .

Everest F, Blom M, Stark PB, Stuckey PJ, Teague V, Vukcevic D (2022). “Auditing Ranked Voting Elections with Dirichlet-Tree Models: First Steps.” doi:10.15157/diss/021 . .

Active bindings

a0

Gets or sets the a0 parameter for the Dirichlet-tree.

min_depth

Gets or sets the min_depth parameter for the Dirichlet-tree.

max_depth

Gets or sets the max_depth parameter for the Dirichlet-tree.

vd

Gets or sets the vd parameter for the Dirichlet-tree.

Methods


Method new()

Create a new dirichlet_tree prior distribution with the specified tree structure. See Everest et al. (2022) for further details.

Usage

dirichlet_tree$new(
  candidates,
  min_depth = 0,
  max_depth = length(candidates) - 1,
  a0 = 1,
  vd = FALSE
)

Arguments

candidates

A character vector, with each element (must be unique) representing a single candidate.

min_depth

The minimum number of candidates which must be specified for a valid ballot in the election.

max_depth

The maximum number of candidates which can be specified for a valid ballot in the election.

a0

The prior parameter for the distribution.

vd

A flag which, when TRUE, employs a parameter structure which reduces to a regular Dirichlet distribution as described by Everest et al. (2022) .

Returns

A new dirichlet_tree prior.

Examples

dtree <- dirichlet_tree$new(candidates = LETTERS, a0 = 1., min_depth = 1)


Method print()

print shows some details of the distribution and its parameters.

Usage

dirichlet_tree$print()

Returns

The dirichlet_tree object.


Method update()

Updates the dirichlet_tree object with observations of ballots. This updates the parameter structure of the tree to yield the posterior Dirichlet-tree, as described in Everest et al. (2022) .

Usage

dirichlet_tree$update(ballots)

Arguments

ballots

A set of ballots of class `prefio::preferences` or `prefio::aggregated_preferences` to observe. The ballots should not contain any ties, but they may be incomplete.

Returns

The dirichlet_tree object.

Examples

ballots <- prefio::preferences(
  t(c(1, 2, 3)),
  format = "ranking",
  item_names = LETTERS[1:3]
)
dirichlet_tree$new(
  candidates = LETTERS[1:3]
)$update(ballots)


Method reset()

Resets the dirichlet_tree observations to revert the parameter structure back to the originally specified prior.

Usage

dirichlet_tree$reset()

Returns

The dirichlet_tree object.

Examples

ballots <- prefio::preferences(
  t(c(1, 2, 3)),
  format = "ranking",
  item_names = LETTERS[1:3]
)
dtree <- dirichlet_tree$new(
  candidates = LETTERS
)$update(ballots)
print(dtree)
dtree$reset()
print(dtree)


Method sample_posterior()

Draws sets of ballots from independent realizations of the Dirichlet-tree posterior, then determines the probability for each candidate being elected by aggregating the results of the social choice function. See Everest et al. (2022) for details.

Usage

dirichlet_tree$sample_posterior(
  n_elections,
  n_ballots,
  n_winners = 1,
  replace = FALSE,
  n_threads = NULL
)

Arguments

n_elections

An integer representing the number of elections to generate. A higher number yields higher precision in the output probabilities.

n_ballots

An integer representing the total number of ballots cast in the election.

n_winners

The number of candidates elected in each election.

replace

A boolean indicating whether or not we should replace our sample in the monte-carlo step, drawing the full set of election ballots from the posterior

n_threads

The maximum number of threads for the process. The default value of NULL will default to 2 threads. Inf will default to the maximum available, and any value greater than or equal to the maximum available will result in the maximum available.

Returns

A numeric vector containing the probabilities for each candidate being elected.

Examples

ballots <- prefio::preferences(
  t(c(1, 2, 3)),
  format = "ranking",
  item_names = LETTERS[1:3]
)
dirichlet_tree$new(
  candidates = LETTERS,
  a0 = 1.,
  min_depth = 3,
  max_depth = 6,
  vd = FALSE
)$update(
  ballots
)$sample_posterior(
  n_elections = 10,
  n_ballots = 10
)


Method sample_predictive()

sample_predictive draws ballots from a multinomial distribution with ballot probabilities obtained from a single realization of the Dirichlet-tree posterior on the ranked ballots. See Everest et al. (2022) for details.

Usage

dirichlet_tree$sample_predictive(n_ballots)

Arguments

n_ballots

An integer representing the total number of ballots cast in the election.

Returns

A prefio::preferences object containing n_ballots ballots drawn from a single realisation of the posterior Dirichlet-tree.

Examples

ballots <- prefio::preferences(
  t(c(1, 2, 3)),
  format = "ranking",
  item_names = LETTERS[1:3]
)
dirichlet_tree$new(
  candidates = LETTERS,
  a0 = 1.,
  min_depth = 3,
  max_depth = 6,
  vd = FALSE
)$update(
  ballots
)$sample_predictive(
  n_ballots = 10
)

Examples


## ------------------------------------------------
## Method `dirichlet_tree$new`
## ------------------------------------------------

dtree <- dirichlet_tree$new(candidates = LETTERS, a0 = 1., min_depth = 1)


## ------------------------------------------------
## Method `dirichlet_tree$update`
## ------------------------------------------------

ballots <- prefio::preferences(
  t(c(1, 2, 3)),
  format = "ranking",
  item_names = LETTERS[1:3]
)
dirichlet_tree$new(
  candidates = LETTERS[1:3]
)$update(ballots)


## ------------------------------------------------
## Method `dirichlet_tree$reset`
## ------------------------------------------------

ballots <- prefio::preferences(
  t(c(1, 2, 3)),
  format = "ranking",
  item_names = LETTERS[1:3]
)
dtree <- dirichlet_tree$new(
  candidates = LETTERS
)$update(ballots)
print(dtree)
#> Dirichlet-tree (a0=1, min_depth=0, max_depth=25, vd=FALSE)
#> Candidates: Z X Y V T Q O N A C W U D I B H S E F G K J P L R M
#> Observations:
#>  preferences frequencies
#>  [A > B > C]           1
dtree$reset()
print(dtree)
#> Dirichlet-tree (a0=1, min_depth=0, max_depth=25, vd=FALSE)
#> Candidates: Z X Y V T Q O N A C W U D I B H S E F G K J P L R M
#> Observations:
#> [1] preferences frequencies
#> <0 rows> (or 0-length row.names)


## ------------------------------------------------
## Method `dirichlet_tree$sample_posterior`
## ------------------------------------------------

ballots <- prefio::preferences(
  t(c(1, 2, 3)),
  format = "ranking",
  item_names = LETTERS[1:3]
)
dirichlet_tree$new(
  candidates = LETTERS,
  a0 = 1.,
  min_depth = 3,
  max_depth = 6,
  vd = FALSE
)$update(
  ballots
)$sample_posterior(
  n_elections = 10,
  n_ballots = 10
)
#>   A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T 
#> 0.3 0.0 0.2 0.0 0.0 0.0 0.0 0.0 0.0 0.1 0.0 0.1 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 
#>   U   V   W   X   Y   Z 
#> 0.0 0.0 0.1 0.0 0.1 0.1 


## ------------------------------------------------
## Method `dirichlet_tree$sample_predictive`
## ------------------------------------------------

ballots <- prefio::preferences(
  t(c(1, 2, 3)),
  format = "ranking",
  item_names = LETTERS[1:3]
)
dirichlet_tree$new(
  candidates = LETTERS,
  a0 = 1.,
  min_depth = 3,
  max_depth = 6,
  vd = FALSE
)$update(
  ballots
)$sample_predictive(
  n_ballots = 10
)
#>                preferences frequencies
#> 1  [A > C > V > P > J > U]           1
#> 2  [D > Q > Z > C > J > A]           1
#> 3  [G > V > Y > S > B > T]           1
#> 4  [L > K > H > V > O > X]           1
#> 5  [L > M > D > H > N > Y]           1
#> 6  [N > K > F > E > L > P]           1
#> 7      [Q > Y > U > B > V]           1
#> 8  [V > A > M > D > R > X]           1
#> 9  [W > P > J > N > E > F]           1
#> 10 [Z > P > Q > I > L > M]           1