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,

• member 0 likes items 0 and 1,
• member 1 likes items 0 and 3, and
• member 2 likes items 0 and 1 (zero-indexed).

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

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

• speed.py measures the speed of FAPE (Section 4.2).
• evaluate_baselines.py evaluates the baseline methods (Section 4.3).
• evaluate_ours.py evaluates FAPE (Section 4.3).

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},
}