Is it possible to find other nearby phones?

Options I can see

1. Bluetooth (BT). I don't know, if I'm not too skeptical about it, but I see couple of problems. Short range. The biggest energy consumption. Maximum 7 peers connected at the same time (but maybe it's enough...). The big advantage is that a lot of devices support BT.

2. BT LE (low energy). Ok, it helps energy consumption problem. But, requires Android 4.3.

3. WiFi Direct (aka P2P). I gave it a shot, I'm a bit disappointed. The problem is that it needs Android 4.0 or higher. Even worse, some devices don't have required hardware. I launched WiFiDirectDemo from Android samples on Samsung Xperia Miro ST23i. Clicked on "search" and the only thing I got was a toast "enable WiFi P2P - in your settings". I clicked on everything in that settings, there is just normal WiFi and other stuff, no mention about Direct or P2P. Xperio Miro just doesn't support WiFi Direct.

4. WiFi connection with a server through internet + device geolocation. Server keeps positions of users and answers questions like "who is 20 feet in my range?". The problem can be the precision of geolocation. If the walls are thick or you are in a place on earth with few satellites - it can be very inaccurate.

To sum up

There is greater probability that somebody will have WiFi turned on all the time than BT. BT also have some time limits after which it is turned off (they make it this way to probably save battery). So, WiFi seems a better choice than BT.

If WiFi Direct is popular enough for you - I would give it a try. If not, option number 4 seems the best. It's not ideal, I know, but at this point it's hard to come with something better (we still need technology development, WiFi Direct looks promising).

I would use the central server approach. Each phone sends position data to the server. The server notifies the other users when they are in range. To limit used data, only send positions when the device reports movement more then X meters.

Also, consider using a Ping button. The user presses it to send the position when they wish to find someone nearby. Position data would only be sent on this ping. This would use very little power and provide good privacy.

It might be possible to detect details about the connected Wifi access point. If you could get the AP or Gateway's MAC address, you could send that as a kind of position. All the players on the same Gateway would be close by.