📊 statistics

Do Not Trust The Auctioneer: Learning to Bid in Feedback-Manipulated Auctions

यह शोध पत्र उन बार-बार होने वाली प्रथम-मूल्य नीलामियों (first-price auctions) का विश्लेषण करता है जहाँ शिलिंग (shilling) आवंटन के बजाय फीडबैक में हेरफेर करती है, जो एक हाइब्रिड एल्गोरिदम का प्रस्ताव देता है जो रोबस्ट इंटरवल एलिमिनेशन (robust interval elimination) को ऑप्टिमिस्टिक डिबायसिंग (optimistic debiasing) के साथ जोड़कर इष्टतम $\tilde{\mathcal{O}}(\sqrt{T})$ रिग्रेट प्राप्त करता है, और साथ ही यह प्रदर्शित करता है कि ऐसा केवल-फीडबैक हेरफेर बोली लगाने सीखने की सांख्यिकीय कठिनाई को काफी बढ़ा देता है।

मूल लेखक: Luigi Foscari, Matilde Tullii, Vianney Perchet

प्रकाशित 2026-05-22

📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Luigi Foscari, Matilde Tullii, Vianney Perchet

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक ऑनलाइन नीलामी में एक दुर्लभ संग्रहणीय वस्तु (rare collectible) खरीदने की कोशिश कर रहे हैं। आप नहीं जानते कि अन्य लोग कितना भुगतान करने को तैयार हैं, इसलिए आपको यह सीखने के लिए देखना होगा कि जब आप अपनी बोलियां (bids) लगाते हैं तो क्या होता है।

आमतौर पर, यदि आप नीलामी हार जाते हैं, तो प्लेटफॉर्म आपको वह उच्चतम बोली बताता है जिसने आपको हराया था। यह आपको सीखने में मदद करता है: "ओह, अगली बार मुझे थोड़ा अधिक बोली लगानी चाहिए।"

लेकिन इस शोध पत्र में, लेखक एक ऐसी स्थिति की कल्पना करते हैं जहाँ नीलामीकर्ता थोड़ा चालाक है। वे इसे "शिलिंग" (shilling) कहते हैं।

चाल: "नकली प्रतियोगी"

कल्पना कीजिए कि नीलामीकर्ता का एक गुप्त दोस्त है जो प्रतिस्पर्धा को वास्तव में जितना तीव्र दिखाना है, उससे कहीं अधिक दिखाने के लिए नकली बोलियां लगाता है।

यदि आप जीतते हैं: बहुत बढ़िया! आपको वस्तु मिल जाती है, और नकली दोस्त का कोई महत्व नहीं रह जाता।
यदि आप हारते हैं: नीलामीकर्ता आपको नकली बोली सहित उच्चतम बोली बताता है।

तो, यदि वास्तविक उच्चतम बोली \ $50 थी, लेकिन नकली दोस्त ने \$ 80 की बोली लगाई, तो नीलामीकर्ता आपको बताता है, "आप $80 की बोली से हार गए!"

समस्या: आप सोच सकते हैं, "वाह, हर कोई \ $80 की बोली लगा रहा है! अगली बार मुझे \$ 85 की बोली लगानी चाहिए!" लेकिन वास्तविक प्रतिस्पर्धा केवल $50 की थी। आपको अधिक भुगतान करने के लिए लुभाया जा रहा है।
ट्विस्ट: कभी-कभी, नकली दोस्त बहुत कम बोली लगाता है (मान लीजिए \ $10)। यदि वास्तविक बोली \$ 50 थी, तो नीलामीकर्ता अभी भी अधिकतम राशि बताता है, जो कि $50 है। इस मामले में, आपको वास्तविक जानकारी मिलती है।

यह शोध पत्र पूछता है: एक स्मार्ट बोली लगाने वाला वास्तविक कीमतों को कैसे सीख सकता है जब नीलामीकर्ता हारने वाली बोलियों के बारे में झूठ बोल रहा हो, लेकिन केवल कभी-कभी?

दो-आयामी रणनीति

लेखकों ने एक "लर्निंग एल्गोरिदम" (कंप्यूटर के लिए नियमों का एक सेट) डिजाइन किया है जो एक सतर्क जासूस की तरह काम करता है। यह एक साथ दो अलग-अलग दृष्टिकोणों का उपयोग करता है, जैसे कि एक सुरक्षा जाल (safety net) और एक हाई-स्पीड कार का होना।

1. सुरक्षा जाल (द "रोबस्ट" ब्रांच)

एल्गोरिदम का यह हिस्सा कहता है, "मुझे हारने वाली बोली की रिपोर्टों पर बिल्कुल भरोसा नहीं है। मैं नकली नंबरों को अनदेखा करूँगा।"

यह केवल इस बात को देखता है कि आप जीते या हारे।
यह नीलामी को एक साधारण "प्राइस टैग" खेल की तरह मानता है (जैसे कॉफी खरीदना जहाँ आप बस देखते हैं कि क्या आप उसे खरीद सकते हैं)।
परिणाम: यह धीमा और सुरक्षित है। यह गारंटी देता है कि आप बहुत अधिक पैसा नहीं खोएंगे, लेकिन आप बहुत तेज़ी से नहीं सीख पाएंगे। यह अंधेरे में सावधानी से चलने जैसा है।

2. आशावादी (द "ऑप्टिमिस्टिक" ब्रांच)

यह हिस्सा कहता है, "आइए हम नकली नंबरों का उपयोग करने की कोशिश करें, लेकिन हमें स्मार्ट होना होगा।"

यह नकली बोलियों के पैटर्न को जानता है (उदाहरण के लिए, "नकली दोस्त आमतौर पर \ $10 और \$ 20 के बीच बोली लगाता है")।
जब यह एक हारने वाली बोली देखता है, तो यह नकली हिस्से को "घटाने" और यह अनुमान लगाने के लिए कुछ गणित करता है कि वास्तविक बोली क्या रही होगी।
कैच: यह केवल तभी अच्छा काम करता है जब नकली बोलियां इतनी कम हों कि वास्तविक बोली झलक सके।
परिणाम: जब नकली बोलियां कम और मददगार होती हैं, तो यह तरीका सुरक्षा जाल की तुलना में बहुत तेज़ी से सीखता है। यह एक साफ सड़क पर तेज़ गाड़ी चलाने जैसा है।

3. "रेसिंग" तंत्र

एल्गोरिदम को पहले से पता नहीं होता कि कौन सा तरीका बेहतर काम करेगा। इसलिए, यह दोनों को एक साथ एक "रेस" में चलाता है।

यह लगातार जांचता है: "क्या आशावादी (Optimist) समझ में आ रहा है? क्या डेटा विश्वसनीय है?"
यदि नकली बोलियां बहुत अधिक हैं और आशावादी भ्रमित हो रहा है, तो एल्गोरिदम वापस सुरक्षा जाल (Safety Net) पर स्विच कर जाता है।
यदि डेटा साफ दिखता है, तो यह तेज़ी से सीखने के लिए आशावादी की ओर झुक जाता है।

बड़ी खोज

यह शोध पत्र सिद्ध करता है कि भले ही नीलामीकर्ता जानकारी में हेरफेर कर रहा हो, फिर भी सीखने वाला व्यक्ति आश्चर्यजनक रूप से अच्छा प्रदर्शन कर सकता है।

यदि नकली बोलियां हमेशा उच्च रहती हैं: सीखने वाला "सुरक्षा जाल" की धीमी गति तक ही सीमित रहता है।
यदि नकली बोलियां कभी-कभी कम होती हैं: तो सीखने वाला "आशावादी" का उपयोग करके तेज़ गति से सीख सकता है, जिससे वह अनुमान लगाने की तुलना में बहुत तेज़ी से सीख पाता है।

लेखकों ने एक गणितीय सीमा भी सिद्ध की: आप अनंत रूप से तेज़ नहीं सीख सकते। एक "गति सीमा" है जो इस बात पर आधारित है कि नकली बोलियाँ कितनी बार गलती से सच्चाई प्रकट करती हैं। यदि नकली बोलियाँ बहुत दुर्लभ (कम संभावना) हैं, तो आप धीरे चलने के लिए मजबूर हैं। यदि वे अक्सर होती हैं, तो आप तेज़ चल सकते हैं।

संक्षेप में

यह शोध पत्र एक फिक्स्ड गेम में बोली लगाने को सीखने के बारे में है जहाँ रेफरी स्कोर के बारे में झूठ बोलता है। लेखकों ने एक ऐसी रणनीति बनाई है जो आवश्यकतानुसार झूठ को अनदेखा करती है लेकिन जहाँ संभव हो, झूठ के भीतर छिपे सच का चतुराई से उपयोग करती है। उन्होंने दिखाया कि भले ही रेफरी झूठ बोल रहा हो, आप अभी भी बाजार की कीमतों को कुशलतापूर्वक सीख सकते हैं, बशर्ते आपके पास यह बताने का तरीका हो कि रेफरी कब मददगार हो रहा है और कब वह केवल आपको उलझा रहा है।

तकनीकी सारांश: फीडबैक-हेरफेर वाले नीलामियों में बोली लगाना सीखना

समस्या का परिवेश (Problem Setting)
यह शोध पत्र बार-बार होने वाली प्रथम-मूल्य नीलामियों (first-price auctions) की जांच करता है जहाँ नीलामीकर्ता (या विक्रेता) "शिलिंग" (shilling) में संलग्न होता है—अर्थात, सीखने वाले बोलीदाता (learner) द्वारा प्राप्त फीडबैक को मैनिपुलेट करने के लिए कृत्रिम बोलियों का उपयोग करना। पारंपरिक मॉडलों के विपरीत, जहाँ हेरफेर आवंटन नियम या भुगतान को बदल सकता है, यह कार्य फीडबैक-हेरफेर वाली नीलामियों पर केंद्रित है। विशेष रूप से, शिक्षार्थी एक वास्तविक उच्चतम प्रतिस्पर्धी बोली, $b_t$ , के विरुद्ध प्रतिस्पर्धा करता है और यदि उनकी बोली $p_t \geq b_t$ है, तो वे जीत जाते हैं। हालाँकि, हारने पर, शिक्षार्थी वास्तविक $b_t$ को नहीं देख पाता है। इसके बजाय, वे एक शिल्ड रिपोर्ट $o_t = \max\{b_t, s_t\}$ देखते हैं, जहाँ $s_t$ एक ज्ञात वितरण $S$ से ली गई एक स्वतंत्र शिल बोली है।

यह सेटअप एक अनूठी सीखने की चुनौती पैदा करता है: आवंटन सत्यनिष्ठ (truthful) रहता है (शिक्षार्थी वास्तविकता के आधार पर जीतता या हारता है), लेकिन सूचना चैनल विकृत हो जाता है। उच्च शिल बोलियाँ वास्तविक प्रतिस्पर्धा को छिपा देती हैं, जबकि कम शिल बोलियाँ "सफिक्स जानकारी" (बड़ी बोलियों के बारे में जानकारी) प्रकट करती हैं। लक्ष्य वास्तविक मूल्य $v_t$ के लिए सर्वोत्तम स्थिर बोली के विरुद्ध रिग्रेट (regret) को न्यूनतम करना है, जो इस मास्क किए गए फीडबैक की उपस्थिति में होता है।

कार्यप्रणाली (Methodology)
लेखक एक एल्गोरिदम का प्रस्ताव करते हैं जो कीमतों और मूल्यों के एक विविक्त ग्रिड (discretized grid) पर युगों (epochs) में कार्य करता है। मुख्य नवाचार एक दोहरी-शाखा दृष्टिकोण (dual-branch approach) है जिसे सत्यापन और रेसिंग प्रक्रिया (validation and racing procedure) के साथ जोड़ा गया है:

रोबस्ट शाखा (अंतराल उन्मूलन - Interval Elimination): यह शाखा शिल्ड रिपोर्टों को पूरी तरह से अनदेखा करती है, और केवल बाइनरी जीत/हार के परिणाम पर निर्भर रहती है। यह समस्या को सेंसर किए गए फीडबैक के साथ एक डायनेमिक प्राइसिंग कार्य के रूप में देखती है। यह शाखा यह गारंटी देती है कि जब शिलिंग गंभीर हो या शिल वितरण सूचनात्मक न हो, तब भी रिग्रेट दर $\tilde{O}(T^{2/3})$ बनी रहेगी।
ऑप्टिमिस्टिक शाखा (डीबायस्ड सफिक्स लर्निंग - Debiased Suffix Learning): यह शाखा शिल्ड रिपोर्टों का लाभ उठाने का प्रयास करती है। चूंकि शिल वितरण $F_S$ $F_{S}$ ज्ञात है, इसलिए एल्गोरिदम $o_t$ $o_{t}$ का उपयोग करके वास्तविक प्रतिस्पर्धी बोली वितरण $F_B$ $F_{B}$ के लिए एक निष्पक्ष अनुमानक (unbiased estimator) का निर्माण करता है।
- यह सफिक्स अवलोकनों (suffix observations) का उपयोग करता है: जब $o_t \leq q$ होता है, तो इसका अर्थ है कि $b_t \leq q$ (यदि शिल पर्याप्त कम था)।
- यह प्रत्यक्ष जीत/हार मापनों के साथ इन सफिक्स-अंतर मापों को संयोजित करने के लिए एक वेटेड लीस्ट-स्क्वेयर्स (weighted least-squares) ढांचे का उपयोग करता है।
- महत्वपूर्ण रूप से, यह एक ज्यामितीय अनिश्चितता विश्लेषण (geometric uncertainty analysis) पेश करता है। एल्गोरिदम केवल बिंदुवार (pointwise) मानों का अनुमान नहीं लगाता है, बल्कि सक्रिय बोलियों के अंतरालों पर कॉन्फिडेंस बाउंड्स का निर्माण करता है, इस तथ्य का लाभ उठाते हुए कि एक एकल कम-शिल घटना उच्च बोलियों की एक पूरी रेंज के बारे में जानकारी प्रकट करती है।
डायैडिक सत्यापन (Dyadic Validation): एल्गोरिदम यह धारणा नहीं मानता कि शिल वितरण का पैमाना (विशेष रूप से एक "लो-शिल" घटना की संभावना $\gamma$ जो जानकारी प्रकट करती है) ज्ञात है। यह शिल स्केल के डायैडिक उम्मीदवारों के सेट के विरुद्ध ऑप्टिमिस्टिक अपडेट्स को सत्यापित करता है। यदि कोई ऑप्टिमिस्टिक उम्मीदवार सत्यापन में विफल रहता है (उदाहरण के लिए, शिल वितरण बहुत अनियमित है या स्केल बहुत छोटा है), तो एल्गोरिदम रोबस्ट शाखा पर वापस चला जाता है।

प्रमुख योगदान (Key Contributions)

सेफ्टी नेट्स के साथ मजबूती (Robustness with Safety Nets): यह पेपर एक रोबस्ट अंतराल-उन्मूलन प्रक्रिया प्रदान करता है जो $\tilde{O}(T^{2/3})$ डायनेमिक प्राइसिंग दर प्राप्त करता है, भले ही शिलिंग फीडबैक को बेकार बना दे।
ऑप्टिमिस्टिक डीबायसिंग (Optimistic Debiasing): यह शिल्ड रिपोर्टों के स्ट्रक्चर्ड सिग्नल से जानकारी निकालने के लिए एक ऑप्टिमिस्टिक प्रक्रिया विकसित करता है। सफिक्स अवलोकनों को आसन्न उपयोगिता अंतर (utility differences) के मापन में बदलकर, एल्गोरिदम तेज़ दर प्राप्त करता है जब सक्रिय बोली क्षेत्र नियमित और अच्छी तरह से कवर होते हैं।
मानदंडों के अनुसार, यह प्रक्रिया डायनेमिक प्राइसिंग शासन (जब शिलिंग भारी होती है) और मानक फर्स्ट-प्राइस ऑक्शन (जब शिलिंग हल्की होती है) के बीच के अंतर को पाटती है।
अनुकूलन क्षमता (Adaptivity): एल्गोरिदम अज्ञात शिल स्तर के माध्यम से अनुकूलित होता है, जिससे शिल स्केल या फीडबैक ज्यामिति के पूर्व ज्ञान की आवश्यकता समाप्त हो जाती है।
टाइट लोअर बाउंड्स (Tight Lower Bounds): लेखक सिंगल-एक्टिव-रीजन मामले के लिए एक मिलान करने वाला लोअर बाउंड सिद्ध करते हैं। वे एक "हिडन सेल" (hidden cell) उदाहरण का निर्माण करते हैं जहाँ एक अज्ञात अंतराल में एक छोटा यूटिलिटी बंप मौजूद होता है। यह प्रमाण दर्शाता है कि रिग्रेट मौलिक रूप से स्थानीय खोज (डायनेमिक प्राइसिंग शासन) और हारने वाले पक्ष की रिपोर्टों के माध्यम से क्रॉस-लर्निंग के बीच के ट्रेड-ऑफ द्वारा सीमित है।

परिणाम (Results)
पेपर (लॉग कारकों को छोड़कर) निम्नलिखित रिग्रेट बाउंड स्थापित करता है:

अपर बाउंड (Upper Bound): एल्गोरिदम $\tilde{O}\left(\min\left\{T^{2/3}, \rho^{1/4}\sqrt{T}\gamma^{-1/4}\right\}\right)$ $\tilde{O} (min {T^{2/3}, ρ^{1/4} T γ^{- 1/4}})$ का रिग्रेट प्राप्त करता है, जहाँ $\rho$ $ρ$ सक्रिय बोली क्षेत्रों की संख्या है और $\gamma$ $γ$ सूचनात्मक लो-शिल घटनाओं की संभावना है।
- सिंगल-एक्टिव-रीजन मामले ( $\rho=1$ ) में, बाउंड $\tilde{O}\left(\min\left\{T^{2/3}, \sqrt{T}\gamma^{-1/4}\right\}\right)$ है।
- यह दर डायनेमिक प्राइसिंग की $T^{2/3}$ दर (जब शिलिंग भारी होती है, $\gamma \to 0$ ) और मानक फर्स्ट-प्राइस ऑक्शन की $\sqrt{T}$ दर (जब शिलिंग हल्की होती है, $\gamma$ बड़ा होता है) के बीच इंटरपोलेट करती है।
लोअर बाउंड (Lower Bound): सिंगल-एक्टिव-रीजन मामले के लिए, पेपर $\Omega\left(\min\left\{T^{2/3}, \sqrt{T}\gamma^{-1/4}\right\}\right)$ का लोअर बाउंड सिद्ध करता है। यह पुष्टि करता है कि एल्गोरिदम लॉगरिदमिक कारकों तक मिनिमैक्स-ऑप्टिमल है। लोअर बाउंड निर्माण यह उजागर करता है कि शिल वितरण के ज्ञान के बावजूद, शिक्षार्थी $\sqrt{T}$ दर को पूरी तरह से प्राप्त नहीं कर सकता यदि सूचनात्मक शिल घटनाएं दुर्लभ हैं, क्योंकि "हिडन सेल" को जल्दी पहचानना कठिन रहता है।

महत्ता और दावे (Significance and Claims)
यह पेपर दावा करता है कि केवल फीडबैक-ओनली शिलिंग (जहाँ आवंटन नियम अछूता रहता है) भी बार-बार होने वाली बोली लगाने की सांख्यिकीय कठिनाई को तीव्रता से बदल सकती है। हेरफेर सूचना चैनल के माध्यम से कार्य करता है, जो शिक्षार्थी को उच्च बोलियों की ओर झुकाता है और उस क्रॉस-लर्निंग संरचना को आंशिक रूप से नष्ट कर देता है जो आमतौर पर फर्स्ट-प्राइस ऑक्शन में $\sqrt{T}$ रिग्रेट की अनुमति देती है।

लेखक इस कार्य को ऑक्शन में फीडबैक हेरफेर के सिद्धांत की दिशा में एक पहला कदम के रूप में प्रस्तुत करते हैं। वे स्पष्ट रूप से कहते हैं कि अज्ञात शिल वितरणों, समृद्ध शिलिंग मॉडलों (जैसे, शिक्षार्थी की बोली पर निर्भर शिलिंग), और अधिक सामान्य सक्रिय-क्षेत्र ज्यामिति तक इन परिणामों का विस्तार करना एक खुला प्रश्न बना हुआ है। इसकी महत्ता इस बात में है कि यह प्रदर्शित करना कि विशिष्ट संरचनात्मक बाधाओं (जैसे ज्ञात वितरण के साथ मैक्स-शिलिंग) का पालन करने पर, हेरफेर किए गए फीडबैक की संरचना का कुशलतापूर्वक लाभ उठाकर, विशुद्ध रूप से रोबस्ट दृष्टिकोण की तुलना में बहुत अधिक रिकवर किया जा सकता है।