My last blog post/question was such a useful source of answers that I have to try this one.
Suppose that you’re about to join a conference excursion with a bunch of game theorists, and the time comes to get on the bus. You join an orderly queue, and when you board the bus, you face a binary choice: either occupy one of an empty pair of seats, or occupy a seat next to someone else. (A standard bus divides its occupants into pairs.) In the latter case, you choose your favourite neighbour amongst people who do not currently have a neighbour, which is easy because, being a game theorist (or if you prefer, a computer scientist) you maintain a complete ranking of how much you like to sit next to each other person. To cover the possibility that the bus has extra space, let’s assume one of the items in the ranking is the case that you have no neighbour.
In order to make that original binary decision, you have to predict who will sit next to you if you occupy one of an empty pair of seats. Luckily, you know the preferences of all the other game theorists, in fact they are common knowledge, along with who precedes who in the queue. So, if you’re the penultimate person to get on, you simply check whether the last person would sit next to you given the opportunity, in which case you choose between him and the best other available person; if not, you choose between being alone and being with the best other available person. If there are 2 people behind you, you assume that the penultimate person would reason like that, and so on. Clearly there’s a unique solution, and… actually let’s say these people are game theorists rather than computer scientists, since I’d like to assume they are computationally unbounded. The question we face as computer scientists is to compute the solution.
All I know is that the problem is in PSPACE. It’s possible to come up with more general, on-steroids versions, such as choosing where to sit at a banquet, but the bus question will do for now.
Suppose that you’re about to join a conference excursion with a bunch of game theorists, and the time comes to get on the bus. You join an orderly queue, and when you board the bus, you face a binary choice: either occupy one of an empty pair of seats, or occupy a seat next to someone else. (A standard bus divides its occupants into pairs.) In the latter case, you choose your favourite neighbour amongst people who do not currently have a neighbour, which is easy because, being a game theorist (or if you prefer, a computer scientist) you maintain a complete ranking of how much you like to sit next to each other person. To cover the possibility that the bus has extra space, let’s assume one of the items in the ranking is the case that you have no neighbour.
In order to make that original binary decision, you have to predict who will sit next to you if you occupy one of an empty pair of seats. Luckily, you know the preferences of all the other game theorists, in fact they are common knowledge, along with who precedes who in the queue. So, if you’re the penultimate person to get on, you simply check whether the last person would sit next to you given the opportunity, in which case you choose between him and the best other available person; if not, you choose between being alone and being with the best other available person. If there are 2 people behind you, you assume that the penultimate person would reason like that, and so on. Clearly there’s a unique solution, and… actually let’s say these people are game theorists rather than computer scientists, since I’d like to assume they are computationally unbounded. The question we face as computer scientists is to compute the solution.
All I know is that the problem is in PSPACE. It’s possible to come up with more general, on-steroids versions, such as choosing where to sit at a banquet, but the bus question will do for now.
No comments:
Post a Comment