JS implementation of the Method of Equal Shares with cost utilities and Add1U completion, including a pabulib file parser

mes.js

// usage: node mes.js <path-to-pb-file>

const fs = require('fs');
const readline = require('readline');

function parsePBFile(filePath) {
    return new Promise((resolve, reject) => {
        const meta = {};
        const projects = {};
        const votes = {};
        const approvers = {};
        let section = "";
        let header = [];

        const rl = readline.createInterface({
            input: fs.createReadStream(filePath),
            crlfDelay: Infinity
        });

        let isHeaderRow = false; 

        rl.on('line', (line) => {
            const row = line.split(';');
            if (['meta', 'projects', 'votes'].includes(row[0].trim().toLowerCase())) {
                section = row[0].trim().toLowerCase();
                isHeaderRow = true; // read next line as header
                return;
            }

            if (isHeaderRow) {
                header = row;
                isHeaderRow = false;
                return;
            }

            if (section === "meta") {
                meta[row[0]] = row[1].trim();
            } else if (section === "projects") {
                projects[row[0]] = {};
                for (let it = 0; it < header.length; it++) {
                    projects[row[0]][header[it].trim()] = row[it].trim();
                }
            } else if (section === "votes") {
                votes[row[0]] = {};
                for (let it = 0; it < header.length; it++) {
                    votes[row[0]][header[it].trim()] = row[it].trim();
                }
                const voterId = row[0];
                const voteIndex = header.findIndex(item => item.trim().toLowerCase() === 'vote');
                if (voteIndex === -1) return; // Skip if the "vote" field is not found
                const projectIds = row[voteIndex].split(',');
                projectIds.forEach(projectId => {
                    if (!approvers[projectId]) {
                        approvers[projectId] = [];
                    }
                    approvers[projectId].push(voterId);
                });
            }
        });

        rl.on('close', () => {
            resolve({ meta, projects, votes, approvers });
        });
    });
}

function sum(xs) {
    return xs.reduce((a, b) => a + b, 0);
}

function equal_shares_fixed_budget(N, C, cost, approvers, B) {
    let budget = {};
    for (let i of N) {
        budget[i] = B / N.length;
    }
    let remaining = new Map(); // remaining candidate -> previous effective vote count
    for (let c of C) {
        if (cost[c] > 0 && approvers[c].length > 0) {
            remaining.set(c, approvers[c].length);
        }
    }
    let committee = [];
    while (true) {
        let best = null;
        let best_eff_vote_count = 0;
        let best_max_payment = Infinity;
        // go through remaining candidates in order of decreasing previous effective vote count
        let remaining_sorted = [...remaining.keys()];
        remaining_sorted.sort((a, b) => remaining.get(b) - remaining.get(a));
        for (let c of remaining_sorted) {
            let previous_eff_vote_count = remaining.get(c);
            if (previous_eff_vote_count < best_eff_vote_count) {
                // c cannot be better than the best so far
                break;
            }
            if (sum(approvers[c].map(i => budget[i])) < cost[c]) {
                // c is not affordable
                remaining.delete(c);
                continue;
            }
            // calculate the effective vote count of c, which involves splitting the cost of c as equally as possible among its approvers
            approvers[c].sort((a, b) => budget[a] - budget[b]);
            let paid_so_far = 0;
            let denominator = approvers[c].length; // this will be the number of approvers who can afford the max payment
            for (let j = 0; j < approvers[c].length; j++) {
                let i = approvers[c][j];
                let max_payment = (cost[c] - paid_so_far) / denominator; // payment if remaining approvers pay equally
                let eff_vote_count = cost[c] / max_payment;
                if (max_payment > budget[i]) {
                    // i cannot afford the max payment, so pays entire remaining budget
                    paid_so_far += budget[i];
                    denominator -= 1;
                } else {
                    // i (and all later approvers) can afford the max payment; stop here
                    remaining.set(c, eff_vote_count);
                    if (eff_vote_count > best_eff_vote_count) {
                        best_eff_vote_count = eff_vote_count;
                        best_max_payment = max_payment;
                        best = c;
                    }
                    break;
                }
            }
        }
        if (!best) {
            break;
        }
        committee.push(best);
        for (let i of approvers[best]) {
            budget[i] = budget[i] - Math.min(budget[i], best_max_payment);
        }
        remaining.delete(best);
    }
    return committee;
}

function equal_shares(N, C, cost, approvers, B) {
    // Method of Equal Shares with Add1U completion
    // Input:
    //   N: list of voters
    //   C: list of candidates
    //   cost[c]: cost of candidate c
    //   approvers[c]: list of voters who approve candidate c
    //   B: budget
    // Output:
    //   committee: list of candidates
    let mes = equal_shares_fixed_budget(N, C, cost, approvers, B);
    let budget = B;
    while (true) {
        // is current outcome exhaustive?
        let is_exhaustive = true;
        for (let extra of C) {
            if (!mes.includes(extra) && sum(mes.map(c => cost[c])) + cost[extra] <= B) {
                is_exhaustive = false;
                break;
            }
        }
        if (is_exhaustive) {
            break;
        }
        // would the next highest budget work?
        let new_budget = budget + N.length;
        let next_mes = equal_shares_fixed_budget(N, C, cost, approvers, new_budget);
        if (sum(next_mes.map(c => cost[c])) <= B) {
            budget = new_budget;
            mes = next_mes;
        } else {
            break;
        }
    }
    // in case there is remaining budget, add the next most popular projects
    let sorted_C = [...C];
    sorted_C.sort((a, b) => approvers[b].length - approvers[a].length);
    for (let extra of sorted_C) {
        if (!mes.includes(extra) && sum(mes.map(c => cost[c])) + cost[extra] <= B) {
            mes.push(extra);
        }
    }
    return mes;
}

const filePath = process.argv[2];
parsePBFile(filePath).then(data => {
    const N = Object.keys(data.votes);
    const C = Object.keys(data.projects);
    const cost = Object.fromEntries(C.map(c => [c, parseInt(data.projects[c].cost)]));
    const B = parseInt(data.meta.budget);
    console.log("number of voters: " + N.length + ", number of projects: " + C.length + ", budget: " + B);

    const result = equal_shares(N, C, cost, data.approvers, B);
    console.log(result);

    // compute the total cost of the result
    let total_cost = 0;
    for (let c of result) {
        total_cost += cost[c];
    }
    console.log("Total cost: " + total_cost);
}).catch(error => console.error(error));