Background

Listen Labs recently held a contest with a problem set to the theme of being a Berghain nightclub bouncer, where guests arrive with flavored attributes and the player must admit or reject each patron with the goal of filling the nightclub with 1000 people, while satisfying several lower bound constraints on the number of patrons with each flavor attribute admitted.

That version was a bit too easy because it considered only static lower bounds, and the scoring approach (lowest rejection of all attempts) selected for players who submitted many trials, rather than efficiently identifying high performing algorithms.

Here we introduce a clone of the game with support for more complicated bounds structures (plus some easy ones to get warmed up on) along with scoring relative to an offline algorithm's rejection count for the same sequence, allowing successful algorithms to be identified with significantly fewer trials.

Problem Statement

Consider a i.i.d. sequence of random vectors. Each random vector consists of N binary-valued attributes, which can be represented as a single symbol. The PMF of the symbols is unknown; instead the marginal probabilities for each attribute and the correlation matrix between attributes is known, but the joint distribution of all attributes is not. There are at least two reasonable ways to generate symbols in this scheme so do not assume a particular generation method.

The objective of the game is to perform online processing of each symbol in a sequence as it is received, classifying it as accepted or as rejected, such that 1000 symbols are accepted, a set of scenario-specific constraints is satisfied, and the total sequence length observed (equivalently, the number of symbols rejected), is minimized.

Each game has a set of known distribution parameters as described above and a set of constraints, consisting of a relational operator (>= or <) and two arithmetic expressions combining constants, number of symbols matching an attribute, and basic operators including addition, subtraction, multiplication, and division. A specific scenario will use the same parameters each time but will produce a new random sequence.

Playing

Sign up with a display name in order to receive a user UUID, which is how you will make requests to the game server.

The game operates through HTTP GET requests, with all parameters encoded as GET arguments and all responses presented as JSON objects. This violates all kinds of design principles such as GET not requests producing side effects, but it has the benefit of being extremely simple to interact with and implement as a server. You will make one GET request to start a game and receive a game UUID, then you will use this UUID to request new symbols and accept or reject pending symbols.

Game Status

So far the basic web API is functional. You can get a user uuid, start and play games, and the outcomes of those games are saved and visible on the website. Several scenarios including goals similar to the first Listen Labs scenario are available, with different probability distributions that result in three types of solutions, and one experimental scenario is defined which includes goals that express bounds between two attributes. The experimental scenario has not been analyzed and could range from trivial to impossible. An analyzer for scoring performance relative to an offline algorithm is also forthcoming. It is ready for the first three scenarios but not ready for the experimental one and has not been integrated into the server software yet as a result.

API

The basic game API is:

/game/new-game?user=&type=0
Arguments:
user uuid of the user playing
type game type id
Response:
{"id":"509a80bb-547a-4f55-92ed-815888b85331"}
Description:
This creates a new game of the given type. The game type determines the probability distribution used and the goals that must be satisfied. Game types and their parameters can be obtained from the /game/params route.
/game/process-person?game=df88afc9-b45e-4005-be23-853f34486cc9&person=0&verdict=true
Arguments:
game uuid of the game
person # of person considered
verdict optional, true to accept this person and false to reject
Response:
{"status":"running","count":0,"next":0} indicating no symbols have been processed and the next arrival has no attributes
{"status":"running","count":1,"next":3} indicating one symbol has been processed and the next arrival has attributes 0 and 1 set
{"status":"completed","count":1546} indicating that 1000 symbols have been accepted (of 1546 total) and all constraints are satisfied
{"status":"failed","count":1000} indicating that 1000 symbols have been accepted (of 1000 total) but not all constraints were satisfied
Description:
This either retrieves the next sequence element (when verdict is omitted) or processes the next sequence element and then retrieves the next, next sequence element (when verdict is provided)
/game/details?game=509a80bb-547a-4f55-92ed-815888b85331
Arguments:
game uuid or integer id of game
Response:
{"count":1000,"accepted":1000,"next":0,"attrs":[365,415,0,0,0,0,0],"type":0,"finished":true,"won":false}
Description:
This retrieves summary information about a game including how many symbols have been seen (count), how many were accepted (accepted), what symbol is next if any (next), how many symbols with each attribute (element of attrs) have been accepted, what parameters are used (type), whether the game has ended (finished), and whether the constraints were met (won). The number rejected must be computed from the number seen and the number accepted. Note that this request does not include all of the symbols seen, as that is found in /game/symbols, since the complete list of symbols is not needed to show summary info and can be obtained later for a detailed look at a particular game.
/game/symbols?game=509a80bb-547a-4f55-92ed-815888b85331
Arguments:
game uuid or integer id of game
Response:
{"count":1000,"symbols":[131,128,128,128,...,131]}
Description:
This retrieves the list of symbols that were seen plus the total expected length of that list. Currently, bits 0-6 encode each of the possible binary variables and bit 7 is set when the symbol was accepted or unset when it was rejected.
/game/params?type=0
Arguments:
type optional, game type id
Response:
{"rulesets":2} when type is omitted
{"type":0,"p":[0.361837,0.411532],"Q":[1.000000,0.781522,0.781522,1.000000],"goals":[[8197,4096,600],[8197,4097,600]]} when type is included
Description:
This retrieves game parameters for a specific type of game. p contains the marginal probabilities for each bit that may be set in a particular symbol, and Q is the square correlation matrix between the possible attributes. goals defines the goals as expressions encoded one per array. Each term in a goal is a packed bitfield, with the following convention: bit 13 (8192) indicates that the term is an operator, with the lower order bits identifying the type of operator: 0 for +, 1 for -, 2 for /, 3 for *, 4 for <, and 5 for >=; bit 12 (4096) indicates that the term is the current value of an attribute with the lower order bits identifying which one; and values smaller than 4096 encode constants exactly. Each goal is an expression in polish notation. The goal [8197, 4096, 600] therefore encodes the expression `>= attr[0] 600` or `attr[0] >= 600` in infix notation.
Currently, p is calculated based on the model used to generate attributes, but Q is measured by generating 10 million symbols and calculating the correlation between each. This means that Q will appear to change between server restarts, but the underlying model will not change! If/when a closed-form solution is obtained for Q that will be used instead.
Errors:
If an error happens, the response will generatelly be a JSON object with a single field named error, such as {"error":"bad or missing arg type"}. Ideally the error message will tell you what you did wrong but this isn't guaranteed. If you're missing a GET argument, the name of the argument will be given like in the example. If there was a database error it will probably just say 'valkey error' with nothing that can help you.