📊 statistics

Online Price Competition under Generalized Linear Demands

यह शोध पत्र सामान्यीकृत रैखिक मांग (generalized linear demands) वाले $N$ विक्रेताओं के बीच क्रमिक ऑनलाइन मूल्य प्रतिस्पर्धा के लिए एक नवीन विकेंद्रीकृत मूल्य निर्धारण नीति, PML-GLUCB, प्रस्तावित करता है, जो अज्ञात मापदंडों और बाइनरी एवं वास्तविक-मान वाले दोनों प्रकार के मांग अवलोकनों को समायोजित करते हुए, बिना किसी समन्वित अन्वेषण चरणों की आवश्यकता के, इष्टतम $\widetilde{O}(\sqrt{T})$ रिग्रेट (regret) प्राप्त करता है।

मूल लेखक: Daniele Bracale, Moulinath Banerjee, Cong Shi, Yuekai Sun

प्रकाशित 2026-06-17

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

CC BY 4.0

मूल लेखक: Daniele Bracale, Moulinath Banerjee, Cong Shi, Yuekai Sun

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

कल्पना कीजिए एक हलचल भरे बाज़ार की जहाँ N अलग-अलग विक्रेता (vendors) समान (लेकिन थोड़े अलग) उत्पाद बेच रहे हैं। हर दिन उन्हें यह निर्णय लेना होता है: आज मुझे क्या कीमत चुकानी चाहिए?

यदि वे बहुत अधिक कीमत वसूलते हैं, तो ग्राहक कहीं और चले जाते हैं। यदि वे बहुत कम कीमत लेते हैं, तो वे मुनाफ़ा छोड़ देते हैं। लेकिन पेच यह है कि एक विक्रेता जो कीमत तय करता है, वह सभी अन्य विक्रेताओं को प्रभावित करती है। यदि विक्रेता A अपनी कीमत कम करता है, तो विक्रेता B अपने ग्राहक खो सकता है, जिससे विक्रेता B को प्रतिक्रिया देने के लिए मजबूर होना पड़ सकता है। यह "प्राइस टैग" के साथ खेला जाने वाला "चिकन" (chicken) का एक निरंतर, उच्च-दांव वाला खेल है।

यह शोध पत्र इन विक्रेताओं के लिए एक नई रणनीति पेश करता है ताकि वे समय के साथ अपने सामान की कीमत सटीक रूप से तय करना सीख सकें, भले ही उन्हें यह न पता हो कि उनके ग्राहक वास्तव में कैसे सोचते हैं या उनके प्रतिद्वंदियों की प्रतिक्रिया कैसी होगी।

उनके समाधान का विवरण यहाँ सरल भाषा में दिया गया है:

1. समस्या: "अनुमान लगाने का खेल"

अतीत में, शोधकर्ताओं ने इसे इस तरह हल करने की कोशिश की कि विक्रेताओं को पहले एक विशिष्ट खेल खेलने के लिए कहा जाए: "पहले 100 दिनों के लिए, बस यह देखने के लिए यादृच्छिक (random) कीमतें चुनें कि क्या होता है। फिर, बाकी समय के लिए, जो आपने सीखा है उसका उपयोग करें।"

लेखक कहते हैं कि वास्तविक दुनिया में यह गलत सलाह है।

क्यों? वास्तविक बाज़ार में, आप महीनों तक यादृच्छिक कीमतों के साथ "प्रयोग" नहीं कर सकते। आप दिवालिया हो जाएंगे। साथ ही, आपको यह भी नहीं पता कि प्रयोग कब तक करना है।
वास्तविकता: विक्रेता केवल अपनी बिक्री देखते हैं। वे कभी नहीं देख पाते कि उनके प्रतिद्वंद्वियों ने कितनी वस्तुएं बेचीं या प्रतिद्वंद्वियों ने कितना पैसा कमाया। वे केवल प्रतिद्वंद्वियों की कीमतें देखते हैं। यह पोकर खेलने जैसा है जहाँ आप मेज पर रखे सभी के कार्ड देख सकते हैं, लेकिन आप उनके चिप्स या उनका अंतिम स्कोर नहीं देख सकते।

2. समाधान: "द ऑप्टिमिस्टिक लर्नर" (आशावादी शिक्षार्थी)

लेखक एक नया एल्गोरिदम प्रस्तावित करते हैं जिसे PML-GLUCB कहा जाता है। इसे एक ऐसे विक्रेता के रूप में सोचें जो आशावादी लेकिन सतर्क है।

एक अलग "लर्निंग फेज" के बजाय, यह विक्रेता बिक्री करते समय सीखता है। यह कैसे काम करता है, यहाँ देखें:

"सर्वश्रेष्ठ अनुमान" (पेनलाइज्ड MLE): हर दिन, विक्रेता अपनी बिक्री और कीमतों के इतिहास को देखता है। वे इस बारे में एक गणितीय सूत्र का उपयोग करते हैं कि ग्राहक कीमतों में बदलाव के प्रति कितने संवेदनशील हैं।
"आशावादी मोड़" (UCB): चूंकि उन्हें अपने अनुमान के बारे में 100% यकीन नहीं है, इसलिए वे एक "सुरक्षा बफर" जोड़ते हैं। वे अज्ञात स्थितियों के लिए सबसे अच्छे परिदृश्य (best-case scenario) को मान लेते हैं।
- उपमा: कल्पना कीजिए कि आप एक रहस्यमय बॉक्स के वजन का अनुमान लगा रहे हैं। आप जानते हैं कि यह 10 और 20 पाउंड के बीच है। सुरक्षित रहने के लिए, आप मान लेते हैं कि यह 20 पाउंड है। यदि आप गलत निकले, तो आप थोड़ा नुकसान उठाएंगे; यदि आप सही निकले, तो आप बड़ा लाभ कमाएंगे। एल्गोरिदम उस कीमत को चुनता है जो इस आशावादी परिदृश्य में विजेता दिखती है।
परिणाम: यह "आशावाद" विक्रेता को स्वाभाविक रूप से अलग-अलग कीमतें आज़माने के लिए मजबूर करता है। वे नए मूल्यों का परीक्षण इसलिए करते हैं क्योंकि वे जिज्ञासु हैं कि क्या वे कीमतें उनके अनुमान से भी बेहतर हो सकती हैं। किसी अलग "प्रयोग चरण" की आवश्यकता नहीं है।

3. "जनरलाइज्ड" (सामान्यीकृत) जादू

पिछले मॉडलों ने माना था कि मांग (कितने लोग खरीदते हैं) एक सीधी रेखा में बदलती है (जैसे, "यदि कीमत $1 बढ़ती है, तो बिक्री 10% गिर जाती है")।

यह शोध पत्र कहता है: "वास्तविक जीवन एक सीधी रेखा नहीं है।"

कभी-कभी कीमत में छोटी सी गिरावट बिक्री में भारी उछाल लाती है।
कभी-कभी कीमत में वृद्धि बिक्री को तब तक प्रभावित नहीं करती जब तक कि वह एक "टिपिंग पॉइंट" (निर्णायक बिंदु) तक न पहुँच जाए।
कभी-कभी बिक्री "हाँ/नहीं" (बाइनरी) होती है, और कभी-कभी सटीक संख्याएँ (निरंतर) होती हैं।

यह नया एल्गोरिदम इन सभी आकारों (वक्र, रेखाएं, हाँ/नहीं) को एक साथ संभाल सकता है। यह मूल्य निर्धारण के लिए एक स्विस आर्मी नाइफ की तरह है, जबकि पुराने मॉडल केवल एक साधारण पेचकस थे।

4. परिणाम: खेल जीतना

यह शोध पत्र सिद्ध करता है कि यदि प्रत्येक विक्रेता इस "ऑप्टिमिस्टिक लर्नर" रणनीति का उपयोग करता है:

वे तेजी से सीखते हैं: एक आदर्श 'ओरेकल' की तुलना में उनका कुल "खोया हुआ पैसा" (रिग्रेट) बहुत धीरे बढ़ता है (विशेष रूप से, समय के वर्गमूल के अनुपात में)। यह इस प्रकार की समस्याओं के लिए ज्ञात सर्वोत्तम गति है।
बाजार स्थिर होता है: भले ही हर कोई अपने आप सीख रहा हो, उनके द्वारा तय की गई कीमतें अंततः एक स्थिर बिंदु (जिसे नैश इक्विलिब्रियम कहा जाता है) पर स्थिर हो जाती हैं।
- उपमा: कल्पना कीजिए कि एक भीड़ भरा डांस फ्लोर है। हर कोई एक-दूसरे से टकराए बिना नाचने के लिए सबसे अच्छी जगह खोजने की कोशिश कर रहा है। भले ही कोई भी नृत्य को निर्देशित नहीं कर रहा है, वे अंततः एक ऐसी लय पा लेते हैं जहाँ हर कोई खुश है और कोई भी हिलना नहीं चाहता। यही नैश इक्विलिब्रियम है।

सारांश

यह शोध पत्र एक कठिन समस्या का समाधान करता है: प्रतिस्पर्धी व्यवसाय एक-दूसरे से बात किए बिना, एक-दूसरे की बिक्री देखे बिना, और बिना किसी अलग "अभ्यास दौर" में समय बर्बाद किए, अपने उत्पादों की कीमत सटीक रूप से कैसे तय करना सीख सकते हैं?

उन्होंने एक स्मार्ट एल्गोरिदम बनाकर ऐसा किया जो अज्ञात के प्रति आशावादी है, जिससे व्यवसाय एक साथ सीख भी पाता है और कमा भी पाता है, जबकि यह उन जटिल, गैर-रेखीय ग्राहक व्यवहारों को भी संभालता है जिन्हें पुराने मॉडल नहीं समझ पाते थे।

तकनीकी सारांश: सामान्यीकृत रैखिक मांग के तहत ऑनलाइन मूल्य प्रतिस्पर्धा

समस्या का निरूपण
यह शोध पत्र $N$ विक्रेताओं के बीच एक सीमित समय क्षितिज $T$ पर संचालित होने वाली क्रमिक मूल्य प्रतिस्पर्धा (sequential price competition) के विषय को संबोधित करता है। पारंपरिक एकाधिकार स्थितियों या रैखिक मांग (linear demand) मानते वाले पूर्व प्रतिस्पर्धी मॉडलों के विपरीत, यह कार्य एक सामान्यीकृत रैखिक (एकल-सूचकांक) मांग ढांचे पर विचार करता है। प्रत्येक विक्रेता $i$ के लिए, अपेक्षित मांग को इस प्रकार मॉडल किया गया है:
$\lambda_i(p) = \mu_i(\langle \theta_{i,0}, p \rangle) = \mu_i(-\beta_{i,0}p_i + \langle \gamma_{i,0}, p_{-i} \rangle)$
जहाँ:

$p$ सभी विक्रेताओं द्वारा एक साथ निर्धारित किए गए मूल्यों का वेक्टर है।
$\mu_i$ एक ज्ञात, सख्ती से बढ़ता हुआ लिंक फंक्शन (जैसे बाइनरी परिणामों के लिए लॉजिस्टिक, या रैखिक के लिए आइडेंटिटी) है।
$\theta_{i,0}$ एक अज्ञात पैरामीटर वेक्टर है जिसमें विक्रेता की अपनी-कीमत संवेदनशीलता ( $-\beta_{i,0}$ ) और प्रतिस्पर्धियों की कीमत संवेदनशीलता ( $\gamma_{i,0}$ ) शामिल है।
मांग के अवलोकन $y_i(t)$ कीमतों पर आधारित कैनोनिकल एक्सपोनेंशियल फैमिली वितरण का पालन करते हैं।

सूचना संरचना और बाधाएं
यह परिवेश एक विशिष्ट सूचना विषमता (information asymmetry) द्वारा अभिलक्षित है जो मानक मल्टी-एजेंट सुदृढीकरण लर्निंग (MARL) से भिन्न है:

आंशिक दृश्यता (Partial Observability): प्रत्येक विक्रेता केवल अपनी वास्तविक मांग (या राजस्व) और प्रतिद्वंद्वियों द्वारा निर्धारित कीमतों को देखता है। वे प्रतिस्पर्धियों की वास्तविक मांग या राजस्व को नहीं देख पाते हैं।
समवर्ती चालें (Simultaneous Moves): विक्रेता एक साथ कीमतें चुनते हैं। फलस्वरूप, एक विक्रेता संदर्भ (प्रतिद्वंद्वियों की कीमतें $p_{-i}$ ) केवल अपनी क्रिया $p_i$ चुनने के बाद देखता है, जिससे एक समय संबंधी विषमता (timing asymmetry) उत्पन्न होती है जो मानक कॉन्टेक्स्टल बैंडिट विश्लेषण को रोकता है जहाँ क्रिया चयन से पहले संदर्भ देखा जाता है।
कोई समन्वय नहीं (No Coordination): नीति पूरी तरह से विकेंद्रीकृत होनी चाहिए; विक्रेता अन्वेषण (exploration) चरणों के लिए समन्वय नहीं कर सकते।

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

पेनलाइज्ड मैक्सिमम लाइकलीहुड एस्टीमेशन (PMLE): प्रत्येक दौर $t$ में, विक्रेता ऐतिहासिक डेटा $(p(s), y_i(s))_{s < t}$ के आधार पर $\theta_{i,0}$ के अपने अनुमान को एक पेनलाइज्ड लॉग-लाइकलीहुड फंक्शन को अधिकतम करके अपडेट करता है। यह सुनिश्चित करने के लिए कि एस्टिमेटर बाउंडेड पैरामीटर स्पेस $\Theta_i$ के भीतर रहे, यदि कच्चा PMLE नॉर्म बाउंड से अधिक हो जाता है, तो एक प्रोजेक्शन स्टेप लागू किया जाता है।
आशावादी मूल्य निर्धारण (Optimistic Pricing - UCB): एक शुद्ध "एक्सप्लोर-देन-कमिट" रणनीति के बजाय, एल्गोरिदम अपर कॉन्फिडेंस बाउंड (UCB) दृष्टिकोण अपनाता है। विक्रेता अनुमानित राजस्व में एक कॉन्फिडेंस बोनस जोड़कर एक आशावादी राजस्व फंक्शन का निर्माण करता है। बोनस को जनरलाइज्ड लीनियर मॉडल के लिए अनुकूलित एक सांद्रता असमानता (concentration inequality) का उपयोग करके प्राप्त किया जाता है, जो समवर्ती चालों के लिए अनुकूलित एक एलिप्टिकल पोटेंशियल बाउंड का उपयोग करता है।
बेस्ट-रिस्पॉन्स अपडेट: विक्रेता इस आशावादी राजस्व फंक्शन को अधिकतम करने वाला मूल्य $p_i(t)$ चुनता है, जो पिछले दौर के प्रतिस्पर्धियों के देखे गए मूल्यों (या एल्गोरिदम के विशिष्ट अपडेट समय के आधार पर वर्तमान दौर के मूल्यों) पर आधारित होता है (हालांकि पाठ इस बात पर जोर देता है कि $p_i$ चुनने के बाद $p_{-i}$ देखा जाता है, एल्गोरिदम $t$ पर $p(t-1)_{-i}$ का उपयोग करता है)।

प्रमुख योगदान

फ्रंट-लोडेड अन्वेषण-मुक्त लर्निंग: यह शोध पत्र एक ऐसी नीति प्रस्तुत करता है जो बिना किसी स्पष्ट प्रारंभिक i.i.d. रैंडम प्राइसिंग चरण के, एक साथ सीखती और अनुकूलित करती है। यह उन व्यावहारिक सीमाओं को संबोधित करता है जहाँ "मूल्यों के साथ प्रयोग करना" अक्सर अव्यवहारिक होता है और यह पूर्व कार्यों में आवश्यक अज्ञात समस्या-विशिष्ट स्थिरांकों पर निर्भरता से बचता है।
मांग मॉडलों का सामान्यीकरण: यह ढांचा मौजूदा रैखिक मांग मॉडलों का सख्ती से सामान्यीकरण करता है ताकि व्यापक श्रेणी के नॉनलीन, मोनोटोन सिंगल-इंडेक्स मॉडलों को शामिल किया जा सके। यह बाइनरी डिमांड (खरीद/न खरीदना) और निरंतर मांग अवलोकनों दोनों के विश्लेषण को एक एकल सैद्धांतिक छत्र के तहत एकीकृत करता है।
नवीन सांद्रता उपकरण (Novel Concentration Tools): समवर्ती-मूव गेम की प्रकृति के कारण, मानक एलिप्टिकल पोटेंशियल लेम्मा (जो बाह्य संदर्भ मानता है) को सीधे लागू नहीं किया जा सकता है। लेखक एक नया एलिप्टिकल-टाइप बाउंड (लेम्मा C.2) व्युत्पन्न करते हैं जो उन परिवेशों के लिए उपयुक्त है जहाँ संदर्भ (प्रतिद्वंद्वियों की कीमतें) एंडोजेनस है और क्रिया के सापेक्ष विलंब से देखा जाता है।

परिणाम

रिग्रेट बाउंड (Regret Bound): एक डायनेमिक बेंचमार्क (पिछली घटनाओं के आधार पर प्रतिद्वंद्वियों के मूल्यों के प्रति बेस्ट रिस्पॉन्स) के सापेक्ष, प्रत्येक विक्रेता एक रिग्रेट बाउंड प्राप्त करता है:
$\text{Reg}_i(T) = \tilde{O}(N^2 \sqrt{T})$
यह लॉगरिदमिक कारकों और विक्रेताओं की संख्या $N$ पर निर्भरता के साथ, रैखिक प्रतिस्पर्धी मूल्य निर्धारण के लिए ज्ञात इष्टतम $\tilde{O}(\sqrt{T})$ दर से मेल खाता है।
नैश इक्विलिब्रियम (NE) की ओर अभिसरण: एल्गोरिदम यह सुनिश्चित करता है कि प्राइस वेक्टर का नैश इक्विलिब्रियम (NE) प्राइस वेक्टर $p^*$ से औसत वर्ग विचलन (average squared deviation) घटता है:
$\frac{1}{T} \sum_{t=1}^T \mathbb{E}[\|p(t) - p^*\|_2^2] = \tilde{O}\left(\frac{N^2}{\sqrt{T}}\right)$
यह दर्शाता है कि रिग्रेट-ऑप्टिमल प्ले औसतन बाजार को नैश इक्विलिब्रियम के करीब रखता है।
कंप्यूटेशनल जटिलता: एल्गोरिदम कंप्यूटेशनल रूप से व्यवहार्य है, जिसमें प्रति दौर प्रति विक्रेता $O(N^2)$ की जटिलता (मैट्रिक्स अपडेट और वेक्टर उत्पादों द्वारा संचालित) होती है, जो मध्यम $N$ के लिए स्केलेबल है।

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

लेखक नोट करते हैं कि जबकि $\sqrt{T}$ निर्भरता इष्टतम है, विक्रेताओं की संख्या $N$ पर $N^2$ निर्भरता इसकी सटीकता (tightness) के संबंध में एक खुला प्रश्न बनी हुई है। इसके अतिरिक्त, शोध पत्र स्वीकार करता है कि जबकि औसत विचलन को नियंत्रित किया जाता है, प्रारंभिक i.i.d. अन्वेषण चरण के बिना प्राइस सीक्वेंस का पॉइंटवाइज कन्वर्जेंस (pointwise convergence) गारंटीकृत नहीं है, जो कि एडेप्टिव बैंडिट एल्गोरिदम के व्यापक साहित्य के अनुरूप है।

1. समस्या: "अनुमान लगाने का खेल"

2. समाधान: "द ऑप्टिमिस्टिक लर्नर" (आशावादी शिक्षार्थी)

3. "जनरलाइज्ड" (सामान्यीकृत) जादू

4. परिणाम: खेल जीतना

सारांश

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