Modeling market coverage in all-or-nothing scenarios with multiple service categories

modelServices.js

////////////////////////////////////////////////////////////////////////////////
// Array helpers
const sum = arr => arr.reduce((a, b) => a + b, 0);

const mul = arr => arr.reduce((a, b) => a * b, 1);

const normalize = arr => {
    const s = sum(arr);
    return arr.map(x => x / s);
};

const newArray = (n, x = 0) => [...new Array(n)].map(() => x);

////////////////////////////////////////////////////////////////////////////////
// Distributions
const uniform = n => normalize(
    newArray(n, 1)
);

const geometric = (n, ratio) => normalize(
    newArray(n).map((_, i) => Math.pow(ratio, i))
);

////////////////////////////////////////////////////////////////////////////////
// Solvers
class GreedySolver {
    constructor({ world, implemented }) {
        this._world = world;
        this._implemented = implemented || newArray(world.length, 0);
        this._covered = this._implemented.map((imp, i) => {
            return sum(this._world[i].slice(0, imp));
        });
    }

    implementNext() {
        for (let i = 0; i < this._implemented.length; ++i) {
            if (this._covered[i] === 0) {
                this._covered[i] += this._world[i][this._implemented[i]];
                ++this._implemented[i];
                return;
            }
        }

        let best = 0;
        let bestPotentialCover = 0;
        for (let i = 0; i < this._implemented.length; ++i) {
            if (this._implemented[i] < this._world[i].length) {
                let potentiallyCovered = this._covered[i] + this._world[i][this._implemented[i]];
                for (let j = 0; j < this._world.length; ++j) {
                    if (j !== i) {
                        potentiallyCovered *= this._covered[j];
                    }
                }
                if (potentiallyCovered > bestPotentialCover) {
                    bestPotentialCover = potentiallyCovered;
                    best = i;
                }
            }
        }

        this._covered[best] += this._world[best][this._implemented[best]];
        ++this._implemented[best];
    }

    covered() {
        return mul(this._covered);
    }
}

const printSolution = ({ world, implemented }) => {
    const solver = new GreedySolver({ world, implemented });

    while (true) {
        const covered = solver.covered();
        console.log(covered);
    
        if (covered === 1) {
            break;
        }
    
        solver.implementNext();
    }        
}


////////////////////////////////////////////////////////////////////////////////
// Models

// 7 categories, each with 5 uniformly distributed services
// Users pick exactly one of each category
console.log('== Uniform (1 of each) ==');
printSolution({
    world: [
        uniform(5),
        uniform(5),
        uniform(5),
        uniform(5),
        uniform(5),
        uniform(5),
        uniform(5)
    ]
});

// 7 categories, each with 5 geometrically distributed services
// Users pick exactly one of each category
console.log('== Geometric (1 of each) ==');
printSolution({
    world: [
        geometric(5, 1/2),
        geometric(5, 1/2),
        geometric(5, 1/2),
        geometric(5, 1/2),
        geometric(5, 1/2),
        geometric(5, 1/2),
        geometric(5, 1/2)
    ]
});

// 7 categories, each with 5 geometrically distributed services
// Users pick at most one of each category
console.log('== Geometric (0/1 of each) ==');
printSolution({
    world: [
        geometric(6, 1/2),
        geometric(6, 1/2),
        geometric(6, 1/2),
        geometric(6, 1/2),
        geometric(6, 1/2),
        geometric(6, 1/2),
        geometric(6, 1/2)
    ],
    implemented: [1, 1, 1, 1, 1, 1, 1]
});