Browse Month

January 2017

Perverse Incentives

gametheory

I do watch a couple of Let’s Plays on YouTube, and one game that a couple of channels have been playing is Trivia Murder Party from the Jackbox Party Pack. I’ve found the format to be interesting and relatively well-designed for building tension, though there are a few weird edge cases because of how the rules are laid out.

The final round has rules as follows:

  • One player is in the lead (the player with the fewest number of spaces left to the finish line).
  • Players are presented with a category, and need to decide if objects presented fit that category or not. The player in the lead has two objects; other players have three (this is a rubberbanding measure used to encourage them to catch up).
  • For example, a category could be “Asian Countries” with objects Russia, Shanghai and the USA. In this case players should only select Russia (Shanghai is a city, and the USA is in North America).
  • For each object correctly classified, players advance one space on the board. No penalties are issued for objects that were incorrectly classified.
  • The player with the lead moves first. If he is across the finish line, he wins (independent of what non-leading players do).
  • In the event of a tie, the highest ranked player (based on the previous rounds) who is not in the lead takes the lead. Furthermore, all tying players apart from the new leader (including the old leader, if relevant) move back 1 space.

One strategy of playing the final round, and an arguably sensible one is to always try and answer the questions to the best of one’s ability. Yet, the aforementioned rubberbanding mechanism means this isn’t always optimal – suppose you’re playing against an incredibly knowledgeable opponent who implements the maximising strategy. Furthermore, suppose you’re in the lead, with 5 spaces to go before finishing, while your opponent has 7. Then, consider:

  • If you advance 2 spaces, you’ll have 3 spaces left to go whilst your opponent has 4. Then, no matter what you do, your opponent will take the lead on your next turn, and you’ll lose.
  • If you advance 1 space and your opponent advances 3, you’ll both be at 4 spaces to go. Because of the tie rule, he leads and you get pushed back one space. This brings you to (5, 4). Now, as a non-leader advance 3 spaces; no matter what happens you retake the lead. Finally, advance 2 spaces and win.

We can generalise this to solve the two-player case, by considering what is a winning position – in the case where both players have very strong trivia knowledge, but the opponent always advances the maximum number of spaces.

  • (1, n), n \geq 2 is clearly a winning position. Simply advance and exit.
  • (2, n), n \neq 1 is also winning for the same reasons (and (2, 1) is losing).
  • (3, n) is a bit more interesting. n \leq 2 is clearly lost. But (3, 4) is actually lost too, because that becomes (2, 1) or (3, 1) after one turn, both of which are losing positions.  (3, n), n \geq 5 and greater are won; advance to (1, n-3) and win.

Having considered a few cases, we can use what’s called induction to determine the rest of the winning positions. What this means is that we are defining winning positions in terms of whether other positions are winning. This can be dangerous if we produce circular definitions, but the relationships we use here are well-founded in that we maintain that the total number of spaces left to go for both players always decreases, for each of the sub-problems we look at.

We thus say that a position (p, q) is winning, if and only if any of the following are true:

  • p = 1, or p = 2, q \neq 1.
  • p > q + 1 and at least one of (p-3, q-2), (p-2, q-2) and (p-1, q-2) is winning.
  • p = q + 1 and at least one of (p-3, q-1), (p-2, q-2) and (p-1, q-2) is winning.
  • p = q - 1 and at least one of (p-1, q-3) and (p, q-3) is winning.
  • p = q - 2 and at least one of (p-2, q-3) and (p, q - 3) is winning.
  • p = q - 3 and at least one of (p-2, q-3), (p-1, q-3) and (p + 1, q-3) is winning.

We can derive a similar inductive rule for cases where one always maximises the number of answers: for each of the “at least one of” choices, always pick the first option. We can then consider when the (probably) “intended” strategy of trying to answer to the best of one’s knowledge fails to be optimal. In terms of implementation, the inductive definition above swiftly lends itself to a dynamic-programming implementation, whether “top-down” or “bottom-up”.

I’ve only considered the 2 player case because it’s relatively simple to analyse… things get substantially more complex once we go beyond that, especially factoring in the tiebreaking rules based on first-round performance. In practice, given that the questions can be difficult and unpredictable, at least for me it would probably be too risky to try to take a dive like this – but I can see this becoming relevant if expert players played this.

Sets of Sets

If I’m asked to think of a real-life example of a set of sets, I think the first example I would come up with was about job lots of items being sold. Interestingly, it actually took a while – the ideas I came up with before that, which were companies I have investments in (note: mutual funds and ETFs own sets of companies), or messages to my friends were really unions of multiple sets.

How would we model a set of sets in Java? Well, that’s not too hard, since a Set is a type after all:

Set<Set<Item>> items = Sets.newHashSet();
Set<Item> thingsBeingSold = Sets.newHashSet();
thingsBeingSold.add(Item.create("1 oz. Gold", 123456));
thingsBeingSold.add(Item.create("1 oz. Silver", 3456));
items.add(thingsBeingSold);

That said, we’ve got to be careful. If we continue the above with this:

Set<Set<Item>> items = Sets.newHashSet();
Set<Item> thingsBeingSold = Sets.newHashSet();
thingsBeingSold.add(Item.create("1 oz. Gold", 123456));
thingsBeingSold.add(Item.create("1 oz. Silver", 3456));
items.add(thingsBeingSold);
thingsBeingSold.add(Item.create("a chopstick", 20));
items.contains(thingsBeingSold);
items.stream().anyMatch(x -> x.equals(items));
items.stream().anyMatch(x -> x == items);

What should the output of lines 7, 8 and 9 be? Are they equivalent, even? Well, there are some possible arguments in each direction:

  • They should return true, because the reference to the set thingsBeingSold is still there.
  • They should return false, because the value of thingsBeingSold isn’t the same as the value inserted.

I would argue that the first point is stronger, and would have been my answer when I first learnt about Java. However, the actual answer is that lines 8 and 9 should return true while line 7 generally returns false, though there are a few special cases:

  • It will return true if thingsBeingSold.hashCode() before line 6 has the same hash as thingsBeingSold.hashCode() after line 6 i.e. there is a hash collision, or
  • if the Item created in line 6 equals either of the Items created in lines 3 and 4 (unlikely).

The operation of line 8 is relatively simple: we check each element in the set to see if it is equal, and assuming our set’s equals() method does what it’s supposed to do we will always find the match. We can potentially improve on this with parallelStream(). Line 9 does a reference-equality check on the elements instead and would probably be faster as we don’t have to actually inspect the set contents. In this case, it’s also going to be true. However, these are linear time operations, at least. The point of using hash-based structures here, among other things, would be to knock the time complexity of lookups down to amortised constant.

In a sense, we find the object only if we fortuitously (!) happen to be looking for the same hash code. Java HashSets effectively are a key-set based view of a HashMap, and when we look up objects we actually investigate them by their hashes first, only bothering to check the values if we have a match on the hashes. This allows for some fairly interesting optimisations, actually; I previously thought that HashMaps use buckets and store an array of linked lists of mappings + information, resizing appropriately when the ratio of elements to buckets exceeded a load factor. This was correct up to Java 7, but in Java 8 it appears there’s a fun new optimisation that builds red-black trees sorted by hash codes (while objects themselves might not be Comparable, their hashes are ints, which certainly are) if some buckets get too large relative to others in an attempt to cut the worst-case complexity from linear to logarithmic. Still, when we inspect nodes, we look at their hashes first.

Note that this isn’t just a problem with HashSets; you can get into similar debacles with TreeSets, because the underlying red-black trees aren’t going to reorder themselves. In general, the Javadoc for Set does warn you that mutable objects shouldn’t be changed in ways that would affect their equals() method after they’ve been put into a set. HashSet and TreeSet are allowed to behave the way they do because of subsequent invariants between equals() and hashCode(), and comparison-based sets are supposed to use comparators that are consistent with equals() i.e. a.equals(b) iff a.compareTo(b) == 0.

One way to get round this is of course to ensure that the types used in these sets are immutable, or at least the parts that are used in equals() and related methods are immutable. If that’s infeasible, a good solution could be to delete the set that is to be changed from the set, and add it back after changes; add is idempotent and so the set will (correctly) stay as a set. Wiring this up seems rather messy, though; it looks like we need to listen for state changes (so some kind of publish/subscribe mechanism), where the objects being stored publish both their old and new state so that we can modify the set accordingly.

A Software Engineer’s Perspective on Shenzhen I/O

I had some opportunity to have a bit of a break over the Christmas and new year period, and James recommended this title to me about a month ago or so, so I thought I’d give it a shot. It’s essentially a kind of competitive hardware programming game – you’re given a task to complete, and the challenge is to build a circuit exhibiting the specified behaviour. Of course, in practice this is wrapped in a pretty fun if frivolous story. To do this, you have to arrange various components on a circuit board, such as microcontrollers (which allow some form of assembly programming), bridges, logic gates, etc. The verification interface (pictured in the screenshot) definitely reminds me of Quartus II.

I did some x86-64 assembly programming during my first year at Imperial, and thus initially hit a bit of a snag (I kept typing in commas between operands, for a bit wondered why cmp, jne or shl weren’t valid commands, and also tried to perform arithmetic operations with both source and destination registers – you have to use an accumulator). It didn’t take too long to figure things out, though.

I’d say the first puzzle which got tricky was this one (there was an earlier one on using a greedy algorithm for coin change which might have been a bit tricky too):

  1. You will receive a signal on a non-blocking IO channel that consists of three packets. The first indicates the location to which you must move a robot using a motor, the second indicates the number of pulses to clean the plants at that location (?) and the third indicates the number of pulses to spray them with nutrition.
  2. To control the robot, you have to use its motor. Fire a signal of 100 for one pulse and then pull back to 50 to move the robot forward (increasing numbers); fire a signal of 0 for one pulse and then pull back to 50 to move it backward (decreasing).
  3. The clean and feed steps must be done for precisely the correct number of cycles.
  4. (Implicit) You may assume that there’s no overlap in signals (i.e. the robot will always have finished its feed steps before it gets another packet).

To add to the challenge, the microcontrollers have limited amounts of memory, and thus our programs have to be pretty short. As tasks grow more complex, we need to break them down into smaller pieces; we then end up needing to define protocols between the components. For example, for the above problem, the workflow is as follows:

  1. The “main” (first) module, upon receiving a packet, dispatches the target location to the second module and then blocks until said second module has sent a signal back.
  2. The second module compares the robot’s current and target locations, and submits commands to a third module (the one in the top right hand corner) to drive the robot to the target.
  3. The third module simply drives the motor to move the robot one step forward on a 0 input, and back on any other input.
  4. Once the robot is in the right location, the second module signals back to the first, unblocking it.
  5. The first module reads the rest of the packet and executes the clean and feed steps appropriately.

While this is of course different from what most software engineers will be doing in practice, I think it is not unreasonable to use this as part of teaching computer architecture and/or assembly (hello first-year Imperial students!). I think the game does teach a couple of useful ideas.

  1. Abstraction. This becomes critical for some of the larger problems. Quite a number of the tasks I’ve completed so far have involved developing protocols that use message passing between two or three modules.
  2. Optimisation can be painful. Most of the time the cleanest factoring is not going to give you the best score, to say the least; I think most users will experience some pain rewriting assembly to fit in fewer lines and/or run with fewer instructions.
  3. Complex conditional structures and gotos. You can use jumps, but those tend to be expensive; it thus becomes pretty common to use nested tests (teq, for example, checks if its two operands have equal value). Tests set a three-valued flag; instructions can be preceded by “+” or “-” to be run only if the flag is set to true or false respectively. Rather nastily, the flag can be set to neither as well (there is a tcp instruction that indeed writes the three-valued output to the flag!)
  4. A reminder to consider edge cases. For the Coin Change circuit, the test cases did include a case with exact change, as well as a case where only the largest coins were needed. I’m not sure if the robot test cases included anything too sneaky beyond no movement being required.

Highly recommended; in addition to all the fiddly circuitry there’s also a pretty cool card game that’s a strange hybrid of FreeCell and Spider Solitaire. I’d give this a 9 out of 10, easily. That said, I think people with no prior programming experience would find the learning curve very steep. The game does pretty well at introducing some useful constructs via suitably contrived tasks (there was one on the ROM module, one on the I/O expander, and one about using the digits of an integer as flags) to help mitigate that, though.

An Unexpected Economic Computation

Here’s a calculation that I found pretty surprising. Have a guess as to its meaning:

\dfrac{\left( \dfrac{60}{(24-15)} \times 2.40 \right)}{1 - (0.4 + 0.02)} \approx 27.59

If you guessed something relating to savings, you’d be on the right track; the denominator would probably have clued you in to something along those lines, since the 0.4 + 0.02 is the marginal tax that higher rate earners in the UK would face (as of the 2016/17 tax year). You might have figured out then, that the fraction on top probably refers to some form of a time savings expressed in minutes. The 2.40 is probably a bit more puzzling especially if you’re not from London; from the previous observations it’s the cost of taking some convenience that saves nine minutes. That’s right; you might recognise that as the price of a single-trip Tube fare.

Putting that together, that computation is actually the effective hourly gross rate I’m being paid to walk to my office as opposed to taking the Tube. Specifically, I’m comparing (a) taking the Tube, which takes about 15 minutes plus a single trip fare of 2.40, and (b) walking, which takes 24 minutes. We’re thus looking at a net rate of 2.40/9 minutes. Of course, I pay for the Tube using post tax money, so we need to factor that in, and to get an hourly rate we scale that linearly.

Now of course this doesn’t mean I’ll never take the Tube to work again, or even that I’ll take it much less often – the 9 minute difference can be important (say there’s a high priority issue going on, or I’m about to be late for a meeting), and walking can be pretty unpleasant (if I’m very tired, it’s late, or it’s too cold; that said, I’ve done this in the current ~0 degree weather and found it fine, at least). Probably, doing this in the mornings would generally be more reasonable and sustainable as I’m pretty tired by the end of the day. Saving one trip even occasionally is enough of a win, I’d say, and getting some time to clear my head in the mornings is probably not too bad as well.

A question could be why I don’t use a Travelcard for the computations instead. The weekly one for zones 1-2 costs 33 and since I largely stay within zone 1 and 2 we can assume that that’s all I’ll need (I’ll ignore the odd trip to Heathrow). I think 16 or 17 is probably about the number of rides I’d take in a week if I used it aggressively (two a day, maybe three or four on the weekends). We can re-run the numbers with \frac{33}{16.5}, which means a trip costs 2.00. Our final answer is 22.99 which is still pretty solid (if you work 42 hours a week that’s a gross annual income of just over 50,000). Anyway, as it turns out because I use contactless, if I happen to have a week where I do travel a lot I’ll effectively be using one.

Now let’s have a look at the monthly or annual tickets. These cost 126.80 for monthly, or 1,320 for annual. Assuming that we make 2.357 trips a day on average (taking the middle of the estimates above), and a month as 365.25/12 days, with the monthly card the cost of a trip falls to 1.767 and with the annual card it falls to 1.533. The “gross wage” calculations become 20.31 and 17.62, which while not as high are still solid amounts. 17.62 an hour corresponds to about just over 38,000 in gross income assuming a 42 hour week, which would put you in about the 78th percentile of earners according to the ONS data for 2013-2014. I guess this will probably be a bit lower now, with inflation/wage growth, but still decent.

Assuming usage is high, it seems that the annual card might be the way to go. However, an issue is that I sometimes need to travel overseas for work potentially a fair chunk (let’s say personal plus work travel adds up to two months a year), so the annual one is quite definitely a non-starter. Multiply the price of a trip by 6/5 to factor that in, and you end up with a per-trip figure that’s higher than the monthly card. I have been getting the monthly card in the past, especially when I was a student and it only cost 86.50, partly because walking to Imperial was going to take a very long time (that route yields savings more on the order of 30 minutes). Note that while losing a card is a legitimate concern, you can usually recover the travel passes using the TfL website.

(N.B. This idea was conceived independent of the currently ongoing Tube strike, though in a sense it’s a bit of a bonus that things aren’t affected.)