Matrix Multiplicative Weights and Non-Zero Sum Games
Milosh Drezgich, Shankar Sastry

Citation
Milosh Drezgich, Shankar Sastry. "Matrix Multiplicative Weights and Non-Zero Sum Games". 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, 2010; Submitted.

Abstract
This article concentrates on the improvements in the vector and matrix version of a widely used multiplicative weights algorithm .The four results that we present are the following. We first present a small improvement in the existing upper bound for the matrix multiplicative weights algorithm for the particular set of two player zero sum games. Second, using the concavity property of unital positive linear maps between *-algebras, we establish the precise connection between the vector and matrix version of the multiplicative updates algorithm, that clearly reveals why the total loss for the both algorithms are the same. Third, as a corollary we present the matrix multiplicative weights algorithm with the iterative updates, that is both computationally less demanding and guarantees the same worst case performance as the conventional cumulative matrix multiplicative weight algorithm, resolving in part the open question stated at COLT 2010. Finally, unlike the vector version of the multiplicative weights algorithm, we present an evidence that the Nash equilibrium strategy for the non-zero sum Shapely game and the augmented Shapely game, can be found using matrix multiplicative weights updates algorithms.

Electronic downloads

(No downloads are available for this publication.)

Citation formats

• HTML

  Milosh Drezgich, Shankar Sastry. <a
  href="http://chess.eecs.berkeley.edu/pubs/780.html"
  >Matrix Multiplicative Weights and Non-Zero Sum
  Games</a>, <i>22nd Annual ACM-SIAM Symposium on
  Discrete Algorithms</i>,  2010; Submitted.

• Plain text

  Milosh Drezgich, Shankar Sastry. "Matrix Multiplicative
  Weights and Non-Zero Sum Games". <i>22nd Annual
  ACM-SIAM Symposium on Discrete Algorithms</i>,  2010;
  Submitted.

• BibTeX

  @article{DrezgichSastry10_MatrixMultiplicativeWeightsNonZeroSumGames,
      author = {Milosh Drezgich and Shankar Sastry},
      title = {Matrix Multiplicative Weights and Non-Zero Sum
                Games},
      journal = {22nd Annual ACM-SIAM Symposium on Discrete
                Algorithms},
      year = {2010},
      note = {Submitted},
      abstract = {This article concentrates on the improvements in
                the vector and matrix version of a widely used
                multiplicative weights algorithm .The four results
                that we present are the following. We first
                present a small improvement in the existing upper
                bound for the matrix multiplicative weights
                algorithm for the particular set of two player
                zero sum games. Second, using the concavity
                property of unital positive linear maps between
                *-algebras, we establish the precise connection
                between the vector and matrix version of the
                multiplicative updates algorithm, that clearly
                reveals why the total loss for the both algorithms
                are the same. Third, as a corollary we present the
                matrix multiplicative weights algorithm with the
                iterative updates, that is both computationally
                less demanding and guarantees the same worst case
                performance as the conventional cumulative matrix
                multiplicative weight algorithm, resolving in part
                the open question stated at COLT 2010. Finally,
                unlike the vector version of the multiplicative
                weights algorithm, we present an evidence that the
                Nash equilibrium strategy for the non-zero sum
                Shapely game and the augmented Shapely game, can
                be found using matrix multiplicative weights
                updates algorithms.},
      URL = {http://chess.eecs.berkeley.edu/pubs/780.html}
  }
  

Posted by Christopher Brooks on 24 Nov 2010.
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.