The python scripts under this folder address random voting games using our quantum algorithm to estimate the Shapley value of each player. The scripts also perform some basic data analysis on the predictions. A summary of the code and the results is shown below.
import quantumBasicVotingGame as vg
from quantumShapEstimation import QuantumShapleyWrapper as qsw
import numpy as np
import matplotlib.pyplot as plt
import pickle
from tqdm.auto import tqdm
numTrails = 32
maxEll = 7
#Defining the different conditions
numPlayersCond = [4,8,12]
thresholdBitCond = [4,5,6]
roughVarianceCond = [1,2,2]
simulations = {}
for trialNum in tqdm(range(numTrails), desc="Current Trial"):
for ell in tqdm(range(1,maxEll), desc="Current Ell"):
for n, thresholdBits, roughVariance in zip(
numPlayersCond, thresholdBitCond, roughVarianceCond
):
trial = (n,ell,trialNum)
#New random game
threshold = 2**(thresholdBits-1)
playerVals = vg.randomVotingGame(
numPlayers=n,
thresholdBits=thresholdBits,
roughVariance=roughVariance
)
#quantum Shapley
qshaps = vg.quantumVotingShap(
threshold=threshold,
playerVals=playerVals,
ell=ell
)
#classical Shapley
cshaps = vg.classicalVotingShap(
threshold=threshold,
playerVals=playerVals,
)
#Store outcome
simulations[trial] = (qshaps, cshaps)
with open('shapleyVoteResults.pkl', 'wb') as f:
pickle.dump(simulations, f)
def meanAbsError(qshaps, cshaps):
err = 0
for qshap, cshap in zip(qshaps, cshaps):
err += abs(qshap-cshap)
return err
plt.rcParams['figure.figsize'] = [12, 5]
fig, ax = plt.subplots(1, len(numPlayersCond))
#We're looking to find reciprocal mean abs error per trial
#For each trial with n players
for i, n in enumerate(numPlayersCond):
#Orient data
resultsX = []
resultsY = []
resultErr = []
for ell in range(1, maxEll):
trialOutcomes = []
for trialNum in range(numTrails):
qshaps, cshaps = simulations[(n,ell,trialNum)]
trialOutcomes.append(
meanAbsError(qshaps, cshaps)
)
trialOutcomes = np.array(trialOutcomes)
resultsX.append(ell)
resultsY.append(trialOutcomes.mean())
resultErr.append(trialOutcomes.std())
# resultsX += len(trialOutcomes) * [ell]
# resultsY += trialOutcomes
ax[i].set_title(f"{n} Players")#, Threshold: {2**thresholdBitCond[i]}")
ax[i].bar(
np.array(resultsX),
1/np.array(resultsY),
# yerr=resultErr,
align='center',
alpha=0.5,
ecolor='black',
capsize=10,
)
ax[i].set_xlabel(r"$\ell$")
ax[i].set_ylabel(r"Reciprocal Mean Absolute Error")
plt.tight_layout()
plt.show()
The code has been tested using the following set of libraries and requirements:
- Python 3.9.2
- IPython 8.14.0
- ipykernel 6.25.0
- ipywidgets 8.1.0
- jupyter_client 8.3.0
- jupyter_core 5.3.1
- jupyter_server 2.7.0
- jupyterlab 4.0.4
- nbclient 0.8.0
- nbconvert 7.7.3
- nbformat 5.9.2
- notebook 7.0.1
- qtconsole 5.4.3
- traitlets 5.9.0
- numpy 1.25.2
- matplotlib 3.7.2
- qiskit 0.44.0
- tqdm 4.65.0
- qiskit aer-0.12.2
Additionally, the following tutorial for amplitude estimation was used as a framework: https://qiskit.org/ecosystem/finance/tutorials/00_amplitude_estimation.html
If using this code for research purposes, please cite:
Iain Burge, Michel Barbeau and Joaquin Garcia-Alfaro. Quantum Algorithms for Shapley Value Calculation. 2023 IEEE International Conference on Quantum Computing and Engineering (QCE 2023), Bellevue, WA, United States, September 17-22, 2023.
@inproceedings{burge-barbeau-alfaro2023Shapley,
title={Quantum Algorithms for Shapley Value Calculation},
author={Burge, Iain and Barbeau, Michel and Garcia-Alfaro, Joaquin},
booktitle={2023 IEEE International Conference on Quantum Computing and Engineering (QCE 2023), Bellevue, WA, United States, September 17-22, 2023},
pages={1--9},
year={2023},
month={September},
}