These "Protection agencies" would, for all intents and purposes, become governing bodies. They would have to decide on sets of "rules" for members to be bound by in arbitration... which would effectively become laws. You would pay these "Protection agencies" a "membership fee", which would effectively be a tax. They would fulfill all the useful roles of government, without out all the bloat. The most significant difference is we would all have a choice. Protection Agency A, Protection Agency B, Protection Agency z, no protection agency, etc....
The most honest answer to any of these "How does ancap deal with..." questions is "I don't know, and it doesn't matter". The point is not how we can force everyone to live a "better" life, but how naturally we can't force anyone to do anything. The government is an evil corporate monopoly, and should be put down.
Does everyone think discussion of protection agencies addresses the real issues here? It's like trying to design a 747 by discussing lavatory specs. A good indication that you're out of your league would be if you are also not factoring in the following topics:
- A total quantification of the damage done by an oil spill
- The real drivers behind oil consumption
- The safety protocols employed by oil companies
- Future projected oil demand due to the aspiring populations of certain nations
- Assessments of environmentally important areas
- Ocean currents
- Fish populations and food chains
- The range of fish (migration)