Stackelberg Scheduling
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
Comments on Lecture 4
I thought we went over some interesting results today…and our discussion turned out so provide some nice intuition about the contrast beween the behavior of a monopoly in the observable and the unobservable models.
If anyone missed class and would like to look over my notes before next time, just drop by my office.
A couple of things that came out of our discussion are:
1) what other extensions of Naor’s model have been studied?
2) What is the PoA in an M/G/1 unobservable queue, and why does it increase with job size variability?
3) What extensions are of the unobservable model have been studied?
4) What is the PoA in other queueing-type congestions games (with more complicated structure than the parallel server case we discussed)?
Next up, Ho-Lin and Vera will teach us what is known along the lines of (4).
Filed under: Uncategorized | Leave a Comment
We need presenters
Hi everyone, it’s getting to the point where we need some volunteers to present in the upcoming weeks…
The presentations needn’t be about your research. We’re all learning this area, so taking a paper or two from the web page or a chapter (or half a chapter) from the book is all that we need.
And remember, the first 5 chapters of the book are online. Also, we have multiple copies on reserve at the library for people to use.
Here’re some idea’s that I think would make good topics, if you have others, just respond with them. Also, just respond if you want to claim a topic.
1) Chapter 4 in the book (on paying to receive higher priority)
2) Chapter 5 in the book (on models where users can renege and jockey between queues)
3) Applications of dynamic games in queues, by Eitan Altman – this has a few nice examples of simple models where game theory and queues interact.
4) Network Routing, Frank Kelly – this paper looks at a network of queues with user’s greedily choosing routes and characterizes the nash and social optimal.
5) The value of congestion, Laurens Debo, Christin Parlour, Uday Rajan & To Join the Shortest or the Longest Queue: Inferring Service Quality from Queue Lengths, Laurens Debo and Senthil Veeraraghavan – Laurens will be coming to Caltech later in the term, and has done some very nice work in this area illustrating “herding” in queueing models.
6) Queueing cost functions in congestion games – This is a little more up in the air, and maybe Ho-Lin will touch on this. But, most of the time congestion games results do not apply to queueing cost functions (1/(mu-lambda)), so it would be nice to find out exactly what has been shown for such cost functions. A starting point for this would be this paper by Tim Roughgarden or his book (which I have in my office if someone wants to borrow it)
Filed under: Uncategorized | 3 Comments
Naor’s model
We just saw our first example of a simple interaction between game theory and queueing theory. Naor’s model takes probably the most basic model from the two setting and combines them. But, I think we could already learn a lot from the comparison.
One question that came up is that of “how far the model has been extended since 69?” This is something I don’t have a good answer to and might be a good topic for a future meeting. Chapter 2 gives a number of pointers to extensions, but I’m sure there are also extensions beyond those. Is anyone interested in giving such a presentation? …going over some of the results from extensions of Naor’s model and describing some of the techniques used?
Another topic that came up was understanding the comparision between the profit max, social opt, and nash in the model. Things like the PoA…or at least a behavioral comparison.
Lastly, I noticed that some people weren’t too comfortable dealing with Markov chains. They’re fundamental to analyzing queueing models, so it’s worth refreshing yourself if you’re not confident with them. If this is you, check out the notes from my advisor’s class here:
http://www.cs.cmu.edu/~harchol/Perfclass/NotesFall07/notes.html
Next week we’ll spend a little more time on some observable games like Naor’s model, and then start talking about unobservable games.
Filed under: Uncategorized | Leave a Comment
Comments on the 2nd meeting
We’ve now covered the basics of game theory and queueing, so we’re ready to get started looking at interactions next week…
The congestion games Jason introduced today will come up very frequently in our meetings, so it’ll be good to look over some of the papers on them if you haven’t seen them before.
A good starting point is Selfish Routing and the Price of Anarchy, Tim Roughgarden, which is available off of his web page.
Anyone else know some good background references on this stuff? If so, post them in a comment…
For the next meeting, it’ll be good to give yourself a quick refresher on Markov chains (which Mani didn’t have time to cover much in the first meeting).
Filed under: Uncategorized | 2 Comments
Comments on our first meeting
Sorry I couldn’t make it to our first meeting, but I hear that it went well. If you have any questions or comments on the background Mani went over, just respond to this post.
Also, a question for you guys:
Mani didn’t get to do much with Markov chains. How comfortable is everyone with solving simple chains?
As a test, suppose we have an M/M/1 queue (exponential interarrival times and job sizes). If we make the state of the chain the number of jobs in the system, does everyone know how to setup and solve this chain for the stationary distribution of number in system?
Filed under: Uncategorized | 1 Comment
Interesting papers
I’ve listed a handful of interesting/relevant papers on the web site already, but I’m hoping that we’ll find a bunch more as we get started. So, if you find any interesting papers you think would be good to go over in the group – post them here!
Filed under: Uncategorized | Leave a Comment
Our first meeting
Unfortunately, I (Adam) won’t be able to make it to our first meeting this Thursday…but I leave you in the expert hands of Mani!
He’ll be going over some background on queueing models/results so that we’re all on the same page in that regard. Depending on how much we get through, we’ll either continue with queueing next week, or move to some basic game theory.
I’ll see you all next week!
Filed under: Uncategorized | Leave a Comment
Welcome
Hey everyone!
I’m hoping that this blog can provide us a place to post links to interesting papers we find, questions/comments about the papers we read, etc…
So, please check this occasionally as you’re reading stuff for our meetings – and post comments!
-Adam
Filed under: Uncategorized | Leave a Comment
-
Recent Comments
Gail on Comments on the 2nd meeti… weiyu xu on We need presenters Adam on We need presenters Tati on We need presenters Adam on Comments on the 2nd meeti…
