Home

Awesome

Enumerating Fair Packages for Group Recommendations (WSDM 2022)

We proposed an efficient method to enumerate all fair packages with respect to envy-freeness and proportionality.

Paper: https://arxiv.org/abs/2105.14423

💿 Installation

$ pip install fape

💡 How to Use

This package is compatible with graphillion and SAPPOROBDD. Please install graphillion via

$ pip install graphillion

Basic Usage

fape.construct_zdd constructs ZDD and outputs a ZDD string.

import fape
import numpy as np
from graphillion import setset

m = 3
n = 4
R = np.array([
    [10.0, 20.0, 5.0, 5.0],
    [10.0, 5.0, 5.0, 30.0],
    [10.0, 20.0, 5.0, 5.0],
]) # 3 members x 4 itmes

zdd_string = fape.construct_zdd(
    R,
    package_size=2,
    tau=3,
    criterion='proportionality',
    delta=0.5
)
setset.set_universe([i for i in range(n)])
ss = setset(setset.loads(zdd_string))
for r in ss:
    print(r)
# {0, 1}
# {0, 2}
# {0, 3}
# {1, 3}

weight = {
    i: R[:, i].mean() for i in range(n)
}
for r in ss.max_iter(weight):
    print(r)
    break
# {1, 3}

In this example, delta = 0.5 means that each member likes the items with top talf ratings. Namely,

tau = 3 means that three members (i.e., all members) should be satisfied. fape.construct_zdd enumerates such packages. There are qualified four packages, {0, 1}, {0, 2}, {0, 3}, and {1, 3}.

weight is a dictionary that stores the average preference of each item. max_iter iterates packages in the descreasing order of weights. In this example, package {1, 3} has the largest weight.

A graphillion.setset.setset supports various operations, including union (|) and intersection (&). Please refer to the document of graphillion for more details.

📝 Results

Dataset<br>MetricMovieLens<br>ProportionalityMovieLens<br>EnvyfreenessMovieLens<br>PreferenceMovieLens<br>TotalScoreAmazon<br>ProportionalityAmazon<br>EnvyfreenessAmazon<br>PreferenceAmazon<br>TotalScore
Averanking1.000 ± 0.0000.725 ± 0.1560.911 ± 0.0272.636 ± 0.1711.000 ± 0.0000.500 ± 0.1250.939 ± 0.0122.439 ± 0.126
LMRanking0.988 ± 0.0370.588 ± 0.1680.876 ± 0.0362.451 ± 0.1880.912 ± 0.2630.425 ± 0.1390.924 ± 0.0312.261 ± 0.373
GreedyVar0.912 ± 0.0800.750 ± 0.1120.812 ± 0.0352.474 ± 0.1570.787 ± 0.2020.637 ± 0.0880.859 ± 0.0312.284 ± 0.287
GreedyLM0.950 ± 0.0610.775 ± 0.1090.813 ± 0.0362.538 ± 0.1550.662 ± 0.1590.600 ± 0.0940.853 ± 0.0312.115 ± 0.249
GFAR0.950 ± 0.0610.762 ± 0.1040.812 ± 0.0382.525 ± 0.1540.762 ± 0.1420.650 ± 0.0750.871 ± 0.0252.284 ± 0.219
SPGreedy1.000 ± 0.0000.525 ± 0.1560.851 ± 0.0412.376 ± 0.1671.000 ± 0.0000.375 ± 0.0790.867 ± 0.015,2.242 ± 0.085
EFGreedy0.925 ± 0.1271.000 ± 0.0000.792 ± 0.0532.717 ± 0.1650.750 ± 0.2440.838 ± 0.0800.854 ± 0.0272.441 ± 0.302
FAPE(ours, exact)1.000 ± 0.0001.000 ± 0.0000.888 ± 0.0372.888 ± 0.0371.000 ± 0.0000.912 ± 0.0570.913 ± 0.0202.825 ± 0.064
FAPE(ours, 10th)1.000 ± 0.0001.000 ± 0.0000.887 ± 0.0372.887 ± 0.0371.000 ± 0.0000.912 ± 0.0570.911 ± 0.0202.824 ± 0.064
FAPE(ours, 100th)1.000 ± 0.0001.000 ± 0.0000.881 ± 0.0402.881 ± 0.0401.000 ± 0.0000.900 ± 0.0500.905 ± 0.0252.805 ± 0.058
FAPE(ours, random)1.000 ± 0.0001.000 ± 0.0000.720 ± 0.0442.720 ± 0.0441.000 ± 0.0000.912 ± 0.0570.878 ± 0.0232.790 ± 0.069

Please refer to the paper for more details.

🧪 How to Reproduce

Dependency of python scripts

Please install graphillion and surprise via pip install graphillion scikit-surprise

Data

You can download and preprocess data by the following command. It may take time. Please use only MovieLens 100k/1m if it takes too much time.

$ bash download.sh

100k.npy, 1m.npy, 10m.npy, 20m.npy, and 25m.npy are variants of the MovieLens dataset. home_and_kitchen.npy is the Amazon dataset.

Evaluation Scripts

Citation

@inproceedings{sato2022enumerating,
  author    = {Ryoma Sato},
  title     = {Enumerating Fair Packages for Group Recommendations},
  booktitle = {Proceedings of the Fifteenth {ACM} International Conference on Web Search and Data Mining, {WSDM}},
  year      = {2022},
}