properties of a certain game

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

>-)
Posts: 527
Joined: Tue Apr 24, 2012 1:10 am UTC

properties of a certain game

this is a two player, zero-sum game.
the state is 2 vectors and two scalars (one vector and scalar per player).
call the vectors x and y and the scalars p and q respectively. x and y have some fixed dimension k. (and if it makes things easier, feel free to let k be infinite)
player 1 wins if p > 0 and q <= 0, and gets 1 reward (player 2 gets -1) and vice versa.

intuitively the idea is that x_0 (and also y_0) is the amount of resources that player 1 and 2 have
player 1 can spend x_0 to decrease q, since it wants to get q to 0
player 1 can also spend x_0 to increase x_1, which increases x_0 each time step -- or it can increase x_2, which increases x_1, which increases x_0
(the same goes for player 2)

formally:
at time t = 0, x_0(t) = y_0(t) = 1 and x_i(t) = y_i(t) = 0 for 1 <= i <= k
also at t = 0: p(t) = q(t) = 1

an action by either player is a positive k-dimensional vector.
call the action vectors a and b for player 1 and 2 respectively
then
x_i(t+1) = x_i(t) + x_{i+1}(t) + a_i(t) for 1 <= i <= k if we say x_{k+1} = 0
x_0(t+1) = x_0(t) + x_1(t) - sum(a(t))
p(t+1) = p(t) + min(a_0(t)-b_0(t), 0)
and all three of these rules hold similarly for player 2 (y). the only major difference is
q(t+1) = q(t) + min(b_0(t)-a_0(t), 0) . notice the swap of b and a
finally there is the constraint that a_i(t) >= 0 and sum(a(t)) < x_0(t) and the same goes for player 2

player 1 and 2 make their moves a(t) and b(t) simultaneously

so the question is what a winning strategy is, or if not that, if there is a nash equilibrium. actually i'd be happy with figuring out a merely "good" strategy
so far all i've determined is that at a_0(0) should be less than 1 --
otherwise player 2 if sets b_0(0) to be a small epsilon, player 2 will not immediately lose, while player 1 is stuck with x = 0 and cannot make any nonzero moves from then onwards

mfb
Posts: 948
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: properties of a certain game

An interesting game. Research first, conclusions towards the end.

The game is perfectly symmetric, I'll consider most things from the view of player 1 but of course it applies to both players. I'll call x_0 "attacking potential", x_1 "income" and a_0 "attacking strength".

Player 1 can force a win if p+x_0 > q + y_0 + 1 at any time.

sum(a_i(0))=1 loses against [b_i(0)=0 for all i and b_0(1)=1], which loses against a_0(0)=1, which loses against b_0(0)=epsilon. I guess the latter is useful independent of the rest. Assuming the opponent follows the epsilon-approach for attacking strength, the initial attacking power is not sufficient to win. I'll ignore the epsilon investments now, as I don't think they play a role in the following rounds.

You have to invest in x_1 or higher. Investing in x_1 at t=0 reduces your attacking potential at t=1, gets neutral at t=2 and only starts increasing it at t=3. The first serious attack can occur here, attacking before does't give any advantage. It also means you don't have to save anything at t=0, and at t=1 you don't invest anything.

Whatever you put in x_2 doesn't matter at t=3, so we get a first strategy to consider: "Attack at t=3", with a(0)=(0, 1, 0, ...), then do nothing, then use a(3)=(2,0,0,..).

The attack will be successful if y(3)<1. We can express this as y(3)=1+b_1(0)-b_3(0)-b_4(0)-... - sum(b(2)).
From t=1 on you know your opponent's strategy, so player 2 can stop investing. I'll drop all the (0) for readability. They survive the first attack if 0 < b_1-b_3-b_4 - ...
The game is not over yet, however. At t=4 player 1 will have an attacking potential of 1 again, so we get the additional constraint 1 < 2b_1+2b_2-b_4-b_5-... where 0,2,2,0 are coefficients of a row of Pascal's triangle minus 1 (the -1 is the investment).
t=5 leads to the inequality 2<3b_1+5b_2+3b_3 - b_5-b_6-... where 0,3,5,3,0 are the next row.

It is easy to find vectors that satisfy all these inequalities, and once you have an income of more than 1 you are done. Some investment in b_1 and b_2 does the job. I don't find nice general conditions (none of the inequalities is redundant). Something we can conclude from this, however: "Attack at t=3" loses against more balanced approaches, probably with decreasing b_i.

How to beat a more balanced approach? For every such approach we can make inequalities again. You win if you invest a little bit more into higher classes, but you lose if you do that too extreme.
If we ignore investments after t=0, this is a (multidimensional) rock-paper-scissors system. You lose against strategies that are much more aggressive, you win against strategies that are just a bit more aggressive, you lose against strategies that are a bit more long-term oriented, and you win against strategies that are much more long-term oriented. The Nash equilibrium is some randomized mixture of these strategies.

I wouldn't expect investments after t=0 to change this. If the difference in strategy between the players is too large, the game is basically done. If the strategy is extremely similar, you just have another rock-paper-scissors system. If there are just small differences, you get biased rock-paper-scissors, where the margins are smaller for one side.

How exactly to distribute the investments? No idea. Something like (eps,0.3+eps,0.4-2eps,0.15,0.075,...) is probably not a bad approach for an approach that survives "attack at t=3" and has a nice long-term growth.

>-)
Posts: 527
Joined: Tue Apr 24, 2012 1:10 am UTC

Re: properties of a certain game

thanks for the observations. i actually played a few test games against a friend yesterday and did notice the things you mention (though that may just be confirmation bias). hastily written code attached.

Spoiler:
in a spoiler tag, because the forum wouldn't let me attach any files for some reason

Code: Select all

`#!/usr/bin/env python2import osimport tracebackdef clear():    for i in range(100):        os.system('clear')            class Session:    def __init__(self, k = 4, d = 3):        self.k = k        self.d = d        self.x = [0.0 for i in range(k)]        self.y = [0.0 for i in range(k)]        self.x = 1.0        self.y = 1.0        self.p = 1.0        self.q = 1.0        self.go()    def step(self, a, b):        assert sum(a) <= self.x        assert sum(b) <= self.y        assert min(a) >= 0        assert min(b) >= 0        for i in range(self.k-1):            self.x[i] += self.x[i+1]            self.y[i] += self.y[i+1]        for i in range(1, self.k):            self.x[i] += a[i]            self.y[i] += b[i]                    self.x -= sum(a)        self.y -= sum(b)        self.p += min(0, a - b)        self.q += min(0, b - a)        self.p = round(self.p, self.d)        self.q = round(self.q, self.d)        for i in range(self.k):            self.x[i] = round(self.x[i], 1)            self.y[i] = round(self.y[i], 1)    def check(self):        if self.p < 0:            print 'player 2 wins'            return True        if self.q < 0:            print 'player 1 wins'            return True        return False    def go(self):        while not self.check():            raw_input("press to continue")            clear()            a = self.getturn('player 1\n')            b = self.getturn('player 2\n')            self.display()            try:                self.step(a,b)                print 'a : '+str(a)                print 'b : '+str(b)                self.display()            except Exception as e:                print 'illegal move made'                traceback.print_exc()                    def getturn(self, msg):        while 1:            try:                self.display()                s = raw_input(msg)                nums = []                for item in s.split(',')[:self.k]:                    if item.strip() == 'e':                        nums.append(0.1**self.d)                    else:                        nums.append(round(float(item), self.d))                clear()                return nums            except:                print 'parsing error -- try again'    def display(self):        print 'x : '+str(self.x)        print 'y : '+str(self.y)        print 'p : %f' % self.p        print 'q : %f' % self.qif __name__ == '__main__':    S = Session()`