Completing a Panini Sticker Album

When I was a kid my main ambition was to fill out the Panini Italia 90 sticker album. I promised myself when I was old and rich I would buy all the stickers I needed to fill out a championship sticker album. Some kids aim to play for Ireland, I aimed low. Turns out I am not rich but I am nerdy so at least I can work out how much it would cost to fill out the album.

This is called the Coupon Collector Problem.
"Given n coupons, how many coupons do you expect you would need to draw with replacement before having drawn each coupon at least once?"

There are 539 stickers in an album to collect. The first sticker you buy is going to be one you need, a 539/539 chance of getting one you need. The second has a 538/539 chance of being one you do not have as there is one it can clash with. This keeps going until for the last sticker every new sticker has a 1/539 of beng the right one. The formula for the number of attempts you would need to calculate the coupon collector number is 539*Harmonic Number of 539. Which according to Wolfram Alpha is 6.867858*539=3701.77. The stickers are sold in packs of five. Which means 740 packs.

On amazon a box of 100 packs cost £43.95. This would mean (assuming you could get .4 of a box at that same price) that filling the album would be expected to cost 325.23 pounds.

Panini sell the stickers at 14p each. So to buy the stickers individually would cost 539*.14=75.46 pounds.

Is there some kind of mixture of boxes of random stickers and individual ones that means you can fill in the album for as cheap as possible. Say the individual stickers can be bought at the price of a box. So thats 0.1162 pounds for each sticker. Which is not that much of a saving. It becomes more efficient to buy individual stickers than random packs at this price after about 90 stickers.

The last sticker takes on average 539 stickers to be bought to find it. So this last sticker costs 0.1162*539=62.63 pounds if you buy it in packets not individually.

But are the tickets independent? As in are some rarer than others and is each pack random? Some people studied this in the very cool paper 'Paninimania: sticker rarity and cost-ef fective strategy'
"We consider some issues related to the famous Panini stickers devoted to the football world cup. In particular, we address the following questions: is there a planned shortage of some stickers? What is a good cost-e ffective strategy to fill in an album?"
Which proves amongst other things I am not the only nerd that still wants to fill in a Panini album.

Crowd Sourced Optimal Fantasy Football Team

All my fantasy football attempts have the problem that I know nothing about football. So for example Berbatov is unlikely to do as well this season as last season so picking him would seem unwise. But how does someone who knows nothing about football find out who will play well next season?

The wisdom of the crowds is the James Surowiecki about "the aggregation of information in groups, resulting in decisions that, he argues, are often better than could have been made by any single member of the group." This sort of thing does not work if the crowd has a bias in a particular direction.

I decided to look at the people is the "team selected by %" that fantasy premier league shows you. If I rerun the optimisation described in this post but instead of trying to great a team that has the maximum number of points last season I try and get the team whose players have been selected by the most other fantasy football managers.

The idea is that a team with the right number of defenders, goalkeepers, midfielders and forwards, that has at most three players from one team, that costs less than 100 and whose members have been picked most often should be really good.

The most popular team is

      Player Club Pos Price Pts people
7     Al-Habsi  WIG  GK    45 125  199410
30        Bale  TOT MID    80 118   189087
37      Barton  NEW MID    60 131   123865
69      Cahill  BOL DEF    55 105   180751
184      Given  AVL  GK    50   0   215091
205  Hangeland  FUL DEF    65 154   192333
231       Huth  STO DEF    60 138   165684
266    Kompany  MCI DEF    60  95  197352
323      N'Gog  LIV STR    55  48   279932
334 Odemwingie  WBA STR    75 171   218485
421     Suarez  LIV STR    95  68   343361
424    Taarabt  QPR MID    65   0   141086
452      Vidic  MUN DEF    80 148   172773
472   Wilshere  ARS MID    65  93   220381
477 Yaya Toure  MCI MID    80 146   167706

Some of these players were probably picked for the first few games and will be transfered out when they are about to play tougher games.

The average player is picked 26794 times. These players have been picked 200486 people on average.
This team would have scored 1415 points last season. The best team I could have picked for last season would have scored 2332 points. I have updated the dataset to include this people picked statistic.

Fantasy Football Optimization 2

So it turns out I was thick last post about picking the fantasy football team. As my friend Bren explained to me "you choose 11 players to be "on the pitch" each week, plus a captain who scores double (and a vice captain in case the captain doesn't play). can only have 1 keeper in the first 11, can choose any formation with a minimum of 3 defenders, 3 midfielders and 1 forward."

So the problem is now pick 11 players that will actually play and some really cheap players that won't

So whats the cheapest of each player you could get?
The cheaperst players in each position are about 4 or 4.5 each. For example
Goalkeeper
Moreira SWA 4.0 0
Defenders
Whitbread NOR 4.0 0
Tate SWA 4.0 0
Midfield
Lappin NOR 4.5 0
Gecov FUL 4.5 0
Allen SWA 4.5 0
Strikers
Miller WBA 4.5 6
Hulse QPR 4.5 0
Agyemang QPR 4.5 0

So if you picked from this price of player knowing they would not play that would allow you to spend more money on those that were on the pitch. Now defenders score less points than midfielders and strikers so lets say we only want three of them. And we then buy two cheap ones that we dont play. 2 cheap defenders costs 8 and one goalie for 4 means we now have 88 to pick the remaining 12 players. The case whether you should have 5 midfielders or 3 strikers is less clear. I will try both and see which has a higher score.

Attempt 1. Cheap goalie and 2 defenders and 1 midfielder. Cost 16.5 on 4 non playing players. Trying to have 3 strikers. The constraints would now be

num_goalkeepers <- 1
num_defenders <- 3
num_midfielders <- 4
num_strikers <- 3
max_team_cost <- 835
max_player_from_a_team <- 3 

Gives a team of

1         Hart  MCI  GK    70 175
48    Ivanovic  CHE DEF    70 144
49        Huth  STO DEF    60 138
51      Hughes  FUL DEF    50 129
197       Adam  LIV MID    90 192
198    Malouda  CHE MID   105 186
200    Dempsey  FUL MID    85 168
201   N'Zogbia  WIG MID    75 167
210     Jarvis  WOL MID    60 133
386   Berbatov  MUN STR    95 176
388 Odemwingie  WBA STR    75 171

scoring 1779. You would make Adam your captain and he would have double points.

Attempt 2. Cheap non playing goalie and 2 defenders and 1 striker. Trying to have two strikers. Cost 16.5 on 4 non playing players.

num_goalkeepers <- 1
num_defenders <- 3
num_midfielders <- 5
num_strikers <- 2
max_team_cost <- 835
max_player_from_a_team <- 3 

1         Hart  MCI  GK    70 175
48    Ivanovic  CHE DEF    70 144
49        Huth  STO DEF    60 138
51      Hughes  FUL DEF    50 129
197       Adam  LIV MID    90 192
198    Malouda  CHE MID   105 186
200    Dempsey  FUL MID    85 168
201   N'Zogbia  WIG MID    75 167
210     Jarvis  WOL MID    60 133
386   Berbatov  MUN STR    95 176
388 Odemwingie  WBA STR    75 171

with a score of 1769. Again Adam would be your captain. It looks like three strikers is a better plan than 5 midfielders. But it is a close run thing.

Just to make things really complicated Bren explained that you should generally have one good player on the subs bench in case one of the rest of the team is injured. "it's quite common for one of the main team to miss a week so you may need to make 1 sub an excellent player (probably defender since they're cheaper)". Having a defender as your good sub has the advantage that you are allowed to play with one forward and three midfielders so if one of your three forwards, four midfielders or three playing defenders gets injured a defender can sub in for any of those.

So assuming we actually want four defenders. We would have one cheap goalie and one cheap defender and one cheap midfielder. At a cost of 12.5 for non playing players.

num_goalkeepers <- 1
num_defenders <- 4
num_midfielders <- 4
num_strikers <- 3
max_team_cost <- 875
max_player_from_a_team <- 3 

giving a team of

         Player Club Pos Price Pts
1         Hart  MCI  GK    70 175
46      Cole A  CHE DEF    75 150
49        Huth  STO DEF    60 138
51      Hughes  FUL DEF    50 129
54    Bardsley  SUN DEF    50 123
197       Adam  LIV MID    90 192
200    Dempsey  FUL MID    85 168
201   N'Zogbia  WIG MID    75 167
203    Downing  LIV MID    85 163
386   Berbatov  MUN STR    95 176
388 Odemwingie  WBA STR    75 171
393   Davies K  BOL STR    65 132

1884 points -123 as Bardley wont play = 1761. Basically Bardsley a Sunderland defender is really cheap at 5. This is one more than you pay for a player you don't want to play but if you do need to lay him he gets 123 points a season.
Davies looks a little low there with 132 points. The worst midfielder has 163 points. So what if we get rid of the third striker and try 5 midfielders?

num_goalkeepers <- 1
num_defenders <- 4
num_midfielders <- 5
num_strikers <- 2
max_team_cost <- 875
max_player_from_a_team <- 3 

   Player Club Pos Price Pts
1         Hart  MCI  GK    70 175
46      Cole A  CHE DEF    75 150
49        Huth  STO DEF    60 138
51      Hughes  FUL DEF    50 129
53      Distin  EVE DEF    55 124
197       Adam  LIV MID    90 192
200    Dempsey  FUL MID    85 168
201   N'Zogbia  WIG MID    75 167
203    Downing  LIV MID    85 163
210     Jarvis  WOL MID    60 133
386   Berbatov  MUN STR    95 176
388 Odemwingie  WBA STR    75 171

1886-124 for Distin who usually wont play = 1762. So this is my best single fantasy football team of last season.

The more I learn about this game the more nuances it has. Off the top of my head
1. Model that the captain gets double points. In this case Adam the highest scoring player is actually quite cheap. But in the case where he was really expensive you would want to take into account that he can earn double points.
2. Take into account who teams are playing. With a full game by game scoring dataset you can investigate really interesting patterns like if playing top five club means less points and bottom five more. And if so make transfers based on upcoming games. This seems to be where a huge amount of the skill in fantasy football is.
3. Change the code so you can have 3->5 defenders, 3-5 midfielders and 1-3 strikers but only 11 total players.
4. Just picking cheap non playing players is probably wrong. You at least want to pick the best cheap players you can. Which I have not. I am told Shane Ferguson is a good buy so I will probably make him one of the cheap players.

If any of the intuitions about having a good substitute or any of my other assumptions are wrong please correct me.
If you predict different points for players this season. If you want to try this method for next season but dont want to run the program linked to in part one


1. Copy the dataset I have here
2. Put this data into a new google docs spreadsheet.
3. Make your predictions on the number of points they will score. So if you think Berbatov won't score 176 points this season but only 160 change that points value. You can delete players you are not interested in as well.
4. Put your new spreadsheet URL in the comments
and I will run a optimization over your predictions for you.

Fantasy Football Optimisation

Some friends challenged me to a game called fantasy "football" where you pretend to be a Russian billionaire. Not the bit where you steal natural resources off the population but where you buy a bunch of poncy overpaid foreigners who flounce around and earn insane amounts of money.

While I'm ranting about "football". Why do football ads always say it has "the beauty of a dance". If you like dancing that much go to the ballet



Anyway So I have to pretend to know something about this "football" which I dont but I do know a bit about optimization and more about copying stuff. I remembered this old R package article about optimising for fantasy football. This was written by prasoonsharma and I have just reused his code.

I scraped last seasons scores off the fantasy premierleague website. Some parsing turned this into the correct format. You can download the cleaned up data here

The constraints for this version of the game are slightly different than the one prasoonsharma was playing. This means you need more goalies, have more money to spend on players and other such changes.

The best single team for last season would have been

        Player Club Pos Price Pts
1         Hart  MCI  GK    70 175
5     Al-Habsi  WIG  GK    45 125
48    Ivanovic  CHE DEF    70 144
49        Huth  STO DEF    60 138
51      Hughes  FUL DEF    50 129
54    Bardsley  SUN DEF    50 123
55     Johnson  WOL DEF    50 120
197       Adam  LIV MID    90 192
200    Dempsey  FUL MID    85 168
201   N'Zogbia  WIG MID    75 167
210     Jarvis  WOL MID    60 133
212     Barton  NEW MID    60 131
386   Berbatov  MUN STR    95 176
388 Odemwingie  WBA STR    75 171
393   Davies K  BOL STR    65 132

with a total score of 2224 points. You get to change the team every week in the real game. This optimisation is just if you got to pick one team and leave it.

Picking a fantasy football team involves
1. Predicting how many points each player will score that week
2. Optimising based on this prediction so you pick the team that covers all the rule constraints that scores the most points.

This code carries out the second part. If you have a prediction for how many points players will score that is better than
"exactly the same amount they scored last season" you can change the data with your new prediction and run it (or I can run it for you if you want). A web app that allowed you to enter your player score predictions and ran an optimisation so that the best team that could be picked based on your predictions was then created might be useful. If you save the data in a new google doc and change the Pts values to your player predictions. Then post a link to that google doc in the comments I will run the optimisation for you.