robust by suitably changing the input LP. Robustness is a topic well-studied in learning theory [@devroye; @partha], although existing results do not seem to apply directly to our problem. We remark that a component of robustness more closely related to the standard PAC-learning literature is used in [@DevanurHayes09].

In recent work, Devanur et al. [@Devanur11] consider the weaker *i.i.d. model* for the general allocation problem. While in the random permutation model one can think that columns are sampled without replacement, in the i.i.d. model they are sampled with replacement. Making use of the independence between samples, Devanur et al. substantially improve requirement on $B$ to $\Omega(\frac{\log (m/\epsilon)}{\epsilon^2})$ while showing that the lower bound $\Omega\left(\frac{\log m}{\epsilon^2}\right)$ still holds in this model. We remark, however, that these models can present very different behaviors: as a simple example, consider an LP with $n$ columns, $m = 1$ constraints and budget $B = 1$, where only one of the columns has $\pi_1 = a^1 = 1$ and all others have $\pi_i = a^i = 0$; in the random permutation model the expected value of the optimal solution is 1, while in the i.i.d. model this value is $1 - (1 - 1/n)^n \rightarrow 1 