Federated Assemblies
Authors: Daniel Halpern, Ariel D. Procaccia, Ehud Shapiro, Nimrod Talmon
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our results are primarily positive, showing that achieving various properties together is indeed tractable. We begin by considering only the first two properties, individual representation and ex ante representation of child assemblies (Section 3). We design a simple algorithm (Algorithm 1) that is able to achieve both of these properties. Next, we throw ex post child representation into the mix (Section 4). This makes the problem much more challenging, so we focus on instances with additional structure. ... Finally, in Section 5, we implement an algorithm based on column generation for convex programming, which, given any instance of our problem, computes a distribution satisfying the three properties. In addition to measuring the running time of the algorithm, our empirical results suggest that all of our properties can be achieved simultaneously in the general case, at least in practice. ... Results. Of the 6400 instances, on all but 15, the algorithm terminated, returning an optimal solution. |
| Researcher Affiliation | Academia | Daniel Halpern 1, Ariel D. Procaccia 1, Ehud Shapiro 2,3 Nimrod Talmon 4 1Harvard University 2Weizmann Institute of Science 3London School of Economics 4Ben-Gurion University EMAIL, EMAIL, EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1: Selection algorithm with ex ante child representation guarantees; Algorithm 2: Selection algorithm for laminar instances with ex post child representation guarantees; Algorithm 3: Algorithm for semi-laminar instances |
| Open Source Code | No | The paper does not provide concrete access to its source code. It mentions using Gurobi for optimizations but does not state that the code implementing their algorithms or experimental setup is publicly available. |
| Open Datasets | No | To sample instances, we first fix a number of equivalence classes (2, 5, 10, or 20) and sample their relative sizes from an exponential distribution. Next, we iterate through a number of federations (2, 5, 10, or 20). Each federation has a randomly selected set of already defined federations or equivalence classes as children. This method allows for arbitrary DAGs to be sampled. |
| Dataset Splits | No | The paper describes generating synthetic problem instances for evaluation (e.g., 'sample several thousand instances', '100 instances for each combination of parameters'). It does not refer to a single dataset that is split into training, validation, or test sets. |
| Hardware Specification | Yes | All optimizations were solved using Gurobi on an Amazon Web Services (AWS) instance with 128 v CPUs of a 3rd Gen AMD EPYC running at 3.6GHz equipped with 1TB of RAM. |
| Software Dependencies | No | The paper mentions using 'Gurobi' for optimizations but does not provide a specific version number for this software or any other software dependencies. |
| Experiment Setup | Yes | To sample instances, we first fix a number of equivalence classes (2, 5, 10, or 20) and sample their relative sizes from an exponential distribution. Next, we iterate through a number of federations (2, 5, 10, or 20). Each federation has a randomly selected set of already defined federations or equivalence classes as children. This method allows for arbitrary DAGs to be sampled. We then test these instances with various assembly sizes n (2, 5, 10, or 20). For each combination of parameters, we sampled and ran 100 instances. |