jtilly / matchingr Goto Github PK

Hi I am very new to SM problems but I have a hard time understanding how the input to the galeShapleyMatching() algorithm should look like. Until now I have interpreted a preference ordering as a vector with reviewer id's in descending order of preference, first position in vector means most preferred reviewer etc.
I have interpreted utility cardinals as if position i in the utility cardinal vector has the highest number then proposer i is the most preferred, I did see that the definition of utility cardinals also stated a bijective relationsship with {1,..,n}.
When using this interpretation I get some odd results,
proposerPref <- matrix(c(2,1,1,2),nrow=2)
reviewerUtils <- matrix(c(1,2,2,1),nrow=2)
galeShapleyMatching(proposerPref, reviewerUtils)
OUTPUT
$proposals
[,1]
[1,] 1
[2,] 2
$engagements
[,1]
[1,] 2
[2,] 0

I expected a 1 instead of a 0, could you please explain this to me if you have time

Best regards
Haakan

Need to also see about running valgrind from travis.

Currently, "slots" is the number of slots that each college has available. But is possible each college may a different number of slots.

Is it possible to change this input parameter of the algorithm?

I followed the steps you've been posted in https://github.com/jtilly/matchingR/
However when I coded, there are some errors in "one2one" and "galeShapley" function.

The output from the algorithm doesn't preserve the row and column names associated with the input matrices, can you please add an option to keep them?

As per Brian Ripley's direction:

'microbenchmark' is a package that does not work at all on some platforms (e.g. Sparc Solaris) and is flaky on others (e.g. my Windows laptop). And its nominal maintainer has vanished.

This makes it undesirable for packages to strictly depend on it, but packages

anMC timeit

do. Also, if it is used in Suggests: it should be used conditionally (see §1.1.3.1 of the manual), but packages

JacobiEigen R6 aoos base64url brotli checkmate cubature fourierin funrar matchingR mkin rtrie rucrdtw schumaker storr tibble wrswoR

do not do so.

Please update your package(s).

Hi,
I have been attempting to apply the galeShapley.collegeAdmissions() function in R to a dataset with the following dimensions:
Number of applicants: 62.941
Number of colleges: 3534
I run into the problem that r-studio crashes (it "encounters a fatal error and aborts the session") after some time when running the function with the full dataset. I am however able to run the function successfully with 55.000 applicants and all 3534 colleges. Hence, the problem seems to be related to the size of the dataset. Do you have any suggestions for how one might tweak the function to make it run on the full population?

Please let me know if you require more details on the problem at hand.

Thank you in advance!

Hello,
Is this possible to use galeShapley.collegeAdmissions with incomplete preferences of students over colleges and of colleges over students?

Duplicate: #21

I want to wrap the DAA into a function with several input arguments:

#Define function
matching <- function(nmen, nwomen, wI, wC) 
{
  #generate individual cardinal preference matrices
  uM <- matrix(rnorm(nmen*nwomen, 1000, 200), nrow=nwomen, ncol=nmen) 
  uW <- matrix(rnorm(nwomen*nmen, 1000, 200), nrow=nmen, ncol=nwomen) 
  
  #Calculate attractiveness score of each agent
  aW <- rowMeans(uM)
  aM <- rowMeans(uW)
  
  #Calculate preferences stated by each agent
  uM2 <- (wI*uM + wC*aW)/(wI+wC)
  uW2 <- (wI*uW + wC*aM)/(wI+wC)
  
  #female-optimal matching
  resultsW <- galeShapley.marriageMarket(uW2, uM2) 
  galeShapley.checkStability(uW2, uM2, resultsW$proposals, resultsW$engagements)

  #calculate average utility of each matched agent
  resultsWW <- diag(uW2[resultsW$proposals,1:nwomen])
  uWWav <- mean(resultsWW, na.rm=TRUE)
  resultsWM <- diag(uM2[resultsW$engagements,1:nmen])
  uWMav <- mean(resultsWM, na.rm=TRUE)
}

#set seed
set.seed(0)
#Invoke function
matching(600, 400, 0.5, 0.5)

However, defining and invoking my own function results in this error:

Warning message:
In cpp_wrapper_galeshapley_check_stability(proposerUtils, reviewerUtils, :
matching is not stable; worker 26 would rather be matched to firm 215 and vice versa.

If I simply run the lines within the function it works just fine. Is this a bug or am I doing something wrong?

@thiloklein suggested that we add an algorithm that computes all stable matchings for the marriage market. The Gale-Shapley algorithm only computes two of potentially many stable matchings (either the male-optimal or the female-optimal matching).

The algorithm to compute all stable matchings is described in Gusfield and Irving (1989) on p 121. There's a Java implementation here. The algorithm is implemented in SMAllMatchingsByRotationsImpl.java.

Hi again, I may be completely wrong but I think that in the mens payoff matrix uM Rows corresponds to men and not columns as it says now.

the same holds for womens payoff matrix uW

If I am correct there is two problems with the preference order matrix prefM

1. rows corresponds to men as in uM
2. and if row 1 corresponds to the preference order of man 1, then the preference order is not proper since it contains two 3's

thanks for a great package otherwise, best regards
Haakan

Ricky gave a great talk at GAMES about applying Scarf's lemma to find 'approximately' stable matchings. I think here is a video of him giving the talk somewhere else.

The basic idea is that the stable roommates problem, or more general matching problems, such as many to one matching in which workers have preferences over the other workers at the firm to which they're matched, often do not have stable matchings, however, an application of Scarf's lemma can result in 'fractionally' stable matchings, which as I understand it are basically matchings in which agents are fractionally assigned. Ricky's paper then is about showing that those fractions are informative in shuffling around parameters (such as the capacities at various firms) to result in a 'nearby' stable matching, and he derives bounds such as "No firm will need to change capacity by more than 3" and "the total change in capacity is no more than 9". He gives an algorithm for computing these nearby stable matchings using Scarf's lemma.

Anyway, the algorithm for solutions to Scarf's lemma is known to be computationally hard. But it might be neat someday to try to implement this.

I would like to set slots for some of the colleges zero, such as this:

studentPref <-
  matrix(data = c(1,2,3,4,1,2,3,4,1,2,3,4), nrow = 4)
collegePref <-
  matrix(data = c(1,2,3,1,2,3,1,2,3,1,2,3), nrow = 3)


galeShapley.collegeAdmissions(
  studentPref = studentPref,
  collegePref = collegePref,
  slots = c(1,2,0,0))

which returns

$matched.colleges
$matched.colleges[[1]]
[1] 1

$matched.colleges[[2]]
[1] 2 3

$matched.colleges[[3]]
[1] NA  3

$matched.colleges[[4]]
[1] NA  3


$matched.students
     [,1]
[1,]    1
[2,]    2
[3,]    4

I believe $matched.colleges[[3]], $matched.colleges[[4]] (both should be empty) as well as $matched.students[3,1] (should be 2) are wrong but I may be doing this wrong.
Setting slots = c(1,2,3,0) in the above example kind of works as expected, except for $matched.colleges[[4]] which should be empty instead of c(NA, NA).

Is it even possible to have zeros as elements of slots vector?

uM = matrix(c(1.0, 0.5, 0.0,

•           0.5, 0.0, 0.5), nrow = 2, ncol = 3, byrow = TRUE)
  

uW = matrix(c(0.0, 1.0,

•           0.5, 0.0,
  

•           1.0, 0.5), nrow = 3, ncol = 2, byrow = TRUE)
  

matching = galeShapley.marriageMarket(uM, uW)
Error in galeShapley.marriageMarket(uM, uW) :
could not find function "galeShapley.marriageMarket"

Should be split out of main.cpp into gale.cpp, stable.spp, util.cpp, etc.