What the old algorithm got wrong

The first version of this tool used a weighted score: part ranking, part price signal, part baseline room quality. It ran a real trip in January 2026 — eighteen people, twelve parties once couples are counted as one. Then we went back and checked what it had actually done to them.

This is the article that changed the project, so it is worth being careful about that nidus. It is one trip. It is eighteen people who all know each other. It is not a benchmark, and a single trip cannot establish that one method beats another in general.

What it can do — and did — is demonstrate that the old method had a failure mode nobody had thought to look for, because nobody had written down a property to check it against.

The two runs, side by side

Same eighteen submissions. Same house. Same total cost. The only difference is which allocator processes them.

Measure	v1 (weighted score)	Envy-free
Parties who envy someone else	9 of 12	0 of 12
Worst single case of envy	$66.00	$0.00
Worst-off person’s surplus	−$47.07	+$11.11
Total value delivered, per person	$550	$800
Spread between cheapest and dearest bed	$354	$425

The first two rows are the ones that describe the argument people were having. Three quarters of the group could point at somebody else’s bed, look at its price, and correctly say I would rather have that one. One of them was $66 better off under a swap that never happened.

The row that actually matters

The headline failure is not the envy. It is the third row: a negative surplus.

Surplus is the gap between what a person said their bed was worth to them and what they were charged for it. Positive means they got a deal on their own terms. Negative means something worse than unfair — it means the system charged them more than they had told it the bed was worth.

Under v1, that happened to six of the eighteen people. A third of the group paid more than their own stated valuation. Not more than they wanted to pay, in the sense that everybody wants to pay less — more than the number they themselves had written down.

One person, specifically

The clearest case: somebody looked at a bunk in a full room and submitted an adjustment of −$150. In plain terms, that is “I will take the bunk, but only if it comes off my share by a hundred and fifty dollars.”

They were assigned that bunk. Their discount came out at −$102.93.

The difference — $47.07 — is exactly the worst-off surplus in the table above. They said what the room was worth, they were given the room, and they were charged $47.07 more than the figure they had named. There was no point in the process where anybody had to overrule them. The algorithm simply never consulted that number when setting the price.

Selecta-bot explains

Somebody said: I will take the bunk, if you knock $150 off my share. The old system gave them the bunk and knocked $102.93 off. Nobody argued them down and nobody outvoted them — the program simply never looked at the number they had written when it decided the price. They paid $47.07 more than they had said the bed was worth to them, and every screen along the way looked perfectly normal.

The mechanism of the bug

v1 priced beds from bed-class averages — what a bunk is generally worth across everyone — and assigned beds from a weighted score. Prices and people were computed by two different procedures that never had to agree. So a price could land above a specific person’s stated value for the specific bed they were given, and nothing in the system was watching for it.

The other failure: submission order was worth money

v1 assigned beds greedily. Greedy assignment has to break ties somehow, and the tiebreak was the order submissions arrived.

That means filling in the form early had cash value, and the tool never disclosed it. Two people with identical preferences got different beds because one of them checked their messages sooner. It is a small thing next to charging somebody $47 over their own valuation, and it is the kind of thing that is impossible to argue about after the fact, because the output looks exactly the same as a legitimate one.

The envy-free allocator computes an exact maximum-weight matching over all possible assignments. Submission order is not an input to it, so it cannot influence the result.

Why the price spread went up, and why that is fine

One number moved in the direction people find uncomfortable: the gap between the cheapest and most expensive bed widened from $354 to $425.

That is not a side effect to apologise for — it is the mechanism working. Envy-freeness buys peace by making the premium on a good room large enough to decline. If the premium is small, the people who did not get the room still want it, and you are back to the auction problem. Making nobody want to trade necessarily spreads the prices further apart.

A group that finds a $425 spread socially unacceptable is having a real disagreement, but it is a disagreement about equal bidding budgets, not about this algorithm.

How we checked the result was right

A single run producing nice numbers is not evidence, particularly when the program grading the run is the same program that produced it. Three separate checks:

An internal "independent auditor." The envy check is a separate program from the allocator. It re-reads the stored submissions and the stored results and re-derives every pairwise comparison from scratch, rather than trusting the allocator’s own self-check.
Local search. 4,000 randomised restarts, trying 2-swaps and 3-cycles against the assignment, reproduced the dynamic programming optimum exactly. If a better assignment existed, this is the kind of search that would stumble into it.
Simulation at scale. 576 generated trips across 144 scenario combinations — varying group size, share of couples, price spread, how correlated people’s tastes are, and how noisy their valuations are. Zero envy violations, checked by the independent auditor. Largest budget error across all of them: $3.41×10⁻¹³, which is floating point, not money. On the trips small enough to enumerate exhaustively, the matching agreed with brute force on every single one.

The auditor itself failed a review once, and the way it failed is instructive: it had been written to group couples by a convention the product had stopped using, so on real data it split couples apart, valued a pair from one member’s bids, and manufactured a violation the allocator had not committed. It did this intermittently, which is why the first clean run was luck rather than evidence. Run a checker twice before believing it, and confirm its model of the inputs matches what the product actually writes today.

And then it was wrong again

The mechanism described above replaced the weighted score, and then we found a defect in it too. That is worth recording rather than quietly fixing, because the pattern is the point: every failure in this project has been found by writing down a property and checking it against real numbers. Not one of them announced itself.

The first defect was that a room was priced per person instead of per room. The same room therefore raised a different amount from the group depending on how many bodies were in it — a single person in a bed for two bought half a room, and everyone else quietly covered the rest. A room now carries a share of the trip total and whoever takes it splits that share, so swapping any two households leaves every bystander’s bill untouched. That is the assumption the fairness argument needs, and it did not have it.

The second was subtler. Ranking and price were the same control, so “this room is worth a lot” and “I want this room” could not be said separately — and for anyone travelling alone they are routinely opposite. Bidding a suite honestly high was indistinguishable from asking for it, which meant the only way to price the best room truthfully was to risk being put in it. Both signals are now read, and they answer different questions.