Incentivizing Peer Grading in MOOCS: An Audit Game Approach

1 Introduction

Massive Open Online Courses (MOOCs), such as those offered by Coursera, are online courses open to the general public. Those who enroll in such a course are usually required to complete ongoing assignments as part of the course requirements. However, as their name suggests, MOOCs tend to have student enrollment in the thousands, with only a limited number of teaching assistants available to grade assignments. To overcome this issue, MOOCs employ peer assessment: the students grade each other, with the course staff acting as highlevel moderators. There are several obvious issues with peer grading. First, students' ability to grade is likely to be quite

Yair Zick

Carnegie-Mellon University yairzick@cmu.edu

heterogeneous: some students naturally have a better grasp of course material than others. Second, students may not be very commited to grading their peers. While Coursera does impose a 20% grade penalty on students who fail to complete their grading assignments on time, this says nothing about the quality of the work. Though there are educational merits to grading others' work (being exposed to different solutions, verifying that one's solution was correct and so on), even the most hard working student may not be interested in spending time on grading if that time can be better spent on completing their own homework assignments.

That said, if course staff employ an overly strict policy towards students who poorly grade their peers, they risk poor student performance on class assignments. Students will spend too much time on peer grading and too little on the actual assignment. To further complicate matters, students who feel that staff is treating them unfairly will simply drop out. Course staff control students' time division by controlling the likelihood that a student's grading is audited. A high likelihood of audit will lead to a higher likelihood of being caught misgrading which in turn leads to the student investing more into peer grading over working on the assignment. Since the hours one can spend auditing are limited, one must carefully assign TAs to student graders in order to ensure that they behave in a desirable manner. This leads to the following natural question: what assignment of TA auditors to students best incentivizes them to optimally balance their time between grading and completing assignments?

In this work, we provide some insights into this matter.

1.1 Our Contribution

We model this setting as a non-cooperative game between course staff and students; the solution concept we employ is a Stackelberg equilibrium. Both choices are natural in this setting.

First, both students and course staff have actions that they may take to further their agendas: students' actions are a choice of the number of hours to assign to grading vs. the number of hours to assign to completing the assignment. The course staff/auditors' actions are an allocation of TAs/auditors to students. Furthermore, both course staff and students have natural utility functions; in the case of students their utility is their grade, and in the case of the course staff their utility is the overall class grade minus a penalty for each misgrading that occurs. A misgrading penalty may encode the number of hours that are invested in dealing with student complaints or expected dropout rates.

Next, Stackelberg equilibrium is an equilibrium concept where one side gets to observe the (mixed) strategy of another. The first player who moves is called the defender and the player who gets to observe the defender's strategy is called the attacker. In our setting we think of the course staff as the defenders and the students as the attackers. Thus, the course staff publicly declare how they plan to audit students (perhaps via their publicly available course handbook). The students must choose how much effort they invest in their homework assignments and how much they invest in grading.

Note that a Stackelberg security game [Tambe, 2011] traditionally has one attacker and one defender, whereas our setting handles multiple independent non-uniform attackers.

We begin by showing that finding a TA allocation that maximizes the expected utility of the course staff is generally NPhard. However, there exists an efficient dynamic programming algorithm that is able to find a TA allocation ε close to the defender-optimal allocation. This solution is, unfortunately, unsatisfactory: we show that there exist games where a TA allocation ε close to the optimal allocation does not guarantee that the defender's utility is ε-close to optimal. In fact, it is possible that a TA allocation that is close to the optimal but has attacker best-responses that offer an arbitrarily low utility to the defender. Intuitively, this may happen since students who have only slightly less TA resources allocated to them may decide to switch from investing a lot in peer grading, to investing nothing. However, we show that under some mild assumptions on the students' utility functions, we can guarantee that TA allocations that are ε-close to the optimal guarantee ε-optimal utility to the defenders.

We assume that the course staff have full information of students' utilities. While this is a rather strong assumption, it can be justified. As Piech et al. [2013] show, it is possible to elicit student grading abilities and expected class performance based on their past grading performance.

1.2 Related work

The most well-known application of Stackelberg games is security games [Tambe, 2011; Jain et al., 2010; Kiekintveld et al., 2009; An et al., 2011]. A key difference between our work and the standard security game model is that we assume multiple attackers with different utility functions. While previous applications of Stackelberg games for physical security have considered multiple attacks by an attacker [Korzhyk et al., 2011], we separate ourselves from them by giving each attacker a disjoint objective. In our model, defenders want to punish attackers for misbehaving, but do not want to do so too much. This assumption is employed in audit games [Blocki et al., 2013; 2015]. However, Blocki et al. [2013] and Blocki et al. [2015] assume that they are given some parameter α representing the "punishment level" for the defender. In our setting, over-auditing of certain students may cause them to invest too much effort into grading, which may not be optimal for the course staff. In other words, in our setting the motivation not to over-audit is intrinsic rather than a given parameter.

The problem of handling low quality peer grading has been studied from various aspects. Piech et al. [2013] focus on using machine learning techniques on peer grading networks in order to find the true scores of homework assignments. Wright et al. [2015] design and test a peer grading mechanism suitable for small sized courses. Their idea is to initially let the TA check every student's grading and then promote some students to an independent grader level, while adding the provision that students may complain about their grades. Shalem et al. [2014] design a graphical model based approach to predict student performance in a MOOC. Ghosh and Kleinberg [2013] focus on designing incentive mechanisms to increase student participation in the course discussion forum. Vallam et al. [2015] model student participation in discussion forums as a game; Li and Conitzer [2013] use a Stackelberg game model to set exam questions. Finally, Jurca and Faltings [2003] propose an incentive compatible peer reputation mechanism; however, their setup is quite different from ours.

2 Preliminaries

Let N = {1, . . . , n} be the set of students. Each student i ∈ N needs to decide how much time to allocate to homework, and how much to allocate to peer grading. Thus, a student's strategy is a value xi ∈ [0, 1], where xi is the percentage of time devoted to homework. The instructor has a total of ktot resources. It is convenient to think of ktot as the number of TA-hours available to the instructor. The instructor's allocation is a vector k ∈ Rn≥0 such that ∑ni=1 ki ≤ ktot , where ki is the probability that student i is audited.

Observe that specifying k is enough to recover a probability distribution over pure allocations of TAs to students - i.e. an instructor mixed strategy - by the Birkhoff von-Neumann decomposition (see [Korzhyk et al., 2011] for details, and [Birkhoff, 1946] for the original result).

The game proceeds as follows. First, the instructor chooses a vector k such that ∑i∈N ki ≤ ktot . Each student i ∈ N observes k, and chooses xi ∈ [0, 1] that maximizes her utility. We assume that every student's utility is completely identifiable with her grades on the assignment. More formally, a student's utility function is given by two real-valued functions: Hi and Mi. Hi(x) is the expected grade of i if she invests an x portion of her time in homework, and Mi(1 - x) is the expected probability that she is punished for misgrading her peers if audited assuming she invests (1 - x) percent of her time on grading. The punishment is scaling, as we do not want to have a case where the punishment is greater than the student's entire homework score. Putting it all together, we get that the expected utility of student i under k if she invests an xi portion of her time in homework is

We assume that Hi is monotone increasing; similarly, we assume that Mi is monotone decreasing. We note that there still may be a chance of misgrading even with a high amount of effort. That is, we are not guaranteed that Mi(1) = 0.

Next, let us consider the utility of the instructor. The instructor is interested in getting students to put reasonable effort into both their homework assignment and into peer grading. The utility that the instructor gets from homework is simply a weighted average over students. That is, each student is associated with a weight αi, and the instructor's utility from homework if students' strategies are given by x is given by ∑ni=1 αiHi(xi). Similarly, the instructor incurs a penalty βi for each student i that has misgraded; thus, the instructor's expected penalty given x is ∑ni=1 βiMi(1 - xi). These different values of αi and βi represent a weighted average over the different types of student. For example, undergraduate students may be expected to perform better on homework, masters students may be expected to focus more on grading, and students who are auditing the class may be expected to spend less time overall. These values are determined solely by the instructor's preferences, and are not influenced by student behavior. Putting it all together, the instructor's utility function is given by

We are interested in finding a TA allocation k that maximizes the instructor's utility, assuming that students observe k and then play a best response to their level of audit.

Definition 2.1 (Instructor-Optimal Stackelberg Equilibrium). An instance of INSTRUCTOROPTEQ is given by:

• A number of students N
• For each student a homework and misgrading function Hi,Mi : [0, 1] → [0, 1]
• For each student an instructor utility function weighted by (α1, . . . , αn); (β1, . . . , βn)
• Audit resources given by ktot
• Target value V

It is a "yes" instance if there exists some instructor mixed strategy k such that for students' best response to k, the instructor's utility is at least V ; it is a "no" instance otherwise.

The optimization variant of Definition 2.1 is

3 Computing Instructor-Optimal Strategies

We begin by showing that INSTRUCTOROPTEQ is computationally intractable for simple step-shaped homework and misgrading functions.

Theorem 3.1. INSTRUCTOROPTEQ is NP-hard.

Proof. Our reduction is from the KNAPSACK problem [Garey and Johnson, 1979]. An instance of KNAPSACK is given by a list of n objects N = {1, . . . , n}, each with a positive weight wi and positive value vi, a value V ∈ R+ and a weight W ∈ R+. It is a "yes" instance if there is some S ⊆ N such that ∑i∈S wi ≤ W and ∑i∈S vi ≥ V , and a "no" instance otherwise. Given an instance of KNAPSACK 〈N = {1, . . . , n}, w, v, V, R〉, We assume that vi and wi are positive integers for all i ∈ N; furthermore, we assume that W ≥ wi for all i ∈ N, and that V < v(N) = ∑ni=1 vi.

We construct the following game: The items are the students. For each student i ∈ N we define

where C > 0 is some very large constant. We also write

We set αi = 0 and βi = wi, making the instructor utility - ∑i∈N wiviMi(1-xi). That is, the instructor does not care at all about students' performance in the course, just about minimizing their misgrading probability, weighted by wivi. We assume that the staff has ktot = 1, and our student utility is - WC (v(N) - V ). Suppose that student i is audited with probability ki and she assigns all of her efforts to doing her homework; then Ui(1, ki) = 1C vi(1 - ki W wi ). For any x < 1, Ui(x, pi) = 0. Therefore, the best response of i to ki is xi = 1 if ki < wi W , and is xi < 1 otherwise.

Suppose that we have a "yes" instance of knapsack. This means that there is some set of students S∗ such that ∑i∈S∗ wi ≤ W and their total value is ≥ V . Suppose that we set k∗ i = wi W for all i ∈ S∗ and k∗ i = 0 for all i ∈ N \ S∗ . Since ∑i∈S∗ wi ≤ W this is a valid instructor strategy. Under this strategy, instructor utility is

-

On the other hand, if there exists an audit strategy k∗ that guarantees utility of at least - WC (v(N)-V ) we observe that setting k∗ i > wi W to student i adds no benefit to the instructor, and if k∗ i < wi W one may as well set k∗ i = 0. Thus, we assume w.l.o.g. that k∗ i ∈ {0, wi W } for all i ∈ N. Then, the students audited with probability wi W correspond to a subset of items that weigh less than W and have a value of at least V , which concludes the proof.

4 Finding Approximately Optimal Strategies

Since computing the optimal solution is computationally infeasible, we then consider finding an approximate solution. If we limit the precision with which we express the probabilities kt, then we obtain an efficient dynamic programming algorithm for solving the instructor-optimal Stackelberg equilibrium problem. Our algorithm involves solving sub-problems where we only consider a subset of our students with a subset of our resources. We define xj(k) to represent the maximum possible utility our instructor can get from all the students with indices t ≤ j with k amount of audit resource to allocate. Note that this k is not necessarily a whole number. Additionally, note that if k > j, xj(k) = xj(j) as at most there is one resource allocated to each student.

Furthermore, define ft(k) to be the utility the instructor gets from just the student t when k audit resources are allocated to him. In general, computing ft(k) is dependent on the student's utility functions. Let ||f|| be the worst case evaluation time of this utility response function.

Suppose we allocate our auditors with maximum bit precision b. From this, we propose Algorithm 1:

Algorithm 1: Solving Fixed Precision K

Data: b, ktot, T = {1, 2, . . . n}, ft(k) Result: xt(ktot) ∀t,k : xt(k) = -∞; for j = 1; j ≤ n; j++ do for k = 0; k ≤ ktot; k = k + 2-b do if j = 1 then xj (k) = max(xj (0), xj (k - 2-b ), fj (k)); else for l = 0; l ≤ 1; l = l + 2-b do xj (k) = max(xj-1(k - l) + fj (l), xj (k));

Proof. First, we reason about the correctness of the algorithm. Suppose for the current iteration of the loop in the algorithm, the indices are j and k. We can show that for all integral j ′ and for all k′ with b bits of precision, we will have already found the optimal solution to the subproblem xj ′ (k′ ). We do so using induction on j.

Our base case where j = 1 computes the following. We iterate through all possible values of f1(l) and take the one that gives the most utility.

For any later loops, inductively assume that we have solved the subproblem for all values j ′ < j, and for all possible values of k. Our optimal solution will assign at most 1 unit of audit to the jth target. We consider every possible fj(l) + xj-1(k - l). Since our total utility is equal to the sum of the utility from each target, the maximum of this value will be the maximum possible utility for xj(k). This completes our claim about optimality in each iteration j.

Thus, at the end of our algorithm we get the maximum possible utility for xn(ktot), and therefore we will have the maximum possible utility our instructor can achieve with the resources available to them.

Regarding the running time: note that we have three levels of loops. The inner loop will iterate at most 2b times, the second level loop will iterate ktot2b times, and the topmost will iterate at most n times. At the core of each loop, we will need to compute fj(k - l) and compare several values. Recall that computing fj(k - l) takes worst case ||f|| time. Therefore, our algorithmwill take time O(ktot4bn||f||).

While the above algorithm is efficient for a fixed b (or for a b proportional to log(ktot)), the important question is whether we can guarantee that the discrete rounded solution provides utility close to the optimal solution. In section 4.2, we identify the conditions under which we can provide ε′ - approximation guarantees for any constant ε′ . In the next section, we demonstrate that guaranteeing an approximate best response from the students could potentially result in a nonnegligible loss of utility for the instructor.

4.1 ε-Best Response

Suppose we are given an optimal (unrounded) solution ki and the students' responses are xi. Suppose we evaluate an approximate strategy ki∗ that is within ε (ε = 2-b ) of the true solution. Additionally, suppose that the student's utility functions are Lipschitz continuous, which means that the function's rate of change is limited. We can then show that xi is an ε-best response to ki∗, meaning that we can cap the loss of utility that a student has for playing xi instead of whatever is the true optimal response to k∗ i . In order to show this, we first prove the following lemma.

Lemma 4.2. Let f : [0, 1]2 → R be a function such that for any fixed x0 and y0, f(x, y0) and f(x0, y) are Lipschitz continuous with constant c. Then the function

is Lipschitz continuous with constant c, i.e.,

Proof. Let y1, y2 ∈ [0, 1] be two points; let x∗1 , x∗2 be two points such that x∗1 ∈ argmaxx∈[0,1] f(x, y1) and x∗2 ∈ argmaxx∈[0,1] f(x, y2). As these function are Lipschitz continuous over a compact set, the max values are within the compact set. Then F(y1) = f(x∗1 , y1) and F(y2) = f(x∗2 , y2). Without loss of generality, suppose that F(y1) ≥ F(y2). By Lipschitz continuity, |f(x∗1 , y1) - f(x∗1 , y2)| ≤ c|y1 - y2|.

Now, either f(x∗1 , y1) ≥ f(x∗1 , y2) or f(x∗1 , y1) < f(x∗1 , y2). If f(x∗1 , y1) < f(x∗1 , y2), then using the fact that f(x∗1 , y2) ≤ f(x∗2 , y2) we can conclude f(x∗1 , y1) < f(x∗2 , y2). The last inequality is nothing but F(y1) < F(y2), a contradiction; therefore f(x∗1 , y1) ≥ f(x∗1 , y2).

Next, by Lipschitz continuity we know that

using the fact that f(x∗1 , y2) ≤ f(x∗2 , y2). Combining the above two inequalities we conclude that f(x∗1 , y1) ≤ c|y1 - y2| + f (x∗2 , y2), which is same as |F (y1) - F (y2)| ≤ c|y1 - y2|. Thus, F(y) is Lipschitz continuous.

We are now ready to prove the following result:

Theorem4.3. Suppose that Hi andMi are Lipschitz continuous with constant c. Suppose that ki is the instructor-optimal solution. Let xi be the student's best response to an audit level of ki, and choose k∗ i such that |ki -k∗ i | ≤ ε. Then xi is a cε-best response to k∗ i

Proof. We have that Hi andMi are Lipschitz continuous. Let OPT(ki) be the best response of student i to an audit level of ki. According to Equation 1, student utility is given by

In an equilibrium, students will play their best response strategies in response to ki. We thus define the utility of a student playing their optimal strategy as

We have that both Hi and Mi are Lipschitz continuous. Therefore, for a fixed k0 we have UTIL(x, k0) is Lipschitz continuous. Suppose we are given y1, y2 such that |y1-y2| < ε. Since both Hi and Mi are positive and bounded by 1 we have that for any fixed x0

Thus, applying Lemma 4.2 we claim that OPT(ki) is Lipschitz continuous, i.e.,

Therefore, if |ki-k∗ i | ≤ ε, then |OPT(ki)-OPT(k∗ i )| ≤ cε.

4.2 Exact Best Response

However, even if xi is an cε-best response to k∗ i , what could be said about the exact best response x∗i to k∗ i ? We would hope that this response x∗i would be close to xi. Unfortunately, that need not be true for an arbitrary Lipschitz continuous function, as we show in the following example.

Example 4.4. Define our utility functions to be:

If we then plug these values into our utility function:

If we consider the two cases disjointly, the two strategies that the student would consider are xi = 0 and xi = 1. The payoffs the student will get from those strategies are 9 10 (1 - 9 10 ki) and 1 10 (1- 1 10 ki) respectively.

If ki = 1, we can see that the student could potentially choose 1. However, if ki is any less, the student would opt for 0. Remember that the utility function of our instructor is of the form:

If we then set αi = 0, we get that this represents a significant drop in the instructor's utility.

Next we characterize the cases where Algorithm 1 guarantees the instructor utility to be close to the optimal. In order to do this, we first present conditions under which the student's strategy is stable under small changes to ki.

Theorem 4.5. Let ki and k∗ i be two different possible audit levels such that |ki -k∗ i | < ε. Let xi and x∗i be the response of our student under ki and k∗ i respectively.

Suppose the student's utility functions ∀k0 : f(x, k0) is strictly concave, ∀k0 : f ′′ (x, k0) < -d, and ∀x0, k0 : f(x, k0), f(x0, k) are Lipschitz continuous.

Proof. We are given ki and k∗ i . By assumption, xi (x∗i ) is the maximizer of f(x, ki) (f(x, k∗ i )). Therefore f(xi, ki) > f(x∗i , ki) and similarly f(xi, k∗ i ) < f(x∗i , k∗ i ).

Remember that |ki - k∗ i | < ε. Due to the Lipschitz continuity of f(x0, k):

For any positive v, consider xi + v. Recall that: ∀k0 : f ′′ (x, k0) < -d. The Taylor expansion of f(xi + v, ki) (in remainder form) is given by

where ˆx lies between xi + v and xi. Since f ′ (xi, ki) is zero and f ′′ (ˆx, ki) < -d we get

We can use a similar derivation to get

Next, for contradiction, we suppose that |xi - x∗i | ≥ √(4cε/d). Take v = |xi - x∗i |. Then, the above two inequalities allow us to conclude that

Using Lipschitz continuity for the LHS and RHS we get

Using the above two we get

By the definition of x∗i , this is a contradiction. Therefore, |xi - x∗i | < √(4cε/d).

If we assume both grading and doing homeworks have diminishing returns, it is very reasonable to say that (for a given ki > 0) Hi(x) and (1 - kiMi(x)) are both strictly monotonically increasing concave nonnegative functions. For shorthand, let g(x) = (1 - kiMi(x).

Therefore, H′ i (x) > 0 and H′′ i (x) < 0. Similarly, g′ (x) > 0 and g′′ (x) < 0. The first derivative of Hi(1 - x)g(x) is Hi(1 - x)g′ (x) - H′ i (1 - x)g(x). The second derivative is equal toH′′ i (1-x)g(x)-2H′ i (1-x)g′ (x)+Hi(1-x)g′′ (x). We can see that it will always be negative.

We also assume the second derivative is below a certain value -d. If both of our functions are strictly increasing by at least a certain value d this assumption would always be true (because -2H′ i (1 - x)g′ (x) < -2d2 ). The intuition behind this assumption is that for a fixed amount of work, the student will always reap a minimum amount of benefit.

Using this result, we characterize when the instructor's utility is close to optimal.

Theorem4.6. If for all i Hi andMi are Lipschitz continuous with constant e and |xi - x∗i | < √(4cε/d), we have the following bound

Proof. Recall that our instructor's utility is given by:

Note that if both Hi andMi are Lipschitz continuous, then

implies that for some constant value e:

Therefore, we bound the instructor utility from each student

Thus, the overall utility is bounded as

The above guarantee is of the order n√ε. Given any constant ε′ we can choose b such that 2-b = ε is of order (ε′ )2 /n2 , giving approximation ε′ and running in time poly(n5 , (ε′ )-4 ).

5 Discussion

The largest barrier to implementing our model in real world scenarios is discovering the utilities of the students. Each student only provides a small number of observations to this function, since students are only in MOOCs for a limited amount of time, ruling out some learning techniques recently proposed [Blum et al., 2014]. Each observation will likely be noisy, as there are many hidden variables that can affect how a student performs week to week. Each observation will likely be biased, as each week their homework and gradees change. Putting these observations together into a coherent utility function is a challenge. Previous work on MOOCs [Piech et al., 2013] was able to get an approximate idea of how good each student was as a grader and how well each student performed, but there still was noise. Any system that attempts to learn the utilities would bound to have noise as well (such as [Nguyen et al., 2014]), which we do not consider here.

Another barrier is communicating changes in audit level in a way that would be relevant to the students. Realistically, students are not going to differentiate between a .051 and a .052 chance of being audited. They might react if they are told that they are being "highly" vs "lowly" audited, or if their chance of being audited has increased. If we were dealing with automated systems, these small changes may matter.

In this model, we assume that students can only improve their grading at the cost of working on homework and can only improve their homework score at the cost of working on grading. There is no way the instructor can motivate a student to allocate more time in total. Expansions on our model might want to add a parameter that represents total time spent on the class instead of capping the total at a normalized value of 1.

Our work could be expanded to scenarios beyond peer grading. We could potentially consider any model where targets have to divide their time between a selfish action and a non-selfish action. For example, this could be extended to a factory dividing their time between making a product and cleaning up their industrial waste. All of our results would carry over, with possibly an easier way of determining utility functions.

6 Conclusion

We introduced a novel way of modelling how audits can incentivize desired student behavior in MOOCs. We argued that our model is realistic, and showed that computing an approximate equilibrium is computationally feasible.

Our work represents a new paradigm for strategic peergrading. MOOCs require trustworthy grading and helpful feedback. By considering the strategic decisions each student has to make, course designers can better understand how their actions influence students' behavior and choose mechanisms to improve the experience of students within the limited TA resources.

7 Acknowledgements

This research was partially supported by the National Science Foundation (NSF) grants CCF0424422 and CNS1064688.