<p><div><div><div><div data-width="100" data-show-faces="false" data-send="true" data-layout="button_count" data-height="21" data-href="https://www.r-bloggers.com/a-knapsack-riddle/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="https://xianblog.wordpress.com/2017/02/13/a-knapsack-riddle/"> R – Xi'an's Og</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<p><img data-image-description="" data-orig-file="https://xianblog.files.wordpress.com/2009/07/gear1-e1486825315156.jpg" data-orig-size="1200,1600" data-image-title="gear1" class="wp-image-2074" data-comments-opened="1" data-recalc-dims="1" data-attachment-id="2074" data-permalink="https://xianblog.wordpress.com/2009/07/12/la-partenza-per-aosta/gear1/" alt="gear" data-medium-file="https://xianblog.files.wordpress.com/2009/07/gear1-e1486825315156.jpg?w=225" data-large-file="https://xianblog.files.wordpress.com/2009/07/gear1-e1486825315156.jpg?w=450" data-image-meta="{&quot;aperture&quot;:&quot;3.2&quot;,&quot;credit&quot;:&quot;&quot;,&quot;camera&quot;:&quot;DiMAGE Z20&quot;,&quot;caption&quot;:&quot;&quot;,&quot;created_timestamp&quot;:&quot;1247304829&quot;,&quot;copyright&quot;:&quot;&quot;,&quot;focal_length&quot;:&quot;6&quot;,&quot;iso&quot;:&quot;160&quot;,&quot;shutter_speed&quot;:&quot;0.025&quot;,&quot;title&quot;:&quot;&quot;}" src="https://i2.wp.com/xianblog.files.wordpress.com/2009/07/gear1.jpg?resize=436%2C327&ssl=1"></p>
<p><strong>T</strong>he [then current now past] <a target="_blank" rel="nofollow" href="https://fivethirtyeight.com/features/can-you-rule-riddler-nation/">riddle of the week</a> is a sort of multiarmed <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/2013/11/05/bandits-at-crest/">bandits</a> optimisation. Of sorts. Or rather a generalised knapsack problem. The question is about optimising the allocation of 100 undistinguishable units to 10 distinct boxes against a similarly endowed adversary, when the loss function is</p>
<p><img title="L(x,y)=(x_1&gt;y_1)-(x_1&lt;y_1)+...+10((x_{10}&gt;y_{10})-(x_{10}&lt;y_{10}))" alt="L(x,y)=(x_1&gt;y_1)-(x_1&lt;y_1)+...+10((x_{10}&gt;y_{10})-(x_{10}&lt;y_{10}))" class="latex" src="https://s0.wp.com/latex.php?latex=L%28x%2Cy%29%3D%28x_1%3Ey_1%29-%28x_1%3Cy_1%29%2B...%2B10%28%28x_%7B10%7D%3Ey_%7B10%7D%29-%28x_%7B10%7D%3Cy_%7B10%7D%29%29&bg=000000&%23038;fg=B0B0B0&%23038;s=0"></p>
<p>and the distribution q of the adversary is unknown. As usual (!), the phrasing of the riddle is somewhat ambiguous but I am under the impression that the game is played sequentially, hence that one can learn about the distribution of the adversary, at least when assuming this adversary keeps the same distribution q at all times.<span></span></p>
<p>Thus given such a q, one aims at maximising the expected loss</p>
<p><img title="\mathbb{E}[L(x,Y)]=\sum_{y} q(y) L(x,y)=\sum_{i=1}^{10} i(P(Y_i&lt;x_i)-P(Y_i&gt;x_i))" alt="\mathbb{E}[L(x,Y)]=\sum_{y} q(y) L(x,y)=\sum_{i=1}^{10} i(P(Y_i&lt;x_i)-P(Y_i&gt;x_i))" class="latex" src="https://s0.wp.com/latex.php?latex=%5Cmathbb%7BE%7D%5BL%28x%2CY%29%5D%3D%5Csum_%7By%7D+q%28y%29+L%28x%2Cy%29%3D%5Csum_%7Bi%3D1%7D%5E%7B10%7D+i%28P%28Y_i%3Cx_i%29-P%28Y_i%3Ex_i%29%29&bg=000000&%23038;fg=B0B0B0&%23038;s=0"></p>
<p>which also amounts to maximising</p>
<p><img title="\sum_{i=1}^{10} i\{2P(Y_i&lt;x_i)+P(Y_i=x_i)\} = \sum_{i=1}^{10} i \{F_i(x_i)+F_i(x_i-1)\}" alt="\sum_{i=1}^{10} i\{2P(Y_i&lt;x_i)+P(Y_i=x_i)\} = \sum_{i=1}^{10} i \{F_i(x_i)+F_i(x_i-1)\}" class="latex" src="https://s0.wp.com/latex.php?latex=%5Csum_%7Bi%3D1%7D%5E%7B10%7D+i%5C%7B2P%28Y_i%3Cx_i%29%2BP%28Y_i%3Dx_i%29%5C%7D+%3D+%5Csum_%7Bi%3D1%7D%5E%7B10%7D+i+%5C%7BF_i%28x_i%29%2BF_i%28x_i-1%29%5C%7D&bg=000000&%23038;fg=B0B0B0&%23038;s=0"></p>
<p>based solely on the marginals of q. Under the constraint that the sum of the allocations is 100. It seems rather natural to assume a Multinomial distribution on y, with probability vector p. Hence Binomial marginals.</p>
<p>If we knew y, the optimum would be obtained as taking as many x[i] equal to y[i]+1 as possible for the largest values of the index i and cancelling all other terms. However, this is not necessarily the best option when, by cancelling one x[i], all remaining lowest terms could then be filled. The other point is that, once a positive loss is achieved, there is plenty of freedom in allocating the remaining bits. But this is not the problem, only the distribution matters. Still, here is an R code to optimise x given y:</p>
<pre>
loz=function(x,y){ 
   return(sum(2*(1:10)*(x>y)+(1:10)*(x==y)))}
#distribution of dominating allocations
T=1e2
armz=matrix(0,T,100)
for (l in 1:T){
# initialisation with default probability
 y=rmultinom(n=1,size=100,prob=1:10) #adversary
 x=y+1 #impossible allocation
 i=1 #get rid of lesser values
 while (sum(x)>100){x[i]=0;i=i+1}
 x[i-1]=100-sum(x) #correct sum
#random search
 maxloz=loss=0
 newloss=loz(x,y)
 t=1
 while ((t&lt;100)||(newloss>loss)){
#exchange two groups
  i=j=sample(1:10,1,prob=(x>0))
  while (j==i)
   j=sample(1:10,1,prob=(x&lt;(y+1))) 
#optimise over amount of move 
  kaz=min(x[i],y[j]+1-x[j]) 
  gain=rep(0,kaz) 
  for (k in 1:kaz){ 
   newx=x newx[i]=x[i]-k;newx[j]=x[j]+k
   gain[k]=loz(newx,y) 
   if (gain[k]>maxloz){
    maxloz=gain[k];argz=newx}}
  gain=gain-loss
#soft simulated annealing
  mov=1 #choice for a move
  if ((max(gain)>0)&amp;(kaz>1))
   mov=sample(1:kaz,1,prob=gain*(gain>0))
  gain=gain+loss;loss=newloss
  newloss=gain[mov]
  x[i]=x[i]-mov;x[j]=x[j]+mov
  t=t+1
  if (maxloz>loz(y,argz)) break()
  }
#creating a distribution on each of the 100 objects
 reprz=rep(1,x[1])
 for (m in 2:10) reprz=c(reprz,rep(m,x[m]))
 armz[l,]=reprz
 }
</pre>
<p>In the riddle, after each round, the posterior on the Multinomial distribution of the adversary can be updated from the latest input. The next step is to play the algorithm against itself, assuming each adversary follows the same track. Or wait for <a target="_blank" rel="nofollow" href="https://fivethirtyeight.com/features/can-you-rule-riddler-nation/">The Riddler</a> to provide the winning solution. Which is what happened to me as a frantic schedule in Warwick over the past two days (and multiple <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/2017/02/05/whiteout-in-les-diablerets-jatp/">activities in the Swiss Alps</a> before) preventing me from procrastinating this way! Still the plane ride back to France and the even longer late (in both senses) night train slog to Paris let me experiment with R codes… Here is for instance a representation of the table of allocations of the 100 units to the ten classes [after re-ordering]:</p>
<p><a target="_blank" rel="nofollow" href="https://i2.wp.com/xianblog.files.wordpress.com/2017/02/riddler0902.jpg?ssl=1"><img sizes="(max-width: 398px) 100vw, 398px" data-image-description="" data-orig-file="https://i2.wp.com/xianblog.files.wordpress.com/2017/02/riddler0902.jpg?resize=398%2C398&amp;ssl=1" data-orig-size="480,480" data-image-title="riddler0902" data-comments-opened="1" class="wp-image-32724" data-recalc-dims="1" data-attachment-id="32724" data-permalink="https://xianblog.wordpress.com/2017/02/13/a-knapsack-riddle/riddler0902/" alt="riddler0902" data-medium-file="https://i2.wp.com/xianblog.files.wordpress.com/2017/02/riddler0902.jpg?resize=398%2C398&amp;ssl=1?w=300" data-large-file="https://i2.wp.com/xianblog.files.wordpress.com/2017/02/riddler0902.jpg?resize=398%2C398&amp;ssl=1?w=450" data-image-meta="{&quot;aperture&quot;:&quot;0&quot;,&quot;credit&quot;:&quot;&quot;,&quot;camera&quot;:&quot;&quot;,&quot;caption&quot;:&quot;&quot;,&quot;created_timestamp&quot;:&quot;0&quot;,&quot;copyright&quot;:&quot;&quot;,&quot;focal_length&quot;:&quot;0&quot;,&quot;iso&quot;:&quot;0&quot;,&quot;shutter_speed&quot;:&quot;0&quot;,&quot;title&quot;:&quot;&quot;,&quot;orientation&quot;:&quot;0&quot;}" src="https://i2.wp.com/xianblog.files.wordpress.com/2017/02/riddler0902.jpg?resize=398%2C398&ssl=1"></a>This makes for a distribution to sample from and try to compete against the adversary. After building this scheme, I went back to <a target="_blank" rel="nofollow" href="https://fivethirtyeight.com/features/can-you-save-the-drowning-swimmer/">The Riddler</a> to check for solutions. And found that I had misinterpreted the riddle since all competitors entered a single value of y instead of a distribution! Like the winning (3,5,8,10,13,1,26,30,2,2). Still, using this repartition as the probability of the adversary in the above quote, using the resulting distribution of x led to a 96.8% success rate:</p>
<pre>
game=function(y,armz){
 w=0
 v=rep(1,100)
 x=rep(0,10)
 for (i in 1:1e3){
  for (u in 1:100) v[u]=sample(armz[u,],1)
  for (b in 1:10) x[b]=sum(v==b)
  w=w+(loz(x,y)>loz(y,x))}
 return(w/1e3)}
</pre>
<p>Checking against other top finishers also led to dominance, albeit less clearly:</p>
<pre>
> cy=c(3,5,8,10,13,1,26,30,2,2)
> game(cy,armz)
[1] 0.966
> sy=c(3,6,7,9,11,2,27,31,2,2)
> game(sy,armz)
[1] 0.91
> ny=c(5,7,9,11,15,21,25,2,2,3)
> game(ny,armz)
[1] 0.609
> jy=c(1,8,2,2,13,18,20,32,2,2)
> game(jy,armz)
[1] 0.977
> my=c(0,0,1,11,11,16,26,31,2,2)
> game(my,armz)
[1] 0.959
</pre>
<p>I wish I had time to test this code against the 1388 solutions <a target="_blank" rel="nofollow" href="https://github.com/fivethirtyeight/data/blob/master/riddler-castles/castle-solutions.csv">proposed there</a>, on Github, which is much less than the 4 10¹² different allocations!, as it would show how resistant the distribution can be to different strategies.</p>
<p>Filed under: <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/category/books/">Books</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/category/pictures/">pictures</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/category/statistics/r-statistics/">R</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/category/statistics/">Statistics</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/category/travel/">Travel</a> Tagged: <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/tag/allocations/">allocations</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/tag/colonel-blotto-game/">Colonel Blotto game</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/tag/github/">github</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/tag/optimisation/">optimisation</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/tag/r/">R</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/tag/simulated-annealing/">simulated annealing</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/tag/the-riddler/">The Riddler</a> <a target="_blank" rel="nofollow" href="http://feeds.wordpress.com/1.0/gocomments/xianblog.wordpress.com/32685/"><img alt="" src="http://feeds.wordpress.com/1.0/comments/xianblog.wordpress.com/32685/" border="0"></a> <img alt="" src="https://i1.wp.com/pixel.wp.com/b.gif?resize=1%2C1&ssl=1" border="0" data-recalc-dims="1"></p>
<p>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="https://xianblog.wordpress.com/2017/02/13/a-knapsack-riddle/"> R – Xi'an's Og</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a title="The R Project for Statistical Computing" rel="nofollow" href="https://www.r-project.org/">R</a> news and <a title="R tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/tutorial">tutorials</a> on topics such as: <a title="Data science" rel="nofollow" href="https://www.r-bloggers.com/search/data%20science">Data science</a>, <a title="Big Data" rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data">Big Data, <a title="R jobs" rel="nofollow" href="https://www.r-users.com/">R jobs</a>, visualization (<a title="ggplot and ggplot2 tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2">ggplot2</a>, <a title="Boxplots using lattice and ggplot2 tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/boxplot">Boxplots</a>, <a title="Maps and gis" rel="nofollow" href="https://www.r-bloggers.com/search/map">maps</a>, <a title="Animation in R" rel="nofollow" href="https://www.r-bloggers.com/search/animation">animation</a>), programming (<a title="RStudio IDE for R" rel="nofollow" href="https://www.r-bloggers.com/search/RStudio">RStudio</a>, <a title="Sweave and literate programming" rel="nofollow" href="https://www.r-bloggers.com/search/sweave">Sweave</a>, <a title="LaTeX in R" rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX">LaTeX</a>, <a title="SQL and databases" rel="nofollow" href="https://www.r-bloggers.com/search/SQL">SQL</a>, <a title="Eclipse IDE for R" rel="nofollow" href="https://www.r-bloggers.com/search/eclipse">Eclipse</a>, <a title="git and github, Version Control System" rel="nofollow" href="https://www.r-bloggers.com/search/git">git</a>, <a title="Large data in R using Hadoop" rel="nofollow" href="https://www.r-bloggers.com/search/hadoop">hadoop</a>, <a title="Web Scraping of google, facebook, yahoo, twitter and more using R" rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping">Web Scraping</a>) statistics (<a title="Regressions and ANOVA analysis tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/regression">regression</a>, <a title="principal component analysis tutorial" rel="nofollow" href="https://www.r-bloggers.com/search/PCA">PCA</a>, <a title="Time series" rel="nofollow" href="https://www.r-bloggers.com/search/time+series">time series</a>, <a title="finance trading" rel="nofollow" href="https://www.r-bloggers.com/search/trading">trading</a>) and more...
<img height="1" alt="" width="1" src="http://feeds.feedburner.com/~r/RBloggers/~4/ELMyzZpOo7o"></a></div>