Diner's Dilemma

Published by strangeworks (04/09/2021)

Written by Bikash's Quantum for the Strangeworks platform.

Diner's dilemma is one of the most interesting problems in both economic and game theories. Here, we solve this problem for n (number of players) =4 with quantum rules and we are able to remove the dilemma of diners between the Pareto optimal and Nash equilibrium points of the game. We find the quantum strategy that gives maximum payoff for each diner without affecting the payoff and strategy of others. We use the quantum principles of superposition and entanglement that gives supremacy over any classical strategies. We present the circuit implementation for the game, design it on a quantum simulator and verify the strategies in the quantum model. 

Introduction

In  our  work,  we  solve  the  well-known  problem  in  game  theory  and  economic theory i.e. “Diner’s Dilemma” using quantum rules. We use two main features of quantum physics, such as entanglement and non-locality. By using the non-local correlations we gain an advantage over classical correlations. Since the game is non-cooperative (i.e. participants can’t interact with each other once the game has started) entanglement plays an important role in deciding their strategy. In 2004, Gneezy, Haruvy and Yafe did a social experiment entitled “The Inefficiency Of Splitting The Bill”, in which six individuals were made to dine together. They produce their results for four different cases. In  our  work,  we  solve  only  for one of the case with  four  participant  because this is the most interesting case in which participants face dilemma in deciding their strategy while placing the order. The setting of a game is such that they can order cheap food (denoted by C) or expensive food (denoted by E). Each participant is unaware of the order placed by the others. They can't  make any strategy for placing order depending on the strategy others are taking. According to the strategy taken, each players will then be awarded with the payoff value. The aim of the each players is to increase their individual payoff. 

Classical model

In classical model all 4  participants (Alice, Bob, Colin and Doug) have two options to order food, either cheap food or expensive food denoted by 0 and 1 respectively. There are total 16 possibilities (0000, 0001,.....,1111). Each of them are assigned a payoff value according to the strategy taken given in payoff table. From that table we form the payoff function of each players. The payoff of doug is given below

​​

(Ref. Fig1: Classical payoff table for diner's dilemma for n=4.)

where P(wxyz) means probability of selecting strategy w, x, y, z by A, B, C and D respectively and w, x, y, z = (C,E). Payoff of Alice, Bob, and Colin can be calculated similarly using classical payoff box. From the payoff box we can see that Nash equilibrium point(i.e 1111) and pareto optimal point (i.e 0000) does not  coincide with each other. Thus players are in dilemma in choosing their strategy and ends up with lowest payoff value i.e 1111.

Quantum model

In this work, we took two basis systems ∣C⟩=[10]|C\rangle=\left [{\begin{array}{c} 1 \\0 \end{array}}\right ]​ and ∣E⟩=[01]|E\rangle=\left [{\begin{array}{c} 0 \\1 \end{array}}\right ]​in the Hilbert space of a two level system i.e., qubit, the two possible outcomes of classical strategy C and E (cheap food and expensive food respectively). At any point, state of the game is described by a vector in the tensor product space which is spanned by the classical game basis ∣WXYZ⟩|WXYZ\rangle​ where (W,X,Y,Z)∈(0,1)(W,X,Y,Z) \in (0,1)​. Four states ∣C⟩|C\rangle​, ∣C⟩|C\rangle​, ∣C⟩|C\rangle​ and ∣C⟩|C\rangle​ are produced by identical sources. Initial state of the game is described by ∣ψ0⟩=∣CCCC⟩|\psi_0\rangle=|CCCC\rangle​, where the first qubit is with Alice, second with Bob, third with Colin and fourth with Doug. 

Then we define an operator,

J^=12(^I⊗I^⊗I^⊗I^+i(iσy)⊗(iσy)⊗(iσy)⊗(iσy)\hat{J}=\frac{1}{\sqrt{2}}(\hat{}{I}\otimes\hat{I}\otimes\hat{I}\otimes\hat{I} + i(i\sigma_y)\otimes (i\sigma_y)\otimes(i\sigma_y)\otimes(i \sigma_y)​​

to create an entanglement, where I^\hat{I}​ is an Identity and σy\sigma_y​ is Pauli-Y operator. we apply the operator on ∣ψ0⟩|\psi_0\rangle​, we get a final state as ∣ψi⟩|\psi_i\rangle​ where ∣ψi⟩=12∣0000⟩+i∣1111⟩|{\psi_i}\rangle=\frac{1}{\sqrt{2}}|{0000}\rangle + i|{1111}\rangle​​

we define the quantum strategies in the form of an operator. Instead of ordering a food now each player will apply an operator on his or her qubit which is given in the form of

U^(θK,ϕK)=[eiΦkcosθk/2sinθk/2−sinθk/2e−iΦcosθk/2]\hat{U}(\theta_K,\phi_K)=\left [{\begin{array}{cc} e^{i\Phi_k}cos\theta_k/2 & sin\theta_k/2 \\ -sin\theta_k/2 & e^{-i\Phi}cos\theta_k/2 \end{array}} \right ]

where θk∈[0,π]\theta_k\in[0,\pi]​,ϕk∈[0,π/2]\phi_k\in[0,\pi/2]​ and k∈(A,B,C,D)k\in(A,B,C,D)​. The three different operator that players apply are 

C^=U^(0,0)=[1001]\hat{C}= \hat{U}(0,0)=\left [{\begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array}} \right ]

E^=U^(π,0)=[01−10]\hat{E}= \hat{U}(\pi,0)=\left [{\begin{array}{cc} 0 & 1 \\ -1 & 0 \end{array}} \right ]

A^=U^(0,π/2)=[i00−i]\hat{A}= \hat{U}(0,\pi/2)=\left [{\begin{array}{cc} i & 0 \\ 0 & -i \end{array}} \right ]

After applying the operator we disentangle it and obtain the final state.

∣ψf⟩=J^†UA^⊗UB^⊗UC^⊗UD^J^∣ψ0⟩|\psi_f\rangle=\hat{J}^\dagger\hat{U_A}\otimes\hat{U_B}\otimes\hat{U_C}\otimes\hat{U_D} \hat{J}|\psi_0\rangle

Payoff of Doug, P(XA,XB,XC,XD)P(X_A,X_B,X_C,X_D)​ is the joint probability that final state of qubits with the players will collapse to XA,XB,XC,XD∈(C,E)X_A,X_B,X_C,X_D\in(C,E)​ on measuring P=∣⟨XA,XB,XC,XD∣ψf⟩∣2P=|\langle{X_A,X_B,X_C,X_D|\psi_f}\rangle|^2​. Here in our game, we have set of strategies for the entangled states whose has no counterparts in classical domain. If all the players choose to play with θ=0\theta=0​ and ϕ=0\phi=0​ then the game reduces to local correlations and shows local correlations. However, it shows non local correlations if ϕ≠0\phi \neq 0​. We define three operators or quantum strategy C^\hat{C}​, E^\hat{E}​, and A^\hat{A}​ where,C^\hat{C}​ and E^\hat{E}

​ are used to place the order for the cheap and expensive foods respectively. We then calculate the payoff value using payoff function for each players. Quantum payoff table is given below 

(Fig. 2: Quantum payoff table for diner's dilemma for n=4.). 

Here we can see that we have 8 pareto optimal point but only one Nash equilibrium point (i.e. by using strategy A^⊗A^⊗A^⊗A^\hat{A}\otimes\hat{A}\otimes\hat{A}\otimes\hat{A}​) which coincides with one of the pareto optimal point. Thus if the players use this strategy they will always end up having maximum payoff value. Therefore, by using this strategy they can remove the dilemma they were facing in classical model.

Quantum Circuits

#Generating a circuit of 4-qubit quantum and 4-qubit classical register
qc = QuantumCircuit(4, 4)

# creating an entanglement with 4 qubits 

qc.cx(0,1)
qc.cx(0,2)
qc.cx(0,3)
qc.u3(0.5*pi,0.5*pi,-0.5*pi,(0))
qc.cz(0,1)
qc.cz(0,2)
qc.cz(0,3)
qc.cx(0,1)
qc.cx(0,2)
qc.cx(0,3)

# applying operator as a strategy on 4 entangled qubits 
qc.u3(0,0,0,(0))
qc.u3(0,0,0,(1))
qc.u3(0,0,0,(2))
qc.u3(pi,pi,pi,(3))

# de-entanglement of the state

qc.cx(0,3)
qc.cx(0,2)
qc.cx(0,1)
qc.cz(0,1)
qc.cz(0,2)
qc.cz(0,3)
qc.u3(pi/2,-pi/2,pi/2,(0))
qc.cx(0,3)
qc.cx(0,2)
qc.cx(0,1)

# measurements of qubits in z basis
qc.measure([0,1,2,3], [0,1,2,3])
 
# get a Strangeworks backend
backend = get_backend("qasm_simulator")
# execute circuit
execute(qc, backend, shots=100)

Execution Results

After executing the circuit, 0001 with 100% probability is obtained (whose payoff is 4), for the case where the strategic operators C^\hat{C}​, C^\hat{C}​, C^\hat{C}​ and E^\hat{E}​are operated on the qubits q[0], q[1], q[2] and q[3] respectively.

For implementing the above game on the quantum simulator, we use different types of gates. For creating an entanglement we use U3U_3​ gate with the parameters (θ,ϕ,λ)=(π/2,π/2,−π/2)(\theta,\phi,\lambda)=(\pi/2,\pi/2,-\pi/2)​, then a series of control-Z gates, and CNOT gates to construct the J^\hat{J} operator. For different quantum strategy, we use U3U_3​ operator with different parameters. For C^\hat{C}​, we have (θ,ϕ,λ)=(0,0,0)(\theta,\phi,\lambda)=(0,0,0)​, for E^\hat{E}(θ,ϕ,λ)=(π,π,π)(\theta,\phi,\lambda)=(\pi,\pi,\pi)​ and for A^\hat{A}(θ,ϕ,λ)=(0,−π/2,−π/2)(\theta,\phi,\lambda)=(0,-\pi/2,-\pi/2)​. After then we use J^†\hat{J}^{\dagger}​ to break the entanglement and finally measure in Z-basis. In the circuit, q[0], q[1], q[2] and q[3] belong to Alice, Bob, Colin and Doug respectively. Here, we present the results obtained from the quantum simulator, for four out of the 81 strategies in the form of histograms. The first, second, third and fourth results are of strategies C^⊗E^⊗C^⊗E^\hat{C}\otimes\hat{E}\otimes\hat{C}\otimes\hat{E}​, C^⊗C^⊗E^⊗A^\hat{C}\otimes\hat{C}\otimes\hat{E}\otimes\hat{A}​, C^⊗C^⊗C^⊗E^\hat{C}\otimes\hat{C}\otimes\hat{C}\otimes\hat{E}​and A^⊗A^⊗A^⊗A^\hat{A}\otimes\hat{A}\otimes\hat{A}\otimes\hat{A}​ respectively.

References:

[1]. Amit Anand, Bikash K. Behera, and Prasanta K. Panigrahi, Solving Diner's Dilemma Game, Circuit Implementation and Verification on the IBM Quantum Simulator, [DOI: 10.13140/RG.2.2.28940.05765]