Optimizing for strategy diversity in the design of video games

• 成果类型: Article; Early Access
• 署名作者: Hanguir, Oussama; Ma, Will; Han, Jiangze; Ryan, Christopher Thomas
• 署名单位: Columbia University; Columbia University; University of British Columbia
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02126-8
• 发表日期: 2024

摘要

We consider the problem of designing a linear program that has diverse solutions as the right-hand side varies. This problem arises in video game settings where designers aim to have players use different weapons or tactics as they progress. We model this design question as a choice over the constraint matrix A and cost vector c to maximize the number of possible supports of unique optimal solutions (what we call loadouts) of Linear Programs max{c inverted perpendicular x divided by Ax <= b,x >= 0}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\max \{c<^>\top x \mid Ax \le b, x \ge 0\}$$\end{document} with nonnegative data considered over all resource vectors b. We provide an upper bound on the optimal number of loadouts and provide a family of constructions that have an asymptotically optimal number of loadouts. The upper bound is based on a connection between our problem and the study of triangulations of point sets arising from polyhedral combinatorics, and specifically the combinatorics of the cyclic polytope. Our asymptotically optimal construction also draws inspiration from the properties of the cyclic polytope.