Hats In A Room

So, I haven't been in town for a while, I've been away at the go congress. My performance there was average, but I'm happy with the games I played. Anyway, onto the new puzzle. I first learned this one from Bart:

There are 100 prisoners in a room (we shall call this room A) and the warden of these prisoners has decided to play a game with them. In another room (room B) there are 100 hats, and each one has the name of one of the prisoners underneath it (each prisoner has a unique name). A prisoner will be selected randomly and sent into room B. While in room B, the prisoner may look underneath 50 of the hats and then will be sent into another room (room C). Room B will then be restored to its initial state before a new prisoner is sent into it.

One by one, each prisoner will have a chance to look underneath 50 hats before being sent into room C. Once they are all in room C, they will all be released if each one of them has looked under the hat that contains their own name. If any of them has not looked under the hat that contains their own name, they will be sent to their cells for another night and the scenario will be run again tomorrow, with the names randomized underneath the hats each time.

The prisoners may plan while in room A. Come up with a strategy that, on average, will set them free in less than a week.

As I understand, Bart first learned this one at a talk entitled "Seven Problems You Swear You've Heard Incorrectly".