Game theory and ad-hoc networks

I am wondering if this could be a growth area... so there's been some work at this intersection, e.g. this paper posted to arxiv (CS and Game Theory) on Tuesday 7th July. Ad-hoc networks are composed of nodes, which in a game-theoretic context would constitute the agents or players.

I recently read another paper "New strategies for Revocation in Ad-Hoc Networks" (link) which doesn't have a game theory spin; I took a look at it because it was reported on in the New Scientist, and it relates to general issues I'm interested in, networks of decentralised agents trying to reach an agreement (so maybe there's an element of social choice theory?) where there are good and bad agents, and the good ones have to avoid being misled by the bad ones... "revocation" means removing the bad agents from the system, or at any rate, "blackballing" them.

For a theorist the paper is a bit unsatisfying to read since it doesn't spell out a mathematical model of what's going on (in terms of how agents can communicate, and what they are trying to achieve). And perhaps there is no nice model that wouldn't rule out the sort of approach one would want to use in practice, or else rule out the sort of attacks that the bad agents are supposed to be capable of. From time to time, agents may observe other agents misbehave, and when that happens, the observing agent, assuming it is one of the "good" agents, would want to report on the "bad" (misbehaving) agent to the other good ones. However, it is apparently possible for a bad agent, or agents, to bear false witness, so care must be taken in how to process one of these accusations. The only advantage the good agents have, is that they are in the majority (much less than one-third of agents are assumed bad). The paper mentions Byzantine generals, but doesn't really discuss the relationship. It would be interesting to come up with a model and relate it to the ones in The Byzantine Generals Problem and maybe also the FLP paper (Impossibility of distributed consensus with one faulty process).

Advertising PhD studentships

(The following is motivated by my work on PhD admissions at Liverpool CS.)

Terence Tao opines that you should move from place to place when you progress from undergraduate to postgraduate to postdoctoral research. I tend to agree, but my sense is that within the UK most students are reluctant to do so.

One obstacle is that departments like to keep their best undergraduate students on their own PhD programmes, another is lack of information about outside opportunities, and which research strengths are located in which departments. New and new-ish web sites that advertise PhD study opportunities may alleviate this problem. Here's a list I made after hunting around; I thought that findaphd.com is probably the best for finding phd studentships, and the discussions on the postgraduateforum will be of interest to most current PhD students. These web sites are mainly geared towards specific projects; to locate general research strengths still requires a prospective student to ask around, or visit individual department web sites.

• jobs.ac.uk
  (mainly UK, not specifically for PhD studentships; (Uni of Warwick/Eduserve, Coventry));
• find a PhD.com;
  (UK/Europe, (The Science Registry Ltd, Sheffield), also operates find a masters and find a postdoc);
• postgraduate forum
  (UK, many online discussions of PhD study issues (The Science registry Ltd, Sheffield));
• postgraduate studentships;
  (UK, (online resource pages, North London))
• hobsons postgrad and postgrad.com
  (UK, (Hobsons, USA); links to a discussion forum, but postgraduateforum has more traffic);
• find a PhD.co.uk
  (UK, links to other sites);
• PhDs.org
  (USA, rank institutions based on your own priorities);
• whatuni
  (UK, mainly reviews of universities, allows search for PhD courses but not many there (hotcourses.com));
• hotcourses.com
  ("the UK's largest course finder", but would you want to use a website with a name like "hotcourses"?)
• prospects.ac.uk;
  (UK; click on "postgrad study"; the site crashed when I tries to search for CS research programmes)

new postdoc positions (update)

A couple of weeks ago I announced two new postdoc jobs (each of 3 years duration) in Algorithmic Game Theory, on the project Efficient Decentralised Approaches in Algorithmic Game Theory (to be run by me and colleagues at Liverpool, and Artur Czumaj at Warwick). At that time, we made preliminary announcement web pages here and here.

Here is the official ad (went live today) for the one at the University of Liverpool and here is the official ad for the one at the University of Warwick (See another copy here.) For both of these the closing date for applications is July 17th.

Here and here are the EPSRC summary pages for the grants for this joint project.

perpetual motion at Sainsbury's

This article caught my eye in the Guardian's technology section: a branch of Sainsbury's supermarket is installing speed bumps that harvest energy "for free" from the cars passing over them.

Hang on a minute. You can only get energy from passing vehicles if you slow them down as they pass. I guess this could validly produce energy that would otherwise be wasted, strictly provided the speed bumps are installed on a stretch of road where most drivers would brake (this is not pointed out in the article). Although for me, in my Toyota Prius, when you brake the car is supposed to recycle that energy by using it to recharge the battery, so if I pass over those speed bumps I lose out -- ending up powering the supermarket and not the car battery.

Mac switchover

Today I finally got around to getting my desktop PC replaced with a Mac that has been waiting in the wings while I come to terms with giving up much of the software I've gotten used to. My laptop is already a Mac, so now the switchover is complete; my souvenir of Windows is a couple of aging laptops left over from earlier.

The switchover was mainly driven by peer pressure; now I can whole-heartedly join in the discussions about the deficiencies of Windows (mainly the start-up time; one of my laptops actually "runs" Vista but I never used it because of a shortage of time).

New degree course in e-Finance

My interest in this new degree programme dates back to just under a year ago, when my head of department asked me to be in charge of setting it up. Luckily, various colleagues at CS and University of Liverpool Management School (ULMS) are also involved, this is not the sort of thing you want to do on your own.

So, it's a 3-year undergraduate course to be taught jointly with ULMS, and it was formally approved a couple of weeks ago. Here is a link that has recently shown up, actually I should get some minor errors fixed in some of the information it contains.
I did not blog about it in case something went horribly wrong with the approval process (approval processes are there to make us resist the urge to set up degree programmes without due care and consideration); we have been under time pressure to get it started up for this September.

Background: lots of students at XJTLU (Liverpool's partner university in China) spend their first 2 years over there and then another 2 years over here. There are about 20 of them who will want to take this new course. Starting in 2010 we will accept new students (mainly UK and EU) to start in year 1 of the course; we don't know how many students it will attract but the students coming from China are enough to justify setting it up.

There is more work to be done, includes setting up a new taught module in CS (probably to be titled "electronic markets") but I'm happy we got the degree approved in time for the first cohort of XJTLU students. Credit must go to Ullrich Hustadt (CS dept expert on XJTLU, and on setting up new degrees) and Frank Steffen (main contact at ULMS). This degree should help to develop further collaborations between the two departments.

European elections

The way that votes within a region are converted into a set of winning candidates is described in a rather unintuitive way here -- here is the relevant passage:

Once the vote count is complete and confirmed:

1. The party with the highest number of votes is allocated the first seat. The candidate at the top of the party's list is elected.
2. The votes of the party winning the first seat are then divided by the number of seats they have won + 1 ( i.e. 2 ) and the resultant number of votes go forward to be compared with the number of votes for the other parties and candidates to decide who wins the next seat.
3. The exercise is then repeated. As each successful party wins its first seat, its votes are divided by 2. This divisor is then increased by 1 each time this party wins a further seat. (NB it is the total number of votes cast for the party which is divided by the divisor, NOT the number resulting from the previous division.)
4. In the event that an independent candidate is elected or all the candidates on a party's list have been elected, the votes cast for that party are excluded from the remainder of the exercise.

This generalises plurality to election of k representatives: scale the votes obtained by each party by dividing them by a common factor chosen so that, when you round the new numbers down to the nearest integers, they add up to k. That's how many representatives each party gets.

My region (North-west England) has suffered the embarrassment of having elected a BNP candidate (one of 8 representatives) with the Green party narrowly failing to edge them out. Note that the number of votes obtained by the BNP actually went down. In my opinion, by putting up their leader as candidate in our region, we were unfairly targeted by them, and this result has more to do with low voter turnout. Both the Greens and the Lib Dems deserved to do better than they did.