IOS Press Ebooks - The Last Voting Rule Is Home: Complexity of Control by Partition of Candidates or Voters in Maximin Elections

<!DOCTYPE html> <html> <head>  <script> window.dataLayer = window.dataLayer || []; function gtag() { dataLayer.push(arguments); } if (localStorage.getItem('consentMode') === null) { gtag('consent', 'default', { 'ad_storage': 'denied', 'ad_user_data': 'denied', 'ad_personalization': 'denied', 'analytics_storage': 'denied', 'personalization_storage': 'granted', 'functionality_storage': 'granted', 'security_storage': 'granted', }); } else { gtag('consent', 'default', JSON.parse(localStorage.getItem('consentMode'))); } gtag('set', 'ads_data_redaction', true); gtag('set', 'url_passthrough', true); </script>  <script>(function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start': new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0], j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src= 'https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f); })(window,document,'script','dataLayer','GTM-W7N3WL5P');</script>  <link href="/favicon.ico" rel="shortcut icon" type="image/x-icon" /> <meta charset="utf-8" /> <meta name="viewport" content="width=device-width" /> <title>IOS Press Ebooks - The Last Voting Rule Is Home: Complexity of Control by Partition of Candidates or Voters in Maximin Elections</title> <meta name="DC.type" content="Text" />  <meta name="citation_publisher" content="IOS Press" />  <meta name="citation_inbook_title" content="ECAI 2020" />  <meta name="citation_firstpage" content="163" /> <meta name="citation_lastpage" content="170" /> <meta name="citation_title" content="The Last Voting Rule Is Home: Complexity of Control by Partition of Candidates or Voters in Maximin Elections" /> <meta name="citation_author" content="Maushagen, Cynthia" /> <meta name="citation_author" content="Rothe, J&#246;rg" /> <meta name="citation_publication_date" content="2020" /> <meta name="citation_online_date" content="2020/08/27" /> <meta name="citation_doi" content="10.3233/FAIA200089" /> <meta name="citation_pdf_url" content="https://ebooks.iospress.nl/pdf/doi/10.3233/FAIA200089" /> <meta name="citation_abstract_html_url" content="https://ebooks.iospress.nl/doi/10.3233/FAIA200089" /> <meta name="citation_fulltext_html_url" content="https://ebooks.iospress.nl/doi/10.3233/FAIA200089" /> <meta name="citation_fulltext_world_readable" content=""> <link href="/Content/themes/iospress/css?v=XPnK8-1eJi79xAnj96qGIM248iqorL44CGZjTHyXSdY1" rel="stylesheet"/> <script src="https://ajax.aspnetcdn.com/ajax/jQuery/jquery-3.5.1.min.js"></script> <script src="/bundles/jqueryval?v=S0zjY_C9SrWh_jAKguTKrt0UAVoLX4jD0DmtC1N35rA1"></script> </head> <body class="iospress">  <div id="header"> <div id="default_header"> <div id="logo"><img alt="IOS Press Ebooks" src="/Content/themes/iospress/images/ioslogo.png" /></div> <div id="divider"></div> <div id="title">IOS Press Ebooks</div> <div style="position:relative; float: right; width: 300px;"> <div id="minibasket"> <div id="minibasket_icon"><a href="/Cart"><img alt="cart" src="/Content/themes/iospress/images/ico-cart.gif" /></a></div> <div id="minibasket_count"><a href="/Cart">Your cart is empty</a></div> </div>  <div id="header_accountbox" class="loggedout"> <div class="accountbox_welcome">Guest Access</div> <div id="header_accountbox_qmark">?</div> <div class="accountbox_actions"> <a data-dialog-title="Registration" href="/Account/Register" id="registerLink">Register</a> | <a data-dialog-title="Identification" href="/Account/Login?returnUrl=%2Fvolumearticle%2F54884" id="loginLink">Log in</a> </div> <div id="header_accountbox_infobox"> <div id="header_accountbox_infobox_arrow"></div> <div id="header_accountbox_infobox_content"> As a guest user you are not logged in or recognized by your IP address. You have access to the Front Matter, Abstracts, Author Index, Subject Index and the full text of Open Access publications. </div> </div> </div> <script type="text/javascript"> $(document).ready(function () { $("#header_accountbox_qmark").mouseenter(function () { $("#header_accountbox_infobox").show(); }); $("#header_accountbox_qmark").mouseleave(function () { $("#header_accountbox_infobox").hide(); }); }); </script> </div> <div id="menu_wrapper"> <div id="menu-primary" class="menu-container"> <div class="menu"> <ul id="menu-primary-items" class=""> <li class="menu-item"><a href="/"><span>Home</span></a></li> <li class="menu-item current-menu-item"><a href="/Publication/Books"><span>Ebooks</span></a></li> <li class="menu-item"><a href="/Publication/OpenAccess"><span>Open Access</span></a></li> <li class="menu-item"><a href="/Publisher/About"><span>About IOS Press</span></a></li> <li class="menu-item"><a href="/Publisher/Offices"><span>Contact</span></a></li> <li class="menu-item"><a href="/Publisher/Faq"><span>FAQ</span></a></li> </ul> </div> </div> </div> </div> </div>  <div id="content" class="clearfix"> <div id="leftcolumn"> <div class="searchtitle"> Search</div> <div id="sidesearchbox" style="font-size: 11px; width: 100%;" class="clearfix"> <form action="/Search" method="post"> <div style="float: left; width: 100px;"><input class="searchterm" id="SearchTerm" name="SearchTerm" type="text" value="" /></div> <input data-val="true" data-val-required="The SearchInAuthors field is required." id="SearchInAuthors" name="SearchInAuthors" type="hidden" value="True" /><input data-val="true" data-val-required="The SearchInTitle field is required." id="SearchInTitle" name="SearchInTitle" type="hidden" value="True" /><input data-val="true" data-val-required="The SearchInKeywords field is required." id="SearchInKeywords" name="SearchInKeywords" type="hidden" value="True" /><input data-val="true" data-val-required="The SearchInISSNISBN field is required." id="SearchInISSNISBN" name="SearchInISSNISBN" type="hidden" value="True" /> <table style="border:0;clear:both;" cellpadding="0px" cellspacing="0px"> <tr> <td align="left" style="padding-top:12px">   </td> <td align="right" style="padding-top:12px; width:100%"> <input type="image" value="SideSearch" src="/Content/themes/iospress/images/searchbutton.png" class="submit" /> </td> </tr> </table> </form></div> <div class="partialContents" data-url="/Subject/BrowserAsync"> <img alt="loader" src="/Content/Images/indicator.white.gif" /> loading subjects... </div> </div> <div id="contentcolumn"> <div class="bookseriesvolumearticleheader"> <div class="content"> <div class="cover"><img alt="cover" class="volume" src="/Content/themes/iospress/images/article.gif" /></div> <div class="metadata"> <div class="value title">The Last Voting Rule Is Home: Complexity of Control by Partition of Candidates or Voters in Maximin Elections</div> <label>Authors</label> <div class="value authors">Cynthia Maushagen, Jörg Rothe</div> <label>Pages</label> <div class="value pages">163 - 170</div> <label>DOI</label> <div class="value doi">10.3233/FAIA200089</div> <label>Category</label> <div class="value category">Research Article</div> <label>Series</label> <div class="value book"><a href="/bookseries/frontiers-in-artificial-intelligence-and-applications">Frontiers in Artificial Intelligence and Applications</a></div> <label>Ebook</label> <div class="value book"><a href="/volume/ecai-2020-24th-european-conference-on-artificial-intelligence">Volume 325: ECAI 2020</a></div> <div class="abstract"> <b>Abstract</b><br /> <section> <p>One of the key topics of computational social choice is electoral control, which models certain ways of how an election chair can seek to influence the outcome of elections via structural changes such as adding, deleting, or partitioning either candidates or voters. Faliszewski and Rothe [13] have surveyed the rich literature on control, giving an overview of previous results on the complexity of the associated problems for the most important voting rules. Among those, only a few results were known for two quite prominent voting rules: Borda Count and maximin voting (a.k.a. the Simpson鈥揔ramer rule). Neveling and Rothe [26, 25] recently settled the remaining open cases for Borda. In this paper, we solve all remaining open cases for the complexity of control in maximin elections all of which concern control by partition of either candidates or voters.</p> </section> </div> </div> <div class="actions"> <form action="/Download/Pdf" id="downloadform54884" method="post"> <input type="hidden" name="id" value="54884" /> <div id='downloadlink54884' class="button getpdf">Download </div> </form> <script type="text/javascript"> $(function () { $('div#downloadlink54884').click(function () { $('form#downloadform54884').submit(); }); }); </script> <div class="button openaccesslicense"> <a rel="license" target="_blank" title="This work is licensed under a Creative Commons License" href="https://creativecommons.org/licenses/by-nc/4.0/deed.en_US"> <img alt="Creative Commons License" style="border-width: 0" src="https://i.creativecommons.org/l/by-nc/4.0/80x15.png" /></a></div> </div> </div> </div> </div> </div> <div id="footer" class="clearfix"> <script type="text/javascript"> $(document).ready(function () { $('[id^="tip_"]').mouseenter(function () { $(this).stop(true); $(this).hide().show(); }); $('.tip').mouseleave(function () { $('[id^="tip_"]').fadeOut(600, function () { $('[id^="tip_"]').hide() }); }); $('[name^="atip_"]').mouseenter(function () { var idtoshow = $(this).attr('name').substring(1); $('#' + idtoshow).hide().fadeIn(600, function () { $('#' + idtoshow).show() }); }); $('[name^="atip_"]').mouseleave(function () { var idtoshow = $(this).attr('name').substring(1); $('#' + idtoshow).fadeOut(600, function () { $('#' + idtoshow).hide() }); }); }); </script> <div id="default_footer"> <div id="footer_contact"> <h3> Contact </h3> <ul class="list" style="float: left"> <li><a name="atip_usa" href="#">North America</a></li> <li><a name="atip_europe" href="#">Europe</a></li> <li><a name="atip_asia" href="#">Asia</a></li> </ul> <a name="atip_usa" id="usa" class="usa" href="#"></a> <a name="atip_europe" id="europe" class="europe" href="#"></a> <a name="atip_asia" id="asia" class="asia" href="#"></a> <div id="tip_usa" style="display: none;"> <div class="tip"> <strong>IOS Press, Inc</strong>.<br /> 6751 Tepper Drive<br /> Clifton, VA 20124<br /> U.S.A.<br /> Tel.: +1 703 830 6300<br /> Fax: +1 703 830 2300<br /> <a href="mailto:sales@iospress.com">sales@iospress.com</a><br /> (Corporate matters and books only)<br /> <hr class="dotted" /> <strong>IOS Press c/o Accucoms US, Inc.</strong><br /> For North America Sales and Customer Service<br /> West Point Commons<br /> Suite 201<br /> Lansdale PA 19446<br /> USA<br /> Tel.: +1 866 855 8967<br /> Fax: +1 215 660 5042<br /> <a href="mailto:iospress@accucoms.com">iospress@accucoms.com</a><br /> (Journals only)<br /> </div> </div> <div id="tip_europe" style="display: none;"> <div class="tip"> <strong>IOS Press</strong><br /> Nieuwe Hemweg 6B<br /> 1013 BG Amsterdam<br /> The Netherlands<br /> Tel: +31 20 688 3355<br /> Fax: +31 20 687 0019<br /> <a href="mailto:info@iospress.nl">info@iospress.nl</a><br /> </div> </div> <div id="tip_asia" style="display: none;"> <div class="tip"> <strong>IOS Press</strong><br /> c/o Ohmsha, Ltd.<br /> 3-1 Kanda Nishiki-cho<br /> Chiyoda-ku<br /> Tokyo 101<br /> Japan<br /> Fax: +81 3 3233 2426<br /> (Books only)<br /> <hr class="dotted" /> <strong>Inspirees International China</strong><br /> Ocean Express F-802<br /> Xiaguangli 66<br /> 100027, Beijing<br /> China<br /> Tel. & Fax: +86 10 8446 7847<br /> Free service line: 400 661 8717<br /> </div> </div> </div> <div id="footer_divider"> </div> <div id="footer_links"> <h3> IOS Press Copyright 2025 </h3> <a href="/publisher/Disclaimer/">Disclaimer</a>     <a href="/publisher/TermsOfUse/"> Terms of use </a>   <a href="/publisher/PrivacyPolicy/"> Privacy Policy </a>   <a href="/publisher/Contact/"> Contact </a>   <a href="/publisher/Faq/">FAQ</a> </div> <div id="footer_twitter"> <a href="http://twitter.com/IOSPress_STM" target="_blank"> <img alt="twitter" src="/Content/themes/iospress/images/twitter.gif" /> </a> </div> </div> </div> <script type="text/javascript"> if (typeof jQuery == 'undefined') { var e = document.createElement('script'); e.src = '/Scripts/jquery-3.5.1.min.js'; e.type = 'text/javascript'; document.getElementsByTagName("head")[0].appendChild(e); } </script> <script src="/bundles/subjectmenu?v=jieOsy0lZdhfbuK00Z1qohST722ZF4yIVuWCjPrX6ZE1"></script> <script src="/bundles/pubility?v=meEJdaSXIsVeUXAotcBmWyMjARi2G38fFL4j3SAMa9c1"></script> <script type="text/javascript"> $(document).ready(function () { initExpandBoxes(10); }) </script> <style> .cookie-consent-banner { display: none; position: fixed; bottom: 0; left: 0; right: 0; background-color: #f8f9fa; box-shadow: 0 -2px 10px rgba(0, 0, 0, 0.1); color: black; padding: 15px; font-size: 14px; text-align: center; z-index: 1000; } .cookie-consent-banner h3 { padding: 0px 0px; font-size: 14px; font-weight: bolder; } .cookie-consent-button { border: none; padding: 8px 16px; text-align: center; text-decoration: none; display: inline-block; font-size: 14px; margin: 4px 2px; cursor: pointer; border-radius: 4px; } .cookie-consent-button:hover { box-shadow: 0 -2px 5px rgba(0, 0, 0, 0.2); } .cookie-consent-button:active { opacity: .5; } .cookie-consent-button.btn-success { background-color: #34a853; color: white; } .cookie-consent-button.btn-grayscale { background-color: #dfe1e5; color: black; } .cookie-consent-button.btn-outline { background-color: #e6f4ea; color: #34a853; } .cookie-consent-options { display: flex; justify-content: center; flex-wrap: wrap; margin-bottom: 10px; } .cookie-consent-options label { margin: 4px 5px; font-size: 12px; font-weight: normal; } .cookie-consent-options input { margin-right: 5px; } </style> <div id="cookie-consent-banner-basic" class="cookie-consent-banner"> <h3>This website uses cookies</h3> <p> We use cookies to provide you with the best possible experience. They also allow us to analyze user behavior in order to constantly improve the website for you. Info about the <a href="/publisher/PrivacyPolicy/">privacy policy</a> of IOS Press. </p> <button id="btn-advanced-basic" class="cookie-consent-button btn-grayscale">Customize</button> <button id="btn-accept-all-basic" class="cookie-consent-button btn-success">Accept</button> </div> <div id="cookie-consent-banner-advanced" class="cookie-consent-banner"> <h3>This website uses cookies</h3> <p> We use cookies to provide you with the best possible experience. They also allow us to analyze user behavior in order to constantly improve the website for you. Info about the <a href="/publisher/PrivacyPolicy/">privacy policy</a> of IOS Press. </p> <button id="btn-reject-all-advanced" class="cookie-consent-button btn-grayscale" style="display:none">Reject All</button> <button id="btn-accept-some-advanced" class="cookie-consent-button btn-outline">Accept Selection</button> <button id="btn-accept-all-advanced" class="cookie-consent-button btn-success">Accept</button> <div class="cookie-consent-options"> <label><input id="consent-necessary" type="checkbox" value="Necessary" checked disabled>Necessary</label> <label><input id="consent-preferences" type="checkbox" value="Preferences" checked>Preferences</label> <label><input id="consent-analytics" type="checkbox" value="Analytics" checked>Analytics</label> <label><input id="consent-marketing" type="checkbox" value="Marketing" checked>Marketing</label> </div> </div> <script> function hideBannerAdvanced() { document.getElementById('cookie-consent-banner-advanced').style.display = 'none'; } function hideBannerBasic() { document.getElementById('cookie-consent-banner-basic').style.display = 'none'; } function hideAll() { hideBannerBasic(); hideBannerAdvanced(); } function showBannerAdvanced() { if (localStorage.getItem('consentMode') !== null) { var consentmode = JSON.parse(localStorage.getItem('consentMode')); document.getElementById('consent-analytics').checked = (consentmode.analytics_storage === 'granted'); document.getElementById('consent-preferences').checked = (consentmode.personalization_storage === 'granted'); document.getElementById('consent-marketing').checked = (consentmode.ad_storage === 'granted'); } document.getElementById('cookie-consent-banner-advanced').style.display = 'block'; } function showBannerBasic() { if (localStorage.getItem('consentMode') !== null) { var consentmode = JSON.parse(localStorage.getItem('consentMode')); document.getElementById('consent-analytics').checked = (consentmode.analytics_storage === 'granted'); document.getElementById('consent-preferences').checked = (consentmode.personalization_storage === 'granted'); document.getElementById('consent-marketing').checked = (consentmode.ad_storage === 'granted'); } document.getElementById('cookie-consent-banner-basic').style.display = 'block'; } document.getElementById('btn-accept-all-basic').addEventListener('click', function () { setConsent({ necessary: true, analytics: true, preferences: true, marketing: true }); hideAll(); }); document.getElementById('btn-accept-all-advanced').addEventListener('click', function () { setConsent({ necessary: true, analytics: true, preferences: true, marketing: true }); hideAll(); }); document.getElementById('btn-advanced-basic').addEventListener('click', function () { hideBannerBasic(); showBannerAdvanced(); }); document.getElementById('btn-accept-some-advanced').addEventListener('click', function () { setConsent({ necessary: true, analytics: document.getElementById('consent-analytics').checked, preferences: document.getElementById('consent-preferences').checked, marketing: document.getElementById('consent-marketing').checked }); hideAll(); }); document.getElementById('btn-reject-all-advanced').addEventListener('click', function () { setConsent({ necessary: false, analytics: false, preferences: false, marketing: false }); hideAll() }); if (localStorage.getItem('consentMode') === null) { showBannerBasic(); } function setConsent(consent) { const consentMode = { 'ad_storage': consent.marketing ? 'granted' : 'denied', 'ad_user_data': consent.marketing ? 'granted' : 'denied', 'ad_personalization': consent.marketing ? 'granted' : 'denied', 'analytics_storage': consent.analytics ? 'granted' : 'denied', 'personalization_storage': consent.preferences ? 'granted' : 'denied', 'functionality_storage': consent.necessary ? 'granted' : 'denied', 'security_storage': consent.necessary ? 'granted' : 'denied', }; gtag('consent', 'update', consentMode); localStorage.setItem('consentMode', JSON.stringify(consentMode)); } </script> </body> </html>

CINXE.COM

IOS Press Ebooks - The Last Voting Rule Is Home: Complexity of Control by Partition of Candidates or Voters in Maximin Elections