Tag Archives: public policy

reverse auctions for the television spectrum and graph coloring problems

Karla Hoffman from George Mason gave an nice talk at the 2013 INFORMS Computing Society Conference about reverse auctions to buy back the TV spectrum. It is an issue if you still use an antenna to watch TV (see the bottom of this post if you are shocked that people still use antennas).

Here is the problem. Once upon a time, the FCC gave the networks the bandwidth. Changes in technology — the move to digital and the needs of broadband — have motivated the need to reassign the spectrum to stations. This will happen in 2014.

The reverse auction problem of assigning networks to a piece of the spectrum. A station requires 6MHz of the spectrum plus a buffer. The same piece of the spectrum could be assigned to stations in, say, Denver and Baltimore. The same antenna would not be able to pick up both stations, and therefore, there would be no interference.  But different stations in, say, Washington DC and Baltimore could not share the same piece of the spectrum.

This leads to a graph covering problem:

  • the TV stations are the vertices
  • there is an edge between two TV stations if the TV stations are nearby (i.e., an antenna could pick up both stations if they are close enough)
  • 6MHz chunks of the spectrum are the colors.

If you’re not familiar with the graph (or vertex) coloring problem, here is the general idea. It is an assignment of “colors” to vertices on a graph, where no two adjacent vertices share the same color [Link]. Coloring a map is a type of graph coloring problem on a planar graph, where the states are the vertices and there is an “edge” between two states if they share a border. This leads a map where no two adjacent states have the same color (see below).

Example of a solution to a graph coloring problem

There are some additional side constraints in the TV spectrum coloring problem, such as UHF and VHF designations and public service space reserved in the spectrum. It’s a complex problem.

The graph coloring problem is a feasibility problem (can I color my graph with 4 colors?) There are only so many “colors” available in the TV spectrum. The graph coloring problem described above could thus lead to infeasible solutions, and this may be an issue in the auctions (a bid should not be accepted if that would lead to an infeasible solution). This motivates the need for a feasibility checking routine during the auctions. Later, broadcasters that do not participat or whose bids are not accepted must be reassigned to the remaining TV stations available.

In terms of the auctions, there are plenty of other challenges, such as planning what the auction will look like, how pricing will be handled, and how one will determine a winner.

In the US, about 10% of people use antennas. Two people in the audience (including me) still use bunny ears. This was such  shocking news for one attendee that he posted it to twitter:

Mike Trick

I try to stay too busy blogging to have time for TV (:

I probably got some of the details about the auctions wrong. It’s a complex problem and Karla did a great job of distilling the essence of the problem without overwhelming us with unneccessary details (there were a lot of necessary details). If you know more about these auctions and how OR will be used, please leave a comment.

Related posts:


the exit polling supply chain

A WSJ Washington Wire blog post describes the Presidential election exit polling supply chain in New York in the immediate aftermath of Hurricane Sandy. The Washington Wire blog post highlights the polling firm Edison Research, based in New Jersey. Edison provided the questionnaires used by pollsters who would collect information about the ballots cast. As you might recall, New Jersey and New York were extremely damaged from the hurricane.

Questionnaires

One of the logistical challenges was in printing and delivering the questionnaires used by pollsters around the country. The questionnaires need to be timely, so they are usually shipped one week before the election. Sandy was on track to strike 8 days before the election, so a rush order was placed with the printer. Two thirds of the questionnaires were mailed before Sandy struck and Edison’s election office lost power along with the rest of New Jersey. The rest of the questionnaires were stored for two days until they had to be shipped. Edison printed the mailing labels from their main office, and then UPS shipped the 400 packages to pollsters via Newark Airport. While Edison had redundancy in their system (e.g., the mailing labels could be printed in another facility and a redundant system alerted employees of the change), it only worked because not all of their offices lost power.

Mail Delivery

While Edison relied on UPS to deliver the mail, it is worth noting that USPS mail service continued as normal except for one day during Hurricane Sandy (HT to @EllieAsksWhy).

Gas

Edison relied on having employees implement Plan B. With the gas shortage, it was difficult for employees to get to work when they needed to save gas for other car trips. Organizing car pools was more difficult than normal, since employees could not rely on communicating by email or cell phone.

Hotels

As I mentioned in an earlier post, there were few/no vacancies at hotels that had power, which provided challenges for Edison employees who wanted to work out of a hotel (most offices and homes were without power) or pollsters who needed to travel to different cities to perform exit polling.  I’m not sure how these issues were resolved.

Local transportation to the polls

The NYC public transportation was up and running on election day, so the pollsters could make it there for the big day. The subway reopened with limited runs the Thursday before Election Day and was running as usual on Election Day.

What if Hurricane Sandy came later?

Edison Research managed, but having an 8 day head start was helpful for successfully completing a contingency plan. If the hurricane hit 5 days or closer, the questionnaires would have already been printed and mailed. However, there may have been more challenges with getting pollsters to the polling locations in New York City and other locations (the subway may still have been closed on Election Day).

Related posts:


a gun offender registry: everyone wants one but the costs and benefits are a mystery

Prince George County in the Washington DC is weighing a bill requiring a gun offender registry, and a vote is expected in early June. If it passes (and it is expected to do so), the county would allow/require police to monitor gun offenders. I think this is akin to the sex offender registries but for those convicted for gun-related violence.  Prince George County is not the first to pursue a gun registry. Gun registries are a trend in local governments across the nation.

Supposedly, gun-offender registry have had “an impact.” I am not surprised. But they surely come with a cost. The cost in this case is a decreased manpower of already-understaffed police force. No one wants to appear soft on crime, but no one wants to pay for it either. I was surprised that the NRA representative quoted in the article appeared to be the most sensible in his assessment of the tradeoffs:

Andrew Arulanandam, the National Rifle Association’s director of public affairs, said his group advocates vigorous enforcement of existing gun laws rather than the creation of new databases. Running a gun-offender registry, he said, requires taxpayers to foot the bill for computer equipment and IT professionals, and it could take officers off the streets and place them in administrative jobs.

Gun registries could be effective despite the costs. If those on the gun registries are “dangerous,” then monitoring those individuals more closely could be an effective use of police manpower, since it focuses police attention on those most likely to commit dangerous crimes. That could more than make up for the policing that is foregone due to the new responsibilities associated with the registry. But I need to see some research that honestly shows the level of impact that registries could have. The police chief in Prince George does indeed intend to use some of their existing 1400 police officers to monitor the gun registry.

[Deputy Police Chief Craig] Howard said police would initially assign a sergeant and four or five detectives to handle the gun registry, pulling them from other jobs in the department. He said the creation of the computer database could be handled by those who run the department’s sex-offender registry and do other IT work.

The 5-6 officers needed for the registry are less than 1% of the police force. But the current registry level is zero and the system is not in steady-state. The registry will likely grow in time as gun offenders are added, necessitating an increasing number of police officers to monitor the registry. I’m not sure that monitoring the registry in the future will be sustainable.

I am agnostic on gun registries. I am not agnostic about honesty regarding the true cost of gun registries and their impacts. Certainly, different municipalities and counties need to weigh the costs with the rewards and make a decision that they can live with. Previous attempts to curb crime—such as the Three Strikes Laws and minimum sentencing—have lowered crime at an enormous cost. The costs here are associated with an exploding prison population. I suspect that the same might be true for gun registries.


elections and OR

With election day coming up on Tuesday, the latest Punk Rock OR Podcast episode addresses elections and OR. You can listen here:


Here are a few show notes and links to extra material.

Walter Mebane, Professor of political science and statistics at the University of Michigan, has written several articles about under-staffing voting locations, election fraud, and election forensics (he may be a political scientist, but his papers have figures that look like they are made in R. Not too shabby). Check it out.

You are more likely to die in a car accident on Presidential election days. Here is the JAMA article that summarizes this disturbing research finding (and a Scientific American podcast about it).

University of Cincinnati PhD student Muer Yang developed a simulation model to reduce and equalize voter waiting times across different voting areas. This is a good example of using OR for elections.

How did the University of Illinois student body elect a gnome and snail for the student body president and vice-president, respectively? Technically, they didn’t. The gnome and snail were disqualified after winning a plurality of the vote, and the controversy led to an investigation. Here is the full story according to the snail. Amazingly, all of this is real.

We followed up on our last episode on pirates and OR. We found a new article in the Journal of Transportation Security that presents statistics on pirate attack success rates.

Don’t forget to email me with your OR jokes. And don’t forget to vote!

Vote!


community based operations research

Michael Johnson, PhDI had the pleasure of interviewing Michael Johnson about his upcoming book Community Based Operations Research in a Punk Rock OR Podcast (21 minutes). It’s a fantastic book: I recommend that you ask your university library to add it to their collection.  If you are heading to the INFORMS Annual Meeting and are interested in CBOR, you might want to check out the two panels that Michael Johnson is chairing.

If you cannot wait for your copy of CBOR to arrive in the mail, I recommend reading Michael Johnson and Karen Smilowitz’s INFORMS Tutorial on CBOR. It’s a must read!


Other Podcasts can be found here.


crowd sizes, home energy usage, baseball odds, and pop songs

This is a blog post about four topics that have nothing in common.

This Popular Mechanics article on estimating crowd sizes is great. I wrote about crowd sizes earlier when I blogged about Obama’s inauguration, but the PM article goes into the details a little better.  Crowd estimates might be obtained by crowd-sourcing in the future. Why are crowd size estimates so important? “[R]emember that accurate crowd counting can have practical applications such as preparing emergency responders. If a fire, terrorist attack, stage collapse or other calamity happened at a large event, Westergard figures that within 20 minutes he could provide first responders with the location of the threat and rough estimates of the number of people who might need treatment.”

You simply must look at these numbers on the DOE’s average home energy use. This site generated quite a bit of discussion between my husband and I. On average, 31.2% of household energy is used for heating and air conditioning, 9.1% is used for the water heater, and 26.7% is used for kitchen appliances. The refrigerator alone uses 13.7% of a home’s energy. Compare this to a mere 2% of energy consumed by PCs and printers (and this was before everyone had more efficient LCD monitors). If you really want to help the environment, turn off the AC and get a smaller fridge. On second thought, maybe I’m not ready to be an environmentalist.

Nate Silver of the NYT calculates the odds that the Red Sox would not make the playoffs. On September 3, they held a 9 game lead over Tampa Bay, with a mere 0.004 chance of missing the playoffs. Ouch. As a Cubs fan, I found a little solace in the Red Sox collapse. It helps to reduce the pain associated with the many, many Cubs collapses over the years. (Luckily, I’m also a White Sox fan). The 10 teams who ruined the greatest chance of making the playoffs is surprisingly not dominated by the Cubs.

What are the odds that the Red Sox would make the playoffs?

The image below is graphical proof that pop song lyrics are becoming more repetitive over time (I’m not sure if it answers the age old question: Music or Lyrics?) It shows that pop song lyrics contain fewer unique words than they used to. This blog post delves into the details. Songs have become longer over time, since technology no longer limits singles to be ~3 minutes long. It’s not surprising that (a) songs have more lyrics and (b) a small proportion of those extra lyrics are new (if the chorus is sung one or twice more, it would add no new words). Some excellent songs have few words (such as Hey Jude by the Beatles), so I wouldn’t equate fewer unique words to a song being bad. HT to John D. Cook.

Fraction of words in pop song lyrics that are unique. Is this graphical proof that songs are getting worse over time?


optimizing school bus routes

This is my second post on politics this month (this month’s INFORMS blog challenge–my first post is about snow removal).  There are few political topics that invoke an emotional response as strongly as does K12 public education.  My daughter started attending the public school system this year, and I have been surprised at how, well, political school is.  But given the budget cuts over the past few years, some of that is understandable.

I learned the bus route that my daughter would take before the school year began.  My first reaction was to wonder if the bus routes were optimized (what else would my reaction be?).  Designing bus schedules isn’t rocket science, but it can be haphazard, leading to kids spending extra time on the bus, wasted gas, and late bus drivers.

A quick search on the web indicates that bus route scheduling is quite the political issue.

In my neck of the woods, I could probably identify near-optimal solutions without having to build a model (there are a number of small, isolated subdivisions with low road connectivity, which makes routing and bus stop selection a breeze).  But other bus routing scenarios are more complex, either due to the sheer size of the school system, the density and layout of neighborhoods, or not-so-simple school boundaries.

One feature that makes bus routing tough are “fair” policies for allocating students to schools that use lotteries to let parents select their schools: any child could attend any school so buses for every school could pass through a single neighborhood.  Good bus routes become much harder to identify (unless OR is used!), and regardless, students would have to spend more time on the bus as the distance to school increases.

Michael Johnson and and Karen Smilowitz’s excellent TutORial on Community Based Operations Research contains a brief overview about allocating public education resources.  In addition to school bus routing, operations research has been used to

  • design recommendations for school closures in a region that reflect socio-economic characteristics of the students in different areas of the region.
  • develop forecasting models for school attendance as input to optimization models for locating public-school buildings and setting attendance boundaries.
  • use data envelopment analysis (DEA) that uses school performance observations to guide secondary schools for ways to improve their performance.

Have you seen OR used for public education?

Related posts:


snow removal using a shovel, a plow, and operations research

This month’s INFORMS blog challenge has the topic of politics.  I’ve written about politics frequently before, mainly as it relates to elections.  I have also written about voting systems as they relate to politics, the Oscars, and the Olympics.  Politics is a broad topic, but I’ll write about something I haven’t before: snow removal.  After all, I am at home during yet another snow day (I live in Virginia:  1″ of snow is enough to paralyze the entire city.  My Midwestern sensibilities do not understand this).

Mike Trick wrote a wonderful post about snow removal last year.  I won’t duplicate his efforts, but I will note that James Campbell from University of Missouri-St. Louis has written several articles about OR and snow removal as has Gene Woolsey.  Snow removal can be formulated as an optimization model using generalized assignment and partitioning problems.

Another way to optimally remove snow is by using OR to influence urban planning.  In many states, including my state of Virginia, new laws limit the number of cul-de-sacs that can be built in new neighborhoods.  Cul-de-sacs and neighborhoods with few entrances and exits cause many problems: they create traffic bottlenecks and accidents, increase ambulance response times, and increase the time for snow removal.  Models that can relate neighborhood design to the cost of providing public services are valuable for removing snow more efficiently for decades to come.

The politics of snow removal are interesting to me.  As a Chicagoland native, I grew up used to seeing buckets of salt dumped on the road before every storm and plows quickly responding to blizzards.  When I was older, I was surprised to learn that most of the country does not have such great public services.  My parents told me why:  the blizzard of 1979–when more than 88″ of snow was dumped on the city–was so mismanaged that the mayor of Chicago lost his reelection bid.  A good snow removal plan that used OR would have reduced or eliminated the public backlash.  We still see political fallout after blizzards, such as the controversy surrounding the EMS response in New York during the December blizzard.  On the other hand, Newark’s major Cory Booker was praised by just about every news outlet for personally digging citizens out of the snow.  Of course, this is not a very efficient method for removing snow, but sometimes appearances matter more than efficiency.

Related posts:

  • *vote* a post about election-oriented politics

half baked operations research

Jon Caulkins from Carnegie Mellon University gave a provocative talk at INFORMS about the policy implications of Proposition 19 in California, which would have decriminalized marijuana had it passed.  Prior to the election last week, about one third of voters opposed Proposition 19, one third supported Proposition 19, and one third were undecided.  The undecided voters could swing the election either way.  The swing voters seemed to respond to economic impacts of Proposition 19.  Since California is just about broke, Proposition 19 becomes very appealing if it reduces incarceration costs, increases tax revenues, and reduces drug cartel violence in Mexico (as its supporters have promised).

Jon Caulkins worked with RAND to unravel the implications of passing Proposition 1, and he presented his findings at INFORMS.  This talk was extremely well-attended, which wasn’t all that surprising.  I came to see an interesting talk about public policy, and I was a little curious about why others came.  (Statistic:  non-drug dependent college graduates represent 7% of the marijuana market).

Caulkins reported six key findings in the RAND report (called “Altered State”) .  There was nothing half baked in his analysis:

1.        The pre-tax price of marijuana would fall at least 80%.  This conclusion was obtained by creating would-be business plans for growing marijuana.  However, the (post tax) price that consumers would pay would be significant.

2.       Given the high tax on marijuana, tax evasion could be a huge problem, which would lower the amount of tax revenue that California could collect.

3.       Marijuana consumption would go up, but no one knows how much.  An increased consumption could have several causes.  First, many have studied the price elasticity of marijuana, but they are all based on the current, high prices.  Second, marijuana could lead to product diversification that we see with many other products.  For example, it could be bundled with, say, brownies and beer.

4.       The criminal justice expenditures on marijuana are exaggerated.

5.       Tax revenues would be lower than the $1.4B CA Board of Equalization estimate as a result of tax evasion (see #2), lower prices leading to lower taxes (see #1), and a greater potency from legal growers leading to consumers needing less marijuana for their fix.

6.       The reduction of violence in Mexico and dollars flowing to Mexico is largely biased.  California represents about 1/7 of the marijuana consumption, and while it would make some improvements, there would still be a huge demand for (illegal) marijuana in the other 49 states.

Points 3 – 5 would result in fewer economic benefits for California.  With fewer economic benefits, there was in an immediate and significant decline in voter support after the release of the RAND report (I can’t find a picture of the polling data as a function of time, but if you find it, please post it in the comments).  Caulkins great OR work likely affected the outcome of the election, which is pretty exciting.

I wish there was more good OR to help me make better decisions in the voting booth.  Have you ever changed how you were going to vote based on math?


Follow

Get every new post delivered to your Inbox.

Join 1,877 other followers