Livestock grazing on public lands continues to be a source of intense conflict and debate. We analyze this problem using a dynamic game. Low grazing fees let ranchers capture more rent from grazing. This increases the incentive to comply with federally mandated regulations. Optimal grazing contracts therefore include grazing fees that are lower than competitive private rates. The optimal policy also includes random monitoring to prevent strategic learning by cheating ranchers and avoid wasteful efforts to disguise noncompliant behavior. Finally, an optimal policy includes a penalty for cheating beyond terminating the lease. This penalty must be large enough that the rancher who would profit the most from cheating experiences a negative expected net return.