Optimizing for strategy diversity in the design of video games: Designing optimization problems with diverse solutions: O. Hanguir et al.
Saved in:
| Title: | Optimizing for strategy diversity in the design of video games: Designing optimization problems with diverse solutions: O. Hanguir et al. |
|---|---|
| Authors: | Hanguir, Oussama1 (AUTHOR) oh2204@columbia.edu, Ma, Will2 (AUTHOR) wm2428@gsb.columbia.edu, Han, Jiangze3 (AUTHOR) jiangze.han@sauder.ubc.ca, Ryan, Christopher Thomas3 (AUTHOR) chris.ryan@sauder.ubc.ca |
| Source: | Mathematical Programming. Mar2025, Vol. 210 Issue 1, p335-376. 42p. |
| Subjects: | Video game design, Polyhedral combinatorics, Linear programming, Combinatorics, Point set theory |
| Abstract: | 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 ⊤ x ∣ A x ≤ b , x ≥ 0 } 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. [ABSTRACT FROM AUTHOR] |
| Copyright of Mathematical Programming is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| Abstract: | 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 ⊤ x ∣ A x ≤ b , x ≥ 0 } 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. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 00255610 |
| DOI: | 10.1007/s10107-024-02126-8 |
