Manipulating Gale-Shapley Algorithm: Preserving Stability and Remaining Inconspicuous
Authors: Rohit Vaish, Dinesh Garg
IJCAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our contribution is threefold: First, we show that the matching induced by an optimal manipulation is stable with respect to the true preferences. Second, we identify a class of optimal manipulations called inconspicuous manipulations which, in addition to preserving stability, are also nearly identical to the true preference list of the manipulator (making the manipulation hard to be detected). Third, for optimal inconspicuous manipulations, we strengthen the stability result by showing that the entire stable lattice of the manipulated instance is contained inside the original lattice. ... We start by stating a lemma (Lemma 6) that will be useful in the proof of Theorem 3. The lemma states that if a fixed man m proposes to a fixed woman w during the run of GS algorithm, then the same holds when w moves that man up/down in her list while making no other changes. ... Our proof of Theorem 4 crucially relies on the swapping lemma (Lemma 7). |
| Researcher Affiliation | Academia | Rohit Vaish Indian Institute of Science, India rohit.vaish@csa.iisc.ernet.in Dinesh Garg IIT Gandhinagar, India dgarg@iitgn.ac.in |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | The paper uses small, illustrative examples (Example 1, Example 2) to demonstrate theoretical concepts, not large-scale datasets for training or evaluation. No public datasets are mentioned with access information. |
| Dataset Splits | No | The paper does not provide specific dataset split information (percentages, sample counts, or methodology) needed to reproduce data partitioning for training, validation, or testing. |
| Hardware Specification | No | The paper does not provide specific hardware details (GPU/CPU models, processor types, memory amounts) used for running experiments, as it is a theoretical paper. |
| Software Dependencies | No | The paper does not provide specific ancillary software details (e.g., library or solver names with version numbers) needed to replicate experiments, as it is a theoretical paper. |
| Experiment Setup | No | The paper does not contain specific experimental setup details (concrete hyperparameter values, training configurations, or system-level settings) in the main text, as it is a theoretical paper and does not conduct experiments. |