I recently got lunch with Jo Jiao, who jointly optimized her utility function over main-dessert pairs, running:
This contrasts with the greedy sequential optimization I usually run:
Jo might’ve run backward induction:
Here are some other algorithms Jo might’ve implemented — ordered from most to least computationally expensive:
Backward induction finds the same optimal solution as joint enumeration, but is easier on working memory:
We get the Bellman-optimal solution:
How much value have I been forfeiting?
I would say the most significant term is whether I have room for dessert at all, and in reality I do actually just about run enough backward induction to make dessert happen when I want it to. But I don’t normally look at the dessert menu before dessert-time. I will start asking GPT-5.2 to calculate optimal pairings over ‘most unique menu items’. In this case, a coconut dessert freed optionality to try a different main.
my usual heuristic is "if there is an interesting enough dessert i will try to make room for it, otherwise i will ignore dessert and decide after i eat main"
the interestingness does mean estimating the main/dessert utility over the space of desserts, and when i do that computation i uh, just ignore the main term altogether, assuming that it's additive with the main