That last line might actually lead to the solution. Have a rat tax levied on land owners, in proportion to their alottment of land, and how many rats government officials find in the district where the respective land holdings are situated, and empower land owners to appoint whichever rat exterminator that they like for their district. I imagine that will lead to the incentives needed to solve the problem.