{"id":1829,"date":"2013-10-28T10:45:45","date_gmt":"2013-10-28T14:45:45","guid":{"rendered":"http:\/\/blogs.law.harvard.edu\/pamphlet\/?p=1829"},"modified":"2019-03-25T12:54:32","modified_gmt":"2019-03-25T16:54:32","slug":"can-gerrymandering-be-solved-with-cut-and-choose","status":"publish","type":"post","link":"https:\/\/archive.blogs.harvard.edu\/pamphlet\/2013\/10\/28\/can-gerrymandering-be-solved-with-cut-and-choose\/","title":{"rendered":"Can gerrymandering be solved with cut-and-choose?"},"content":{"rendered":"

Update\u00a0March 25, 2019:<\/strong>\u00a0Wesley Pegden, Ariel D. Procaccia, and Dingli Yu have an elegant working out of the proposal<\/a> below that they call “I cut, you freeze.” Pegden and Procaccia describe it in a Washington Post opinion piece<\/a>.<\/em><\/p>\n\n\n\n\n
\"'Halves'<\/a><\/td>\n<\/tr>\n
\u2026how to split a cupcake\u2026<\/span>
\n\u201cHalves<\/a>\u201d image by flickr user Julie Remizova<\/a>.<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Why is gerrymandering even possible in a country with a constitutional right to equal protection<\/a>?:<\/p>\n

No State shall make or enforce any law which shall\u2026deny to any person within its jurisdiction the equal protection of the laws.<\/p><\/blockquote>\n

By reshaping districts to eliminate the voting power of particular individuals, as modern district mapping software allows, some persons are being denied equal protection, I\u2019d have thought. And so have certain Supreme Court justices<\/a>.<\/p>\n

It\u2019s hard to know what to do about the problem. Appeals to fairness aren\u2019t particularly helpful, since who decides what\u2019s fair? It would be nice to think that requirements of \u201ccompact districts of contiguous territory<\/a>\u201d (as Chief Justice Harlan put it) would be sufficient. But this reduces the problem of districting to a mathematical optimization problem;\u00a0James Case proposes<\/a> something like minimum isoperimetric quotient<\/a> tessellation of a polygon. But such purely mathematical approaches may yield results that violate our intuitions about what is fair. They ignore other criteria, such as \u201cnatural or historical boundary lines<\/a>\u201d, determined for instance by geographical features like rivers and mountains or shared community interests. These boundaries may not coincide with the mathematical optima, so any mathematical formulation would need to be defeasible to take into account such features. This leads us right back to how to decide in which cases the mathematical formulation should be adjusted: who should decide what is fair?<\/p>\n

A comment<\/a> at a ProPublica article about gerrymandering<\/a> from \u201cdamien\u201d caught my attention as a nice way out of this quandary. In essence, he proposes that the parties themselves<\/em> choose what\u2019s fair.<\/p>\n

The first solution to gerrymandering is to have a fitness measure for a proposed districting (e.g. the sum of the perimeters), and then to allow any individual or organisation to propose a districting, with the winner having the best fitness value.<\/p><\/blockquote>\n

What “damien” is proposing, I take it, is the application of an algorithm somewhat like one familiar from computer science (especially cryptography) and grade school cafeterias known as \u201ccut and choose<\/a>\u201d. How do you decide how to split a cupcake between two kids? One cuts; the other chooses. The elegance of cut-and-choose is that it harmonizes the incentives of the two parties. The cutter is incentivized to split equally, since the chooser can punish inequity.<\/p>\n

Cut-and-choose is asymmetrical; the two participants have different roles. A symmetrical variant has each participant propose a cut and an objective third party selecting whichever is better according to the pertinent objective measure. This variant shares the benefit that each participant has an incentive to be more nearly equal than the other. If Alice proposes a cut that gives her 60% of the cupcake and Bob 40%, she risks Bob proposing a better split that gives her only 45% with him taking the remaining 55%. To avoid getting taken advantage of, her best bet is to propose a split as nearly equal as possible.<\/p>\n

In the anti-gerrymandering application\u00a0of the idea, the two parties propose districtings, which they could gerrymander however they wanted. Whichever of the two proposals has the lower objective function (lower isoperimetric quotient, say) is chosen. Thus, if one party gerrymanders too much, their districting will be dropped in favor of the other party\u2019s proposal. Each party has an incentive to hew relatively close to a compact partition, while being allowed to deviate in appropriate cases.<\/p>\n

A nice property of this approach is that the optimization problem doesn\u2019t ever need to be solved. All that is required is the evaluation of the objective function for the two proposed districtings, which is computationally far simpler. (In fact, I\u2019d guess the minimum isoperimetric quotient optimization problem might well be\u00a0NP-hard<\/a>.)<\/p>\n

There are problems of course.\u00a0The procedure is subject to gaming when the proposal-generating process is not private to the parties.\u00a0It is unclear how to extend the method to more than two parties. Of course, the obvious generalization works once the eligible parties are determined. The hard part is deciding what parties are eligible to propose a redistricting. Most critically, the method is subject to collusion, especially in cases where\u00a0both parties benefit from gerrymandering<\/a>. In particular, both parties benefit from a districting that protects incumbencies for both parties. The parties could agree, for instance, not to disturb each other’s safe districts, and would benefit from observing the\u00a0agreement.<\/p>\n

Nonetheless, once districting is thought of in terms of mechanism design<\/a>, the full range of previous algorithms can be explored.\u00a0Somewhere in the previous literature there might be a useful solution.\u00a0(Indeed, the proposal here is essentially the first step in Brams, Jones, and Klamler’s surplus procedure<\/a>\u00a0for cake-cutting.)<\/p>\n

Of course, as with many current political problems (campaign financing being the clearest example), the big question is how such new mechanisms would be instituted, given that it is not in the incumbent majority party’s interest to do so. Until that\u2019s sorted out<\/a>, I\u2019m not holding out much hope.<\/p>\n","protected":false},"excerpt":{"rendered":"

Update\u00a0March 25, 2019:\u00a0Wesley Pegden, Ariel D. Procaccia, and Dingli Yu have an elegant working out of the proposal below that they call “I cut, you freeze.” Pegden and Procaccia describe it in a Washington Post opinion piece. \u2026how to split a cupcake\u2026 \u201cHalves\u201d image by flickr user Julie Remizova. Why is gerrymandering even possible in […]<\/p>\n","protected":false},"author":2110,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[380,116,62109],"tags":[],"class_list":["post-1829","post","type-post","status-publish","format-standard","hentry","category-computer-science","category-policy","category-politics-policy"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p5pLfN-tv","jetpack-related-posts":[{"id":1977,"url":"https:\/\/archive.blogs.harvard.edu\/pamphlet\/2014\/03\/13\/a-document-scanning-smartphone-handle\/","url_meta":{"origin":1829,"position":0},"title":"A document scanning smartphone handle","author":"Stuart Shieber","date":"Thursday, March 13, 2014","format":false,"excerpt":"\u2026my solution to the problem\u2026 (Demonstrating the Scan-dle to my colleagues from the OSC over a beer in a local pub. Photo: Reinhard Engels) They are at the end of the gallery; retired to their tea and scandal, according to their ancient custom. \u2014 William Congreve For a project that\u2026","rel":"","context":"In "libraries"","block_context":{"text":"libraries","link":"https:\/\/archive.blogs.harvard.edu\/pamphlet\/category\/scholarly-communication\/libraries\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/blogs.law.harvard.edu\/pamphlet\/files\/2014\/03\/scandle-plans-300x158.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":124,"url":"https:\/\/archive.blogs.harvard.edu\/pamphlet\/2009\/06\/15\/an-economic-solution-to-reviewing-load\/","url_meta":{"origin":1829,"position":1},"title":"An economic solution to reviewing load","author":"Stuart Shieber","date":"Monday, June 15, 2009","format":false,"excerpt":"Hal Daume at the NLP blog bemoans the fact that \"there is too much to review and too much garbage among it\" and wonders \"whether it's possible to cut down on the sheer volume of reviewing\". He lists several possible approaches, most of which apply only to conference papers (which\u2026","rel":"","context":"In "scholarly communication"","block_context":{"text":"scholarly communication","link":"https:\/\/archive.blogs.harvard.edu\/pamphlet\/category\/scholarly-communication\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":247,"url":"https:\/\/archive.blogs.harvard.edu\/pamphlet\/2009\/07\/06\/as-library-budgets-collapse-authors-need-to-take-responsibility-for-access\/","url_meta":{"origin":1829,"position":2},"title":"As library budgets collapse, authors need to take responsibility for access","author":"Stuart Shieber","date":"Monday, July 6, 2009","format":false,"excerpt":"Jonathan Eisen at The Tree of Life writes If you need any more incentive to publish a paper in an Open Access manner if you have a choice - here is one. If you publish in a closed access journal of some kind, it is likely fewer and fewer colleagues\u2026","rel":"","context":"In "libraries"","block_context":{"text":"libraries","link":"https:\/\/archive.blogs.harvard.edu\/pamphlet\/category\/scholarly-communication\/libraries\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":1075,"url":"https:\/\/archive.blogs.harvard.edu\/pamphlet\/2011\/12\/01\/conan-doyle-on-the-prevention-of-cruelty-to-books\/","url_meta":{"origin":1829,"position":3},"title":"Conan Doyle on the prevention of cruelty to books","author":"Stuart Shieber","date":"Thursday, December 1, 2011","format":false,"excerpt":"\u201c...dog-eared in thirty-one places...\u201d I've been reading Arthur Conan Doyle's first novel, The Narrative of John Smith, just published for the first time by the British Library. It's no The Adventures of Sherlock Holmes, that's for sure. For one thing, he seems to have left out any semblance of plot.\u2026","rel":"","context":"In "libraries"","block_context":{"text":"libraries","link":"https:\/\/archive.blogs.harvard.edu\/pamphlet\/category\/scholarly-communication\/libraries\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":1440,"url":"https:\/\/archive.blogs.harvard.edu\/pamphlet\/2012\/06\/11\/editorial-board-members-what-to-ask-of-your-journal\/","url_meta":{"origin":1829,"position":4},"title":"Editorial board members: What to ask of your journal","author":"Stuart Shieber","date":"Monday, June 11, 2012","format":false,"excerpt":"...good behavior... Harvard made a big splash recently when my colleagues on\u00a0the\u00a0Faculty Advisory Council to the Harvard Library\u00a0distributed a Memorandum on Journal Pricing. One of the main problems with the memo, however,\u00a0is the relatively imprecise recommendations that it makes. It exhorts faculty to work with journals and scholarly societies on\u2026","rel":"","context":"In "scholarly communication"","block_context":{"text":"scholarly communication","link":"https:\/\/archive.blogs.harvard.edu\/pamphlet\/category\/scholarly-communication\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/archive.blogs.harvard.edu\/pamphlet\/wp-json\/wp\/v2\/posts\/1829","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/archive.blogs.harvard.edu\/pamphlet\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/archive.blogs.harvard.edu\/pamphlet\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/archive.blogs.harvard.edu\/pamphlet\/wp-json\/wp\/v2\/users\/2110"}],"replies":[{"embeddable":true,"href":"https:\/\/archive.blogs.harvard.edu\/pamphlet\/wp-json\/wp\/v2\/comments?post=1829"}],"version-history":[{"count":21,"href":"https:\/\/archive.blogs.harvard.edu\/pamphlet\/wp-json\/wp\/v2\/posts\/1829\/revisions"}],"predecessor-version":[{"id":2430,"href":"https:\/\/archive.blogs.harvard.edu\/pamphlet\/wp-json\/wp\/v2\/posts\/1829\/revisions\/2430"}],"wp:attachment":[{"href":"https:\/\/archive.blogs.harvard.edu\/pamphlet\/wp-json\/wp\/v2\/media?parent=1829"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/archive.blogs.harvard.edu\/pamphlet\/wp-json\/wp\/v2\/categories?post=1829"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/archive.blogs.harvard.edu\/pamphlet\/wp-json\/wp\/v2\/tags?post=1829"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}