Existence and computation of monomial families of near-optimal strategies for recursive games
In a finite recursive game in the sense of Everett, both players have stationary epsilon-optimal strategies for every epsilon>0. Frederiksen and Miltersen strengthened this result by showing that the strategies for all sufficiently small epsilon can be encoded by finitely many monomials: at every state, all but possibly one of the action probabilities are constants times integer powers of epsilon. The resulting finite symbolic object specifies a strategy for every sufficiently small accuracy. Their proof uses semialgebraic selection and Puiseux series. We give an alternative elementary proof…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.08017
curl -X POST /api/v1/records/arxiv/2608.08017/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.08017/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'