Low-Distortion Social Welfare Functions
Authors: Gerdus Benadè, Ariel D. Procaccia, Mingda Qiao1788-1795
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our computational results demonstrate that it is practical to compute deterministic distortion-minimizing rankings for instances with up to 10 alternatives. This constraint on the instance size is not unreasonable, as 98.3% of Robo Vote instances have 10 or fewer alternatives. For larger instances we test several heuristics and find that the Borda and Kemeny rules typically lead to low distortion and near-optimal social welfare. |
| Researcher Affiliation | Academia | Gerdus Benad e Tepper School of Business Carnegie Mellon University Ariel D. Procaccia Computer Science Department Carnegie Mellon University Mingda Qiao Computer Science Department Stanford University |
| Pseudocode | No | The paper describes the construction of its social welfare function in text (e.g., "Sort the alternatives into a ranking ν such that score(ν(1)) score(ν(2)) score(ν(m)). Let tmax = log2 m and α = m ln m. Draw t uniformly at random from [tmax] and set m t = min ( 2tα , m). With probability 1/2, return a uniformly random permutation of [m]. Otherwise, shuffle the first m t elements of ν uniformly at random, and return the resulting ordering.") but does not present it in a formally structured pseudocode or algorithm block. |
| Open Source Code | No | The paper does not provide any statement or link indicating that source code for the described methodology is publicly available. |
| Open Datasets | No | The paper describes a synthetic data generation process for its experiments rather than using a predefined public dataset, stating: "Every alternative a is assigned a quality ca, and ui({a}) is drawn from a truncated normal distribution around ca. Vector ui = (ui({a}))a [m] induces σi. Weights wi are drawn uniformly at random in [0, 1], and ordered." |
| Dataset Splits | No | The paper describes how the synthetic data was generated for experiments but does not provide specific details on train/validation/test splits, such as percentages or sample counts. |
| Hardware Specification | Yes | Runtime (in seconds) for increasing instance size, on an a machine with an Intel Core i5-4200U CPU and 8 GB RAM. |
| Software Dependencies | No | The paper mentions the use of Gurobi 8.0.0 for solving the optimization problem, but it does not specify versions for other general software components or libraries beyond this specialized solver. |
| Experiment Setup | No | The paper describes the generation of synthetic data and the problem formulation but does not provide specific hyperparameter values or detailed system-level training settings. |