MGMatch: Fast Matchmaking with Nonlinear Objective and Constraints via Multimodal Deep Graph Learning
Authors: 
Yu Sun, Kai Wang, Zhipeng Hu, Runze Wu, Yaoxin Wu, Wen Song, Xudong Shen, Tangjie Lv, Changjie FanAuthors Info & Claims
Pages 5741 - 5751
Abstract
As a core problem of online games, matchmaking is to assign players into multiple teams to maximize their gaming experience. With the rapid development of game industry, it is increasingly difficulty to explicitly model players' experiences as linear functions. Instead, it is often modeled in a data-driven way by training a neural network. Meanwhile, complex rules must be satisfied to ensure the robustness of matchmaking, which are often described using logical operators. Therefore, matchmaking in practical scenarios is a challenging combinatorial optimization problem with nonlinear objective, linear constraints and logical constraints, which receives much less attention in previous research. In this paper, we propose a novel deep learning method for high-quality matchmaking in real-time. We first cast the problem as standard mixed-integer programming (MIP) by linearizing ReLU networks and logical constraints. Then, based on supervised learning, we design and train a multi-modal graph learning architecture to predict optimal solutions end-to-end from instance data, and solve a surrogate problem to efficiently obtain feasible solutions. Evaluation results on real industry datasets show that our method can deliver near-optimal solutions within 100ms.
References
[1]
Ross Anderson, Joey Huchette, Will Ma, Christian Tjandraatmadja, and Juan Pablo Vielma. 2020. Strong mixed-integer programming formulations for trained neural networks. Mathematical Programming, Vol. 183, 1--2 (2020), 3--39.
[2]
Tadas Baltruvsaitis, Chaitanya Ahuja, and Louis-Philippe Morency. 2018. Multimodal machine learning: A survey and taxonomy. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 41, 2 (2018), 423--443.
[3]
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. 2021. Machine learning for combinatorial optimization: a methodological tour d'horizon. European Journal of Operational Research, Vol. 290, 2 (2021), 405--421.
[4]
Ksenia Bestuzheva, Mathieu Besanccon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, et al. 2021. The SCIP optimization suite 8.0. arXiv preprint arXiv:2112.08872 (2021).
[5]
Ralph Allan Bradley and Milton E Terry. 1952. Rank analysis of incomplete block designs: I. The method of paired comparisons. Biometrika, Vol. 39, 3/4 (1952), 324--345.
[6]
Quentin Cappart, Didier Chételat, Elias B Khalil, Andrea Lodi, Christopher Morris, and Petar Velivcković. 2023. Combinatorial optimization and reasoning with graph neural networks. Journal of Machine Learning Research, Vol. 24, 130 (2023), 1--61.
[7]
Dirk G Cattrysse and Luk N Van Wassenhove. 1992. A survey of algorithms for the generalized assignment problem. European Journal of Operational Research, Vol. 60, 3 (1992), 260--272.
[8]
Zhengxing Chen, Su Xue, John Kolen, Navid Aghdaie, Kazi A Zaman, Yizhou Sun, and Magy Seif El-Nasr. 2017. Eomm: An engagement optimized matchmaking framework. In Proceedings of the 26th International Conference on World Wide Web. 1143--1150.
[9]
Chih-Hong Cheng, Georg Nührenberg, and Harald Ruess. 2017. Maximum resilience of artificial neural networks. In Automated Technology for Verification and Analysis: 15th International Symposium, ATVA 2017, Pune, India, October 3-6, 2017, Proceedings 15. Springer, 251--268.
[10]
Arthur Delarue, Ross Anderson, and Christian Tjandraatmadja. 2020. Reinforcement learning with combinatorial actions: An application to vehicle routing. Advances in Neural Information Processing Systems, Vol. 33 (2020), 609--620.
[11]
Qilin Deng, Hao Li, Kai Wang, Zhipeng Hu, Runze Wu, Linxia Gong, Jianrong Tao, Changjie Fan, and Peng Cui. 2021. Globally optimized matchmaking in online games. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 2753--2763.
[12]
Jian-Ya Ding, Chao Zhang, Lei Shen, Shengyin Li, Bing Wang, Yinghui Xu, and Le Song. 2020. Accelerating primal solution findings for mixed integer programs based on solution prediction. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 34. 1452--1459.
[13]
Arpad E Elo and Sam Sloan. 1978. The rating of chessplayers: Past and present. (1978).
[14]
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. 2019. Exact combinatorial optimization with graph convolutional neural networks. Advances in Neural Information Processing Systems, Vol. 32 (2019), 15580--15592.
[15]
Mark E Glickman. 1995. A comprehensive guide to chess ratings. American Chess Journal, Vol. 3, 1 (1995), 59--102.
[16]
Mark E Glickman. 1999. Parameter estimation in large dynamic paired comparison experiments. Journal of the Royal Statistical Society Series C: Applied Statistics, Vol. 48, 3 (1999), 377--394.
[17]
Linxia Gong, Xiaochuan Feng, Dezhi Ye, Hao Li, Runze Wu, Jianrong Tao, Changjie Fan, and Peng Cui. 2020. Optmatch: Optimized matchmaking via modeling the high-order interactions on the arena. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2300--2310.
[18]
Yu Gong, Yu Zhu, Lu Duan, Qingwen Liu, Ziyu Guan, Fei Sun, Wenwu Ou, and Kenny Q Zhu. 2019. Exact-k recommendation via maximal clique optimization. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 617--626.
[19]
Thore Graepel and Ralf Herbrich. 2006. Ranking and matchmaking. Game Developer Magazine, Vol. 25 (2006), 34.
[20]
Ignacio E Grossmann. 2002. Review of nonlinear mixed-integer and disjunctive programming techniques. Optimization and Engineering, Vol. 3 (2002), 227--252.
[21]
Prateek Gupta, Maxime Gasse, Elias Khalil, Pawan Mudigonda, Andrea Lodi, and Yoshua Bengio. 2020. Hybrid models for learning to branch. Advances in Neural Information Processing Systems, Vol. 33 (2020), 18087--18097.
[22]
LLC Gurobi Optimization. 2021. Gurobi optimizer reference manual.
[23]
David Ha, Andrew Dai, and Quoc V. Le. 2016. HyperNetworks. arXiv preprint arXiv:1609.09106 (2016).
[24]
Qingyu Han, Linxin Yang, Qian Chen, Xiang Zhou, Dong Zhang, Akang Wang, Ruoyu Sun, and Xiaodong Luo. 2023. A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programming. In International Conference on Learning Representations.
[25]
He He, Hal Daume III, and Jason M Eisner. 2014. Learning to search in branch and bound algorithms. Advances in Neural Information Processing Systems, Vol. 27 (2014), 3293--3301.
[26]
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 770--778.
[27]
Ralf Herbrich, Tom Minka, and Thore Graepel. 2006. TrueSkill?: a Bayesian skill rating system. Advances in Neural Information Processing Systems, Vol. 19 (2006), 569--576.
[28]
Jie Hu, Li Shen, and Gang Sun. 2018. Squeeze-and-excitation networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 7132--7141.
[29]
Taoan Huang, Aaron M Ferber, Yuandong Tian, Bistra Dilkina, and Benoit Steiner. 2023. Searching large neighborhoods for integer linear programs with contrastive learning. In International Conference on Machine Learning. PMLR, 13869--13890.
[30]
Diederik P Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014).
[31]
Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016).
[32]
Wouter Kool, Herke van Hoof, and Max Welling. 2019. Attention, Learn to Solve Routing Problems!. In International Conference on Learning Representations.
[33]
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. 1998. Gradient-based learning applied to document recognition. Proc. IEEE, Vol. 86, 11 (1998), 2278--2324.
[34]
Yao Li, Minhao Cheng, Kevin Fujii, Fushing Hsieh, and Cho-Jui Hsieh. 2018. Learning from group comparisons: exploiting higher order interactions. Advances in Neural Information Processing Systems, Vol. 31 (2018), 4981--4990.
[35]
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid Von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. 2020. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13349 (2020).
[36]
Max B Paulus, Giulia Zarpellon, Andreas Krause, Laurent Charlin, and Chris Maddison. 2022. Learning to cut by looking ahead: Cutting plane selection via imitation learning. In International Conference on Machine Learning. PMLR, 17584--17600.
[37]
Laurent Perron and Vincent Furnon. [n.,d.]. OR-Tools. Google. https://developers.google.com/optimization/
[38]
Moonkyung Ryu, Yinlam Chow, Ross Anderson, Christian Tjandraatmadja, and Craig Boutilier. 2019. CAQL: Continuous action Q-learning. arXiv preprint arXiv:1909.12397 (2019).
[39]
Anna Sapienza, Palash Goyal, and Emilio Ferrara. 2019. Deep neural networks for optimal team composition. Frontiers in big Data, Vol. 2 (2019), 14.
[40]
Lara Scavuzzo, Feng Chen, Didier Chételat, Maxime Gasse, Andrea Lodi, Neil Yorke-Smith, and Karen Aardal. 2022. Learning to branch with tree mdps. Advances in Neural Information Processing Systems, Vol. 35 (2022), 18514--18526.
[41]
Aleksandr Semenov, Peter Romov, Sergey Korolev, Daniil Yashkov, and Kirill Neklyudov. 2017. Performance of machine learning algorithms in predicting game outcome from drafts in dota 2. In Analysis of Images, Social Networks and Texts: 5th International Conference, AIST 2016, Yekaterinburg, Russia, April 7-9, 2016, Revised Selected Papers 5. Springer, 26--37.
[42]
Thiago Serra, Xin Yu, Abhinav Kumar, and Srikumar Ramalingam. 2021. Scaling up exact neural network compression by ReLU stability. Advances in neural information processing systems, Vol. 34 (2021), 27081--27093.
[43]
Jialin Song, Ravi Lanka, Yisong Yue, and Masahiro Ono. 2020. Co-training for policy learning. In Uncertainty in Artificial Intelligence. PMLR, 1191--1201.
[44]
Jialin Song, Yisong Yue, Bistra Dilkina, et al. 2020. A general large neighborhood search framework for solving integer linear programs. Advances in Neural Information Processing Systems, Vol. 33 (2020), 20012--20023.
[45]
Wen Song, Zhiguang Cao, Jie Zhang, Chi Xu, and Andrew Lim. 2022. Learning variable ordering heuristics for solving constraint satisfaction problems. Engineering Applications of Artificial Intelligence, Vol. 109 (2022), 104603.
[46]
Yunhao Tang, Shipra Agrawal, and Yuri Faenza. 2020. Reinforcement learning for integer programming: Learning to cut. In International conference on machine learning. PMLR, 9367--9376.
[47]
Vincent Tjeng, Kai Xiao, and Russ Tedrake. 2017. Evaluating robustness of neural networks with mixed integer programming. arXiv preprint arXiv:1711.07356 (2017).
[48]
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. Advances in neural information processing systems, Vol. 30 (2017).
[49]
Kai Wang, HaoyuLiu Liu, ZhipengHu Hu, Xiaochuan Feng, Minghao Zhao, Shiwei Zhao, Runze Wu, Xudong Shen, Lv TangjieLv, and Changjie Fan. 2024. EnMatch: Matchmaking for Better Player Engagement via Neural Combinatorial Optimization. In Proceedings of the AAAI Conference on Artificial Intelligence.
[50]
Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. 2021. Learning large neighborhood search policy for integer programming. Advances in Neural Information Processing Systems, Vol. 34 (2021), 30075--30087.
[51]
Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Xu Chi. 2020. Learning to dispatch for job shop scheduling via deep reinforcement learning. Advances in Neural Information Processing Systems, Vol. 33 (2020), 1621--1632.
[52]
Jianan Zhou, Yaoxin Wu, Zhiguang Cao, Wen Song, Jie Zhang, and Zhenghua Chen. 2023. Learning large neighborhood search for vehicle routing in airport ground handling. IEEE Transactions on Knowledge and Data Engineering, Vol. 35, 9 (2023), 9769--9782.
Index Terms
- MGMatch: Fast Matchmaking with Nonlinear Objective and Constraints via Multimodal Deep Graph Learning
Index terms have been assigned to the content through auto-classification.
Recommendations
QuickSkill: Novice Skill Estimation in Online Multiplayer Games
CIKM '22: Proceedings of the 31st ACM International Conference on Information & Knowledge ManagementMatchmaking systems are vital for creating fair matches in online multiplayer games, which directly affects players' satisfactions and game experience. Most of the matchmaking systems largely rely on precise estimation of players' game skills to ...
Lagrangean decomposition for integer nonlinear programming with linear constraints
We present a Lagrangean decomposition to study integer nonlinear programming problems. Solving the dual Lagrangean relaxation we have to obtain at each iteration the solution of a nonlinear programming with continuous variables and an integer linear ...
Improve Deep Learning with Unsupervised Objective
Neural Information ProcessingAbstractWe propose a novel approach capable of embedding the unsupervised objective into hidden layers of the deep neural network (DNN) for preserving important unsupervised information. To this end, we exploit a very simple yet effective unsupervised ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
August 2024
6901 pages
Copyright © 2024 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 24 August 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- National Science Foundation of China
- Shandong Provincial Natural Science Foundation
Conference
KDD '24: The 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
August 25 - 29, 2024
Barcelona, Spain
Acceptance Rates
Overall Acceptance Rate 1,133 of 8,635 submissions, 13%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 170Total Downloads
- Downloads (Last 12 months)170
- Downloads (Last 6 weeks)35
Reflects downloads up to 23 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in