HW 6 is out

...post any questions you have here.

Lecture 14: Project proposal presentations

I really enjoyed hearing about all your project proposals and am excited that so many of you are planning to work on them next term in 145.

For those of you interested in 145 who don't have a group yet ... if you heard about a project that interested you yesterday, just talk to those students (or post a comment here) about possibly joining forces.  You should be sure to find your group soon because the project plan due at the end of the term is meant to be the concrete plan for approaching the project in the spring.

Lecture 12-13: Routing Games

During the last two lectures we've focused on "routing games" a.k.a. "congestion games" where sources must choose the route they (or their packets) take through a network to a destination.  We've gone through the same set of analyses we did for load balancing games -- We studied the existence and the efficiency of Nash equilibria.  We saw that Nash equilibria need not exist, but that in the case of linear latency functions they will always exist and, not only that, they will be quite efficient (i.e. small "price of anarchy").  But, unlike load balancing games, the "price of stability" is not 1, and so the optimal routes are no longer always an equilibrium.


In addition to the particular application of routing games, we also introduced the class of "potential games" which has a number of important properties that helped us in our analysis.  Further, we saw an example of the technique of "marginal cost pricing", which can be used to align the local incentives of players with the global goal.  These two concepts are important and useful far beyond routing games.

Next class, we'll leave routing games and move on to the study of Ad auctions.

Hw 5 is out

Homework 5 is out! Grab it from the course page. Note that the printout handed out in class missed a page!

Please post your queries/commentsregarding this homework in the comments.

Project proposal presentations Wed 2/24

After taking a look through the project proposals everyone turned in, I've decided that it will be fun to give you all a chance to hear what your classmates proposed.  This could be especially useful for people who are taking 145 next term since they might find something really exciting to pursue.


So, next Wednesday (2/24), we will have a project proposal presentation session. 

Here's how it will work: Each group will have 5 minutes.  They can use this as they please -- presenting 1 idea or multiple ideas.  You can use the blackboard, the projector, or just talk.  You can have 1 group member talk or multiple people talk.   It's completely up to you.  However, if you want to use the projector you must send me your files before noon on the 24th so that I can preload them onto my laptop (which is a PC -- pdf or ppt are the safe choices).

The quality of the presentation will be incorporated into the grade for the proposals.

Lecture 11: Load balancing games

Today we looked at our first CSy games -- load balancing games.  These games are motivated by the fact that a data center / server farm is simply too big to optimally assign jobs, so instead we could consider just using a greedy heuristic of sending jobs to the best server they can go.  Well, this algorithm can be viewed as a game where the players are the jobs...and we spent the lecture starting the analysis of this game.  We've seen so far that Nash equilibria always exist and that the optimal assignment is always an equilibrium.  Next class we'll look at how bad equilibria can be, and then we'll move on to routing games.

My notes include everything for the next lecture too, so I won't post them yet. 

Also, remember that Monday is a holiday, so we won't have lecture again until Wednesday.

Lecture 10: Economics and networks

We started the day with a quick review of pagerank and all the other topics we covered in Module 1, and then we finally moved on to Module 2 --Economics and networks.

We spent the lecture providing a primer on (i) why game theory is important for understanding today's networks and (ii) providing an introduction to "baby" game theory, which will hopefully be enough background for us to cover the 3 topics in this module.  Wednesday, we move to our first case study -- how game theory provides insight for routing.

Note -- I messed up the example where there was no Nash Equilibria in class today...but it's correct in the notes that are online.  I'll go over it at the beginning of the next class.

HW4 is out!

This is a fun one (I think) ... so I hope you enjoy it. Grab it from the course web page.

Like I said in class, be sure that you start early because if you don't you'll be in at a big disadvantage for the "gaming google" problem.  And, if you're having trouble finding a group of 2-3 people for the "gaming google" problem, just post a comment here and coordinate with people that way.  I'd like everyone to have a partner for it, but if you really can't find one feel free to do it alone.  I'm really hoping that you come up with some creative ways to get ranked highly, so think outside of the box....and talk to me and the TAs if you're stuck.

Lectures 8-9: Search

We moved on from the network structure and network formation topics that we've been studying so far, to now discuss one example of how to exploit our understanding of network structure -- Search.  We spent most of today talking about the general architecture of a search engine (crawling, indexing, ranking, and display), but just got to the point where we were discussing the key new insight of google when it formed -- pagerank.

We ended by putting up a first take on pagerank and I left you with the question of coming up with an example webgraph that "breaks" our first cut at pagerank.  So, we'll pick up there on Wednesday.

Remember -- the next homework will go out soon and you'll be competing in groups of two for ranking on google for the term "rankmaniac 2010".  One key constraint that I forgot to mention in class about this though is your page (which you are aiming to have show up first on google/bing) cannot be on the caltech domain.  So, you have to grab a free blog/wiki/etc from somewhere else to host your page.

Location change for office hours

Apparently the department prefers that we limit access to the 2nd floor of Annenberg in the evenings, so we have to switch the location for office hours.  From now on, we'll hold office hours in the 1st floor conference room in Annenberg (the fish bowl next to the computer lab).  I hope to see you Tuesday night to discuss the project proposals!

Remember, you're required to come at least once in the first 5 weeks of office hours and we're closing in on that number...