Author Archives: david

Turning deterministic strategy games into nondeterministic games of voting

I posted yesterday about using classic deterministic strategy games like Reversi (aka Othello) as a test bed for voting systems. The problem is that the experiment I described is actually quite hard to coordinate.

After some refinement of the idea I came up with the following randomization strategy for producing a game that, over enough runs, will produce something not totally dissimilar from this experiment.

The initial idea is to use a voting mechanism which can be repurposed into a variety of systems. I don’t know if this system has a name. I refer to it as gin ranking for historical reasons (I initially started using it on types of gin for a blind taste testing). It’s very simple: You first assign grades to everything, you then put the items in each grade in a strict order of preference.

This can then be turned into a vote in a variety of ways because it provides both grades and a strict ordering of the candidates: You can use a condorcet system, you can use approval voting on anything >= a certain grade, you can use range voting, you can use majority judgement, etc. So we don’t have to decide just yet what voting system we’re going to use (more on this later).

But we can also use this ranking in a single player game. Here is how you play Randomized Ranked Reversi:

It’s played on a normal reversi board with the normal reversi rules. All that is changed is that you may be started in an arbitrary board position and the way you make your move.

Your turn consists of being presented with a list of options for moves. I still don’t have a good sense of whether providing the list of all possible moves will be an overwhelming number. If is, you get presented a random subset.

You gin rank this set of moves. A move is then randomly selected based on your rankings. The exact mechanism doesn’t matter terrible – all that matters is that if you ranked A better than B you should be more likely to get A, and if you graded A better than B you should be significantly more likely to get it.

Your opponent can either be an AI or another player. For our purposes it will be an AI.

This gives a strong incentive to get your vote correct in all the particulars – ranking something well makes it likely to be picked, ranking something badly makes it less likely, and your grades then influence those probabilities even more strongly.

How do we use this game to run the previous experiment?

Well, the idea is we make a slight simplification and ignore history. All we care about is a board position (including whose turn it is) and the votes by users on moves from that position. So every play of the random game is a contributing a vote.

At any given time we have a population of people playing the game and a set of board positions we’re interested in the answer to. The goal is to get a minimum number of votes on each interesting board position.

When a new player starts they are given a random board position that we are currently interested in gathering more votes for. They then play randomized ranked reversi against an opponent who behaves as follows:

  1. If there’s a move I could make that would put the player in a board position I’m currently interested, make that. If there is more than one, pick the one which currently has the most data already gathered
  2. If there are existing votes for my position, pick one at random (preferring ones in which the player won) and run the RRR algorithm to pick a move from that
  3. Fall back to some fairly dumb AI. Might even just pick a move at random

We can now use this to answer the experiment I previously proposed, as long as you restrict yourself to voting strategies that can be applied to gin ranking. You do it as follows:

In order to play a game as strategy X with N voters, you proceed as follows:

If we are in a state where we have M votes for that state we do one of three things:

  1. If M is >= N, we sample a subset of size N from M (with or without replacement? Not sure), run the strategy on that sample and play the winning move
  2. If M is < N but still pretty large we generate a population of size N by sampling with replacement and run the strategy
  3. If M is too small, we submit it to our players as an interesting board position and get them to fill it out. We pause the simulation until they have done so.

What are the benefits of doing it this way?

  • has much lower coordination costs – people don’t need to wait for the other people in their group to vote in order to make progress
  • by not imposing a voting system up front you get a lot more reuse out of the data
  • It might actually be fun to play. I suspect playing the real version of the experiment would be a nightmare slog of waiting for other people to finish voting
  • If you institute some sort of leader board as an incentive to win, the players are given a fairly strong incentive to vote honestly and accurately

The main downside is that it suffers badly from sparsity of data – I expect 90% or more of positions in a given game will be unique. There are a lot of valid reversi boards. I don’t know how many, but I expect it to be on the order of 2^100. The fact that the valid moves are quite constraining and people will tend to make similar decisions should help, but I don’t know how much. It might be possible to help this by steering some subset of the players randomly assigned moves towards boards we want, but you can only do that so much before people cotton on and it starts to distort the results.

I still don’t know if I actually care enough to implement this, but in this incarnation it sounds like an interesting enough project that I might at some point.

This entry was posted in Uncategorized on by .

Greetings from the Ministry for Dancing, Getting High and Fucking

Pozorvlak has an interesting blog post spawned by this rant by Vinay Gupta.

The TLDR is that he wants a concrete strategic plan for how you would run a government ministry whose goal it was to promote dancing, getting high and fucking.

Whilst I’m a very boring person who only has a more than passing interest in one of the three (no prizes for guessing which), I’m sufficiently megalomaniacal to believe that obviously I should be put in charge. So here’s an outline of my plan to utilize the forces of central planning and bureaucracy to get the population both high and laid.

I’m leaving aside the question of whether this is a good idea. This post will focus on how I would do it rather than whether we should do it.

Getting High

Decriminalization

It’s pretty hard to be in charge of Getting High if it’s illegal to get high. So let’s fix that.

Step 1 is to simply decriminalize the consumption of drugs. Don’t care what it is – if you want to put it in your body that’s ok with us.

The sale of drugs is another matter. A lot of drugs are very harmful. And a lot aren’t. I would form a department of the government whose goal was to research in an objective manner the effects of various drugs and to determine which should be made legal and which should remain banned due to adverse individual or social effects. It will also be responsible for quality control standards on all drugs sold.

I’m going to go out on a limb here and say that I expect to very quickly decriminalize the use of both Marijuana and MDMA. I’ve pretty limited knowledge of the subject, but based on a little bit of reading I feel semi-confident in saying that these are probably not substantially worse for you than already legal drugs like alcohol, caffeine and cigarettes and that their use is sufficiently widespread that keeping them illegal would basically be no more than a fiction anyway.

Licenses for the sale of alcohol would be extended automatically to include licenses for the sale of other legal highs (perhaps not all of them? I don’t know). Whilst bars and stores would not be required to sell them, we would hope they would do so and would run a marketing campaign to encourage it.

Ensuring quality and price

The second government institution I will form is in charge of flagrantly and maliciously interfering with the free market like a damn liberal hippy. It’s responsible for the producing of legal highs. It will produce a cheap, high quality instance of all legal drugs (including alcohol, cigarettes and caffeinated beverages as well as currently illegal drugs). These will be sold at a profit, but profit margins will be kept deliberately low and production will be tax free. Additionally all profits will be ploughed back into the ministry budget.

The goal here is to basically undercut the competition. By ensuring a steady supply of cheap but decent drugs you force the market to compete on quality rather than price. As well as making sure good drugs are affordable to all it has the nice feature of making it quite difficult for the existing criminal elements to compete.

Dancing

My plan for dancing (which incidentally should also improve our quality metrics on getting high and fucking) is to institute a series of certifications for clubs and bars.

These certifications will have three incentives attached:

  1. Tax breaks
  2. Discounts on government highs
  3. Marketing: The ability to say you are government certified in various ways. A/B testing will be performed to determine the effectiveness of various different phrasings of the certifications on custom. e.g. Out of “The Man thinks we’re awesome!” and “Government certified not-a-shithole” which is likely to be more effective?

Certification criterion will include but not be limited to the following:

  1. Enjoyment, as measured by our expert (and socially diverse) panel of random club and bar samplers (official job title: “I have the most awesome job ever”)
  2. Cleanliness
  3. Safety
  4. Inclusivity (price of entry, obnoxious bouncers, etc)
  5. Cost
  6. Spaciousness

Each of these cause the club to accrue points, and points mean pri- err. certifications. Each certification level requires a minimum score from each of the categories and a total score across all of them.

The certification levels will be kept deliberately unbounded so you can always reach a higher level of certification. The first time a new level of certification (e.g. the first club to reach certification level 10) is reached, the government will sponsor a massive party in the relevant venue in celebration. It may also be worth sponsoring parties in other high quality venues from time to time.

Additionally, specific facilities are encouraged and come with their own certifications, subsidies and rewards. These include:

  • On site medical facilities (nothing too extreme, just basic care for if you’ve injured yourself or had too much of something)
  • Chill out rooms for people who want a break or want to go take something a bit more relaxing
  • Rooms available for rent (this is actually a good idea regardless of whether you want to encourage sex. Sex will happen, and this helps make sure it’s in a safe place)

There will also be a separate scheme providing free contraceptives in clubs, regardless of their certification level.

Additionally, the government will perform regular surveys about access to clubs. In areas where there is an indication of a high unmet demand (or an unwillingness of the existing venues to meet government certification standards) we will subsidize the creation of clubs designed to meet a high level of quality. Similar to our production of drugs, these will be run in a tax free low profit manner for which the profits will be returned to the ministry budget.

Fucking

This is the hard one. So to speak.

Hopefully the increase in dancing and getting high will lead to a greater amount of fucking. But the simple fact of the matter is that the people most in need of the solutions we hope to offer in this space are the people least likely to willingly avail themselves of them.

In the interests of exploring solutions to this problem we will found the department of “sex is awesome” education. It will explore solutions to this problem.

The primary tool of this department will be Science. I would be extremely surprised if anyone actually knows what works here. Different things need to be tried to see what works.

First, we need to start with educating the children. Hangups about sex start young, and need to be addressed then. A/B testing will be performed to determine the optimal way to get teenagers talking to adults about sex in a comfortable no-judgement manner. Schools will be provided with at least one councellor whose job it is to address any questions they have. Parents who are uncomfortable with these goals for their children will be kindly invited to go practice the goals of this department with themselves.

For the generations for whom the damage is already done the problem is more difficult. I don’t have a good solution right now, other than that we should fund research on how to deprogram people of some of their more negative attitudes, so I’m going to pass on it for the moment. Hopefully everything so far is enough to trigger social change and that will gradually improve peoples’ attitudes as a whole.

Mini conclusion

I’ve actually more or less convinced myself that most of this is a good idea in the course of writing this. I’m not sure the details work, but I suspect where they don’t it’s merely in need of modification rather than outright dismissal.

Edit: I’ve realised I’ve not answered a lot of the questions from the original post. I’ve largely been focused on policy.

How do you measure your department’s effectiveness?

There are a couple obvious things to measure.

Firstly, we measure the results of certification. If an increased level of certification does not lead to an increase (or at the very least a non-decrease) in popularity we are doing something wrong.

We measure sales of our brands of drugs vs other ones. If we’re not selling well then something is wrong with our strategy and we should fix that.

We conduct random polls of people to find out what they think of us.

How do you recruit and train new DDGHF staff, and what kind of organisational culture do you try to create?

This is a tricky one. There are two types of personality type we need here: We need people who are really good at organizing things and people who are really inclined to party.

I would be inclined to focus on the former more than the latter – the goal here is to get the nation to party, not to get our department to. The main things I would do to offset this are quite simply to impose from on high not taking ourselves too seriously and to throw regular parties to break any ice that might form.

How does the new broom affect other departments?

Well, the effect on Justice is obviously quite a big deal due to the changing laws on what’s criminal.

I have a sneaking suspicion it might do some interesting things to tourism. Not sure why.

Already mentioned the changes to education. It’s probably confined to those.

I have absolutely no idea what it’ll do the the economy. It basically just throws all the dice up into the air to see where they land.

Not sure beyond that.

How do we manage diplomatic relations with states that are less hedonically inclined?

Invite them around to a party? It depends who they are and what their objections are.

One concern is trade sanctions. A ready supply of legal drugs makes us in danger of becoming part of the illegal drug trade in other countries. The easiest solution is to make export of drugs illegal even though their domestic sale is legal.

I don’t expect countries will outright ban their citizens from visiting us: cf. Amsterdam.

What are the Party Party’s policies on poverty, the economy, defence and climate change?

Probably that you shouldn’t have elected a one policy party if you care about this sort of thing.

I’m assuming they’re unlikely to be pro a large defence budget. Poverty is bad because it interferes with peoples’ ability to party. I refer you to my prior political ranting as to what I’d do about that.

Climate change is bad. It’s hard to dance with wet feet. Let’s sort that out.

This entry was posted in Uncategorized on by .

An interesting experiment in social choice

The following experiment design has occurred to me. I think it would be interesting, but I’m not sure it would be quite interesting enough for me to put in the effort to create it.

The domain of experiment is as follows: Given a presumed homogenous group trying to make a decision about a shared goal, what is the best decision procedure (i.e. voting system) for combining their opinions about it into a single decision?

The setup is as follows.

We take a strategy game. I picked reversi as a nice sweet spot between complicated and simple (it also has the nice property that the number of valid moves is quite constrained). Teams of people are assigned to black and white respectively.

A turn is played as follows:

The set of valid moves is generated. If there are no valid moves or only one play proceeds in the obvious constrained fashion without user input.
If there are more than some cap of valid moves pick a random subset of them (I’m not sure this is necessary. The maximum number of valid moves in reversi shouldn’t be very large).
The team then votes in some manner on which move to take.
The move which the voting system declares to be the winner is taken.

Note that this requires that the decision procedure not allow ties. This isn’t a terrible constraint as you can just add a random tie breaker to the decision procedure.

What’s the output of this experiment?

Each game generates the following data point:

Black had N players using voting procedure X
White had M players using voting procedure Y
C won

(it also generates the complete history of the game if that’s useful or interesting, but I suspect that’s too complicated to properly analyze)

A sufficiently large sample of this data can be used to answer a number of questions. The following are particularly interesting:

  1. Given the same size of group, does voting procedure X tend to beat voting procedure Y?
  2. Given a fixed voting procedure X, what is P(X applied to a group of size N beats a single opponent) as a function of N?
  3. Given a fixed voting procedure X, what is P(X applied to a group of size N beats X applied to a group of size M) as a function of M, N

Obviously you can’t then go on from this to say “This is the best voting procedure” as it’s applied to a very simple case, but I think the results would be interesting.

This entry was posted in voting on by .

pageme: A gem for invoking pagers from ruby

I got annoyed with being unable to page large amounts of data inside IRB, so I thought “Surely there must be a gem for this”. It turns out there isn’t. I mean there are extended versions of IRB that satisfy this specific need, but there’s no gem for “pipe this output to a pager”. Various gems do their own paging in various ways.

So I wrote one. It’s got a pretty simple API, but it seems to nicely do what I want: You can page strings to it, you can page from a block, you can redirect STDOUT and STDERR to a pager, etc.

It works on JRuby, which is apparently novel. Apparently no one has actually got that to work properly before. I can’t take too much credit for it – I merely observed that the posix-spawn gem works well enough in JRuby to launch a pager on a file then applied sufficient creative evil to bootstrap that into paging arbitrary things. The way it works is rather a hack – instead of piping directly to the less process it uses a unix domain socket to communicate with a netcat process piped into it. Really. And yes, a FIFO would be better, but for one reason or another I had a hell of a time getting it to work.

Charles Nutter has got an experimental version working with Java 7’s process builder which I hope to be able to incorporate, but I haven’t yet and will still have to leave a fall back approach in place for dealing with Java pre 7.

So far my cross-platform testing has been extremely thin on the ground. I’ve tried on MRI 1.8.7, MRI 1.9.2, JRuby 1.6.2 and JRuby-head, but only on my (linux) laptop. It probably doesn’t work entirely correctly under OSX (I’d expect the non JRuby version to, as it doesn’t do anything terribly controversial, but it might not). There’s no chance at all that it will work under windows.

My current plans which would allow me to take it to 1.0 are basically to get anyone who is interested in using it to do the cross platform testing for me, see if anything jumps out at me as wrong with the API, and figure out a way to do automated testing of this (I haven’t yet, because it’s by its nature mostly about interaction. I can definitely test some bits of it though).

Patches and suggestions welcome.

This entry was posted in programming on by .

Feeling tired? You should read this

I’ve had to give this advice to a few people now, so I thought I’d write an actual post about it for slightly broader distribution.

How are you feeling? Energy levels doing ok? Or maybe you’re feeling a bit tired. In fact, maybe you’ve been feeling tired for quite a long time. It gets a lot of us.

It’s very easy to accept being constantly tired as just a natural state of being. Maybe you’re overworked, stressed or full on burned out. It really does happen.

But a lot of the time if you are feeling constantly drained of energy it is because there is something physically wrong with you and you should see a doctor about it.

It’s extremely easy to suffer from nutritional deficiencies which can cause this. It is especially easy if you’re vegan, or even just vegetarian.

I’ve had this happen to me twice – once with vitamin B12 deficiency, once with vitamin D deficiency. Iron is another common thing you could be deficient in that would cause a lack of energy, though I’ve not personally experienced it. In the case of the vitamin D it was just completely magical watching the problem go away as soon as I started taking supplements. The B12 I was more borderline so the improvement from fixing it was not as dramatic, but for people who have serious problems with it I’ve heard similar reports of magically returning energy levels.

This isn’t necessarily what’s wrong with you, and I’m not in any way competent to offer you medical advice, but if you are having problems with your energy levels and you haven’t seen your doctor about it I would strongly encourage you to go see them about it an ask for a blood test to check for standard nutritional deficiencies. It’s easy, quick and may completely change your life.

Edit for clarification: There is a lot of bullshit in the vitamin and supplement industry. Do not uncritically read this post and go “I have a deficiency! I will buy pills and it will make everything better!”. My advice is not “You have a deficiency. Take supplements” it is “You might have a deficiency. Go see a doctor and find out”

This entry was posted in life on by .