How does the Multiplicative Weights Update method maximize entropy? "The Multiplicative Weights Update (MWU) method is known to maximize both utility and entropy". This is a comment by C. Papadimitriou on MWU. I understand that MWU maximizes utility as it solves linear programming, for example. 

The question is how MWU maximizes entropy? Can you give some example/information on this point?
Here's one way to look at it, based on usul's comment.

Let the gains of each expert $i$ at time $t$ be given by $g_i^t$.

Then the expected gains of the algorithm are:

$$\sum_{u=1}^{t-1}\sum_i p_i^t g_i^u$$

We can then define the potential function

$$\Phi=\epsilon \sum_{u=1}^{t-1}\sum_i p_i^t g_i^u + \sum_i p_i^t \ln \left(\frac{1}{p_i^t}\right)$$

Where the right-hand term is the entropy and $\epsilon$ is a learning rate.

This function is maximized for

$$p_i^t = \exp\left(\epsilon \sum_{u=1}^{t-1} g_i^u-1\right)$$

We can find a similar expression that maximizes the function for $t+1$.

Taking the logarithms of these expressions and subtracting gives:

$$p_i^{t+1}=p_i^t \exp (\epsilon g_i^t)$$

Which is the MWU update rule.

Therefore, by applying this update rule we are maximizing a potential function of utility and entropy.