Tuesday, July 8, 2014

Finding the Best Book Quotes: Power Ranking Goodreads

My friend Jordan Ellenberg wrote an article for the Wall Street Journal recently describing a metric to roughly measure the least read books, which he calls the Hawking Index (HI). As he describes it, take the page numbers of a book's five top highlights, average them, and divide by the number of pages in the whole book.

On a discussion thread on Facebook, this led to a proposal from me for measuring the general quality of a quote. Assume a user has some level of discrimination \(D\); the higher the value of \(D\), the more likely they are to quote a passage. Now assume each passage has some measure of quality \(Q\); the higher the value of \(Q\), the more likely a passage is to be quoted. Let's try a classic Bradley-Terry-Luce model - if a user with discrimination \(D\) quotes at least one passage from a particular work, the probability \(p\) that they'll quote a given passage with quality \(Q\) from that same work is roughly \[ p = \frac{Q}{Q+D}.\]
Nice, but where can we find data to actually test this theory? It turns out an excellent source is Goodreads. Users are numbered sequentially starting with Goodreads founder Otis Chandler's ID of 1; a user's associated quote page has a simple URL structure. Furthermore, every user's quote list has an associated RSS/Atom URL that provides an easy to parse XML file.

The steps:
  1. Write a simple Go scraper to uses a goroutine to quickly and sequentially get user quote pages, grab the count of quotes shown on that page (truncated at 30), then grab the RSS/Atom URL. This is able to process about 2500/users minutes over a slow internet connection.
  2. Write a simple Ruby program to fetch quote XML files for every user that has at least one quote.
  3. Write a simple Ruby program to fetch the author URL and work URL for every quote cited by at least one user.
  4. Load all this data into a PostgreSQL database.
  5. Write a simple R program to pull the data from the database and fit our model. We assign a value for the outcome "quoted" of 1 if the user quoted a passage; we assign "quoted" the value 0 if the user quote a passage from that work, but not that particular passage. Both user "discrimination" and quote "quality" are treated as factors and modeled as random effects; the R package "lmer" was used to fit the model.
If there is interest, I can make all of this code publicly available through my GitHub account. None of it is proprietary.

As a test I grabbed the data from 333760 users, 10724 had at least one quote, there were 83160 total quotes and 32621 unique quotes. The model took about 3.5 minutes to fit using an optimized BLAS library and 4 hyperthreaded CPU cores.

The top 10 quotes on Goodreads, ranked by quality:
  1. “No one can make you feel inferior without your consent.”
    Eleanor Roosevelt, This is My Story
  2. “Outside of a dog, a book is man's best friend. Inside of a dog it's too dark to read.”
    Groucho Marx, The Essential Groucho: Writings For By And About Groucho Marx
  3. “Twenty years from now you will be more disappointed by the things that you didn't do than by the ones you did do. So throw off the bowlines. Sail away from the safe harbor. Catch the trade winds in your sails. Explore. Dream. Discover.”
    H. Jackson Brown Jr., P.S. I Love You
  4. “I am so clever that sometimes I don't understand a single word of what I am saying.”
    Oscar Wilde, The Happy Prince and Other Stories
  5. “Insanity is doing the same thing, over and over again, but expecting different results.”
    Narcotics Anonymous, Narcotics Anonymous
  6. “He has achieved success who has lived well, laughed often, and loved much;Who has enjoyed the trust of pure women, the respect of intelligent men and the love of little children;Who has filled his niche and accomplished his task;Who has never lacked appreciation of Earth's beauty or failed to express it;Who has left the world better than he found it,Whether an improved poppy, a perfect poem, or a rescued soul;Who has always looked for the best in others and given them the best he had;Whose life was an inspiration;Whose memory a benediction.”
    Bessie Anderson Stanley, More Heart Throbs Volume Two in Prose and Verse Dear to the American People And by them contributed as a Supplement to the original $10,000 Prize Book HEART THROBS
  7. “The trouble with having an open mind, of course, is that people will insist on coming along and trying to put things in it.”
    Terry Pratchett, Diggers
  8. “Love all, trust a few, do wrong to none.”
    William Shakespeare, All's Well That Ends Well
  9. “The Paradoxical Commandments
    People are illogical, unreasonable, and self-centered.
    Love them anyway.
    If you do good, people will accuse you of selfish ulterior motives.
    Do good anyway.
    If you are successful, you will win false friends and true enemies.
    Succeed anyway.
    The good you do today will be forgotten tomorrow.
    Do good anyway.
    Honesty and frankness make you vulnerable.
    Be honest and frank anyway.
    The biggest men and women with the biggest ideas can be shot down by the smallest men and women with the smallest minds.
    Think big anyway.
    People favor underdogs but follow only top dogs.
    Fight for a few underdogs anyway.
    What you spend years building may be destroyed overnight.
    Build anyway.
    People really need help but may attack you if you do help them.
    Help people anyway.
    Give the world the best you have and you'll get kicked in the teeth.
    Give the world the best you have anyway.”
    Kent M. Keith, The Silent Revolution: Dynamic Leadership in the Student Council
  10. “She is too fond of books, and it has turned her brain.”
    Louisa May Alcott, Work: A Story of Experience

Monday, April 7, 2014

Five Free Student Tickets for the SaberSeminar in Boston (August 17-18, 2014)

Meredith Wills, Will Carroll and myself are donating four student two-day tickets, including lunch, for the upcoming baseball analytics Saberseminar run by Dan Brooks. This is a wonderful event, and 100% of the proceeds are donated to the Jimmy Fund. You must be a current student. Meredith and myself will by choosing four students by the end of this week, Sunday April 13, 2014.

Please note:
  • These tickets are for both days, August 17-18, 2014
  • The event is in Boston, MA
  • Lunch is included, but no other meals
  • Transportation and lodging are not included

If you would like to be considered for a donated ticket, please send:
  • Your full name (first and last)
  • If you're outside of the Boston area, how will you be getting to the event?
  • Your school affiliation and whether high school or college
  • Best contact email address (if different from reply-to address)
  • A little about your baseball interests, analytical or otherwise
  • Do you see yourself working in baseball? For a team, as a journalist, or something else?

Please email the above information to me at sabermetrics@gmail.com.

Again, please do so by the end of the day on Sunday, April 13, 2014. Once the tickets are awarded they're gone.

Monday, December 30, 2013

A Stupid and Strange Way of Looking at Sports Power Ratings that could be Smart and Useful

As I've mentioned previously, a common method used in sports for estimating game outcomes known as log5 can be written \[p = \frac{p_1 q_2}{p_1 q_2+q_1 p_2}\] where \(p_i\) is the fraction of games won by team \(i\) and \(q_i\) is the fraction of games lost by team \(i\). We're assuming that there are no ties. What's the easiest way to derive this estimate? Here's one argument. Assume team \(i\) has a probability \(p_i\) of beating an average team (a team that wins half its games). Now imagine that this means for any given game the team has some "strength" sampled from [0,1] with median \(p_i\) and that the stronger team always wins. Thus, the probability that team 1 beats team 2 is \[ p = \int_0^1 \int_0^1 \! \mathrm{Pr}(p_1 > p_2) \, \mathrm{d} p_1 \mathrm{d} p_2 .\] This looks complicated, but but with probability \(p_1\) team 1 is stronger than an average team and with probability \(p_2\) team 2 is stronger than an average team. From this perspective the log5 estimate is just the Bayesian probability that team 1 will be stronger than an average team while team 2 will be weaker than an average team, conditional on either team 1 being stronger than an average team and team 2 weaker than an average team, or team 1 weaker than an average team and team 2 stronger than an average team. In these cases it's unambiguous which team is stronger. The cases where the strength of both teams is stronger or weaker than an average team (the ambiguous cases) are thus discarded.

How could this be useful? Instead of ignoring the ambiguous outcomes when estimating the outcome probabilities under this "latent strength" model, we could instead determine which probability distributions best fit the outcome distributions for a given league! Furthermore, this allows us to cohesively put a power rating system into a Bayesian framework by assigning to each team a Bayesian prior strength distribution. These priors could either be uninformative or informative using e.g. preseason rankings.

Thursday, November 7, 2013

Building a Personal Supercomputer

It's time for a workstation upgrade; here's what I've assembled.

The massive case has plenty of space for additional drives to store the extreme amount of data that nearly every sport is now collecting together with the associated video footage. The case, power supply and motherboard allow up to 3 additional video cards to use as GPU units as your analytical needs demand (and budget can handle).
  1. Cooler Master Cosmos II - Ultra Full Tower Computer Case


    An absolutely massive case - plenty of room for an E-ATX motherboard, large power supply, multiple video cards and hard drives.

  2. PC Power & Cooling 1200W Silencer MK III Series Modular Power Supply


    An exceptionally large power supply, but platinum rated and plenty of room to spare allows it to operate nearly silenty, plus it'll handle any additional video cards you'll add later for GPU computing.

  3. ASUS Rampage IV Black Edition LGA 2011 Extended ATX Intel Motherboard


    Space for 4 video cards, 8 memory sticks (up to 64GB), superb quality and extreme tweakability.

  4. Intel i7-4930K LGA 2011 64 Technology Extended Memory CPU


    Ivy Bridge, 6 cores, exceptional ability to overclock.

  5. (2) Corsair Dominator Platinum 32GB (4x8GB) DDR3 2133 MHz


    Total of 64GB. Top-quality, you'll need your RAM in matched sets of 4 to enable quad-channel.

  6. EVGA GeForce GTX TITAN SuperClocked 6GB GDDR5 384bit


     Top-of-the-line NVIDIA Kepler card for GPU computing. 2688 CUDA cores that reach 4800 TFLOPS single-precision and 1600 TFLOPS double-precision.

  7. (2) Seagate NAS HDD 2TB SATA 6GB NCQ 64 MB Cache Bare Drive

    Solid hard drive; you'll need 2 or more drives for a RAID 10 array.

  8. Samsung Electronics 840 Pro Series 2.5-Inch 256 GB SATA 6GB/s Solid State Drive

    Small, fast SSD for quick booting and anything bottlenecked by drive read/write times.

  9. Silverstone Tek 3.5-inch to 2 x 2.5-Inch Bay Converter

    Needed to adapt the SSD to the Cosmos II case.

  10. Ubuntu Linux


     Ubuntu Linux - what else?

Sunday, September 15, 2013

The Good, the Bad and the Weird: Duels and the Gentleman's Draw

As I mentioned in the previous article "The Good, the Bad and the Weird: Duels, Truels and Utility Functions", a classic probability puzzle involves a 3-way duel (called a "truel").
A, B and C are to fight a three-cornered pistol duel. All know that A's chance of hitting his target is 0.3, C's is 0.5, and B never misses. They are to fire at their choice of target in succession in the order A, B, C, cyclically (but a hit man loses further turns and is no longer shot at) until only one man is left unit. What should A's strategy be?
There's a subtle issue involved in these types of problems in that we don't know how each participant values each outcome. If we allow duelists to deliberately miss there are \(2^3-1=7\) possible outcomes; each person may or may not be shot and at least one person will not be shot. Even if deliberate missing isn't allowed, there are still 3 possible outcomes. A, for example, could conceivably value B winning more than C winning.

The classic solution concludes that with the given hit probabilities the optimal strategy for the first trueler is to deliberately miss. My contention is that this is an incomplete solution; for some sets of utility values this may not be the first trueler's optimal strategy. Let's examine duels using utility values as the first step towards addressing truels.

Let the two duelers have hit probabilities \( p_i \) for \( i=1,2\), and also let the values each assigns to a dueling win, loss or tie be \( W_i, L_i, T_i\). I'm assuming these values are all known to both duelers and that \( W_i > T_i > L_i\). Note that a strategy that optimizes expected utility is preserved under a positive affine transformation, so under the assumption that all values are finite, we may assume \(W_i=1\) and \(L_i=0\) for all \(i\).

We'll declare the duel a "gentleman's draw" if both duelers deliberately miss in a single round. Let the expected utility value for dueler \(i\) be \(U_i\).

Trivially, if the optimal strategy for dueler 1 is trying for a hit, the optimal strategy for dueler 2 must be to also try for a hit. Conversely, the optimal strategy for dueler 1 can be to deliberately miss if and only if the optimal strategy for dueler 2 is also to deliberately miss. Assume the draw is taken if there's indifference (they are, after all, gentlemen).

If dueler 1 deliberately misses, dueler 2 has two choices. If he deliberately misses, it's a gentleman's draw and \(U_2 = T_2\); if he tries for a hit, both duelers will subsequently try to hit each other and \(U_2 = p_2 + q_2 q_1 U_2 \). Solving, we get \[U_2 = \frac{p_2}{1-q_1 q_2}.\] It's therefore optimal for dueler 2 to take the gentleman's draw if and only if \[T_2 \geq \frac{p_2}{1-q_1 q_2}.\] As a consequence, dueler 1 will not deliberately miss if \[T_2 < \frac{p_2}{1-q_1 q_2}.\] If dueler 1 tries for a hit, both will subsequently try to hit each other and we have \( U_1 = p_1 + q_1 q_2 U_1\). Solving, we get \[ U_1 = \frac{p_1}{1-q_1 q_2}.\] Thus, the optimal strategy for dueler 1 is to deliberately miss if and only if \[ T_1 \geq \frac{p_1}{1-q_1 q_2}\] and \[T_2 \geq \frac{p_2}{1-q_1 q_2}.\] These are, as expected, precisely the conditions under which dueler 2 will deliberately miss.

For example, if \(p_1=p_2=1/2\), it'll be a gentleman's draw if and only if \(T_1,T_2 \geq 2/3\). Paradoxically, both will fire under these hit probabilities if \( T_1 = 4/5 \) and \( T_2 = 1/2 \), even though this results in lower expected utility for both duelers than if they had agreed to a draw. This is a type of prisoner's dilemma.

Sunday, August 11, 2013

A Man, a Plan, a Cat, a Canal - Panama!

A man, a plan, a cat, a master, a minae, a lunula, a tora, a vela, a cola, a belga, a tola, an uta, a dona, a tiara, an aura, a kata, a mana, a nipa, a cabana, a law, a harem, a taces, a liard, a gnat, a mut, a dawed, a bura, a nim, a levator, an eh, a trams, a sall, a vacates, an up, a garb, a keets, a serin, a sored, a patamar, a gater, a lees, a strep, a lama, a pat, a lame, a haded, a wag, a naan, a kalian, a fer, a yaws, a remit, a keep, a loom, a neep, a ha, an ai, a retailor, a cabals, a subah, a slits, a pated, a callet, a xu, a faena, a tups, a sati, a rapider, a reps, a rapid, a korat, a dens, a sled, a tical, a pipages, a rats, a seeks, a defi, a wasts, a peracid, a nomas, a rosarian, a bran, a nonet, a gama, a sac, a scrota, a lab, a cain, an aid, a statin, a reel, a tiff, a haj, a talas, a nares, a mares, a laics, an allot, a til, an arena, a nits, a palace, a fanum, a yarer, a daub, a basts, a masas, a called, a slay, a galoots, a senega, a ton, a span, a mum, a dracaenas, a coda, a must, a satis, a lion, a yob, a reknit, a dessert, a lex, an aver, a red, a fab, a katas, a deet, a diaper, a nos, a snips, a spot, a fed, a wap, a past, a galax, an apos, a zaps, a lat, a rai, a resale, a tallit, a boob, a hag, a fayed, a sports, a loof, a ragg, a sashay, an agar, a selah, a spit, a brad, a strap, a wolf, a reified, a navar, a cases, a bedaub, a tassels, a gaes, a runaway, an amahs, a burg, a sorter, a del, a basely, a kae, an evades, a lader, a waved, a spirts, a pas, a slam, a hasps, a nalas, a snog, a cedar, an ulama, a lasagnas, a leud, a poh, a larum, a si, a retained, a pay, a pit, a raps, a repots, a sell, a datums, a yard, a hey, a terces, a prod, a skips, a gip, a lin, a sib, a lac, a jaded, a later, a beef, a sallet, a panicum, a gnar, a pall, a gas, a rotator, a tamis, a gel, a snawed, a decaf, a pol, a jawans, a dual, a gateman, a tins, a ran, a riff, a za, a minim, a get, a bard, a spud, a sum, a stem, a rases, a tsar, a lobate, a hasp, a hwan, a lotahs, an agas, a pad, a reed, a slim, an attar, a steels, a medina, a gar, a tub, an asarum, a pows, an ava, a mib, a map, a stab, a rasp, a tala, a nadir, a seton, a stoped, a repoll, a waste, a hades, a ragi, a tsades, a bap, a rain, a ratels, a hasten, a gid, a snot, a basal, a vinas, an upas, a nonacid, a naval, a lahar, a sonar, a lovat, a wares, a bal, a ripsaw, a jatos, a sup, a sh, a haed, a hailed, a moor, a vaned, a delf, a revel, a tan, a meter, a sob, an evil, a deific, a peracids, an ass, a bait, a buran, a far, a lamas, a robalo, a gaum, a sha, an arak, a macer, a macs, a snub, a stirps, a deffer, a perp, a naw, a jar, a vain, a ban, a miladi, a rasps, a wallop, a rex, a waney, a rase, a caird, a patrons, a tun, a stob, a japans, a maws, an awa, a con, a spoons, a fir, a stroma, a mil, a keen, a lace, a canon, an allod, a spay, a ten, a kop, a yah, a regal, a modal, a dinar, a madame, a hallahs, a dor, a repel, a reflet, a noma, a gen, a fast, a waggon, a dewan, a recap, a wort, a pin, a sung, a bag, a sos, a tepal, an abash, an ami, a manias, a pees, a diols, a repp, a taxed, a deb, a spans, a reman, a reward, a poons, a smug, a now, a teff, a hakeem, a seem, a rami, a simaruba, a ness, a cadets, a teraohm, a knob, a sewan, a seven, an oot, a skeets, a demur, a lanai, an unassuaged, a stared, a seam, a meed, a naos, a bus, a wad, a xis, a hon, a dan, a snail, a kayak, a looter, a gob, a men, a sorb, an inner, an oxen, an emes, a seder, a reknits, a loid, a saw, a pint, a castes, a stop, a debut, a tows, a tog, a kips, a rep, a cask, a yam, a minareted, a reflow, a laced, a bun, a keels, an ort, an assent, a faun, a reign, a manat, a rakus, a lade, a dater, a minarets, a nay, a fanos, a matt, an arhat, a tram, a tel, a vat, a ba, a pal, a pager, a tarps, a plug, a nod, a rash, a rotas, a ramal, a butane, a galiot, a paws, a pals, a stressed, a derat, an um, a mac, a sri, a mas, a lagan, an ajar, a laid, a big, a lass, a vara, a mail, a sikas, a yawl, an add, a simas, a romano, a kalam, a tannin, a less, a tater, a carer, a pasts, a caseic, a papayas, a salal, a haffits, a snivel, an atlas, a bases, a macaber, a tress, an alerts, a water, an imaginer, a pec, a golf, a pupils, a gnaws, a mos, a la, a baklawa, a gan, a stums, a step, an ikat, a keel, a dot, a loll, a tares, a renamed, a nanas, a sematic, a tap, a zareeba, a mob, an ales, a lox, a tass, a matsah, a ports, a names, a batik, a secs, a fane, a haleru, a lasts, a fats, a valley, a spam, a spools, a saner, an aspis, a hun, a stops, a tots, a tils, a gamely, a put, a las, a vaw, a ranid, a ham, an ataps, a barca, a gig, a strow, a struts, a speed, a draw, an axon, a gaga, a birr, an agnail, a pow, a tuber, a teel, a rip, a tail, a tatar, a hay, a ray, a lall, a barege, a janitor, a caff, an auk, a hah, an areic, a raster, a casks, a basil, a bubal, a donas, a bananas, a lobar, a lades, a cadi, a caw, a tad, an ogam, a janes, a sirup, a cram, a lets, a passus, a nuts, a muton, a cyma, a mix, a madam, a let, a corban, a partan, a melanin, a top, a wot, a bad, a bows, a resod, a nae, a parol, a vastness, an anime, a hares, a rax, a lam, a tabbis, a bins, a liar, a straw, a pant, a cares, a papa, a res, a sass, a mattes, a nopal, a daff, a yapon, a toped, an ivy, a maven, a ganef, a sovran, a gorp, a divan, a dexes, a moot, a prat, a nips, a redips, a mood, a sabir, a zarebas, a shales, a nett, a papal, a japan, a swots, a seral, a sip, a tarots, a path, a baseness, a callan, a drib, a nairu, a salep, a last, a babuls, a kiths, an orc, a daps, a galoot, a stink, a sail, an ameer, a haslets, a pats, a medal, a ganof, a dim, an atoll, a hall, a feral, a robalos, a sin, a radioed, a cycases, a kuna, an as, an arepa, a ki, a haps, an asks, a mair, a saloops, a vug, a stang, a tophs, a dak, a yay, a serac, a vav, a lap, a gad, a laden, a manioc, a fin, a dub, a loons, a teemer, a sris, a soar, a matador, a saros, a vavassor, a kayos, a setal, a maid, a waw, a palet, a rayon, a solon, a dine, a rumaki, a hae, a gaff, a lipases, a ladder, a stub, an akees, a seller, a manats, a barytas, a lied, a nona, a mars, an ait, a suber, a cimex, a tau, a vail, a grana, a pan, a sums, a ramadas, a rood, a teels, a muts, a torr, a paeon, a sow, an alfa, a rob, a mures, a toper, a rerun, a mall, a canoe, an apart, a seer, a saps, a wait, a laxer, a cats, a manor, a baton, a tag, a strown, a fax, a wab, a jauk, a racial, a lev, a gasser, a careens, a swat, a rein, a wanigan, a tenner, a flora, a rolf, a rennet, an agin, a wanier, a taws, a sneer, a caress, a gavel, a laic, a raku, a jab, a wax, a fanworts, a gat, a not, a baron, a mast, a carex, a lati, a wasp, a sarees, a trap, an aeon, a call, a manurer, a repot, a serum, a bora, a flan, a wos, an oe, a parrot, a stum, a sleet, a door, a sad, a marasmus, a napa, an argali, a vau, a taxemic, a rebus, a ti, an asrama, an on, a deil, a satyr, a bast, an amarelles, a seek, an abuts, a redd, a lases, a pilaff, a gae, a haik, a muraenid, a nolos, an oy, a ratel, a paw, a wadi, a malates, a soy, a kaross, a vavasor, a sarod, a tamaraos, a sirs, a remeet, a snool, a bud, an if, a coin, a maned, a lad, a gap, a lav, a vac, a resay, a yak, a dashpot, a gnats, a guv, a spool, a sari, a masks, an asp, a haika, a per, an asana, an ukases, a cycadeoid, a ranis, a sol, a boral, a refall, a hallot, an amid, a fon, a gal, a demast, a pastels, a hareem, an alias, a knits, a tool, a gasp, a dacron, a shtik, a slub, a bats, a lapel, a saurian, a bird, an all, a cassenes, a baht, a pastor, a tapis, a lares, a stows, a nap, a jalap, a patten, a selahs, a saber, a zaribas, a doom, a spider, a spin, a tarp, a toom, a sexed, an avid, a prog, an arvos, a fen, a ganev, a mayvin, a depot, an op, a yaff, a dalapon, a sett, a massas, a sera, a pap, a ser, a catnap, a warts, a rail, a snib, a sibb, a tam, a lax, a raser, a haemin, an assents, a valor, a paean, a doser, a swob, a dab, a tow, a pot, an in, a leman, a trapan, a brocatel, a mad, a maxima, a myc, a notum, a stun, a suss, a pastel, a marc, a puris, a sen, a jam, a gonad, a taw, a caid, a cased, a lar, a bolas, an anabas, a nodal, a bubalis, a basks, a carets, a racier, a nah, a haku, a naff, a carotin, a jaeger, a ball, a lay, a rayah, a rat, a tali, a tapir, a leet, a rebut, a wop, a liang, an arriba, a gag, an ox, an award, a deeps, a sturts, a worts, a giga, a crab, a spat, an amah, a din, a raw, a vasal, a tup, a ylem, a gaslit, a stot, a spots, an uh, a sips, an arenas, a sloops, a maps, a yell, a vast, a fasts, a laurel, a haen, a fasces, a kit, a baseman, a strop, a hast, a mass, a taxol, a sel, an aboma, a beer, a zap, a tacit, a mesas, an anadem, an eraser, a tallol, a tod, a leek, a takin, a pets, a smuts, an aga, a walk, a baal, a som, a swang, a slipup, a flog, a cep, a renig, a minaret, a wastrel, an assert, a reb, a camases, a basalt, an alevins, a stiff, a halalas, a say, a papacies, a casts, a parer, a caret, a tassel, an inn, a tamal, a kaon, a moras, a misadd, an alway, a sakis, a li, a maar, a vassal, a gib, a dial, a raj, a nan, a galas, a mairs, a cam, a mun, a tared, a desserts, a slap, a swap, a toil, a gaen, a tubal, a maras, a torahs, a radon, a gulp, a sprat, a reg, a palapa, a bat, a valet, a mart, a tahr, an att, a mason, a fay, an aster, an imaret, a daedal, a suk, a ratan, a mangier, a nu, a fatness, a natron, a sleek, a nub, a decal, a wolfer, a deter, an imam, a yaks, a caper, a spik, a got, a swot, a tubed, a pots, a sets, a catnip, a was, a diol, a stinker, a redes, a semen, an exon, a rennin, a bros, an em, a bog, a retool, a kay, a kalians, an ad, a noh, a six, a daw, a sub, a so, an adeem, a maes, a derats, a degauss, an unai, an alarumed, a steeks, a toon, a neves, an awes, a bonk, a mho, a retasted, a cassena, a bur, a misaim, a ramees, a meek, a haffet, a won, a gums, a snoop, a drawer, a namer, a snaps, a bed, a dex, a tapper, a sloid, a seep, a sain, a maim, an ahs, a banal, a petasos, a gab, a gnus, a nip, a trow, a pacer, an awed, a nogg, a wats, a fanega, a mon, a telfer, a leper, a rod, a shall, a haem, a damar, a nidal, a domal, a gerah, a yapok, a net, a yaps, a doll, an anon, a caecal, an eek, a lima, a morts, a rif, a snoops, an oca, a wan, a swam, a snap, a jabots, a nut, a snort, a padri, a caesar, a yen, a waxer, a poll, a wasps, a raid, a liman, a bani, a var, a jawan, a prep, a reffed, a sprits, a buns, a scam, a rec, a makar, an aahs, a mu, a gaol, a boras, a malar, a fan, a rubati, a bass, an asdic, a repacified, a liven, a bos, a retem, an at, a lever, a fled, a den, a varoom, a deli, a hade, a hahs, a pus, a sot, a jaw, a spiral, a baser, a wat, a volar, an osar, a halal, a vanadic, a nonas, a punas, a nival, a sabatons, a dig, a nets, a haslet, a rani, a rap, a based, a staig, a rased, a haets, a walloper, a depots, a notes, a rid, an aal, a taps, a rabats, a pam, a bima, a van, a swop, a muras, an abut, a raga, an idem, a sleets, a rattan, a mils, a deer, a dap, a sag, an ash, a tolan, a whaps, a haet, a bolar, a stases, a ramets, a mus, a dups, a drab, a teg, a minima, a zaffir, an ar, a snit, a nametag, a laud, a snaw, a jalop, a faced, a dewans, a leg, a sim, a tarot, a toras, a gall, a parang, a mucin, a patellas, a feeb, a ret, a laded, a jacal, a bis, a nil, a pig, a spiks, a dorp, a secret, a yeh, a dray, a smut, a dalles, a stoper, a spar, a tip, a yap, a deni, a terais, a mural, a hop, a duel, a sang, a salaam, a lunar, a decagons, a sal, an asps, a hamals, a sap, a strips, a dev, a wared, a lased, a venae, a kayles, a baled, a retros, a grub, a shaman, a yaw, an urase, a gasless, a tabu, a debases, a caravan, a deifier, a flow, a parts, a darb, a tips, a hales, a rag, an ayahs, a saggar, a fool, a strops, a dey, a fag, a haboob, a till, a tael, a serai, a ratal, a spaz, a sop, an axal, a gats, a papaw, a def, a tops, a spins, a son, a repaid, a teed, a sat, a kab, a fader, a rev, an axel, a tressed, a tinker, a boy, a noil, a sit, a satsuma, a doc, a sane, a cardamum, a naps, a nota, a genes, a stool, a gayals, a dell, a casas, a masts, a babu, a darer, a yamun, a faecal, a pastina, an er, an alit, a toll, an asci, a laser, a maser, a nasal, a taj, a haffit, a leer, a nit, a tsadi, an ani, a cabala, a torcs, a casa, a mag, a tenon, an arb, an air, a soras, a monadic, a repasts, a waifed, a skees, a star, a seg, a pipal, a citadels, a sned, a tarok, a dip, a rasper, a redip, a raitas, a sputa, a ne, a faux, a tell, a cadet, a pastils, a habus, a slab, a caroli, a terai, an aah, a peen, a mool, a peek, a timer, a sway, a ref, a nail, a kana, a nag, a waded, a haemal, a tapa, a malaperts, a seel, a retag, a ram, a tapaderos, an ires, a steek, a brag, a pun, a set, a cavallas, a smart, a hen, a rot, a velamina, a rub, a dew, a datum, a tang, a drail, a sec, a tamer, a hawala, an abaca, a pina, an ama, a taka, a ruana, a raita, an oda, a tuna, a lota, a gleba, a loca, a leva, a rota, a lunulae, an imarets, a mat, a canal - Panama!

Saturday, August 10, 2013

The Good, the Bad and the Weird: Duels, Truels and Utility Functions

In the excellent (and highly recommended) book "Fifty Challenging Problems in Probability with Solution", Frederick Mosteller poses "The Three-Cornered Duel":
A, B and C are to fight a three-cornered pistol duel. All know that A's chance of hitting his target is 0.3, C's is 0.5, and B never misses. They are to fire at their choice of target in succession in the order A, B, C, cyclically (but a hit man loses further turns and is no longer shot at) until only one man is left unit. What should A's strategy be?
This is problem 20 in Mosteller's book, and it also appears (with an almost identical solution) in Larsen & Marx "An Introduction to Probability and Its Applications".

Mosteller's solution:
A is naturally not feeling cheery about this enterprise. Having the first shot he sees that, if he hits C, B will then surely hit him, and so he is not going to shoot at C. If he shoots at B and misses him, then B clearly shoots the more dangerous C first, and A gets one shot at B with probability 0.3 of succeeding. If he misses this time, the less said the better. On the other hand, suppose A hits B.  Then C and A shoot alternately until one hits. A's chance of winning is \( (.5)(.3) + (.5)^2(.7)(.3) + (.5)^3(.7)^2(.3) + \ldots\) . Each term corresponds to a sequence of misses by both C and A ending with a final hit by A. Summing the geometric series we get ... \(3/13 < 3/10\). Thus hitting B and finishing off with C has less probability of winning for A than just missing the first shot. So A fires his first shot into the ground and then tries to hit B with his next shot. C is out of luck.
Is this right? What if B were to follow A's example and fire into the ground? What if all three were to keep firing into the ground? That this type of an outcome isn't unreasonable for certain sets of shot accuracy probabilities can be illustrated by considering the case where A's accuracy is 0.98, B's accuracy is 1.0 and C's accuracy is 0.99. Mosteller's argument is equally applicable in this case, but if B shoots C after A deliberately misses he'll be shot by A with probability 0.98. Is that reasonable?

Under the assumption that deliberately missing is allowed, there are \(2^3-1=7\) possible outcomes - each participant can be shot or not shot, and there must be at least one participant not shot. The lack of clarity for what the ideal strategies are for A, B and C in the general case arises from the utility of 2- or 3-way ties to each of the participants being undefined.

In the next article I'll analyze 2-way duels where deliberate missing is allowed by using such fully-defined utility functions. These results will be used in a third article on 3-way duels (truels); in particular, I'll re-examine Mosteller's solution.