On domination game analysis for microeconomic data mining

ABSTRACT

Game theory is a powerful tool for analyzing the competitions among manufacturers in a market. In this article, we present a study on combining game theory and data mining by introducing the concept of domination game analysis. We present a multidimensional market model, where every dimension represents one attribute of a commodity. Every product or customer is represented by a point in the multidimensional space, and a product is said to “dominate” a customer if all of its attributes can satisfy the requirements of the customer. The expected market share of a product is measured by the expected number of the buyers in the customers, all of which are equally likely to buy any product dominating him. A Nash equilibrium is a configuration of the products achieving stable expected market shares for all products. We prove that Nash equilibrium in such a model can be computed in polynomial time if every manufacturer tries to modify its product in a round robin manner. To further improve the efficiency of the computation, we also design two algorithms for the manufacturers to efficiently find their best response to other products in the market.

REFERENCES

• 1: Stephan Börzsönyi , Donald Kossmann , Konrad Stocker, The Skyline Operator, Proceedings of the 17th International Conference on Data Engineering, p.421-430, April 02-06, 2001
• 2: Tom Brijs , Gilbert Swinnen , Koen Vanhoof , Geert Wets, Using association rules for product assortment decisions: a case study, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.254-260, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312241]
• 3: Chee-Yong Chan , Pin-Kwang Eng , Kian-Lee Tan, Stratified computation of skylines with partially-ordered domains, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066181]
• 4: Chee-Yong Chan , H. V. Jagadish , Kian-Lee Tan , Anthony K. H. Tung , Zhenjie Zhang, Finding k-dominant skylines in high dimensional space, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142530]
• 5: Chomicki, J., Godfrey, P., Gryz, J., and Liang, D. 2003. Skyline with presorting. In Proceedings of the International Conference on Data Mining. 717--816.
• 6: Gao Cong , Beng Chin Ooi , Kian-Lee Tan , Anthony K. H. Tung, Go Green: Recycle and Reuse Frequent Patterns, Proceedings of the 20th International Conference on Data Engineering, p.128, March 30-April 02, 2004
• 7: Evangelos Dellis , Bernhard Seeger, Efficient computation of reverse skyline queries, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 8: Xiaotie Deng , Christos Papadimitriou , Shmuel Safra, On the complexity of equilibria, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509920]
• 9: Nikhil R. Devanur , Christos H. Papadimitriou , Amin Saberi , Vijay V. Vazirani, Market Equilibrium via a Primal-Dual-Type Algorithm, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.389-395, November 16-19, 2002
• 10: Martin Ester , Rong Ge , Wen Jin , Zengjian Hu, A microeconomic data mining problem: customer-oriented catalog segmentation, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014119]
• 11: Alex Fabrikant , Christos Papadimitriou , Kunal Talwar, The complexity of pure Nash equilibria, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007445]
• 12: Parke Godfrey , Ryan Shipley , Jarek Gryz, Maximal vector computation in large data sets, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 13: Georg Gottlob , Gianluigi Greco , Francesco Scarcello, Pure Nash equilibria: hard and easy games, Proceedings of the 9th conference on Theoretical aspects of rationality and knowledge, June 20-22, 2003, Univerity of Indiana, Indiana [doi>10.1145/846241.846269]
• 14: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 15: Zhiyong Huang , Christian S. Jensen , Hua Lu , Beng Chin Ooi, Skyline Queries Against Mobile Lightweight Devices in MANETs, Proceedings of the 22nd International Conference on Data Engineering, p.66, April 03-07, 2006 [doi>10.1109/ICDE.2006.142]
• 16: H. V. Jagadish , Raymond T. Ng , Beng Chin Ooi , Anthony K. H. Tung, ItCompress: An Iterative Semantic Compression Algorithm, Proceedings of the 20th International Conference on Data Engineering, p.646, March 30-April 02, 2004
• 17: Wen Jin , Anthony K. H. Tung , Martin Ester , Jiawei Han, On Efficient Processing of Subspace Skyline Queries on High Dimensional Data, Proceedings of the 19th International Conference on Scientific and Statistical Database Management, p.12, July 09-11, 2007 [doi>10.1109/SSDBM.2007.20]
• 18: M. Jürgens , H.-J. Lenz, The R-tree: An Improved R*-tree with Materialized Data for Supporting Range Queries on OLAP-Data, Proceedings of the 9th International Workshop on Database and Expert Systems Applications, p.186, August 26-28, 1998
• 19: Jon Kleinberg , Christos Papadimitriou , Prabhakar Raghavan, Segmentation problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.473-482, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276860]
• 20: Jon Kleinberg , Christos Papadimitriou , Prabhakar Raghavan, A Microeconomic View of Data Mining, Data Mining and Knowledge Discovery, v.2 n.4, p.311-324, December 1998 [doi>10.1023/A:1009726428407]
• 21: Donald Kossmann , Frank Ramsak , Steffen Rost, Shooting stars in the sky: an online algorithm for skyline queries, Proceedings of the 28th international conference on Very Large Data Bases, p.275-286, August 20-23, 2002, Hong Kong, China
• 22: Koutsoupias, E. and Papadimitriou, C. H. 1999. Worst-case equilibria. In Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science. 404--413.
• 23: H. T. Kung , F. Luccio , F. P. Preparata, On Finding the Maxima of a Set of Vectors, Journal of the ACM (JACM), v.22 n.4, p.469-476, Oct. 1975 [doi>10.1145/321906.321910]
• 24: Iosif Lazaridis , Sharad Mehrotra, Progressive approximate aggregate queries with a multi-resolution tree structure, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.401-412, May 21-24, 2001, Santa Barbara, California, United States
• 25: Cuiping Li , Beng Chin Ooi , Anthony K. H. Tung , Shan Wang, DADA: a data cube for dominant relationship analysis, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142547]
• 26: Cuiping Li , Anthony K. H. Tung , Wen Jin , Martin Ester, On dominating your neighborhood profitably, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 27: Li, X. Honor year report: Rtree-based dada for dominant relationship queries and domination game model. https://dl.comp.nus.edu.sg/dspace/handle/1900.100/2487.
• 28: Nash, J. F. 1950. Equilibrium points in n-person games. Proc. Nat. Acad. Sci. 36, 48--49.
• 29: Osborne, M. J. and Rubinstein, A. 1994. A Course in Game Theory. The MIT Press.
• 30: Dimitris Papadias , Panos Kalnis , Jun Zhang , Yufei Tao, Efficient OLAP Operations in Spatial Data Warehouses, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.443-459, July 12-15, 2001
• 31: Dimitris Papadias , Yufei Tao , Greg Fu , Bernhard Seeger, An optimal and progressive algorithm for skyline queries, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872814]
• 32: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 33: Mehdi Sharifzadeh , Cyrus Shahabi, The spatial skyline queries, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 34: Steuer, R. 1986. Multiple Criteria Optimization. Wiley, New York.
• 35: Kian-Lee Tan , Pin-Kwang Eng , Beng Chin Ooi, Efficient Progressive Skyline Computation, Proceedings of the 27th International Conference on Very Large Data Bases, p.301-310, September 11-14, 2001
• 36: Yufei Tao , Xiaokui Xiao , Jian Pei, Efficient Skyline and Top-k Retrieval in Subspaces, IEEE Transactions on Knowledge and Data Engineering, v.19 n.8, p.1072-1088, August 2007 [doi>10.1109/TKDE.2007.1051]
• 37: Adrian Vetta, Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.416, November 16-19, 2002
• 38: Balke, W. T. U. and Guntzer, J. X. Z. 2004. Efficient distributed skylining for web information systems. In Proceedings of the International Conference on Extending Database Technology.
• 39: Ke Wang , Senqiang Zhou , Jiawei Han, Profit Mining: From Patterns to Actions, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.70-87, March 25-27, 2002
• 40: Wang, S., Ooi, B. C., Tung, A. K. H., and Xu, L. 2007. Efficient skyline query processing on peer-to-peer networks. In Proceedings of the International Conference on Data Mining. 1126--1135.
• 41: Raymond Chi-Wing Wong , Ada Wai-Chee Fu , Ke Wang, MPIS: Maximal-Profit Item Selection with Cross-Selling Considerations, Proceedings of the Third IEEE International Conference on Data Mining, p.371, November 19-22, 2003
• 42: Wu, P., Zhang, C., Feng, Y., Zhao, B. Y., Agrawal, D., and Abbadi, A. E. 2006. Parallelizing skyline queries for scalable distribution. In Proceedings of the International Conference on Extending Database Technology. 112--130.
• 43: Tian Xia , Donghui Zhang, Refreshing the sky: the compressed skycube with efficient support for frequent updates, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142529]
• 44: Yao, J. T. 2003. Sensitivity analysis for data mining. In Proceedings of the 22nd International Conference of the North American Fuzzy Information Processing Society (NAFIPS). 272--277.
• 45: Yidong Yuan , Xuemin Lin , Qing Liu , Wei Wang , Jeffrey Xu Yu , Qing Zhang, Efficient computation of the skyline cube, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms

Keywords:
Domination game, data mining, game theory