5
$\begingroup$

First of all, I preemptively apologize if my question happens to be naive, I am no expert of CGT (or general game theory, for that matter).

Now the question:

**is there such a thing as the study of resource-aware combinatorial games?

By this I mean the following: there are two players, each with an assigned amount of resources (say a heap of money).

The two players play a game in the sense of CGT, but each move is preassigned a cost. A player loses iff he loses in the standard sense (gets to some terminal state) OR he/she runs out of money. Using the graph terminology, this would amount to playing on a weighted graph, the weight being the cost of that particular move**

NOTE: If I remember correctly, there has been some work on categorical CGT, and even on game semantics for resource-aware logics (Linear Logic and the like), so I would think that the scenario I informally described has been envisioned. If so, I would appreciate any pointers you may have.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Something like that is mentioned in Winning Ways, Vol. I, in the context of nimbers, if I remember correctly. I think that these games can be reduced to ordinary games. $\endgroup$
    – Martin Brandenburg
    Commented Jun 17, 2012 at 19:24
  • $\begingroup$ Thanks Martin! I will take a look at it. If the reduction procedure is indeed possible, I would be interested in knowing what is the price for the reduction in terms of complexity (measured, say, by the amount of states). In other terms, let us say I have a cost-aware finite game G_0 and I transform it in another cost-free finite game G_1. How much more complex is G_1? $\endgroup$
    – Mirco A. Mannucci
    Commented Jun 17, 2012 at 19:34
  • 1
    $\begingroup$ If each move has a fixed cost, and we represent games by trees, then we can represent the cost-free version by a simpler tree: just delete those nodes on the game tree which force some player to have negative money. If we represent the game by a graph, instead, this gets trickier, and I think the cost-free version might become more complex, but I'm not sure. $\endgroup$
    – Noah Schweber
    Commented Jun 17, 2012 at 20:06
  • 1
    $\begingroup$ Just to clarify: the resources spent on moves are removed from the game? I'm asking because there is also the related version in which they go to the opponent, so that you can actually regain resources (and they don't a priori limit they number of moves). $\endgroup$
    – Klaus Draeger
    Commented Jun 18, 2012 at 13:10
  • $\begingroup$ @Klaus: yes, the games I was interested in are the ones where resources are moved from the table (to confess the truth, I am thinking of those games to model something else). However, your question is pertinent, because in real life most money games simply move money between players. I would think modeling those game is harder, but maybe I am wrong. $\endgroup$
    – Mirco A. Mannucci
    Commented Jun 19, 2012 at 10:32

1 Answer 1

Reset to default
1
$\begingroup$

By including both players' money into the state of the game, you can analize it using some tools in combinatorial game theory, specifically partizan game tools: even if the original game would naturally be a symmetric game, including both players' money inevitably breaks its symmetry except for a handful of positions, so I would suggest symmetric games aren't the ones you are looking for (so Nim and the theory of nimbers would be of little use).

For a practical example (but maybe too elementary to be useful), you can have a look at this game and its analysis, I think it fits into the kind of games you could be interested into.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Grazie Lorenzo! $\endgroup$
    – Mirco A. Mannucci
    Commented Jul 14, 2012 at 22:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .