Dark room problem

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

myrcutio
Posts: 44
Joined: Wed Dec 30, 2009 7:28 pm UTC

Dark room problem

Postby myrcutio » Mon Oct 07, 2013 11:40 pm UTC

I have a problem, and I suspect it exists somewhere else under another name, but I thought I'd lay it out as an analogy and let someone smarter than I tell me if there is a solution. Here's the setup:

There's a party, and it's really packed. Wall to wall bodies, but there's enough room for one or two people to move at a time. There's only one door, and any one person can get through at a time but if they all rushed for it it would take a long time to clear out. The circuit for the lights goes out and everyone's left standing in the dark. They all know someone has to go to the basement to flip the breaker, but if everyone tries to go at once it'll just make things worse.

Here's the question:
How can any one person in the room know, without seeing or talking to anyone else, that they are the one person who should go to the basement and flip the switch?
"Lightning must have hit it, and now it won't work in anything but Windows 95."

Faustus runs afoul of Microsoft.

User avatar
headprogrammingczar
Posts: 3072
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

Re: Dark room problem

Postby headprogrammingczar » Tue Oct 08, 2013 12:33 am UTC

They'd solve it by seeing that they were the closest to the door. Since this sounds like a metaphor for networking, I'm going to step out of the metaphor to say that this problem becomes easier when each node has access to not just the communications cost of itself to each neighbor, but also the costs of neighbors to neighbors of neighbors. The basement would then be just another node, and your solution is "if I can see the basement and I am the lowest cost to go to the basement, pick myself".
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you

User avatar
Bloopy
Posts: 215
Joined: Wed May 04, 2011 9:16 am UTC
Location: New Zealand

Re: Dark room problem

Postby Bloopy » Mon Nov 18, 2013 12:59 am UTC

Each person would need to be conscious of who or what was nearby, so it's like a swarm robotics problem. Under what conditions does a robot break formation and carry out a solo mission? When the lights go out, the person who remembers being in easiest reach of the door goes for it.

User avatar
Moose Anus
Posts: 420
Joined: Fri Oct 14, 2011 10:12 pm UTC

Re: Dark room problem

Postby Moose Anus » Thu Nov 21, 2013 8:30 pm UTC

What do you mean by "should"? Should really drunk people not do it? Should only the building owner do it because they know where the circuit breakers are?

They might just talk about it to figure it out. Like, "Hey, I know where the circuit breakers are. Let me through!"
Lemonade? ...Aww, ok.

Nem
Posts: 336
Joined: Fri Aug 14, 2009 12:19 pm UTC

Re: Dark room problem

Postby Nem » Fri Nov 22, 2013 11:54 pm UTC

myrcutio wrote:I have a problem, and I suspect it exists somewhere else under another name, but I thought I'd lay it out as an analogy and let someone smarter than I tell me if there is a solution. Here's the setup:

There's a party, and it's really packed. Wall to wall bodies, but there's enough room for one or two people to move at a time. There's only one door, and any one person can get through at a time but if they all rushed for it it would take a long time to clear out. The circuit for the lights goes out and everyone's left standing in the dark. They all know someone has to go to the basement to flip the breaker, but if everyone tries to go at once it'll just make things worse.

Here's the question:
How can any one person in the room know, without seeing or talking to anyone else, that they are the one person who should go to the basement and flip the switch?


Everyone should just go. If they don't get out easily then they weren't closest and can abort. The objective isn't to clear the room, it's for one person to get to the basement fastest - whoever's closest will get there first.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 9 guests