Redistricting from the Bottom Up: Sampling Communities of Interest with Differential Privacy

तकनीकी सारांश: विभेदक गोपनीयता (Differential Privacy) के साथ नीचे से ऊपर की ओर पुनर्गठन (Redistricting)

समस्या विवरण
स्वतंत्र पुनर्गठन आयोगों (IRCs) का उपयोग 'बॉटम-अप' (नीचे से ऊपर की ओर) पुनर्गठन को सुगम बनाने के लिए तेजी से किया जा रहा है, जिसका उद्देश्य इस प्रक्रिया को पक्षपातपूर्ण हेरफेर से सुरक्षित रखना है। हालांकि, "हितों के समुदायों" (Communities of Interest - COI) के डेटा को एकत्र करने के लिए उपयोग की जाने वाली सार्वजनिक गवाही प्रक्रियाएं प्रतिकूल हमलों (adversarial attacks) के प्रति संवेदनशील हैं। कैलिफोर्निया और फ्लोरिडा के ऐतिहासिक उदाहरण दर्शाते हैं कि राजनीतिक कार्यकर्ता जिला सीमाओं में हेरफेर करने के लिए स्क्रिप्टेड या प्रॉक्सी गवाही देने वाले समूहों को समन्वित कर सकते हैं। जबकि एंसेम्बल विधियां (मार्कोव चेन मोंटे कार्लो) ऊपर से नीचे (top-down) के गेरीमेंडरिंग का पता लगाने में प्रभावी हैं, उनमें COI गवाही को इस तरह शामिल करने का तंत्र नहीं है जो ऐसे प्रतिकूल इनपुट के प्रति मजबूत हो। मुख्य चुनौती एक ऐसा पुनर्गठन एल्गोरिदम डिजाइन करने की है जो सार्वजनिक गवाही डेटा को शामिल तो करे, लेकिन यह सुनिश्चित करे कि कोई भी एकल गवाही या समन्वित समूह परिणाम को असमान रूप से प्रभावित न कर सके।

कार्यप्रणाली
लेखक एक ढांचा प्रस्तावित करते हैं जो विभेदक गोपनीयता (Differential Privacy - DP) को एंसेम्बल सैंपलिंग के साथ जोड़ता है ताकि पुनर्गटिंग योजनाओं को उत्पन्न किया जा सके जो COI गवाहियों का सम्मान करती हैं और व्यक्तिगत डेटा बिंदुओं के प्रभाव को सीमित करती हैं।

1. डेटा प्रतिनिधित्व:

   • राज्य को एक ग्राफ $G=(V, E)$ के रूप में मॉडल किया गया है जहाँ वर्टिस (vertices) जनगणना ब्लॉक समूहों को दर्शाते हैं और एडजेस (edges) आसन्न इकाइयों को जोड़ते हैं।
   • गवाहियों को बाइनरी वेक्टर्स के रूप में एनकोड किया जाता है जो यह दर्शाते हैं कि कौन सा समुदाय किन ब्लॉक समूहों को एक साथ रखना चाहता है।
   • गवाहियों को निकटता के आधार पर भौगोलिक क्लस्टरों में एकत्रित किया जाता है।

2. स्कोर फंक्शन (Score Functions):
   लेखक COI संरक्षण को मापने के लिए दो अलग-अलग स्कोरिंग फंक्शन पेश करते हैं:

   • गवाही स्कोर ($s_t$): यह मापता है कि व्यक्तिगत गवाहियों का वह अनुपात कितना है जो पूरी तरह से एक ही जिले के भीतर रहता है। यह एक बाइनरी "सब-या-कुछ-नहीं" (all-or-nothing) मीट्रिक है।
   • क्लस्टर स्कोर ($s_c$): यह प्रत्येक क्लस्टर के लिए "सर्वश्रेष्ठ" जिले में कुल क्लस्टर भार के संरक्षित अंश को मापता है। यह आंशिक संरक्षण और अधिक सूक्ष्मता की अनुमति देता है।

3. सैंपलिंग तंत्र:

   • लेखक एक लक्ष्य वितरण से पुनर्गठन योजनाओं को नमूना लेने के लिए एक्सपोनेंशियल मैकेनिज्म (Exponential Mechanism) का उपयोग करते हैं जो $\exp(-\frac{\epsilon}{2\Delta(s)} s(t, \xi))$ के समानुपाती है, जहाँ $s$ चुना गया स्कोर फंक्शन है और $\Delta(s)$ उसकी संवेदनशीलता (sensitivity) है।
   • इस वितरण से नमूना लेने के लिए, वे मार्क्ड एज वॉक (Marked Edge Walk - MEW) का उपयोग करते हैं, जो एक लिफ्टेड मार्कोव चेन मोंटे कार्लो (MCMC) एल्गोरिदम है। MEW स्पैनिंग ट्री और मार्क्ड एडजेस के टुपल्स (tuples) पर कार्य करता है, जिससे यह स्थानीय 'फ्लिप-वॉक' की तुलना में स्टेट स्पेस को अधिक कुशलता से पार कर सकता है और स्पैनिंग ट्री संरचनाओं से स्वतंत्र वितरणों पर अभिसरण (converge) कर सकता है।
   • लक्षित वितरण में एक कॉम्पैक्टनेस टर्म (कट एडजेस पर गाऊसी वितरण) भी शामिल है जो लागू योजना के मान पर केंद्रित है ताकि ज्यामितीय वैधता सुनिश्चित की जा सके।

4. गोपनीयता ढांचा:

   • प्रणाली को $(\epsilon, \delta)$-विभेदक रूप से निजी (differentially private) के रूप में परिभाषित किया गया है। एक एकल गवाही (या एक गवाही के अंतर वाला पड़ोसी डेटासेट) को शामिल करने या हटाने से किसी भी आउटपुट योजना की प्रायिकता में होने वाला परिवर्तन सीमित होता है।
   • $\Delta(s)$ की गणना दोनों स्कोर फंक्शनों के लिए की जाती है। गवाही स्कोर की संवेदनशीलता $1/T$ (जहाँ $T$ गवाहियों की संख्या है) है, जबकि क्लस्टर स्कोर का भार के एकत्रीकरण के कारण उच्च संवेदनशीलता है।

प्रमुख परिणाम
इस पद्धति को मिसौरी के मध्य-चक्र पुनर्गठन (mid-cycle redistricting) पर 8в8 COI गवाहियों के साथ लागू किया गया।

• बेसलाइन बनाम प्रदर्शन: COI-सूचित सैंपलिंग ने अनइंफॉर्म्ड बेसलाइन (केवल कॉम्पैक्टनेस पर आधारित सैंपलिंग) और लागू योजना की तुलना में लगातार बेहतर प्रदर्शन किया। लागू योजना ने गवाही स्कोर पर 0.62 और क्लस्टर स्कोर पर 0.71 प्राप्त किया, जबकि DP-नमूनाकृत वितरण $\epsilon$ (प्राइवेसी बजट) बढ़ने के साथ उच्च स्कोर प्राप्त करते हैं।
• प्राइवेसी-उपयोगिता ट्रेड-ऑफ (Privacy-Utility Trade-off): जैसे-जैसे $\epsilon$ बढ़ता है, नमूनाकृत योजनाएं उच्च COI संरक्षण स्कोर की ओर बढ़ती हैं। हालांकि, बहुत उच्च $\epsilon$ पर, चेन मिश्रण (mix) करने में संघर्ष करती है क्योंकि एक्सपोनेंशियल मैकेनिज्म उन प्रस्तावों को बहुत कम प्रायिकता देता है जो स्कोर को कम करते हैं।
• स्कोर फंक्शन तुलना:
  • गवाही स्कोर ने मजबूत औपचारिक गोपनीयता गारंटी (कम संवेदनशीलता) प्रदान की लेकिन "बलिदान" (sacrifice) व्यवहार प्रदर्शित किया: उच्च $\epsilon$ पर, यह कुछ गवाहियों को अन्य को संरक्षित करने के लिए अधिक बार विभाजित करता है, जो स्कोर की असतत (discrete) प्रकृति के कारण होता है।
  • क्लस्टर स्कोर ने अधिक सहज परिणाम और उच्च बजट पर बेहतर मिक्सिंग प्रदान की, लेकिन उच्च संवेदनशीलता के कारण कमजोर औपचारिक गोपनीयता गारंटी दी।
• प्रतिकूल मजबूती (Adversarial Robustness): एक प्रयोग में जहाँ 9 गवाहियों के एक क्लस्टर को एक अलग भौगोलिक क्षेत्र को कवर करने वाले प्रतिकूल डेटा से बदल दिया गया था:
  • क्लस्टर स्कोर के तहत, प्रतिकूल क्लस्टर को निम्न $\epsilon$ पर बेसलाइन के अनुरूप दर पर संरक्षित किया गया, और $\epsilon$ बढ़ने के साथ बढ़ते हुए संरक्षित किया गया।
  • गवाही स्कोर के तहत, प्रतिकूल गवाहियों को उच्च $\epsilon$ बढ़ने के साथ तेजी से विभाजित किया गया, जिससे शेष 800+ गवाहियों की अखंडता को बनाए रखने के लिए उन्हें बलिदान कर दिया गया।
  • परिणाम बताते हैं कि यह विधि छोटे पैमाने के समन्वित हमलों के प्रति मजबूत है, जो औपचारिक समूह गोपनीयता सीमाओं (जो हमलावरों की संख्या के साथ रैखिक रूप से घटती हैं) द्वारा अनुमानित होने की तुलना में व्यावहारिक रूप से बेहतर प्रदर्शन करती है।
• जनसांख्यिकीय प्रभाव: इस धारणा के विपरीत कि COIs को संरक्षित करने से अल्पसंख्यक या डेमोक्रेटिक मतदाताओं को एकल जिलों में "पैक" (packing) किया जाता है, परिणामों ने दिखाया कि मिसौरी में मजबूत COI संरक्षण से अल्पसंख्यक और डेमोक्रेटिक प्रतिनिधित्व शीर्ष तीन जिलों में अधिक समान रूप से फैल (spread) गया। इसका श्रेय मिसौरी के दो प्रमुख शहरी केंद्रों (सेंट लुइस और कंसास सिटी) के बीच भौगोलिक अलगाव को दिया गया; स्थानीय समुदायों को अक्षुण्ण रखने से कंसास सिटी में प्रतिनिधित्व के विखंडन को रोका गया, जिसे लागू योजना में विभाजित किया गया था।

महत्व और दावे
यह पत्र दावा करता है कि यह "बॉटम-अप" पुनर्गठन के लिए एक नवीन ढांचा प्रदान करता है जो सार्वजनिक गवाही को शामिल करने और प्रतिकूल हेरफेर के विरुद्ध मजबूती के बीच संतुलन बनाता है।

• मजबूती: प्राथमिक योगदान यह प्रदर्शित करना है कि पुनर्गठन योजनाओं के आउटपुट वितरण पर विभेदक गोपनीयता (DP) को लागू किया जा सकता है ताकि किसी एकल गवाही या छोटे समन्वित समूह के प्रभाव को सीमित किया जा सके, बिना डेटा को पूरी तरह से हटाए।
• व्यावहारिक अनुप्रयोग: अध्ययन वास्तविक दुनिया के डेटा (मिसौरी 2021 गवाहियाँ) और एक विशिष्ट MCMC एल्गोरिदम (MEW) का उपयोग करके इस दृष्टिकोण को मान्य करता है जो गैर-मानक लक्ष्य वितरणों से नमूना लेने में सक्षम है।
• सीमाएँ: लेखक विनम्रतापूर्वक नोट करते हैं कि यह विधि समस्या को पूरी तरह से हल नहीं करती है; पर्याप्त बड़े समन्वित हमले अभी भी तंत्र को ओवरवेलम कर सकते हैं क्योंकि समूह गोपनीयता रैखिक रूप से घटती है। इसके अलावा, MEW के लिए सैद्धांतिक मिक्सिंग गारंटी सीमित है, जिसके लिए अनुभवजन्य अभिसरण निदान (empirical convergence diagnostics) पर निर्भर रहना पड़ता है। यह दृष्टिकोण संरचित गवाही डेटा (जैसे, Districtr जैसे प्लेटफार्मों के माध्यम से) की उपलब्धता पर भी निर्भर करता है और इसके लिए गोपनीयता मापदंडों और क्लस्टरिंग विधियों के सावधानीपूर्वक चयन की आवश्यकता होती है।

निष्कर्षतः, यह पत्र तर्क देता है कि जबकि IRCs एक आशाजनक उपकरण हैं, उन्हें हेरफेर के विरुद्ध गणितीय सुरक्षा उपायों की आवश्यकता है। प्रस्तावित DP-MEW ढांचा किसी भी प्रतिकूल इनपुट के प्रभाव पर एक मात्रात्मक सीमा प्रदान करता है, जिससे ऐसी पुनर्गठन योजनाएं बनाना संभव होता है जो सामुदायिक हितों से सूचित भी हों और सबवर्जन (subversion) के प्रति लचीली भी।