CoCalc -- 2017-11-14-214710.sagews

Maximizing the cost of bringing participation to zero, simple game

Path: 2017-11-14-214710.sagews

Views: ²³


if True:
    print "Now, we will consider Alice's participation the following game, for which she must place a deposit of size D to participate and which is repeated for N rounds\n\n"


    print ""
    print "______|______Bob________| "
    print "  |   |____C___|____F___|"
    print " A| C |____0___|_-D_i*P_|"
    print "__|_F_|_-D_i*P_|_-D_i*P_|"
    print ""

    print "Any outcome where either Alice or Bob plays F is called `faulty'"
    print "D_i denotes the total amount of deposits that Alice has remaining at the start of round i"
    print "We insist that D_0 = D, the amount that Alice places on deposit, and D_i = (1 - P)*D_(i-1) if round i-1 was faulty."
    print "For participating in the game, Alice is compensated a reward of R."


    print "\n\nVariables\nr: required rate of return\nD: deposit/participation amount\nR: participation reward \nP: proportional penalty for faulty round\nq: perceived rate of Byzantine faults (successful participation for honest players)\nN: number of rounds\n\n\n"

    print "First, for Linear Utility: \n U(x) = x\n"
    print "Alice has an expected utility of choosing strategy C:"
    print "E[U(payoff|choose C)] = E(X ~ penalties)[U(R - X)]"
    print "              = U(R) + E(C ~ penalties)[U(-X)]"
    print "              = R - E(X ~ penalties)[X]"
    print "              = R - E(X ~ binomial(q,N))[D - D*(1-P)^X]"
    print "              = R - D + D*E(X ~ binomial(q,N))[(1-P)^X]"


    print "\n Now recall that the moment generating function of the binomial distribution is:"
    print "M(t) = E(X ~ binomial(q,N))[exp(tX)] = (1 - q + qe^t)^N"
    print "\n So,"
    print "M(ln(1-P)) = E(X ~ binomial(q,N))[exp(ln(1-P)*X)]"
    print "           = E(X ~ binomial(q,N))[exp(ln(1-P))^X]"
    print "           = E(X ~ binomial(q,N))[(1-P)^X]"
    print "\n And,"
    print "M(ln(1-P)) = (1 - q + qe^ln(1-P))^N"
    print "           = (1 - q + q(1-P))^N"
    print "           = (1 - qP)^N"
    print "\n Therefore\n"
    print "E(X ~ binomial(q,N))[(1-P)^X] = (1 - qP)^N"
    print "\n And"
    print "E[U(C)] = R - D + D*(1 - qP)^N"


    print "\n So we will use the following equilibrium equation:\n"
    print "U(required return) = E[U(payoff|choose C)]"
    print "r*D == R - D + D*(1 - qP)^N\n"

    #E = r*D == R - D + D*(1 - q*P)^N

    print "\nSolving for D, we get"
    print "D == R/(r + 1 - (1 - q*P)^N)"
    print "\n The equilibrium deposit amount."



    print "\n Taking a moment to visualize the equilibrium deposit amount"
    print "The x-axis is P (penalty), y-axis is perceived rate of Byzantine faults, and z-axis deposit amount"


    var("x")
    for x in xrange(1):



        var("N", "r", "D", "R", "P", "q", "i", "C")

        reward = 1
        required_rate = 1
        num_rounds = 3#(x+1)**2

        print "\n Using r = ",  required_rate, ", R = ", reward, ", N = ", num_rounds


        #E = r*D == R - D + D*(1 - q*P)^N
        #E = E.substitute(R == reward, r == required_rate, N == num_rounds)
        #show(implicit_plot3d(E,(P,0,1),(q,0,1),(D,0,1)))


        D = R/(r + 1 - (1 - q*P)^N)

        #integral D dq for D > 0.6 = K/P

        #z = 1/(2 - (1-xy)^N)
        #z = 1/(2 - 1 + xy)
        #z = 1/(1 + xy)


        D = D.substitute(R == reward, r == required_rate, N == num_rounds)

        print "\n D:"

        D


        show(plot3d(D, (P, 0, 1),(q, 0, 1), (C, 0, 1)))


        print "Quadratic utility: "

        D = R/(r + 1 - (1 - q + q*(1-P)^0.5)^(2*N))

        #integral D dq for D > 0.6 = K/P

        #z = 1/(2 - (1-xy)^N)
        #z = 1/(2 - 1 + xy)
        #z = 1/(1 + xy)


        D = D.substitute(R == reward, r == required_rate, N == num_rounds)

        print "\n D:"

        D


        show(plot3d(D, (P, 0, 1),(q, 0, 1), (C, 0, 1)))

        print "Logarithmic utility: "


        D = R/(r + 1 - (1 - P)^(q*N))

        #integral D dq for D > 0.6 = K/P

        #z = 1/(2 - (1-xy)^N)
        #z = 1/(2 - 1 + xy)
        #z = 1/(1 + xy)


        D = D.substitute(R == reward, r == required_rate, N == num_rounds)

        print "\n D:"

        D


        show(plot3d(D, (P, 0, 1),(q, 0, 1), (C, 0, 1)))






        if False:

            print "\n\n\nintegral(D,q,0,1, algorithm='sympy') \n"

            #integral(D,q,0,1)

            print "\n\n\nWe want to maximize the cost of bringing participation to a minimum "
            print "In the worst case, Alice loses her whole deposit and gains reward R"
            print "So, to earn her required rate of rethurn, Alice must have"
            print "D(1+r) = R, or D = R/(1+r)"
            print "\n We will therefore sum the product of deposit amounts D until participation gets close to this minimum"
            print "and then multiply the participation rate over time by the penalty P"


            print "So, the cost of bringing participation to the minimum is: \n (P*D.substitute(q == i/10)).sum(i, 0, T), for some T\n"

            print "First showing the total sum of deposits over time"


            var("M", "Q")
            M = 25
            Q = 1000

            var("j")
            p = []
            for j in range(M+1): #P
                p.append([])
                for i in range(Q+1): #q
                    p[j].append(D.substitute(q==i/Q, P == j/M).n())



            #print p
            #C = (P*D.substitute(q == i/10)).sum(i, 0, 10)
            #C

            s = []
            e = []
            for j in range(M + 1): #P
                s.append(0)
                e.append([])
                for i in range(Q + 1): #q
                    if i != 0:
                        if p[j][i] >= 0.6:#1*reward/(1+required_rate):#*((1 + 0.01)**25 - 1)/(1 + 0.01)**25:
                            s[j] += p[j][i]
                            e[j].append(0)
                        else:
                            e[j].append(1)




            #for j in range(M + 1): #P
            #    print "P = ", j/M, ": \t", e[j]

            pts = []
            for j in range(M+1):
                pts.append((j/M, s[j]))
            show(points(pts, color='darkgreen', pointsize=50))


            print "\n\n\nNow looking to maximize the cost of attack by multiplying the above by P"

            print "Plotting the cost of attack against the penalty.\n Axes: y = C, x = P\n"



            pts = []
            for j in range(M+1):
                pts.append((j/M, j/M*s[j]))
            show(points(pts, color='darkgreen', pointsize=50))



if False:
    if False:
        if False:
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------
            #----------------------------------------------------------------------------------------------------------


            print "Now, we will consider Alice's participation the following game, for which she must place a deposit of size D to participate and which is repeated N times\n\n"


            print ""
            print "______|______B______| "
            print "  |   |__C___|__F___|"
            print " A| C |__R___|_-D*P_|"
            print "__|_F_|_-D*P_|_-D*P_|"
            print ""



            var("N", "r", "D", "R", "P", "q", "i", "C")

            print "Variables\nr: required rate of return\nD: deposit/participation amount\nR: return from successful participation\nP: proportional penalty for unsuccessful participation\nq: perceived rate of Byzantine faults (successful participation for honest players)\n\n\n"

            print "First, for Linear Utility: \n U(x) = x\n"
            print "Expected utility of returns:"
            print "R*N*(1-q) - (D - D*(1-P)^(N*q)) \n"

            print "Equilibrium equation:\n r*D == R*N*(1-q) - (D - D*(1-P)^(N*q))\n"


            #E = (P*R/r + r*D)^0.5 == (P*R/r + R)^0.5*(1-q) + (P*R/r - P*D)^0.5*q


            #E = U(r*D) == E_{X ~ returns}[U(X)]

            #E = U(r*D) == E_{Z ~ penalties}[U(R - Z)]

            #E = U(r*D) == E_{Z ~ penalties}[(P*R/r + R - Z)^0.5]

            # if Z' ~ bernoulli(q,N)
            # then Z ~ D - D*(1-P)^Z'

            # so
            # U(r*D) == E_{Z' ~ bernoulli(q,N)}[(P*R/r + R - (D - D*(1-P)^Z'))^0.5]

            # U(r*D) == E_{Z' ~ bernoulli(q,N)}[(P*R/r + R - (D - D*(1-P)^Z'))^0.5]


            # U(r*D) == Sum_{i = 0..N}[(P*R/r + R - (D - D*(1-P)^i))^0.5 * Choose(N, i) * q^i*(1-q)^(N-i)]


            E = P*R/r + r*D == add([(P*R/r + R - (D - D*(1-P)^i))*sage.arith.misc.binomial(25, i)^2*q^(2*i)*(1-q)^(2*(N-1)) for i in [0..25]])

            '''
            we want rate of return per period to be on the order of penalties per period
            lets target 0.1 per period, for our example
            so that means R = (1 + 0.1)^N - 1
            '''


            print "\nletting R = (1 + 0.1)^N - 1, r = R = (1 + 0.1)^N - 1\n"

            E = E.substitute(R == (1 + 0.01)^N - 1, r == (1 + 0.01)^N - 1)
            #E = E.substitute(R == 0, r == 0.01)

            '''
            we want rate of return per period to be on the order of penalties per period
            lets target 0.1 per period, for our example
            so that means R = (1 + 0.1)^N - 1
            '''


            print "\nletting R = (1 + 0.1)^N - 1, r = R = (1 + 0.1)^N - 1\n"

We want to maximize the cost of bringing p
            E = E.substitute(R == (1 + 0.01)^N - 1, r == (1 + 0.01)^N - 1)
            #E = E.substitute(R == 0, r == 0.01)

            print "\nletting N = 25\n"
            E = E.substitute(N == 25)
            E



            #show(implicit_plot3d(E,(P,0,1),(q,0,1),(D,0,3)))


            #print "Solving for D"

            #S = solve(E,D)
            #S

            #D = S[0].right().substitute(R == (1 + 0.01)^N - 1, r == (1 + 0.0)^N - 1)
            #D = S[0].right()


            print "D == ", D

            print "\nPlotting participation against penalties and fault rates.\n Axes: z = D, x = P, y = q\n"

            E
We want to maximize the cost of bringing p

            show(implicit_plot3d(E, (q, 0.01, 1),(P, 0.01, 0.99), (D, -10, 2)))


            var("M", "Q")
            M = 10
            Q = 10

            var("j")
            p = []
            for j in range(M+1): #P
                p.append([])
                for i in range(Q+1): #q
                    p[j].append(D.substitute(q==i/Q, P == j/M).n())


            print "Cost of bringing participation to zero: \n (P*D.substitute(q == i/10)).sum(i, 0, 10)\n"

            #print p
            #C = (P*D.substitute(q == i/10)).sum(i, 0, 10)
            #C




            s = []
            for j in range(M + 1): #P
                s.append(0)
                for i in range(Q + 1): #q
                    if i != 0:
                        if p[j][i] > R/r:
                            s[j] += p[j][i]

            print "Plotting the cost of attack against the penalty.\n Axes: y = C, x = P\n"

            pts = []
            for j in range(M+1):
                pts.append((j/M, s[j].n()))
            show(points(pts, color='darkgreen', pointsize=50))

            pts = []
            for j in range(M+1):
                pts.append((j/M, j/M*s[j].n()))
            show(points(pts, color='darkgreen', pointsize=50)) in no

Now, we will consider Alice's participation the following game, for which she must place a deposit of size D to participate and which is repeated for N rounds



______|______Bob________| 
  |   |____C___|____F___|
 A| C |____0___|_-D_i*P_|
__|_F_|_-D_i*P_|_-D_i*P_|

Any outcome where either Alice or Bob plays F is called `faulty'
D_i denotes the total amount of deposits that Alice has remaining at the start of round i
We insist that D_0 = D, the amount that Alice places on deposit, and D_i = (1 - P)*D_(i-1) if round i-1 was faulty.
For participating in the game, Alice is compensated a reward of R.


Variables
r: required rate of return
D: deposit/participation amount
R: participation reward 
P: proportional penalty for faulty round
q: perceived rate of Byzantine faults (successful participation for honest players)
N: number of rounds



First, for Linear Utility: 
 U(x) = x

Alice has an expected utility of choosing strategy C:
E[U(payoff|choose C)] = E(X ~ penalties)[U(R - X)]
              = U(R) + E(C ~ penalties)[U(-X)]
              = R - E(X ~ penalties)[X]
              = R - E(X ~ binomial(q,N))[D - D*(1-P)^X]
              = R - D + D*E(X ~ binomial(q,N))[(1-P)^X]

 Now recall that the moment generating function of the binomial distribution is:
M(t) = E(X ~ binomial(q,N))[exp(tX)] = (1 - q + qe^t)^N

 So,
M(ln(1-P)) = E(X ~ binomial(q,N))[exp(ln(1-P)*X)]
           = E(X ~ binomial(q,N))[exp(ln(1-P))^X]
           = E(X ~ binomial(q,N))[(1-P)^X]

 And,
M(ln(1-P)) = (1 - q + qe^ln(1-P))^N
           = (1 - q + q(1-P))^N
           = (1 - qP)^N

 Therefore

E(X ~ binomial(q,N))[(1-P)^X] = (1 - qP)^N

 And
E[U(C)] = R - D + D*(1 - qP)^N

 So we will use the following equilibrium equation:

U(required return) = E[U(payoff|choose C)]
r*D == R - D + D*(1 - qP)^N


Solving for D, we get
D == R/(r + 1 - (1 - q*P)^N)

 The equilibrium deposit amount.

 Taking a moment to visualize the equilibrium deposit amount
The x-axis is P (penalty), y-axis is perceived rate of Byzantine faults, and z-axis deposit amount
x
(N, r, D, R, P, q, i, C)

 Using r =  1 , R =  1 , N =  3

 D:
1/((P*q - 1)^3 + 2)

3D rendering not yet implemented

Quadratic utility: 

 D:
-1/((sqrt(-P + 1)*q - q + 1)^6 - 2)

3D rendering not yet implemented

Logarithmic utility: 

 D:
-1/((-P + 1)^(3*q) - 2)

3D rendering not yet implemented

*** WARNING: Code contains non-ascii characters    ***


Error in lines 130-137
Traceback (most recent call last):
  File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1013, in execute
    exec compile(block+'\n', '', 'single') in namespace, locals
  File "<string>", line 1
    We want to maximize the cost of bringing p
          ^
SyntaxError: invalid syntax