Stackelberg Scheduling

20Nov07

Ho-Lin gave a nice overview of the stackelberg scheduling problem today… We looked at the same parallel link model we discussed at the end of the last class, and we saw that if alpha percent of the flow is controlled centrally, then the PoA is bounded by 1/alpha regardless of the latency function. Further, if the latency function is linear, the PoA is 4/(3+alpha).

The natural question for us now is, what if we look at queueing latency functions? What happens to the PoA in that setting? We know that if no flow is controlled, the PoA is N (the number of parallel links) – how does that change if alpha flow is controlled?

Also, if someone is looking for other work to present. It would be interesting to discuss what happens when we consider the stackelberg instance of more general networks?

After thanksgiving, we’ll continue looking at congestion games, and Vera will describe PoA results for general networks and a variety of latency functions – queueing included.

Filed under: Uncategorized   |  Leave a Comment