*banner
 

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.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.

You are not logged in 
©2002-2017 Chess