Chennai Mathematical Institute


Clustered Domination Game

Nagarajan Krishnamurthy
Chennai Mathematical Institute.


Domination Game (Zhang, Lakshmanan and Tung (2009)) is a game between manufacturers who produce one type of product and try to maximize their market share. Each customer requires one unit of this product and has requirements on each attribute of the product. Zhang, Lakshmanan and Tung (2009) use potential functions (Monderer and Shapley (1996)) to show that this game has a pure Nash equilibrium and propose algorithms to solve this game.

We generalize the domination game to the case where customers (may) require multiple units of the product. One way to solve the multiple-unit game is to reduce it to the single-unit game. For each customer, we introduce as many dummy customers as the number of units. If the number of customers is large (as is normally the case) or if some customers require large numbers of units of the product, the number of dummy customers introduced is large. We use modified payoff functions and appropriately modify the potential function to show that we do not need to introduce dummy customers. We prove that this modified multiple-unit game also has a pure Nash equilibrium. In fact, all Nash equilibria of this game and the game with dummy customers correspond.

Further, we cluster customers requirements, thereby reducing the size of the domination game and hence, the time taken to solve the game. We also extend the domination game to the case where manufacturers produce multiple products. The multiple-product case together with clustering captures the case where manufacturers manufacture different product instances of the same product type (for example, products of different quality) possibly targeting various customer segments. In all these cases, we prove the existence of pure Nash equilibria. Furthermore, we show that Nash equilibria in the clustered domination game are in one-to-one correspondence with those of the original game. By restricting product profiles to a d-dimensional grid (where d is the number of product attributes) and assuming uniform distribution of customers within each cluster, we find approximate Nash equilibria.