# Diner's Dilemma

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

$Pf_{D}=6P(0000)+8P(0010)+4P(0010)+4P(0011)+4P(0100)+4P(0101)+3P(0110)+3P(0111)+4P(1000)+4P(1001)+3P(1010)+3P(1011)+3P(1100)+3P(1101)+0P(1110)+1P(1111)$

(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 ]$ and $∣E⟩=[01 ]$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⟩$ where $(W,X,Y,Z)∈(0,1)$. Four states $∣C⟩$, $∣C⟩$, $∣C⟩$ and $∣C⟩$ are produced by identical sources. Initial state of the game is described by $∣ψ_{0}⟩=∣CCCC⟩$, where the first qubit is with Alice, second with Bob, third with Colin and fourth with Doug.

Then we define an operator,

$J^=2 1 (^I⊗I^⊗I^⊗I^+i(iσ_{y})⊗(iσ_{y})⊗(iσ_{y})⊗(iσ_{y})$

to create an entanglement, where $I^$ is an Identity and $σ_{y}$ is Pauli-Y operator. we apply the operator on $∣ψ_{0}⟩$, we get a final state as $∣ψ_{i}⟩$ where $∣ψ_{i}⟩=2 1 ∣0000⟩+i∣1111⟩$

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})=[e_{iΦ_{k}}cosθ_{k}/2−sinθ_{k}/2 sinθ_{k}/2e_{−iΦ}cosθ_{k}/2 ]$

where $θ_{k}∈[0,π]$,$ϕ_{k}∈[0,π/2]$ and $k∈(A,B,C,D)$. The three different operator that players apply are

$C^=U^(0,0)=[10 01 ]$

$E^=U^(π,0)=[0−1 10 ]$

$A^=U^(0,π/2)=[i0 0−i ]$

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

$∣ψ_{f}⟩=J^_{†}U_{A}^ ⊗U_{B}^ ⊗U_{C}^ ⊗U_{D}^ J^∣ψ_{0}⟩$

Payoff of Doug, $P(X_{A},X_{B},X_{C},X_{D})$ is the joint probability that final state of qubits with the players will collapse to $X_{A},X_{B},X_{C},X_{D}∈(C,E)$ on measuring $P=∣⟨X_{A},X_{B},X_{C},X_{D}∣ψ_{f}⟩∣_{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$ and $ϕ=0$ then the game reduces to local correlations and shows local correlations. However, it shows non local correlations if $ϕ =0$. We define three operators or quantum strategy $C^$, $E^$, and $A^$ where,$C^$ and $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^$) 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^$, $C^$, $C^$ and $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 $U_{3}$ gate with the parameters $(θ,ϕ,λ)=(π/2,π/2,−π/2)$, then a series of control-Z gates, and CNOT gates to construct the $J^$ operator. For different quantum strategy, we use $U_{3}$ operator with different parameters. For $C^$, we have $(θ,ϕ,λ)=(0,0,0)$, for $E^$ $(θ,ϕ,λ)=(π,π,π)$ and for $A^$ $(θ,ϕ,λ)=(0,−π/2,−π/2)$. After then we use $J^_{†}$ 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^$, $C^⊗C^⊗E^⊗A^$, $C^⊗C^⊗C^⊗E^$and $A^⊗A^⊗A^⊗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]