be a satisficer or use the secretary problem to find love!

I was surprised to read that a study recommends using a satisficing strategy to find a mate [Link to article, Michigan State press release]

The researchers studied the evolution of risk aversion and discovered that it is in the human nature to go for the safe bet when their stakes are high. For instance whether or not mate. This human nature is traced back to the earliest period of their evolution.

The study is computational (i.e., not a psychological study) and involves simulation that mimics the degree and range of risk-taking in human behavior. It suggests that we are satisficers, not optimizers* and that something like the secretary problem is not suitable for finding a mate/spouse [read Mike Trick’s counterpoint here].

In the secretary problem, the goal is to maximize the probability of finding the “best” secretary and its optimal solution by interviewing up to n secretaries, letting a few go, and then selecting the next secretary that is the “best” so far (totally how dating works, right?!) The secretary problem focuses on finding the best possible solution (only the best will do) but the optimal strategy may lead to a suboptimal secretary (good but not the best) or no secretary at all. In fact, the optimal strategy leaves a pretty big chance of finding no secretary, which will occur if the “best” overall is one of those candidates that we let go at the beginning. I have a figure below of the probability that a candidate is hired at all (it’s the blue line), and it’s way less than 1.0.

The probability of hiring a secretary/finding a spouse as a function of the number of candidates (n) simulated over 10,000 replications

The probability of hiring a secretary/finding a spouse and the probability of hiring the *best* secretary/choosing the right spouse as a function of the number of candidates (n) simulated over 10,000 replications

Do I think this satisficing advice is really worth taking? Well, I have three daughters and I’ll encourage them to optimize instead of satisfice.

Here are my other Valentine’s Day, secretary problem, and love posts from my blog archive:

Valentine’s day posts from the #orms blogosphere:

* Yes, I know that satisficing and optimizing are really the same thing, but I finding-the-absolute-best and not-walking-away-without-empty-handed are really two different objective functions.

Do you optimize or satisfice? What other OR models can be compared to finding a partner for life aside from the secretary problem?

snowblowing is NP-complete

The recent winter storm left a lot of snow on my driveway. A lot. My driveway is the perfectly place for huge snowdrifts to form. A tweet of my shoveling resulted in the discovery of The Snowblower Problem  by Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell, and Valentin Polishchuk (HT @fbahr)

The Snowblower Problem (SBP) answers the following question:

How does one optimally use a snowblower to clear a given polygonal region?

The snowblower problem is like the Traveling Salesman Problem (TSP): the  objective to find the shortest snow removing tour to remove all the snow from a domain (the polygonal region). The difference between TSP and SBP is that the snow is displaced into a nearby region in the SBP and that if the snow is piled too high, then the snowblower cannot clear the snow. SBP is NP-complete.

There are three model variants considered in the paper differ in how and where you can throw the snow: (1) the default model where snow can be thrown in any direction, (2) the adjustable throw direction (left, right, or center) and (3) left throw only. Changing the snow throw direction is cumbersome, so the fixed direction model variant (the left throw only) has more practical value.

Theorem: The SBP is NP-complete, both in the default model and in the adjustable throw model, for inputs that are polygonal domains with holes.

From the paper.

From The Snowblower Problem by Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell, and Valentin Polishchuk.

The SBP is similar in spirit to various zombie research models: it’s a silly problem context that has real applications. The applications for SBP are in milling and lawn-mowing. And you guessed it: lawn mowing is also NP-complete.

The paper goes on to present various approximation algorithms for SBP. The algorithms used decompose the snowy region into Voronoi cells and then clear the domain cell-by-cell. It is difficult to succinctly summarize the results here without introducing a bunch of mathematical notation so I’ll refer you directly to the paper for mathematical details.  The conclusion notes that the approximation ratios are likely not the best possible, so there are opportunities for follow on work.

What is your snow removing algorithm and how close to optimality is it?


Update: this is my favorite comment about this post on twitter. I also shovel my snow the old fashioned way and agree!


it’s possible that we have both record levels of immunization & record levels of vulnerability to infectious disease: why social networks matter

My recent blog post on eradicating polio through vaccination ends with this:

Part of the reason why vaccination is challenging is because social networks play a critical role in disease transmission. Even if enough people have been vaccinated in aggregate to obtain herd immunity in theory, it may not be enough if there are hot spots of unvaccinated children who can cause outbreaks. There are hot spots in some areas in California and other states that have generous exemption policies.

I want to elaborate. It’s possible that we have both:

  1. record levels of immunization, and
  2. record levels of vulnerability to highly infectious diseases.

The CDC estimates that 95% of kindergarteners have had MMR and DTaP immunization and 93% have had varicella (chicken pox) immunization. [Link] And yet there are outbreaks! The CDC’s immunization goal is 95%. Given that some kids truly should not be immunized (like those with specific allergies or those who have had serious reactions to other vaccines), there isn’t much room to allow for parents to choose to opt out while maintaining herd immunity. In fact, just a few people opting out has been linked to several disease outbreaks [Links here and here]. This is especially critical for newborns, who cannot be immunized for anything except Hepatitis B, and babies under a year old who cannot get the MMR vaccine for the measles. There is a measles outbreak among babies who cannot be vaccinated against the measles yet in a Chicagoland day care. In other words: please vaccinate your children if you can.

<side note>The rotavirus vaccine was off the market from 1999 to 2006, so my oldest daughter wasn’t vaccinated. She came down with a bad case of rotavirus at age 3.5 when my second daughter was 3 months old. Luckily, my second daughter had received her first rotavirus immunization 2 weeks prior and didn’t get sick.<\side note>

Despite having record levels of immunization, we’ve seen a lot of cases of pertussis, measles, and other infectious diseases. It’s all about social networks!

Let’s return to herd immunity. Estimates from Wikipedia indicate that most diseases require an immunization rate of 85%-94% (the herd immunity threshold) in a “well mixed” population to achieve herd immunity. In other words, this might be an optimistically low threshold when kind of ignoring social networks. An article in The Atlantic reports a 92% herd immunity threshold for most diseases and a 95% herd immunity threshold for highly infectious diseases like the measles (they cite a World Health Organization document). A population being well-mixed is a big assumption. Kids within the same school may travel in different social circles that are more homogenous than the school as a whole. That’s important. A social circle that has a low level of immunization may introduce risk to the kids in the community even if the school as a whole is above the herd immunity threshold. That’s what happened in the Chicagoland day care with the unvaccinated babies who hung out together every day. But more generally, people who don’t vaccinate generally have friends who also don’t vaccinate.

The Guardian has a nice simulation about herd immunity and social networks. They consider a few different communities with different vaccination rates (from 10% to 99.7%) with vaccinated, unvaccinated (susceptible) and vaccinated but susceptible individuals (the CDC estimates that MMR only “takes” in 93%-97% of those vaccinated). A few random individuals then come in contact with the measles. The red individuals represent infections. There are measles outbreaks even with a 90% vaccination rate.

The Guardian simulation results for exposing a community to measles.

The Guardian simulation results for exposing a community to measles. Sometimes a vulnerable community is OK (see the 83.8% vax rate here) but in general there is an outbreak.

We need vaccines because they protect against highly contagious diseases. Epidemiologists use the “basic reproduction number” (R0) to estimate how infectious a disease is, where R0 is the average number of people someone with the disease is expected to infect. The smaller R0 is, the less a disease tends to spread. Exponential growth happens when R0 > 1, but there is exponential growth (flu R0=2.5) and then there is exponential growth (measles R0 = 16!!). While R0 can be lowered by actions like good hygiene, some diseases are inherently more contagious than others. We can’t get the measles to spread as “slowly” as seasonal flu no matter how much we encourage people to wash their hands and use hand sanitizer. This is why we need vaccines as well as a higher herd immunity threshold for diseases like measles than we do for the flu. When that one person who hasn’t been vaccinated infects 12-18 other people, we have an epidemic on our hands. From the Wall Street Journal:

“Imagine if you had a reproduction number of 15 for measles with everybody susceptible,” said Derek A.T. Cummings, a professor of epidemiology at Johns Hopkins Bloomberg School of Public Health. “If you go in and vaccinate half the people, the expected reproduction number goes down to 7.5.”

The Guardian provides a nice figure of deadliness (the y-axis) vs. the basic reproduction numbers (the x-axis) of various diseases. That cluster of diseases on the right hand side is composed of highly infectious. Measles, rotavirus, whooping cough are highly infectious in ways that the seasonal flu just isn’t. In fact, the CDC recommends vaccines for that entire cluster of highly infectious diseases over there on the right except for malaria (which isn’t a huge problem in the US) because they are really that bad.

Deadliness vs. Basic Reproduction Number.

Deadliness vs. Basic Reproduction Number.

I get the impression we keep having these debates without agreeing on what the problem is and what its consequences are. It’s reasonable to say that most people in my generation have no idea what a massive infectious disease outbreak looks like. It’s not like the seasonal flu, where you know just a few people who succomb to the flu every year but you’re usually OK. With these highly contagious diseases, outbreaks may be rare but then BOOM, everyone you know is sick. Chicken pox (R0 = 8.5) may be an exception. The chicken pox epidemic in my kindergarten class was the only time I experienced a massive infectious disease outbreak (class attendance dwindled to 3-5 students for a few days).

<side note>I may have had the mildest case of the chicken pox ever recorded. I had just a few poxes/blisters and itched for maybe an hour. But I bear a scar on my face from one of the few poxes I had(!) </side note>

I’ll stop here for now. Let me know your thoughts on vaccination, social networks, herd immunity, and disease outbreaks.

Related posts:

eradicating polio through vaccination and with analytics

The most recent issue of Interfaces (Jan-Feb 2015, 45(1)) has an article about eradicating polio published by Kimberly M. Thompson, Radboud J. Duintjer Tebbens, Mark A. Pallansch, Steven G.F. Wassilak, and Stephen L. Cochi from Kid Risk, Inc., and the U.S. Centers for Disease Control and Prevention (CDC). This paper develops and applies a few analytics models to inform policy questions regarding the eradication of polioviruses (polio) [Link to paper].

The article is timely given that vaccination is in the news again. At least this time, the news is fueled by outrage over GOP Presidential contenders Chris Christie and Rand Paul’s belief that parents should have the choice to vaccinate their children [example here].

Polio has essentially been eradicated in the United States, but polio has not been eradicated in the developing world. The Global Polio Eradication Initiative (GPEI) helped to reduce the number of paralytic polio cases from 350,000 in 1988 to 2,000 in 2001. This enormous reduction has mainly been achieved through vaccination. There are two types of vaccines: the live oral vaccine and the inactivated vaccine (IPV). Those who have been vaccinated have lifelong protection but can participate in polio transmission.

The paper summarizes a research collaboration that occurred over a decade and was driven by three questions asked by global policy leaders:

  • What vaccine (if any) should countries use after wild polioviruses (WPV) eradication, considering both health and economic outcomes?
  • What risks will need to be managed to achieve and maintain a world free of polio?
  • At the time of the 1988 commitment to polio eradication, most countries expected to stop polio vaccinations after WPV eradication, as had occurred for smallpox. Would world health leaders still want to do so after the successful eradication of WPVs?

The paper is written at a fairly high level, since it summarizes about a decade of research that has been published in several papers. They ended up using quite a few methodologies to answer quite a few questions, not just about routine immunization. Here is a snippet from the abstract (emphasis mine):

Over the last decade, the collaboration innovatively combined numerous operations research and management science tools, including simulation, decision and risk analysis, system dynamics, and optimization to help policy makers understand and quantify the implications of their choices. These integrated modeling efforts helped motivate faster responses to polio outbreaks, leading to a global resolution and significantly reduced response time and outbreak sizes. Insights from the models also underpinned a 192-country resolution to coordinate global cessation of the use of one of the two vaccines after wild poliovirus eradication (i.e., allowing continued use of the other vaccine as desired). Finally, the model results helped us to make the economic case for a continued commitment to polio eradication by quantifying the value of prevention and showing the health and economic outcomes associated with the alternatives. The work helped to raise the billions of dollars needed to support polio eradication.

The following figure from the paper summarizes some of the problems addressed by the research team. The problems involved everything from stockpiling vaccines, to administering vaccines for routine immunization and to containing outbreaks:

A decision tree showing the possible options for preventing and containing polio. From "Polio Eradicators Use Integrated Analytical Models to Make Better Decisions" by Kimberly M. Thompson, Radboud J. Duintjer Tebbens, Mark A. Pallansch, Steven G.F. Wassilak, Stephen L. Cochi in Interfaces

A decision tree showing the possible options for preventing and containing polio. From “Polio Eradicators Use Integrated Analytical Models to Make Better Decisions” by Kimberly M. Thompson, Radboud J. Duintjer Tebbens, Mark A. Pallansch, Steven G.F. Wassilak, Stephen L. Cochi in Interfaces

I wanted to include one of the research figures used in the paper that helped guide policy and obtain funding. The figure (see below) is pretty interesting. It shows the costs, in terms of dollars ($) and paralytic polio cases associated with two strategies over a 20 year horizon: (1) intense vaccination until eradication or (2) intense vaccination but only until it’s “cost effective” (routine immunization). The simulation results show that the cumulative costs (in dollars or lives affected) are much, much lower over a 20 year time horizon if they adopt a the vaccination until eradication strategy. This helped to make a big splash. From the paper:

In a press release related to this analysis, Dr. Tachi Yamada, then president of the Bill & Melinda Gates Foundation’s
Global Health Programs stated: “This study presents a clear case for fully and immediately funding global polio eradication, and ensuring that children everywhere, rich and poor, are protected from this devastating disease.” In 2011, Bill and Melinda Gates made polio eradication the highest priority for their foundation


In full disclosure, I’m a big fan of immunization. All of my children are fully vaccinated. My grandmother was born in 1906 and used to tell stories about relatives, so many of whom ultimately died of infectious diseases (Grandma lived until she was ~102!). I’m glad my kids don’t have to worry about getting many of these diseases. I’m also proud to contribute to herd immunity.  We come in contact with people who have compromised immune systems or could not get immunized, and I’m glad we’re playing our part in keeping everyone else healthy. Part of the reason why vaccination is challenging is because social networks play a critical role in disease transmission. Even if enough people have been vaccinated in aggregate to obtain herd immunity in theory, it may not be enough if there are hot spots of unvaccinated children who can cause outbreaks. There are hot spots in some areas in California and other states that have generous exemption policies.

Related posts:



rare events: there is an app for that

Is my flight going down?

The Economist has a story about an iOS app called “Am I Going Down?” that estimates the odds of your flight going down based on the departure and arrival airports, the airline, and the type of plane used [Link]. The methodology isn’t available, but presumably it’s based on past performance (# crashes / # of flights)

This app highlights our terror associated with rare events. The Economist story came out yesterday and there was a plane crash today. I’m trying not to overestimate the risk associated with rare events, but it’s hard when they happen and the endless news cycle begins.

People are really bad at assessing risk. There is a huge risk analysis literature on how we tend to overestimate rare events, and this overestimation drives policy decisions. I like two papers by Chauncey Starr and Chris Whipple about how we perceive risk and what we do about these perceived risk. I’ve included 2 figures from their 1980 Science paper on how to identify which technological risks are acceptable to society.

Perception of risk. We tend to overestimate rare risks. Unless they are incredibly rare, in which case we are able to ignore these risks completely.

Perception of risk. We tend to overestimate rare risks. Unless they are incredibly rare, in which case we are able to ignore these risks completely.


Here are a few estimates of risks. We tend to overestimate rare risks (like those associated with getting vaccinated) and underestimate common risks (like Type 2 diabetes).


Starr, C., & Whipple, C. (1980). Risks of risk decisions. Science, 208(4448), 1114-1119.

Starr, C., & Whipple, C. (1984). A perspective on health and safety risk analysis. Management Science, 30(4), 452-463.

I’ve blogged before about rare risks. Here are a few of these blog posts:

What rare risks do you over-estimate?

what are the odds of 3+ people winning the lottery?

I was on the 10 o’clock evening news last night on NBC15 Madison to talk about the odds of three people in Dane County winning the Supercash! lottery. There are about half a million residents, and I have no idea how many people play the lottery every day, but I was able to do a few quick back of the envelope calculations

  • If everyone in Dane County plays the lottery every day (unrealistic!) then we would expect 3+ people to win in a single day to happen every 0.71 years.
  • If half of everyone in Dane County plays the lottery every day (almost all the adults, still unrealistic!) then we would expect 3+ people to win in a single day to happen every 5.12 years.
  • If 1 in 10 people in Dane County play the lottery every day (in the ballpark of reality) then we would expect 3+ people to win in a single day to happen every 584 years.
  • If 1 in 20 people in Dane County play the lottery every day (in the ballpark of reality) then we would expect 3+ people to win in a single day to happen every 4620 years.

I am having trouble embedding the video, but you can go here to see it.

Area nerd explains the probability of winning the lottery, compares the likelihood of winning the lottery to being eaten by a bear.

Tips for working with the media:

  • You can overthink it. “Make things as simple as possible, but not simpler.” Except in this case, even simpler is good. You don’t have a couple of minutes to break apart a concept. Insightful comments that can fit in a tweet are good.
  • News moves fast. I was recorded 2 hours after getting the call for the story. In that two hours, I had to take care of things at work, pick up my daughters, and go home. There was very little time for research.
  • Crunch some numbers ahead of time to put things into perspective. You may only have time for back of the envelope calculations. If you don’t have all the information (like how many people play the lottery every day), make an assumption and test a few values.
  • I find it helpful to explain probabilities in terms of odds (1 in 1.6 million) and expected time to observe the event (every 584 years).
  • If you’re dealing with rare events, be prepared to compare the rare event to other rare events. Someone will definitely ask about the odds of getting struck by lightning.

Related posts:

operations research for drug policy and addiction

I enjoyed listening to Jon Caulkins’ Omega Rho lecture at the INFORMS Annual Meeting. The abstract for the talk is:

Operations Research in Service of Drug and Addictions Policy: Lessons from and for the Discipline of Operations Research
Jonathan P.Caulkins
H.Guyford Stever Professorship of Operations Research and Public Policy
Carnegie Mellon University

I am an OR missionary. I have carried our tools and perspectives into the fields of drug policy and addiction. When traveling far afield, one often encounters opportunities to do good by applying what seem to be quite basic precepts back home, and one returns with a deeper understanding of one’s own culture and its strengths and weaknesses. That has certainly been true of my professional tour. I will share success stories – instances in which by virtue of being the only person thinking about an issue from the perspective of a math modeler, I was able to make fundamental contributions by doing analyses that anyone with training in OR would view as quite elementary. I will also try to share some insights into our disciplinary culture. Drug policy, like most policy domains, is inherently interdisciplinary. So I work with scholars from many disciplines. That experience has given me an appreciation of different disciplines’ strengths and limitations when grappling with messy unstructured problems. I firmly believe that diversity is essential to good decision making, including disciplinary diversity. But I am also interested in which disciplines’ graduates are leaders, not just members, of the teams that shape high-level and strategic decision making. I will close with some thoughts about how we might increase our discipline’s “market share” within t! hose leadership roles.

This was an interesting talk about being an OR practitioner and solving real problems. Jon talked about the general principles he uses to influence policies. This involves doing good work, but more importantly, it involves asking good research questions. Jon asks excellent research questions. Jon summarized the impact his answers to these questions have had on policy. Jon’s work modeled drug lifetimes and life cycles using Markov chain models, a feature common to all drug types that could be used to forecast when drugs would go out of favor. He talked about modeling types of users–heavy and light–and the insights one can obtain when considering different classes of users. I enjoyed the discussion on pricing and drug purity, two issues that are often overlooked by decision makers and therefore have impact.

A really great part of the talk was when Jon took on Big Data. He said that in his experience, being the first with any data at all is really important for influencing policy. Many times, public safety leaders make decisions with zero data points or one data point (an anecdote!). Going from 0 to 100 data points can change a policy, going from 100 data points to “Big Data,” not so much.

David Hutton blogged about Jon’s talk on the INFORMS2014 blog [Link].

Earlier posts about Jon Caulkins’ talks:


Get every new post delivered to your Inbox.

Join 2,611 other followers