selfish rout­ing

You are currently browsing articles tagged selfish rout­ing.

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: , , ,

A couple of weeks ago, I presen­ted at the Algorithms Read­ing Group two papers that I had pre­vi­ously read for my hon­ours work. The first week, I presen­ted How Bad is Selfish Rout­ing? (Roughgarden and Tar­dos), and that attempt was … let’s just say that there was (sub­stan­tial) room for improve­ment in the present­a­tion style. Sev­er­al points to take away:

  • Slides don’t really help in present­ing a paper: the mode of deliv­ery of a paper is neces­sar­ily dif­fer­ent to that of a lec­ture. It’s much more dense, and the bite-sized chunks that slides give you don’t do justice to the mater­i­al in the paper, and in fact, make it harder to fol­low. For example, defin­i­tions are great, but when taken off the page and onto sev­er­al slides-worth of defin­i­tions, your eyes do glaze over.
  • Sleep is use­ful: nev­er present after get­ting very little sleep
  • Know the details very well: you might think you know the paper well, but when present­ing a paper, you need to know how each part can be obtained with pre­ci­sion. People will ask you things you’ve nev­er thought about. It’s often stated that you only know some­thing well when you can teach it. Corol­lary: prac­tise present­a­tions before giv­ing them.

Over­all, it was a good first attempt. I’m quite proud of the slides still, and they might be use­ful for someone start­ing out in this area: they can be down­loaded here (handout). This was my first attempt at using the LaTeX Beam­er class, and I must say that I’m now a con­vert. Power­Point has its uses still, but def­in­itely not for very tech­nic­al talks.*

The second attempt was far bet­ter. This was present­ing The Price of Rout­ing Unsplit­table Flow (Awer­buch, Azar and Epstein), and I did the entire thing with a white­board and a mark­er… and I rehearsed it with Tasos. I walked into it feel­ing more con­fid­ent, and I felt that the audi­ence walked out of it with a good under­stand­ing of the paper’s con­tents.

For anoth­er hon­ours-related mor­al: Don’t edit your work after you’ve writ­ten it. Just hand it in. Bizarre? Well, it turned out that while edit­ing the Research Approach doc­u­ment after dis­cuss­ing it with my super­visor, I acci­dent­ally deleted half of a sen­tence and didn’t real­ise it. The mark­er adjus­ted the mark accord­ingly. Fine, to be fair, it should be: Don’t edit your work when you’re half asleep. The mis­take is now cor­rec­ted.

Foot­note:
* I recently got Math­em­at­ica 6, and there’s a new slide show view — so that might be a good way to go for those who don’t like typ­ing LaTeX code. As an aside, I’m quite impressed with the new visu­al­isa­tion cap­ab­il­it­ies of Math­em­at­ica 6, and I’ll be sure to use it in my work.

Tags: , , , , , , , , , ,

Pigou

From this Google Answers page, it seems like Pigou (a Brit­ish eco­nom­ist) is pro­nounced as “pi-GOO”, the “g” being hard, and the adject­ive form of his name is (argued to be) “Pigouvi­an”. Use­ful to know when I’m present­ing Pigou’s Example, an example of the non-optim­al­ity of selfish rout­ing.

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: , , ,

The hon­ours pro­ject has made some head­way with the com­ple­tion of the lit­er­at­ure review. The pur­pose of a lit­er­at­ure review in an hon­ours pro­ject is to exam­ine what research­ers in the field have done pre­vi­ously, in a bid to identi­fy a niche for your pro­ject — because the con­tri­bu­tion you make must be a nov­el con­tri­bu­tion. In the com­pleted thes­is, it will even­tu­ally go at the begin­ning, togeth­er with a sur­vey of some basic math­em­at­ic­al the­ory (because I’m doing the­or­et­ic­al CS).

I’ve uploaded it here for all to view, and it’s good as a quick over­view of the field of selfish rout­ing and the price of anarchy. (I’ve also uploaded my pro­ject abstract and my lit­er­at­ure search, and star­ted using my wiki for Hon­ours-related work.)

Togeth­er with Tasos, we looked at num­ber of things at the last meet­ing: namely (what we’ve termed) inverse con­ges­tion games (where con­ges­tion is good) and simply invert­ing the edge cost func­tions.

Just a couple of thoughts about using a wiki for hon­ours: One­Note is def­in­itely out of the ques­tion because it doesn’t sup­port maths (it doesn’t even sup­port the maths Auto­Cor­rect found in Word 2007 — which makes little sense). I could type everything in LaTeX but then it’s a night­mare to nav­ig­ate, and just jot­ting down a quick note means a recom­pile. Medi­aWiki is a good com­prom­ise, as it has maths sup­port, although the res­ult­ing page looks rather ugly (because of the dif­fer­ence between the maths font and the text font), and for some reas­on, some LaTeX com­mands are miss­ing (e.g. \succ) even though everything else in their pack­age works.

Tags: , , , ,

Oops, I haven’t blogged about hon­ours for a while — not a good sign! What has happened since last time… fin­ished the “Data­base Search Res­ults” assign­ment, where I sum­mar­ised a couple of papers and came up with a list of 50 (poten­tially) rel­ev­ant papers. Also, Tasos spoke to Joachim from NICTA who men­tioned an inter­est­ing prob­lem: selfish rout­ing of tax­is. I haven’t giv­en it much thought yet, but some pre­lim­in­ary dis­cus­sions extrac­ted the fol­low­ing issues:

  • In com­par­is­on with the Roughgarden mod­el of selfish rout­ing, there’s more than one under­ly­ing graph to con­sider (e.g. the actu­al road net­work, a bipart­ite match­ing graph), and the con­ges­tion may have to be refor­mu­lated in anoth­er way.
  • It is an online match­ing prob­lem, and there are issues to do with loc­al­ity (you only know what’s hap­pen­ing in your loc­al area, and not the entire graph) and the exist­ence of a prob­ab­il­ity dis­tri­bu­tion of demand.
  • It may be related to the prob­lem of all-optic­al rout­ing. I’ll also try and link it with the mul­tic­ast rout­ing prob­lem as well, but for the time being, com­ing up with a simple-enough mod­el of the selfish taxi rout­ing prob­lem (in LP form?) is the first step.

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: , , ,