CSC/ECE 517 Spring 2019 - Project E1928. Allow reviewers to bid on what to review

About Expertiza

Expertiza is a web application through which students can submit and peer-review learning objects (articles, code, web sites, etc). The Expertiza project is supported by the National Science Foundation. It is used in select courses at NC State and by professors at several other colleges and universities.

Problem statement

Students currently are able to “bid” for the projects that they want to do as an assignment. On the other hand, for reviewing others’ work, the policy that’s currently in use is “first-come-first-serve”. We would try to implement the Top Trading Cycles algorithm that assigns review topics to students in a priority.

The bidding policy for project topics that students want to work on is already implemented. Students can currently bid on project topics for their team assignment. This reduces a lot of possible conflicts in assigning topics to each team. This is in contrast to our desired implementation, which will make use of students instead of teams, since a single student bids on a topic.

There’s also reviewing work for each assignment. Currently, the policy to assign the project to the reviewer is “first-come-first-serve”. Students that choose to review a project first will get that project.

However, this policy creates an issue — while reviewing students’ work, sometimes the same project is requested to be reviewed a lot of times, while some other projects are not requested as much. A similar bidding policy for assigning projects to reviewers can help students who want to review a project the most to be most likely to receive that project. The completion of this project will allow students to also bid on what projects they are interested in reviewing.

We need to alter the “first-come-first-serve” to the “bidding” policy. In this policy, students will be matched to review a submission up to the maximum reviewers.

The projects includes implementation of the top trading cycles algorithm on Expertiza.

Bidding policy (Stable marriage problem)

As part of this assignment, we have to analyse the implementation of the stable marriage problem which is a stable sorting algorithm.

A certain community consists of n men and n women. Each person ranks those of the opposite sex in accordance with his or her preferences for a marriage partner. We seek a satisfactory way of marrying off all members of the community. Imitating our earlier definition, we call a set of marriages unstable (and here the suitability of the term is quite clear) if under it there are a man and a woman who are not married to each other but prefer each other to their actual mates.

Definition: An assignment of couples will be called unstable if there are two men α and β who are married to women A and B, respectively, although β prefers A to B and A prefers β to α.

So, we can ask the question: For any pattern of preferences is it possible to find a stable set of marriages?

Before giving the answer let us look at some examples.

Example 1. The following is the “ranking matrix” of three men, α, β, and γ , and three women, A, B, and C.

Man\Woman	A	B	C
α	1,3	2,2	3,1
β	3,1	1,3	2,2
γ	2,2	3,1	1,3

The first number of each pair in the matrix gives the ranking of women by the men, the second number is the ranking of the men by the women. Thus, α ranks A first, B second, C third, while A ranks β first, γ second, and α third, etc.

There are six possible sets of marriages; of these, three are stable. One of these is realized by giving each man his first choice, thus α marries A, β marries B, and γ marries C. Note that although each woman gets her last choice, the arrangement is nevertheless stable. Alternatively one may let the women have their first choices and marry α to C, β to A, and γ to B. The third stable arrangement is to give everyone his or her second choice and have α marry B, β marry C, and γ marry A. The reader will easily verify that all other arrangements are unstable.

In the existing implementation, we have match_new_teams_to_topics method in lottery_controller that performs this stable sorting algorithm for teams that have bid for an assignment. Our objective would be to implement a similar strategy, but we would use students instead of teams since there are no "team reviews". Every student selects their own assignment to review

References

1. College Admissions and the Stability of Marriage (1962), D. Gale and L. S. Shapley
2. CSC/ECE_517_Fall_2018/E1856_Allow_reviewers_to_bid_on_what_to_review