Knapsacks of Legal Gambling!

by swtouw

Have you ever heard of Fanduel or DraftKings?  Some people have full time jobs winning on them…

Basically it’s a twist on classic fantasy football (or fantasy sport x), instead of drafting a single team at the start of the year, you draft short-lived teams on weekend, daily, or even day-segment basis.  Why?  Well, there’s ample opportunity to get it right, instead of classic fantasy football where you have all your eggs in a single basket, you can now draft a team for the Saturday NFL playoff games only, for example, and challenge others for money.

Yes, and it’s totally legal:

 “Fantasy sports is considered a game of skill and received a specific exemption from the 2006 Unlawful Internet Gambling Enforcement Act (UIGEA 2006).”

A game of skill.

So, before I get to the meat of testing the game of skill, here’s how it works at one thousand feet:  Each available player has a value associated to them, and you draft your team using a salary cap assigned to the contest (a contest made up of one or more of the same sporting events which contain the players you are choosing).  It’s like shopping for players and you have a limited amount of fake cash to buy them (what I like to call space bucks).  You must also fill a certain amount of roster spots.  So a typical College football contest could have players that range from 4.5 – 11 space bucks, and you have to fill a roster of QB (1), RB (2), WR (3), TE (1) and have a salary cap of 45 space bucks.  Then you take your roster and put it up against other player(s), as a bet, and that bet can range from $1 to thousands (that’s real money, not space bucks)…and of course, just like Vegas, Fanduel and DraftKings keep a slice of the winnings for themselves.

If you’re a machine learning guy competing on Kaggle, you really should be looking here too, in my opinion.  Here’s why, you are playing other players and not the house.  In other words, you can do head-to-head games, and you never know who you’re going to get – there’s no weight class or handicap.  So, if you can master the statistics behind your roster selections in these smaller windows provided by these games, you likely have an advantage against opponents relying on heuristics and luck (more on luck later).   One of my favorite blog posts on a similar subject comes from Mike Greenfield, you should read it, but the gist of it is, why battle to eek out victories in efficient markets like the stock market or Vegas, when you can win big in inefficient markets like NCAA tournament bracket pools with your buddies who are making irrational decisions?

Ok, so to the meat, there’s actually two things you need to solve here:

1. Create some kind of metric to assign a value to each player

2. Determine the perfect roster that optimizes value but remains under your space buck salary cap

The point of this blog is #2.  My buddy Matt and I spent too much time last week gathering statistics and building a value score for each player, and then, the night before the games, we had to pick our roster and were brute force doing it by hand to achieve a roster that looked to have the best value within cost.

So, for you computer science guys, does this sound familiar?  Albeit modified, it’s the classic Knapsack problem:

 “The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.”

500px-Knapsack.svg

There are 3 types of Knapsack problems I’m aware of, none of which match our problem at hand, but are a good starting point for solving #2; those options are:

Unbounded: there are unlimited players and you can take duplicates to get the most value for cost (you could have a roster of 5 Andrew Lucks)

0-1: there are only one of each player, and you need select the best combination to get the most value for cost (you could have a roster with the wrong amounts of positions, like 4 QBs)

Bounded: there are varying quantities of individual players, and you need to select the best combination to get the most value for cost (There could be 2 Andrew Lucks, 5 Tom Bradys to choose from and you end up with the problems associated with unbounded and 0-1)

All of the above have algorithms to solve them efficiently, but unfortunately, none of them match the extra constraint we have with our problem which is there must be a set amount of player types, in this case types are positions.  I call this fourth Knapsack problem:

0-1 Type-Bounded: There are only one of each player, but we need to have a set amount of positions in our knapsack to fill out a valid knapsack.  In this knapsack problem, our items have a fourth characteristic: item, value, cost, type

So I needed to create a new algorithm, and of course the best start point is looking at how the known algorithms work and then modifying one.  However, after messing around with 0-1 for too long I was stuck; but then I read this post.  I don’t know about you, but just examining code to extend or modify it never really works for me, I have to have some prose describing what it is really trying to do, well Mr. Givens in this post gave me my breakthrough when he eloquently states:

“The unbounded knapsack problem is fairly easy to solve:

  1. Determine the value-weight ratio of every item.
  2. Starting with the highest value-weight ratio item, place as many of this item as will fit into the sack.
  3. Move onto the next-highest value-weight item and repeat step 2 until the sack is full or there are no other items.”

The ah-ha part for me here was that by sorting by value-weight ratio (in our case value-cost ratio) largest to smallest and adding it to the knapsack actually solves the unbounded problem – voila.  All I needed to do now was use that logic, except skip over positions that are already filled and don’t add the same player more than once.

So:

Create a sorted list, largest to smallest, of all the players using their value-cost ratio.

Iterate through that list adding the player to the roster, but only if the roster is not already filled for that position.

BOOM.  It works, and it’s fast.  Here’s the code:

public class TypeBoundedKnapsack 
{
	public static void main(String[] args)
	{
		Map<String,Integer> max = new HashMap<String,Integer>();
		max.put("QB", 1);
		max.put("RB", 2);
		max.put("WR", 3);
		max.put("TE", 1);

		Map<String,Integer> counts = new HashMap<String,Integer>();
		counts.put("QB", 0);
		counts.put("RB", 0);
		counts.put("WR", 0);
		counts.put("TE", 0);

		Roster r = new Roster();
		double maxRosterCost = 50000;

		File file = new File(args[0]);
		Set<Player> players = populatePlayers(file, max);

		for (Player p : players)
		{
			if (counts.get(p.position) < p.maxOnRoster && r.getCost() <= maxRosterCost)
			{
				r.players.add(p.copy());
				int rosterCount = counts.get(p.position);
				rosterCount++;
				counts.put(p.position, rosterCount);
			}
		}

		System.out.println(r.toString());
	}

	private static Set<Player> populatePlayers(File file, Map<String,Integer> counts)
	{
		Set<Player> players = new TreeSet<Player>();
		BufferedReader br;
		try {
			br = new BufferedReader(new FileReader(file));

			String line;
			while ((line = br.readLine()) != null) 
			{
				String[] playerData = line.split("\t");
				int maxOnRoster = counts.get(playerData[0]);
				Player p = new Player(playerData[0], 
						playerData[1], 
						Double.parseDouble(playerData[2]), 
						Double.parseDouble(playerData[3]),
						maxOnRoster);
				players.add(p);
			}
			br.close();
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}

		return players;
	}
}

And the Players:

public class Player implements Comparable<Player>
{
	public double cost;
	public double value;
	public String name;
	public String position;
	public int maxOnRoster;
	
	public Player()
	{
		
	}
	
	public Player(String position, String name, double cost, double value, int maxOnRoster)
	{
		this.position = position;
		this.name = name;
		this.cost = cost;
		this.value = value;
		this.maxOnRoster = maxOnRoster;
	}

	public int compareTo(Player p) {
		//I want in reverse order, highest to lowest
		return new Double(p.value / p.cost).compareTo(new Double(this.value / this.cost));
	}

	protected Player copy() 
	{
		Player p = new Player();
		p.cost = this.cost + 0.0;
		p.value = this.value + 0.0;
		p.name = this.name + "";
		p.position = this.position + "";
		p.maxOnRoster = this.maxOnRoster + 0;
		
		return p;
	}
	

}

And the Roster:

public class Roster {

	public List<Player> players = new ArrayList<Player>();
	
	public double getCost()
	{
		double totalCost = 0;
		for (Player p : players)
		{
			totalCost += p.cost;
		}
		return totalCost;
	}
	
	public double getValue()
	{
		double totalValue = 0;
		for (Player p : players)
		{
			totalValue += p.value;
		}
		return totalValue;
	}

	@Override
	public String toString() 
	{
		String team = "";
		for (Player p : players)
		{
			team += p.position + ": " + p.name + "\n";
		}
		
		return "Total Cost: " + this.getCost() + "\n" + 
				"Total Value: " + this.getValue() + "\n" + 
				team;		
	}
}

So, remember I said I’d get back to the luck part?

Well, the first time we tried this we went 12-6. Cool.

The next time, 1-15.  Ouch.

Since we’ve created the algorithm for solving the perfect roster combination, it’s either a poor method we are applying to create our “value” score for the players (#1 above), or it’s just bad luck.  Probably a little of both.

Or maybe the guys we played were just more skilled than us?