Constraints & Slackness Reasoning Exercises

Epistemic sta­tus: no idea if this will work at all for learn­ing the rele­vant thought-skills. Please post feed­back if you try any ex­er­cises, es­pe­cially if you hadn’t in­ter­nal­ized these skills already.

The goal of this post is to briefly ex­plain and prac­tice a very gen­eral thought-tool. If you’ve ever tried to hold off on propos­ing solu­tions, then sat there with­out any idea where to start, then this is the sort of tool which you may find use­ful. We’ll start with a short ex­am­ple and ex­pla­na­tion, then dive right into the ex­er­cises.

Here’s a re­ac­tion you may have used in high school or un­der­grad chem lab to syn­the­size as­pirin:

(source)

Each mole of as­pirin re­quires one mole each of sal­i­cyclic acid and acetic an­hy­dride to pro­duce.

Warm-up ques­tion: we start with one mole of sal­i­cyclic acid and two moles of acetic an­hy­dride. As­sum­ing the re­ac­tion runs to com­ple­tion (i.e. as much of the re­ac­tants as pos­si­ble are con­verted to as­pirin), which will re­sult in more to­tal as­pirin pro­duc­tion: one ex­tra mole of sal­i­cyclic acid, or one ex­tra mole of acetic an­hy­dride?

In the lan­guage of op­ti­miza­tion/​eco­nomics, we have two con­straints:

  1. the amount of as­pirin pro­duced is less than or equal to the amount of sal­i­cyclic acid available (in moles)

  2. the amount of as­pirin pro­duced is less than or equal to the amount of acetic an­hy­dride available (in moles)

In the case of our warm-up ques­tion, we would say that con­straint 1 is “taut” and con­straint 2 is “slack”. Once 1 mole of as­pirin is pro­duced, we can­not pro­duce any more, be­cause there is no “room left” in con­straint 1 - just like a taut rope can­not be pul­led fur­ther, a taut con­straint can go no fur­ther. Con­versely, just like a slack rope can be pul­led fur­ther, con­straint 2 has ex­tra room—ex­tra acetic an­hy­dride left, which could pro­duce more as­pirin if only we had more sal­i­cyclic acid.

Key point: the slack con­straint is com­pletely and to­tally ir­rele­vant to the amount of as­pirin pro­duced, so long as it re­mains slack: adding one ad­di­tional mole of acetic an­hy­dride will pro­duce ex­actly zero ex­tra moles of as­pirin. If we want to max­i­mize the amount of as­pirin pro­duced, then we should ig­nore the slack con­straint (acetic an­hy­dride) and fo­cus on the taut con­straint (sal­i­cyclic acid).

This idea gen­er­al­izes: when­ever we want to op­ti­mize some­thing, we can ig­nore slack con­straints. Only the taut con­straints mat­ter.

In more re­al­is­tic situ­a­tions, “con­straints” usu­ally aren’t perfectly bind­ing. For in­stance, a real as­pirin-pro­duc­ing re­ac­tion might not run all the way to com­ple­tion—it might reach some equil­ibrium where there’s a lit­tle bit of both sal­i­cyclic acid and acetic an­hy­dride in the solu­tion, and adding ei­ther one will pro­duce at least some ex­tra as­pirin. But even then, con­straint 1 will be “more taut” than con­straint 2 - one ex­tra mole of sal­i­cyclic acid will pro­duce a lot more ex­tra as­pirin than one ex­tra mole of acetic an­hy­dride. We can quan­tify this via marginal pro­duc­tion (a.k.a. the gra­di­ent), but that’s not re­ally the goal here.

The goal here is to build some in­tu­ition for rec­og­niz­ing which con­straints in a prob­lem are prob­a­bly more taut or more slack, and us­ing that in­tu­ition to make trade­offs. In the real world, this usu­ally re­quires a bunch of do­main-spe­cific knowl­edge, so we’ll be us­ing some made-up games to keep it sim­ple.

Game Exercises

In these ex­er­cises, the rules of a game are laid out up-front. Iden­ti­fy­ing po­ten­tial con­straints/​re­sources should be rel­a­tively easy; the fo­cus is on pre­dict­ing which con­straints will be taut. The main ques­tion will be: what do you ex­pect to be the main bot­tle­neck?

Side notes: these ex­er­cises are in­tended for peo­ple not already fa­mil­iar with the spe­cific sub­ject mat­ter, so if you’ve never played Magic: The Gather­ing or Civ­i­liza­tion V or what­ever then don’t worry. Feel free to post clar­ify­ing ques­tions in the com­ments. If you post solu­tions or ma­jor hints in the com­ments, please rot13 them.

Ex­er­cise 1: Deck-Build­ing Game

Con­sider a sim­plified deck-build­ing com­bat game, along the lines of Magic or Hearth­stone. You start each turn with five ran­dom cards from your deck, and three mana. Each card costs one mana to play, and does use­ful things: sum­mons or boosts al­lies, dam­ages your op­po­nent or their al­lies, etc. On your turn, you can play as many cards as you like, un­til you run out of ei­ther cards or mana. At the end of your turn, any lef­tover cards get shuffled back into your draw pile, along with any cards you played.

Start each turn with 5 ran­dom cards and 3 mana. Each card costs 1 mana to play. At the end of your turn, all cards (both played and in hand) are shuffled back into your draw pile.

You have a choice be­tween two cards to add to your deck:

  • En­ergy card: gain 2 mana im­me­di­ately (Note that it costs 1 mana to play)

  • Draw card: draw 2 cards immediately

Th­ese are the only cards in the game which gain mana or draw cards, re­spec­tively.

All else equal, which of the two cards above would you choose? For each sce­nario be­low, iden­tify rele­vant con­straints, pre­dict which con­straints are taut/​slack, and use this knowl­edge to pick your card. If your an­swer de­pends on some­thing, say what (and quan­tify it if pos­si­ble!).

  1. The en­tire rest of the deck is copies of the At­tack card

  2. Full deck has size 25 cards, you have 2 En­ergy cards already, rest of the deck is At­tack (Hint: you draw 5 ran­dom cards each turn. What con­straint has the high­est prob­a­bil­ity of be­ing taut?)

  3. Full deck has size 25 cards, you have 8 En­ergy cards already, rest of the deck is Attack

  4. The rest of the deck is 50% At­tack and 50% Defend. Depend­ing on the turn, you want to ei­ther only at­tack or only defend—the other card is use­less.

  5. As pre­vi­ous, ex­cept 30% At­tack and 70% Defend.

  6. One card in your deck wins the game in­stantly. (If your an­swer de­pends on some­thing, quan­tify it.)

  7. There are roughly 4 differ­ent card types in your deck, with differ­ing num­bers of each, each suited to differ­ent situ­a­tions.

  8. As pre­vi­ous, ex­cept full deck size is 25 cards and you have 5 Draw and 2 En­ergy cards already.

Ex­er­cise 2: 4X Game

Next, let’s con­sider a sim­plified 4X game, along the lines of Civ (4X = ex­plore, ex­pand, ex­ploit, ex­ter­mi­nate). You start the game with your home base (fixed po­si­tion) and one unit (mo­bile), lo­cated some­where on a large and mostly-un­re­vealed map. The unit always starts at your home base, and comes in one of four types:

  • Scout: fast, long sight range (good for ex­plo­ra­tion)

  • Set­tler: can es­tab­lish new bases (good for ter­ri­to­rial ex­pan­sion)

  • Worker: builds im­prove­ments on your bases/​ter­ri­tory (good for ex­ploit­ing re­sources)

  • War­rior: can fight other play­ers and take their stuff (good for ei­ther offense or defense)

You can ob­tain more units by pay­ing for them with re­sources. Re­sources are pro­duced by the ter­ri­tory around your bases: in gen­eral, more bases ⇒ more ter­ri­tory ⇒ more re­sources ⇒ buy more units. How­ever, differ­ent lo­ca­tions may pro­duce more/​differ­ent re­sources. Im­prove­ments (built by work­ers) will gen­er­ally in­crease re­source yield, but have diminish­ing re­turns: sec­ond or third im­prove­ments have less per­centage im­pact than first im­prove­ments.

The base col­lects re­sources from its ter­ri­tory—five light­ning and two heart re­sources. Differ­ent lo­ca­tions pro­duce more/​differ­ent re­sources, and the hex to the north pro­duces no re­sources at all. Most of the map is un­ex­plored, as in­di­cated by “?”. The unit north-east of the base can move around, e.g. to ex­plore the map.

Un­less oth­er­wise stated, you may as­sume that:

  • Your home base pro­duces what­ever re­sources are needed to cre­ate any ad­di­tional units, but not very quickly.

  • There are no units ex­cept those be­long­ing to the play­ers (i.e. no “bar­bar­ian” units).

  • Play­ers usu­ally start far apart.

  • Win con­di­tion is to ex­ter­mi­nate the other play­ers, but the game is long enough that ex­ter­mi­na­tion usu­ally isn’t di­rectly rele­vant in the early game.

For each sce­nario be­low, you get to pick ex­actly one unit to start the game with. For each one, iden­tify rele­vant con­straints, pre­dict which are taut (all else equal), and then pick a unit type. If your an­swer de­pends on some­thing, say what (and quan­tify it if pos­si­ble!), and at least try to elimi­nate some of the unit types.

  1. Map is uniform (no lo­ca­tion differ­ent from any other).

  2. Sparse re­sources: most lo­ca­tions pro­duce no re­sources.

  3. Your start­ing lo­ca­tion has un­usu­ally good re­sources.

  4. You start right next to an­other player.

  5. The map starts with one-time re­source caches, picked up by the first unit to find them.

  6. You do not know how close you start to other play­ers.

  7. The en­tire map, in­clud­ing other play­ers’ bases, is re­vealed at the start.

  8. The en­tire map, in­clud­ing other play­ers’ bases and units, is visi­ble through­out the game.

  9. Im­prove­ments have in­creas­ing rather than de­creas­ing re­turns.

  10. There are hos­tile “bar­bar­ian” units scat­tered around the map which at­tack the play­ers’ units.

Ex­er­cise 3: Eng­ine-Build­ing Game

Fi­nally, we’ll look at a sim­plified en­g­ine-build­ing game. Each player has some re­sources and some cards. On your turn, you draw four cards from the deck, and can pur­chase as many of them as you want (and can af­ford) us­ing what­ever re­sources you’ve ac­cu­mu­lated. Each card does differ­ent things—some give an im­me­di­ate one-time benefit (e.g. trad­ing one re­source for an­other), oth­ers give long-term benefits (e.g. pro­duc­ing re­sources ev­ery turn or ev­ery time some­thing spe­cific hap­pens), and some give the player new ca­pa­bil­ities (e.g. the abil­ity to trade one re­source for an­other in­definitely).

To keep it sim­ple, we’ll as­sume that:

  • You’re usu­ally not di­rectly com­pet­ing with other play­ers for par­tic­u­lar cards.

  • The first player to amass a cer­tain amount of re­sources wins.

In each sce­nario be­low, pick which cards to buy (or de­cide not to buy any). For each one, iden­tify rele­vant con­straints, pre­dict which are taut (all else equal), and then pick cards. If your an­swer de­pends on some­thing, say what (and quan­tify it if pos­si­ble!), and at least try to elimi­nate some of the cards.

  1. On your first turn, you have a choice be­tween two types of cards: Machines, which pro­duce one re­source per turn, and Ma­chine Shops, which pro­duce one Ma­chine per turn. You can spend all your re­sources to buy ei­ther three Machines or one Ma­chine Shop. Which do you pick? If your an­swer de­pends on some­thing, quan­tify it.

  2. Same as pre­vi­ous ques­tion, but it’s late in the game rather than your first turn.

  3. There are two differ­ent re­sources in the game: di­a­monds and ru­bies. You have a choice be­tween a Ma­chine which pro­duces two di­a­monds per turn, or a Ma­chine which pro­duces one re­source of your choice per turn. All re­source-pro­duc­ing Machines are quite com­mon in the game.

  4. Same as (3), ex­cept ruby-pro­duc­ing Machines are rare.

  5. Same as (3), ex­cept di­a­mond-pro­duc­ing Machines are rare.

  6. Same as (3), ex­cept there are six re­sources in the game rather than two.

  7. Same as (3), ex­cept you can trade with other play­ers.

  8. Same as (3), ex­cept you can trade with other play­ers and the other play­ers already have lots of di­a­mond pro­duc­tion.

  9. Same as (3), ex­cept you can trade with other play­ers and the other play­ers already have lots of ruby pro­duc­tion.