## Invited Session Wed.1.MA 041

#### Wednesday, 10:30 - 12:00 h, Room: MA 041

**Cluster 3: Complementarity & variational inequalities** [...]

### Complementarity modeling and its game theoretical applications

**Chair: Samir Kumar Neogy**

**Wednesday, 10:30 - 10:55 h, Room: MA 041, Talk 1**

**Samir Kumar Neogy**

Generalized principal pivot transforms, complementarity problem and its applications in game theory

**Abstract:**

The notion of principal pivot transform (PPT) was introduced by Tucker and it is encountered in mathematical programming, complementarity problem, game theory, statistics, matrix analysis and many other areas. It is originally motivated by the well-known linear complementarity problem. In this talk, we discuss the concept of generalized principal pivot transform and present its properties and applications. The proposed generalized principal pivoting algorithm has many game theoretical applications. This generalized principal pivoting algorithm is a finite step algorithm and even in the worst case, this algorithm is partial enumeration only. It is demonstrated that computational burden reduces significantly for obtaining the optimal stationary strategies and value vector of the some structured stochastic game problem.

**Wednesday, 11:00 - 11:25 h, Room: MA 041, Talk 2**

**Abhijit Gupta**

Complementarity model for a mixture class of stochastic game

**Abstract:**

Researchers from the field of game theory adopted Lemke's approach to the field stochastic games and formulated the problem of computing the value vector and stationary strategies for many classes of structured stochastic game problem as a complementarity problem and obtain finite step algorithms for this special class of stochastic games. In this talk we consider a mixture class of zero-sum stochastic game in which the set of states are partitioned into sets *S*_{1}, *S*_{2} and *S*_{3} so that the law of motion is controlled by Player I alone when the game is played in *S*_{1}, Player II alone when the game is played in *S*_{2} and in *S*_{3} the reward and transition probabilities are additive. We obtain a complementarity model for this mixture class of stochastic game. This gives an alternative proof of the ordered field property that holds for such a mixture type of game. Finally we discuss about computation of value vector and optimal stationary strategies for discounted and undiscounted mixture class of stochastic game.

**Wednesday, 11:30 - 11:55 h, Room: MA 041, Talk 3**

**Arup Kumar Das**

A complementarity approach for solving two classes of undiscounted structured stochastic games

**Abstract:**

In this talk, we consider two classes of structured stochastic games, namely, undiscounted zero-sum switching controller stochastic games and undiscounted zero-sum additive reward and additive transitions (ARAT) games. Filar and Schultz observed that an undiscounted zero-sum stochastic game possesses optimal stationary strategies if and only if a global minimum with optimum value zero can be found to an appropriate linearly constrained nonlinear program. However, a more interesting problem is the reduction of these nonlinear programs to linear complementarity problems or linear programs. The problem of computing the value vector and optimal stationary strategies is formulated as a linear complementarity problem for these two classes of undiscounted zero-sum games. Implementation of available pivoting algorithms on these two formulations are also discussed.