"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.
The details are on page 3 of the paper Algorithms, games, and evolution by Erick Chastain, Adi Livnat, Christos Papadimitriou, and Umesh Vazirani. They explain how the multiplicative weights update rule $x_i^{t+1}(j) = \frac{x_i^t(j)}{Z^t} (1 + \epsilon u_i^t(j))$ can be recovered by imagining that we want to design an update rule that maximizes some convex combination of cumulative utility (expected) and entropy for each time $t$:
$$ \sum_j x_i^t(j) \sum_{t'=1}^t u_i^{t'}(j) - \frac{1}{\epsilon} \sum_j x_i^t(j) \ln x_i^t(j). $$
More details can be found in the Supporting Information text that comes with the paper.
