💻 computer science

Profit Maximization in Bilateral Trade against a Smooth Adversary

यह शोध पत्र द्विपक्षीय व्यापार में एक लाभ-अधिकतमीकरण करने वाले ब्रोकर के लिए एक लर्निंग एल्गोरिदम प्रस्तुत करता है, जो एक स्मूथ प्रतिपक्षी (smooth adversary) के विरुद्ध $\tilde{O}(\sqrt{T})$ का टाइट रिग्रेट बाउंड प्राप्त करता है, जो स्मूथ इंस्टेंस की निरंतरता और एक पदानुक्रमित नेट-निर्माण (hierarchical net-construction) का लाभ उठाकर स्टोकेस्टिक और पूर्णतः प्रतिपक्षी सेटिंग्स के बीच के प्रदर्शन अंतराल को पाटता है।

मूल लेखक: Simone Di Gregorio, Paul Dütting, Federico Fusco, Chris Schwiegelshohn

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

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

CC BY 4.0

मूल लेखक: Simone Di Gregorio, Paul Dütting, Federico Fusco, Chris Schwiegelshohn

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

कल्पना कीजिए कि आप एक बिचौलिये (matchmaker) हैं जो एक व्यस्त बाज़ार चला रहे हैं। हर दिन, एक नया विक्रेता और एक नया खरीदार आता है, जिनमें से प्रत्येक के मन में एक गुप्त कीमत होती है: विक्रेता कम से कम $X के लिए बेचना चाहता है, और खरीदार अधिक से अधिक$ Y चुकाना चाहता है।

आपका काम सौदे के नियम तय करना है। आप जितना अधिक लाभ (profit) कमा सकें, उतना ही बेहतर है (वह अंतर जो खरीदार भुगतान करता है और जो विक्रेता को मिलता है), लेकिन आपको निष्पक्ष भी रहना है:

आप उन्हें झूठ बोलने के लिए धोखा नहीं दे सकते।
उन्हें भाग लेने से नुकसान नहीं होना चाहिए।

चुनौती यह है कि आपको उनकी गुप्त कीमतों का पहले से पता नहीं है। आपको समय के साथ इन नियमों को 'ट्रायल एंड एरर' (परीक्षण और त्रुटि) के माध्यम से सीखना होगा।

"प्रतिद्वंद्वी" (Opponents) के तीन प्रकार

इस शोध पत्र में, लेखक देखते हैं कि तीन अलग-अलग प्रकार के "विरोधी" (वे लोग जो कीमतें निर्धारित करते हैं) के खिलाफ इन नियमों को सीखना कितना कठिन है:

रैंडमाइज़र (The Randomizer - Stochastic/i.i.d.): कल्पना कीजिए कि कीमतें एक निश्चित, अपरिवर्तित रेसिपी (जैसे पासा फेंकना) से ली गई हैं। इसे सीखना आसान है। आप बस एक औसत (average) निकालते रहते हैं, और आप बहुत जल्दी इसमें माहिर हो जाते हैं।
धोखेबाज (The Trickster - Adversarial): कल्पना कीजिए कि एक मास्टरमाइंड है जो आपकी रणनीति को जानता है और आपको भ्रमित करने और विफल करने के लिए जानबूझकर कीमतें चुनता है। इस सबसे खराब स्थिति में, यह शोध पत्र एक ज्ञात तथ्य की पुष्टि करता है: आप सीख नहीं सकते। आपकी एल्गोरिदम कितनी भी स्मार्ट क्यों न हो, आप कभी भी सर्वश्रेष्ठ रणनीति की बराबरी नहीं कर पाएंगे।
स्मूथ एडवरसरी (The Smooth Adversary - द नया नायक): यह बीच का रास्ता है। प्रतिद्वंद्वी अभी भी आपको परेशान करने के लिए हर दिन कीमतें बदल सकता है, लेकिन उन्हें बहुत अधिक "नुकीला" (spiky) होने की अनुमति नहीं है। वे कीमतों को अचानक $0.01 से$ 0.99 में नहीं बदल सकते। उनके बदलाव "स्मूथ" होने चाहिए, जैसे एक लहर, न कि बिजली की कौंध की तरह।

बड़ा सवाल: क्या हम इस "स्मूथ एडवरसरी" के खिलाफ प्रभावी ढंग से सीख सकते हैं? लेखक कहते हैं कि हाँ, और वे इसे सिद्ध करते हैं।

समाधान: "सीढ़ी" रणनीति (HIER-MECH)

मुख्य कठिनाई यह है कि जो "नियम" आप सेट कर सकते हैं, वे अविश्वसनीय रूप से जटिल हैं। आप केवल एक कीमत (जैसे "₹5 पर बेचें") नहीं चुन रहे हैं। आप एक जटिल मानचित्र (map) चुन रहे हैं जो यह तय करता है कि कब व्यापार होता है, जो खरीदार और विक्रेता दोनों की कीमतों पर आधारित होता है। यह मानचित्र एक वर्गाकार कागज पर खींची गई एक आकृति की तरह है।

यदि आप इस आकृति का अनुमान लगाने के लिए हर संभव संस्करण का परीक्षण करने की कोशिश करते हैं, तो आपको अनंत आकृतियों का परीक्षण करना होगा। यह असंभव है।

लेखकों ने एक चतुर एल्गोरिदम का आविष्कार किया जिसे HIER-MECH (Hierarchical Mechanism) कहा जाता है। यह इस प्रकार काम करता है, एक सीढ़ी के उदाहरण का उपयोग करते हुए:

खुरदरी सीढ़ी (Coarse Ladder - Rungs): कल्पना कीजिए कि एक सीढ़ी है जिसके डंडे (rungs) एक-दूसरे से बहुत दूर हैं। नीचे, आपके पास बहुत सरल, ब्लॉक जैसी आकृतियाँ हैं (जैसे एक बड़ा वर्ग)। ऐसे बहुत कम विकल्प हैं।
बारीक सीढ़ी (Fine Ladder - Rungs): जैसे-जैसे आप ऊपर जाते हैं, डंडे करीब आते जाते हैं। आकृतियाँ अधिक विस्तृत और सटीक होती जाती हैं।
रणनीति: सीधे पूर्ण आकार खोजने के बजाय, एल्गोरिदम इस सीढ़ी पर "अनुमान और जाँच" (guess and check) का खेल खेलता है।
- यह नीचे से शुरू होता है, बड़े और सरल आकारों का परीक्षण करता है।
- यह यह तय करने के लिए एक स्मार्ट बेटिंग सिस्टम (जिसे HEDGE कहा जाता है) का उपयोग करता है कि सीढ़ी पर कौन सा रास्ता सबसे अधिक आशाजनक लग रहा है।
- यह केवल एक आकार नहीं चुनता; यह सीढ़ी पर एक "रैंडम वॉक" बनाता है। यह प्रभावी रूप से कहता है, "मुझे 90% यकीन है कि उत्तर इसी सामान्य क्षेत्र में है, इसलिए अगली बार मैं उस क्षेत्र में थोड़े अधिक विस्तृत आकारों का परीक्षण करूँगा।"

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

परिणाम: एक आदर्श संतुलन

यह शोध पत्र सिद्ध करता है कि यह सीढ़ी रणनीति अविश्वसनीय रूप से कुशल है।

गति: एल्गोरिदम लगभग $\sqrt{T}$ (जहाँ $T$ दिनों की संख्या है) की दर से सीखता है।
तुलना: यह "रैंडमाइज़र" (आसान मामला) से सीखने की गति के बराबर है।
ब्रेकथ्रू: यह एक बड़ी उपलब्धि है क्योंकि अब तक, हमें लगता था कि आप केवल तभी इतनी तेज़ी से सीख सकते हैं जब डेटा रैंडम हो। लेखक दिखाते हैं कि "स्मूथ एडवरसरी" (जो आपको भ्रमित करने की कोशिश कर रहा है, बस बहुत अधिक आक्रामक तरीके से नहीं) के खिलाफ भी, आप उतनी ही तेज़ी से सीख सकते हैं जितना कि सब कुछ रैंडम होने पर।

उन्होंने यह भी दिखाया कि यह परिणाम टाइट (tight) है। आप इससे बेहतर नहीं कर सकते; $\sqrt{T}$ इस समस्या के लिए सबसे तेज़ संभव गति है।

एक साइड क्वेस्ट: "जॉइंट एड्स" (Joint Ads) की समस्या

लेखकों ने यह भी दिखाया कि उनकी सीढ़ी रणनीति "जॉइंट एड्स" नामक एक संबंधित समस्या के लिए भी काम करती है।

परिदृश्य: कल्पना कीजिए कि दो विज्ञापनदाता एक ही विज्ञापन स्लॉट को एक साथ खरीदना चाहते हैं। या तो वे दोनों इसे प्राप्त करते हैं, या कोई भी नहीं।
संबंध: लेखकों ने सिद्ध किया कि यह समस्या द्विपक्षीय व्यापार (bilateral trade) समस्या के गणितीय रूप से समान है। "जॉइंट एड्स" समस्या को उनके "द्विपक्षीय व्यापार" ढांचे में बदलकर, वे उसी सीढ़ी एल्गोरिदम का उपयोग कर सके।
परिणाम: उन्होंने इस विज्ञापन समस्या के लिए पिछले सर्वोत्तम ज्ञात सीखने की गति में सुधार किया, जिससे यह व्यापार समस्या के समान तेज़ हो गई।

सारांश

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

इसका उत्तर यह है कि एक ही बार में पूर्ण नियम का अनुमान लगाने की कोशिश करना बंद करें। इसके बजाय, पहले सरल नियमों का परीक्षण करने के लिए, फिर धीरे-धीरे उन्हें परिष्कृत करने के लिए एक पदानुक्रमित सीढ़ी (hierarchical ladder) का उपयोग करें। यह दृष्टिकोण एक ब्रोकर को उतनी ही तेज़ी से सीखने की अनुमति देता है जितनी तेज़ी से वह तब सीख सकता है जब दुनिया पूरी तरह से रैंडम हो, भले ही दुनिया सक्रिय रूप से कठिन होने की कोशिश कर रही हो, बशर्ते वह कठिनाई बहुत अधिक "नुकीली" न हो।

तकनीकी सारांश: एक सुचारू प्रतिपक्षी (Smooth Adversary) के विरुद्ध द्विपक्षीय व्यापार में लाभ अधिकतमकरण

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

लर्निंग परिवेश को एक $\sigma$ -सुचारू प्रतिपक्षी ( $\sigma$ -smooth adversary) द्वारा परिभाषित किया गया है। मानक स्टोकेस्टिक सेटिंग (जहाँ मूल्यांकन एक निश्चित वितरण से i.i.d. रूप से प्राप्त होते हैं) या मानक प्रतिपक्षी सेटिंग (जहाँ मूल्यांकन मनमाने हो सकते हैं) के विपरीत, यहाँ $\sigma$ -सुचारू प्रतिपक्षी प्रत्येक समय चरण पर ऐसे वितरण चुनता है जो "बहुत अधिक केंद्रित न होने" (अर्थात, किसी भी बोरेल सेट पर उनका संभाव्यता द्रव्यमान, उस सेट के लेबेग माप के विभाजित $\sigma$ के बराबर है) के रूप में सीमित होते हैं।

मुख्य चुनौती गैर-पैरामीट्रिक क्रिया स्थान (non-parametric action space) की प्रकृति है; वैध तंत्रों का सेट अनंत और जटिल है; एक तंत्र को इकाई वर्ग $[0,1]^2$ में एक मोनोटोन आवंटन क्षेत्र और संबंधित मायर्सन भुगतानों द्वारा परिभाषित किया जाता है। यह समस्या को मानक ऑनलाइन तंत्र डिजाइन साहित्य से अलग करता है, जो अक्सर पैरामीट्रिक सेटिंग्स (जैसे, एकल रिजर्व प्राइस सीखना) पर ध्यान केंद्रित करता है। पिछले कार्यों ने स्थापित किया था कि सामान्य प्रतिपक्षी सेटिंग में उप-रैखिक पछतावा (sublinear regret) असंभव है, लेकिन i.i.d. सेटिंग में यह प्राप्त करने योग्य है। खुला प्रश्न यह था कि क्या $\sigma$ -सुचारू प्रतिपक्षी मॉडल के माध्यम से इन दोनों चरम सीमाओं के बीच के "अंतराल" को भरा जा सकता है।

कार्यप्रणाली (Methodology)
लेखक एक लर्निंग एल्गोरिदम प्रस्तावित करते हैं जिसका नाम HIER-MECH है, जो $\tilde{O}(\frac{1}{\sigma}\sqrt{T})$ का रिग्रेट बाउंड प्राप्त करता है। इसकी कार्यप्रणाली तीन प्रमुख तकनीकी घटकों पर निर्भर करती है:

ग्रिड तंत्र और $L_1$ -नेट गारंटी:
लेखक निरंतर तंत्र स्थान को $\epsilon$ -ग्रिड तंत्रों का उपयोग करके विविक्त (discretize) करते हैं, जहाँ आवंटन क्षेत्र $\epsilon$ के स्टेप साइज वाले एक समान ग्रिड के टाइल्स का संघ (union) है। महत्वपूर्ण रूप से, वे इस समस्या के लिए विशिष्ट एक नवीन $L_1$ -नेट गारंटी (लेम्मा 2) सिद्ध करते हैं। वे दिखाते हैं कि किसी भी तंत्र $M$ के लिए, एक ग्रिड सन्निकटन $\phi_\epsilon(M)$ मौजूद है, जिससे अपेक्षित लाभ में अंतर $O(\epsilon/\sigma)$ द्वारा सीमित है। यह बाउंड प्रतिपक्षी की सुचारूता और द्विपक्षीय व्यापार भुगतानों की विशिष्ट ज्यामितीय संरचना (आवंटन सीमा पर प्रोजेक्शन) पर निर्भर करता है। पिछले कार्यों के विपरीत, जो नियतात्मक $L_\infty$ नेट्स पर निर्भर थे (जो इस हाइपोथेसिस क्लास के लिए अस्तित्व में नहीं हैं), यह संभाव्य बाउंड विश्लेषण के लिए पर्याप्त है।
एल्गोरिद्मिक चेनिंग (Algorithmic Chaining):
उन सीमाओं को दूर करने के लिए जहाँ मानक "फॉलो-द-लीडर" या "हेज" दृष्टिकोण विफल हो जाते हैं (या सीधे ग्रिड पर लागू होने पर $O(T^{2/3})$ जैसी उप-इष्टतम दरें देते हैं), लेखक एल्गोरिद्मिक चेनिंग का उपयोग करते हैं।

वे एक मैकेनिज्म ट्री (Mechanism Tree) का निर्माण करते हैं जहाँ स्तर $h$ के नोड्स $2^{-h}$ -ग्रिड तंत्रों का प्रतिनिधित्व करते हैं।
एल्गोरिदम प्रत्येक आंतरिक नोड (internal node) के लिए एक स्थानीय HEDGE एल्गोरिदम के कई इंस्टेंस बनाए रखता है।
प्रत्येक समय चरण पर, एल्गोरिदम ट्री में एक रैंडम वॉक करता है, और स्थानीय हेज वितरणों के आधार पर एक लीफ (leaf) तंत्र चुनता है।
यह पदानुक्रमित संरचना स्टोकैस्टिक सेटिंग्स में उपयोग किए जाने वाले संभाव्य चेनिंग (probabilistic chaining) के प्रभाव की नकल करती है। यह एल्गोरिदम को "ड्यूडली-टाइप" बाउंड प्राप्त करने की अनुमति देता है, जो मानक $\sqrt{T \log N}$ एक्सपर्ट बाउंड (जहाँ $N$ विशेषज्ञों की संख्या है) में सुधार करता है।

जॉइंट एड्स (Joint Ads) से न्यूनीकरण (Reduction):
लेखक जॉइंट एड्स समस्या (जहाँ दो एजेंट एक गैर-अपवर्जित वस्तु खरीदने के लिए सहयोग करते हैं) से द्विपक्षीय व्यापार में एक औपचारिक न्यूनीकरण स्थापित करते हैं। द्विपक्षीय व्यापार डोमेन को एक विशिष्ट उप-आयत (sub-rectangle) तक सीमित करके और एक कोआर्डिनेट ट्रांसफॉर्मेशन लागू करके, वे जॉइंट एड्स समस्या को द्विपक्षीय व्यापार सेटिंग में मैप करते हैं। यह न्यूनीकरण दो उद्देश्यों की पूर्ति करता है:

यह जॉइंट एड्स समस्या पर $\tilde{O}(\frac{1}{\sigma}\sqrt{T})$ का ऊपरी बाउंड स्थानांतरित करता है, जो पिछले $O(T^{2/3})$ बाउंड में सुधार करता है।
यह द्विपक्षीय व्यापार के लिए $\Omega(\sqrt{T})$ का निचला बाउंड (lower bound) प्रदान करता है, जिससे यह सिद्ध होता है कि HIER-MECH एल्गोरिदम की दर (पॉली-लॉगैरिथमिक कारकों तक) सटीक (tight) है।

प्रमुख परिणाम

रिग्रेट बाउंड: HIER-MECH एल्गोरिदम एक $\sigma$ -सुचारू प्रतिपक्षी के विरुद्ध $O(\frac{1}{\sigma}\sqrt{T} \log T)$ का रिग्रेट बाउंड प्राप्त करता है।
सटीकता (Tightness): यह दर स्टोकेस्टिक i.i.d. मामले के मिनिमैक्स रेट से मेल खाती है, और सामान्य प्रतिपक्षी मामले (जहाँ उप-रैखिक पछतावा असंभव है) से अलग है। $\Omega(\sqrt{T})$ निचला बाउंड यह पुष्टि करता है कि HIER-MECH की दर $T$ पर निर्भरता के मामले में इष्टतम है।
जॉइंट एड्स: न्यूनीकरण जॉइंट एड्स समस्या के लिए एक सटीक $\tilde{O}(\frac{1}{\sigma}\sqrt{T})$ रिग्रेट बाउंड प्रदान करता है, जिससे पूर्व साहित्य का एक खुला प्रश्न हल होता है।

महत्व और दावे
यह शोध पत्र दावा करता है कि यह आर्थिक तंत्र डिजाइन में तेज़ लर्निंग रेट प्राप्त करने योग्य सेटिंग्स के दायरे को महत्वपूर्ण रूप से विस्तृत करता है। i.i.d. सेटिंग से $\sigma$ -सुचारू प्रतिपक्षी तक मजबूत रिग्रेट गारंटी का विस्तार करके, लेखक प्रदर्शित करते हैं कि आर्थिक समस्याओं में प्रतिपक्षी असंभवता परिणामों (adversarial impossibility results) को पार करने के लिए 'सुचारूता' (smoothness) एक प्रभावी उपकरण है।

यह कार्य एल्गोरिद्मिक चेनिंग के पहले अनुप्रयोगों में से एक है जो एक गैर-पैरामीट्रिक तंत्र डिजाइन समस्या पर लागू होता है, जो ऑनलाइन रिग्रेशन में इसके पारंपरिक उपयोग से आगे बढ़ता है। लेखक रेखांकित करते हैं कि जबकि सांख्यिकीय दर ( $\sqrt{T}$ ) प्राप्त कर ली गई है, फिर भी एक कंप्यूटेशनल गैप बना हुआ है: HIER-MECH का रनिंग टाइम $\exp(\sqrt{T})$ के रूप में स्केल करता है, जबकि i.i.d. सेटिंग एक बहुपद-समय (polynomial-time) एल्गोरिदम की अनुमति देती है। इस कंप्यूटेशनल गैप को बंद करना और $\sigma$ पैरामीटर पर निर्भरता को और अधिक सटीक बनाना मुख्य खुले प्रश्न हैं।

संक्षेप में, यह शोध पत्र एक $\sigma$ -सुचारू प्रतिपक्षी के विरुद्ध द्विपक्षीय व्यापार में सीखने की सूचना-सैद्धांतिक सीमाओं (information-theoretic limits) को स्पष्ट करता है, यह दिखाते हुए कि सांख्यिकीय दृष्टिकोण से, सुचारू प्रतिपक्षी i.i.d. सेटिंग जितना ही "आसान" है, भले ही इसके लिए मौलिक रूप से भिन्न एल्गोरिद्मिक तकनीकों की आवश्यकता होती है।

"प्रतिद्वंद्वी" (Opponents) के तीन प्रकार

समाधान: "सीढ़ी" रणनीति (HIER-MECH)

परिणाम: एक आदर्श संतुलन

एक साइड क्वेस्ट: "जॉइंट एड्स" (Joint Ads) की समस्या

सारांश

इसी तरह के और पेपर