Illegal extraction of forest resources is fought, in many developing countries, by patrols that try to make this activity
less profitable, using the threat of confiscation. With a limited
budget, officials will try to distribute the patrols throughout
the forest intelligently, in order to most effectively limit extraction. Prior work in forest economics has formalized this
as a Stackelberg game, one very different in character from
the discrete Stackelberg problem settings previously studied
in the multiagent literature. Specifically, the leader wishes to
minimize the distance by which a profit-maximizing extractor will trespass into the forest—or to maximize the radius
of the remaining “pristine” forest area. The follower’s costbenefit analysis of potential trespass distances is affected by
the likelihood of being caught and suffering confiscation.
In this paper, we give a near-optimal patrol allocation algorithm and a 1/2-approximation algorithm, the latter of which
is more efficient and yields simpler, more practical patrol allocations. Our simulations indicate that these algorithms substantially outperform existing heuristic allocations.