it’s over. sleep now.

You are currently browsing the archive for the **Honours** category.

**Tags:** deadline, last minute, thesis

Tick tock

There’s no way to stop the clock

**Tags:** deadline, last minute, thesis

Oh dear, how did it get to here.

**Tags:** deadline, last minute, thesis

Just listing some recent files:

The thesis presentation was my first attempt at doing a Lessig Method presentation — I know it’s not entirely original, but I wanted to do something to make people wake up after half a dozen or so presentations. It wasn’t entirely smooth, but with practice, it should get better (I did it again at the SUITS AGM — slides later).

**Tags:** lessig method, poster, presentation

I haven’t blogged for over an entire month, and I’ve been wanting to blog, because I love blogging but things in RL have conspired to take me away from here. I have a whole list of things I want to blog about, and I have a few posts queued up waiting to be finished, but I think they’ll have to wait until after everything is done for this semester.

Thesis.

What an awful concept. They’re hard to write.

[ramble]

If I were a world dictator, I’d change the onus from writers to readers for constructing coherent arguments and structuring prose. 🙂 We’re already doing you the favour of finding all the material to talk about — why should we also bother to present it nicely?

[/ramble]

Sigh. Well, it’s been an interesting year, and I have no regrets taking a year off law to do honours. I’ll blog more about that later, when I have the pleasure of reflecting back in a stress-free environment.

Signing off for probably another couple of weeks…

This semester, we’ve been taking a course called “Algorithmic Game Theory”, which is the broad area that my thesis topic belongs in. Although Tasos is the course coordinator, and lectured the first couple of lectures, the bulk of the “lecturing” has fallen to the students in the course.

Last week was my turn, and I did my talk on evolutionary game theory. I had been interested in that ever since I read Dawkin’s *The Selfish Gene*, where he makes use of evolutionary game theory, albeit in a non-mathematical way, to explain his ideas for the evolution of genes. In a nutshell, evolutionary game theory allows you look at the evolution of strategies/genes/behaviours in a large population of organisms. For example, can a mutant gene overtake an incumbent gene? See the link before for more information, or read my lecture slides: evolutionary.pptx, evolutionary.pdf.

Now, onto the second half of the post’s title: why I’d hesitate to use PowerPoint again. I’ll begin with a clarification: why I’d hesitate to use PowerPoint again where I need to use equations at all. (If you’re an OpenOffice fan and you’re beginning to smirk, here’s something to wipe your smirk off: OpenOffice Impress fails to impress me even more dramatically. Sorry.)

I’ve been using LaTeX with Beamer for my presentations this year, and I’ve had a good experience with it so far. Why did I use PowerPoint? Mainly because I haven’t used PowerPoint 2007 for any *real* purpose so far, and secondly, because I saw that Word 2007 had a new flashy equation editor that’s kind of nice. It was a bit of a disappointment for me when I had finished writing all the slides with no maths to find that PowerPoint somehow failed to inherit this. Back to old Equation Editor. I hate it, so I took to doing the equations in Word and then copying them over as pictures. The main problem with all this is that, for a mathematical presentation, equations should *not* be treated as pictures. PowerPoint and OpenOffice both lack the ability to insert equations as inline text, and that frustrates me to no end. Another minor little gripe is that there’s no in-built way to have navigation bars like you do in Beamer.

The shocking thing is that most lecturers in academia, such as the School of IT, continue to use PowerPoint even though the set of tools it provides for technical presentations is minimal. (If you’re doing a sales pitch with pie charts and dot points, it’s fine.) Unfortunately, this just means there’s little incentive for Microsoft to go and improve the tools for this important market segment.

**Tags:** academia, algorithms, beamer, coursework, evolution, game theory, latex, powerpoint, presentation, richard dawkins

Braess’ paradox is a counter-intuitive result in transportation science, which in essence states that if you add additional capacity to a network, overall network performance may in fact decrease, if agents are free to (greedily) choose a path that minimises their own latency. In this post, I’ll explain Braess’ paradox, and provide a new example that uses only non-increasing cost functions.

Let’s consider the following network 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 network. The cost functions c(x) on the links indicate how long it takes to use that route as a function of the fraction of the traffic that will take that link (in some unit of time, say hours). For example, if the link’s cost function is c(x) = x and half the traffic goes along that link, then it will take everyone half an hour to traverse that link. You can think of these roads as narrow roads that are rather susceptible to congestion. The links with cost functions c(x) = 1 are not affected by the traffic flow at all; these are analogous to long, but very wide, highways.

In the above case, because the top route (s-v-t) is identical to the bottom route (s-w-t), traffic will spread itself out between the two routes: half will go up the top and the other half will go down the bottom. The average time taken is 1.5 hours. But what if the local government decided to improve the network by adding a new super-fast highway from v to w that takes absolutely no time to traverse?

The people taking the s-w link will think, “Hey, going via s-v-w is no worse than taking s-w, and it can actually be quicker. I’ll take that instead!” The same logic goes for why everyone will end up taking v-w-t instead of v-t, because v-w-t cannot be worse, but it can actually be faster, if a small fraction of people don’t take it (note the cost function on w-t). So everyone ends up on s-v-w-t, which means an average time of 2 hours. Oops.

If you think back to the real world, that’s why building a new highway doesn’t solve all our traffic nightmares, and can, in some cases, make the problem worse. People using sides roads or taking the train to work converge on the new highway, and you’re back to square one.

Braess’ paradox doesn’t just occur for networks where the cost of a link goes up as the number of people use it. For networks with non-increasing cost functions (e.g. the cost of a link goes down as the number of people use it goes up), where congestion is a good thing, we can find an analogous situation. Consider the following network, where 1 unit of traffic needs to be routed from s1 to t1, and another unit from s2 to t2:

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

The direct s1-t1 route is more attractive than the 3 hour hike via u and v, so everyone who wants to go from s1 to t1 takes that route instead. Because the u-v link isn’t shared anymore, its cost goes up quite a bit, and the total cost now becomes 6.5. Sharing is caring.

**Tags:** braess' paradox, congestion, game theory, roads, selfish routing

So I did a bit of AMPL modelling today, now that I’ve read the AMPL book from cover to cover. (AMPL lacks online documentation. The book is the documentation!) I just did the basics… did up Pigou’s example — it’s interesting how you think you have all the tools for the job and then you try the simplest of things and it falls apart. The first stumbling block is that there’s no way you can represent multiedges in AMPL, because sets cannot have repeated elements. So, if you’ve got two s-t edges, you’ll need to break one up into s-u-t.

The next weird thing is that once you move beyond the traditional examples where you have nice pretty convex functions, CPLEX goes belly up (the School has a license for AMPL and CPLEX), so I’m forced to go back to the free student version, which has a larger variety of solvers (but all limited in a multitude of ways). Even then, you run into the guess and check game with non-linear optimisation, because maths and computer science haven’t progressed far enough to make non-linear optimisation *just work*. I guess you could summarise the book’s recommendations: guess and check, but guess and check intelligently.

So, where I’ve progressed since I last blogged about honours a while back is that I’ve gone through some more papers (Tasos pointed me to the complementarity proof by Aashtiani et al), and learnt AMPL. Next station: install some for loops (like wow!) to do the stupid guess and check and build something that’s a little less fragile to play with.

**Tags:** ampl, cplex, graphs, non-linear optimisation, pigou's example

Yesterday, I did my honours research proposal presentation: the slides can be downloaded here. Despite the very mathsy topic that I have, I’ve managed to make it pretty much maths free (except for the last slide 😛 ) and just about anyone should be able to make it through at the least the introduction — so take a look if you’re wondering just what on earth I’m doing.

In other news, some (obviously very bored) people have applied game theory to the problem of cohabiting males and females sharing a toilet: the cooperative and non-cooperative cases are analysed.

**Tags:** game theory, presentation, selfish routing, toilet

Yesterday, I completed the Research Proposal for the Research Methods course. Research proposals. Yawn.

**Tags:** coursework, research