rsd function

Random serial dictatorship mechanism

Implements the random serial dictatorship algorithm algorithm for a fair division of indivisible objects among individuals. The mechanism takes individuals' prioirty order as an input or alternatively draws a random permutation of the agents form the uniform distribution. Individuals are then successively assigned an object in that order (so the first agent in the ordering gets the first pick and so on).

rsd(
  nIndividuals = ncol(prefs),
  nObjects = nrow(prefs),
  prefs,
  priority,
  seed = NULL,
  nSlots = rep(1, nObjects)
)

Arguments

• nIndividuals: integer indicating the number of individuals in the matching problem. Defaults to ncol(prefs).
• nObjects: integer indication the number of objects in the matching problem. Defaults to nrow(prefs).
• prefs: matrix of dimension nObjects x nIndividuals with the jth column containing students j's ranking over the objects in decreasing order of preference (i.e. most preferred first).
• priority: (Optional) vector of length nIndividuals indicating the priority of the individuals in decreasing order (i.e. highest individuals first). If none is given, a random order is chosen.
• seed: (Optional) integer setting the state for random number generation. Defaults to seed = 123.
• nSlots: (Optional) vector of length nObjects indicating the owners/slots possible/available for each object. (If nSlots only consists of ones this means that every object can only have one owner, if the numbers are higher interpreting objects for example as schools might be more intuitive). Defaults to a vector of length nObjects filled with ones.

Returns

rsd returns a data frame containing the final matching of individuals (ind) to objects (obj).

Examples

## Generate preference-matrix
prefs <- matrix(c(1,2,3,
                  3,1,2,
                  1,3,2),
                  byrow = FALSE, ncol = 3)

priority <- c(1,2,3)
nSlots <- c(1,1,1)

rsd(prefs = prefs, priority = priority, nSlots = nSlots)

Author(s)

Thilo Klein, Alexander Sauer