Great write-up. Love how everyone is sharing their solutions. Fun fact, this is an actual business problem we have to solve at our company (Listen Labs).
We have an AI customer interviewing platform our customers ask us things like:
“I want to talk to 200 people, at least 100 who are ChatGPT Pro users, 75 who use Gemini weekly, and 50 from each region of the US.”
We don’t know those attributes upfront, so we have to ask participants screening questions and decide in real time whether to move forward.
Of course, it's a bit different as we optimize for the average case, not the best case, and we don't know the distributions (but can estimate with LLMs!).
The trick for Scenarios 2 and 3 is that most of the constraints don't end up being bottlenecks. For example in Scenario 2, well-connected pretty much always gets satisfied while doing the other constraints, so the DP table only needs 4 dimensions (space, Berlin local, techno lover, creative).
My other trick was to only build the full DP table for the latter half of the game (i.e. when all the constraints are at least 50% satisfied) which across 4 dimensions reduces the size by a factor of 16. For the beginning half of the game I combined Berlin and techno into a single parameter, which technically isn't perfect but doesn’t matter too much in the early game. I wrote up my approach here if you want more details: https://chriskw.xyz/2025/09/16/Berghain/
Re: optimizing for best case vs expected case, I thought about that but in simulations my strategy mostly performed the same as a "perfect knowledge" strategy where you could see all of the people in line ahead of time and retroactively accept people. When it under performed it was usually because some miraculous string of people showed up near the end, but betting on that happening seemed like it would do more harm than good, i.e. it would throw away more best case scenarios than it would salvage.
I still remember my first job porting a VB6 code to VB.net. The code was written before object-oriented code was a thing. Back then I thought OO would have solved it. Looking back all it was really missing was a strong type system.
We have an AI customer interviewing platform our customers ask us things like: “I want to talk to 200 people, at least 100 who are ChatGPT Pro users, 75 who use Gemini weekly, and 50 from each region of the US.”
We don’t know those attributes upfront, so we have to ask participants screening questions and decide in real time whether to move forward.
Of course, it's a bit different as we optimize for the average case, not the best case, and we don't know the distributions (but can estimate with LLMs!).