Communications of the ACM
Last byte
Opioid Games
Credit: Amani A / Shutterstock
There are two sources of illegal opioids: legitimately manufactured ones that have been diverted to drug dealers, and criminally manufactured ones that were always intended for dealers. A special video dispenser, markings on the pills, and a little machine vision can go a long way toward dealing with the legitimately manufactured ones. This column, however, is concerned about with the criminally manufactured opioid pills.
The setting is 10 ports of entry. For simplicity each port has 1000 importers of whom 100 are smugglers (but law enforcement does not know who they are). Each importer brings in 10 containers per day (so 10,000 containers per port per day) and there are 10 packages per container. One agent can inspect five containers per day. Law enforcement (L) has 1000 agents altogether for all 10 ports.
The trafficker (T) wants to bring in 100 opioid packages a day through each port and may allocate them in many ways among smugglers. Law enforcement (L) wants to capture as many opioid packages as possible.
Good strategies for each party depend on how many days this "game" goes on.
If we consider a game of just one day and L distributes 100 agents to each port, then consider two extremal strategies between which T could choose for each port:
- (Centralized) Give all 100 opioid packages to one smuggler to put in evenly among that smuggler's 10 containers; and
- (Distributed) Give one opioid package to each of 100 smugglers. Each smuggler will put the opioid package in a random one of the 10 containers that smuggler imports.
Suppose L allocates its agents randomly to 100 of the 1000 importers and each agent inspects five containers of that importer. L instructs the agents to modify the purely random strategy with what L calls the "Teamwork Modification:" if an agent finds an opioid package then another agent will help the first one so together they will inspect all the containers of that importer. We call this combined strategy the Random with Teamwork strategy.
Warm-up. What is the expected number of opioid packages that L will capture, when using the Random with Teamwork strategy, based on each extremal strategy of T?
Solution to Warm-Up. The expectation for the Distributed strategy is the number of agents times the probability that an agent is inspecting a smuggler's containers times the probability that the five containers inspected by the agent contain at least one opioid package times the number of opioid packages the agent will find: 100 * (1/10) * (1/2) * 1 = 5 opioid packages. For the Centralized strategy, the expected capture rate is 100 * (1/1000) * 100 = 10 opioid packages, because the Teamwork Modification strategy suggests that other agents will help the one who finds a first opioid package. Together, they will find all 100 in the 1-in-10 chance that some agent finds at least one opioid package.
Conclusion. The Distributed strategy enjoys a greater expected number of opioid packages that get through for T than the Centralized strategy.
The consequences for the smugglers are somewhat different however. With the Distributed strategy, approximately five smugglers would be captured. With the Centralized strategy, at most one and only with probability 1/10.
Question. Suppose T insists on the Distributed strategy all the time. Can L capture all the smugglers in 20 days possibly by delaying some containers from leaving the port by a day or two and reallocating agents?
Solution. By allocating all 1000 agents to one port for two days—d and d+1—the agents can go through all the containers of day d and identify all the smugglers. This is called the Carpeting Strategy.
So if the game is played long enough, the Carpeting Strategy should encourage the trafficker T to use the Centralized strategy, because more smugglers will avoid arrest for longer. However, a compromise is possible: T might use the "Semi-Distributed strategy" in which 10 smugglers each receive 10 opioid packages and each smuggler puts those packages in one of that smuggler's containers. This has the same expected loss to T as the Distributed strategy in terms of the number of opioid packages that can be lost to agents (if there are 100 agents in that port), but it puts fewer smugglers in danger if L uses the Carpeting Strategy.
Upstart 1. Given the setting of this problem as described here and given that L uses the Random with Teamwork strategy and keeps 100 agents at every port, how many days must the game be played for Semi-Distributed to be worse for T than Centralized measured in terms of the total number of opioid packages delivered?
Upstart 2. Answer the same question when T uses the Carpeting Strategy.
Upstart 3. If L uses the Carpeting Strategy for every pair of days with a certain probability p but otherwise uses the Random with Teamwork Strategy, what is the best strategy for T over some number k days where T can choose between Centralized, Distributed, and Semi-Distributed?
Footnotes
All are invited to submit their solutions to [email protected]; solutions to upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html
The Digital Library is published by the Association for Computing Machinery. Copyright © 2019 ACM, Inc.
No entries found