Discrete Geometry Seminar: Kyle Chapman (UCSB), 'An alternative to the Shapley-Snow algorithm for completely solving matrix games'

Event Date: 

Wednesday, January 22, 2014 - 2:00pm to 3:00pm

Event Location: 

  • 4607B South Hall

Event Contact: 

Michael Dougherty
Email: dougherty@math.ucsb.edu

Abstract: Matrix games can often be very large, which isn't a problem if our goal is simply to find one solution, as the simplex algorithm finds one solution quickly. If we want to find the entire solution set, however, we need to use a different algorithm, known as Shapley-Snow algorithm. This algorithm has a very large run time. The talk will present an alternative which uses the one solution given by the simplex algorithm to simplify the computations. The talk will briefly describe the definitions for matrix games and their solutions along with each algorithm involved.