game the­ory

You are currently browsing articles tagged game the­ory.

This semester, we’ve been tak­ing a course called “Algorithmic Game The­ory”, which is the broad area that my thes­is top­ic belongs in. Although Tasos is the course coordin­at­or, and lec­tured the first couple of lec­tures, the bulk of the “lec­tur­ing” has fallen to the stu­dents in the course.

Last week was my turn, and I did my talk on evol­u­tion­ary game the­ory. I had been inter­ested in that ever since I read Dawkin’s The Selfish Gene, where he makes use of evol­u­tion­ary game the­ory, albeit in a non-math­em­at­ic­al way, to explain his ideas for the evol­u­tion of genes. In a nut­shell, evol­u­tion­ary game the­ory allows you look at the evol­u­tion of strategies/​genes/​behaviours in a large pop­u­la­tion of organ­isms. For example, can a mutant gene over­take an incum­bent gene? See the link before for more inform­a­tion, or read my lec­ture slides: evolutionary.pptx, evolutionary.pdf.

Now, onto the second half of the post’s title: why I’d hes­it­ate to use Power­Point again. I’ll begin with a cla­ri­fic­a­tion: why I’d hes­it­ate to use Power­Point again where I need to use equa­tions at all. (If you’re an Open­Of­fice fan and you’re begin­ning to smirk, here’s some­thing to wipe your smirk off: Open­Of­fice Impress fails to impress me even more dra­mat­ic­ally. Sorry.)

I’ve been using LaTeX with Beam­er for my present­a­tions this year, and I’ve had a good exper­i­ence with it so far. Why did I use Power­Point? Mainly because I haven’t used Power­Point 2007 for any real pur­pose so far, and secondly, because I saw that Word 2007 had a new flashy equa­tion edit­or that’s kind of nice. It was a bit of a dis­ap­point­ment for me when I had fin­ished writ­ing all the slides with no maths to find that Power­Point some­how failed to inher­it this. Back to old Equa­tion Edit­or. I hate it, so I took to doing the equa­tions in Word and then copy­ing them over as pic­tures. The main prob­lem with all this is that, for a math­em­at­ic­al present­a­tion, equa­tions should not be treated as pic­tures. Power­Point and Open­Of­fice both lack the abil­ity to insert equa­tions as inline text, and that frus­trates me to no end. Anoth­er minor little gripe is that there’s no in-built way to have nav­ig­a­tion bars like you do in Beam­er.

The shock­ing thing is that most lec­tur­ers in aca­demia, such as the School of IT, con­tin­ue to use Power­Point even though the set of tools it provides for tech­nic­al present­a­tions is min­im­al. (If you’re doing a sales pitch with pie charts and dot points, it’s fine.) Unfor­tu­nately, this just means there’s little incent­ive for Microsoft to go and improve the tools for this import­ant mar­ket seg­ment.

Tags: , , , , , , , , ,

Braess’ para­dox is a counter-intu­it­ive res­ult in trans­port­a­tion sci­ence, which in essence states that if you add addi­tion­al capa­city to a net­work, over­all net­work per­form­ance may in fact decrease, if agents are free to (greed­ily) choose a path that min­im­ises their own latency. In this post, I’ll explain Braess’ para­dox, and provide a new example that uses only non-increas­ing cost func­tions.

Let’s con­sider the fol­low­ing net­work setup:

Braess’ paradox - initial setup

We have four towns, s, v, w and t, and one unit of traffic that needs to get from s to t using this net­work. The cost func­tions c(x) on the links indic­ate how long it takes to use that route as a func­tion of the frac­tion of the traffic that will take that link (in some unit of time, say hours). For example, if the link’s cost func­tion is c(x) = x and half the traffic goes along that link, then it will take every­one half an hour to tra­verse that link. You can think of these roads as nar­row roads that are rather sus­cept­ible to con­ges­tion. The links with cost func­tions c(x) = 1 are not affected by the traffic flow at all; these are ana­log­ous to long, but very wide, high­ways.

In the above case, because the top route (s-v-t) is identic­al to the bot­tom route (s-w-t), traffic will spread itself out between the two routes: half will go up the top and the oth­er half will go down the bot­tom. The aver­age time taken is 1.5 hours. But what if the loc­al gov­ern­ment decided to improve the net­work by adding a new super-fast high­way from v to w that takes abso­lutely no time to tra­verse?

Braess’ paradox - augmented network

The people tak­ing the s-w link will think, “Hey, going via s-v-w is no worse than tak­ing s-w, and it can actu­ally be quick­er. I’ll take that instead!” The same logic goes for why every­one will end up tak­ing v-w-t instead of v-t, because v-w-t can­not be worse, but it can actu­ally be faster, if a small frac­tion of people don’t take it (note the cost func­tion on w-t). So every­one ends up on s-v-w-t, which means an aver­age time of 2 hours. Oops.

If you think back to the real world, that’s why build­ing a new high­way doesn’t solve all our traffic night­mares, and can, in some cases, make the prob­lem worse. People using sides roads or tak­ing the train to work con­verge on the new high­way, and you’re back to square one.

Braess’ para­dox doesn’t just occur for net­works where the cost of a link goes up as the num­ber of people use it. For net­works with non-increas­ing cost func­tions (e.g. the cost of a link goes down as the num­ber of people use it goes up), where con­ges­tion is a good thing, we can find an ana­log­ous situ­ation. Con­sider the fol­low­ing net­work, where 1 unit of traffic needs to be routed from s1 to t1, and anoth­er unit from s2 to t2:

Decreasing case - initial setup

You’ll find that the total cost is 6 (3 each for the s1-t1 and s2-t2 guys). Now, someone with deep pock­ets builds a new link to shave a little off the s1-t1 route:

Decreasing case - augmented network

The dir­ect s1-t1 route is more attract­ive than the 3 hour hike via u and v, so every­one who wants to go from s1 to t1 takes that route instead. Because the u-v link isn’t shared any­more, its cost goes up quite a bit, and the total cost now becomes 6.5. Shar­ing is caring.

Tags: , , , ,

Yes­ter­day, I did my hon­ours research pro­pos­al present­a­tion: the slides can be down­loaded here. Des­pite the very math­sy top­ic that I have, I’ve man­aged to make it pretty much maths free (except for the last slide 😛 ) and just about any­one should be able to make it through at the least the intro­duc­tion — so take a look if you’re won­der­ing just what on earth I’m doing.

In oth­er news, some (obvi­ously very bored) people have applied game the­ory to the prob­lem of cohab­it­ing males and females shar­ing a toi­let: the cooper­at­ive and non-cooper­at­ive cases are ana­lysed.

Tags: , , ,

I’m read­ing Richard Dawkin’s The Selfish Gene at the moment, and I’m rather engrossed with it cur­rently — I’m a suck­er for pop sci. One thing I’ll have to say is that his style of argu­ment has def­in­itely reversed my pre­vi­ous opin­ion that bio­logy is a fluffy field of study. I won’t say much more because there are people who are able to make far more cap­able com­ment­ar­ies about the work, but I will say that the use of game the­ory, a cent­ral theme in my hon­ours work, in the study of evol­u­tion has opened my eyes to the wide applic­ab­il­ity of game the­or­et­ic approaches.

Tags: , ,

Today, I com­pleted the Out­line of Research Approach for my hon­ours pro­ject, and it can be down­loaded here. It’s basic­ally there to show that I’ve thought about what con­tri­bu­tions I can make, and how I intend to go about mak­ing them — I jot­ted down some of the aven­ues that are look­ing prom­ising and ana­lo­gies from exist­ing lit­er­at­ure. Tasos did men­tion that what I had writ­ten down looked like suf­fi­cient work for 4 hon­ours pro­jects so yeh… >.<

This Fri­day, I need to pre­pare a short sum­mary of my pro­ject for the ANRG group meet­ing, and next Monday, I’m present­ing the Roughgarden-Tar­dos work at the Algorithms Read­ing Group. Fun!

Tags: , , ,

At today’s meet­ing with Tasos, we went through chapter 2 of Roughgarden’s Selfish Rout­ing and the Price of Anarchy. This chapter con­tains the back­ground math­em­at­ics and graph mod­el required for under­stand­ing this top­ic. As home­work, what I think I’ll have to do is write up a sum­mary of key defin­i­tions and pro­pos­i­tions, and work through some of the proofs slowly. Next week, we will dis­cuss the mul­tic­ast rout­ing paper.

On an unre­lated note, my hon­ours com­puter is a piece of crap: 15″ screen, 512MB RAM, Pen­ti­um 4, 27GB HD. I want ViSLAB’s hanu­man with the 19″ screen! 🙁 Today, I installed Ubuntu on top of Win­dows that was pre-installed, because I find it con­veni­ent to have both plat­forms read­ily access­ible (I have Vista on my laptop), and have some­where to ssh into. Many thanks to Masa who let me bor­row ViSLAB’s Ubuntu 6.10 CD — I burnt myself a copy but the installer fails with a cryptic I/​O error. The lab upstairs tends to be a little sparse in terms of use­ful little tid­bits of tools like that, which I am a little dis­ap­poin­ted about.

Tags: , , ,

(This has been cross-pos­ted from the ViS­LAB blog.)

Ah, so it is time for me to say good­bye to ViS­LAB… for now any­way. I’ve taken a lot from my pro­jects here, and I thank every­one who’s made it worth­while, mem­or­able and enjoy­able.

I am doing hon­ours upstairs with Tasos Viglas in the inter­sec­tion of game the­ory and graph the­ory. I’m try­ing to run fast to cov­er the ground-work (I haven’t stud­ied game the­ory before, and (non-)linear pro­gram­ming still makes me blue in the face), but pos­sible dir­ec­tions are with the price of anarchy (e.g. How bad is selfish rout­ing?), or game the­or­et­ic­al applic­a­tions to pri­cing for mul­tic­ast rout­ing (e.g. Shar­ing the cost of mul­tic­ast trans­ac­tions). Sounds like fun, but I won’t get to play with all the shiny toys that ViS­LAB people seem to get.

The net­works lab doesn’t have a com­mon blog or wiki like ViS­LAB, but I think hav­ing them around does actu­ally encour­age you to try and organ­ise your work bet­ter, so I’ll be self-host­ing them. My blog is at http://​www​.nointrigue​.com/​b​l​og/, and there is an RSS feed if you want to sub­scribe. Please do! It means a lot when you know people read what you have to say.

As for my little side adven­ture, I’ll con­tin­ue to work on that in my own time and host the devel­op­ment on my site.

Bye for now!

Tags: , , ,