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:

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:

• graph coloring problems over the holidays