View source for अनियमित-प्रतिदर्शी यंत्रविन्यास

अनियमित-प्रतिदर्शी यंत्रविन्यास (RSM) एक [[सच्चा तंत्र|तथ्यभाषी यंत्रविन्यास]] है जो [[पूर्व-मुक्त तंत्र|पूर्व-मुक्त यंत्रविन्यास]] और [[पूर्व-स्वतंत्र तंत्र|पूर्व-स्वयंत्र यंत्रविन्यास]] में लगभग-इष्टतम लाभ प्राप्त करने के लिए [[नमूनाकरण (सांख्यिकी)|प्रतिदर्शी (सांख्यिकी)]] का उपयोग करता है।

मान लीजिए हम नीलामी में कुछ वस्तुओं को बेचना चाहते हैं और अधिकतम लाभ प्राप्त करना चाहते हैं। महत्वपूर्ण कठिनाई यह है कि हम नहीं जानते कि प्रत्येक खरीदार किसी वस्तु के लिए कितना भुगतान करने को तैयार है। यदि हम जानते हैं कि कम से कम खरीदारों का मूल्यांकन कुछ ज्ञात संभाव्यता वितरण के साथ [[यादृच्छिक चर|अनियमित चर]] हैं, तो हम [[बायेसियन-इष्टतम तंत्र|बायेसियन-इष्टतम यंत्रविन्यास]] का उपयोग कर सकते हैं। लेकिन अधिकांशतः हम वितरण को नहीं जानते हैं। इस प्रकरण में, अनियमित-प्रतिदर्शी यंत्रविन्यास एक वैकल्पिक समाधान प्रदान करते हैं।

== बड़े विपणनों में आरएसएम ==

=== विपणन आधा करने की योजना ===
जब विपणन बड़ा होता है, तो निम्नलिखित सामान्य योजना का उपयोग किया जा सकता है:<ref name=agt>{{Cite Algorithmic Game Theory 2007}}</ref>{{rp|341–344}}
# खरीदारों से उनके मूल्यांकन को प्रकट करने के लिए कहा जाता है।
# खरीदार दो उप-विपणनों में विभाजित हैं, <math>M_L</math> (बाएं) और <math>M_R</math> (दाएं), जिसमे सरल अनियमित प्रतिदर्शी का उपयोग करते हुए प्रत्येक खरीदार एक उचित सिक्के को उछालकर किसी एक पक्ष में जाता है।
# प्रत्येक उप-विपणन में <math>M_s</math>, एक [[अनुभवजन्य वितरण समारोह|अनुभवजन्य वितरण फलन]] <math>F_s</math> परिकलित करता है।
# बायेसियन-इष्टतम यंत्रविन्यास (मायर्सन यंत्रविन्यास) उप-विपणन में <math>M_R</math> वितरण के साथ <math>F_L</math>, और <math>M_L</math> के साथ <math>F_R</math> लागू होता है।
इस योजना को अनियमित-प्रतिदर्शी एम्पिरिकल मायर्सन (आरएसईएम) कहा जाता है।

प्रत्येक खरीदार की घोषणा का उसके द्वारा भुगतान की जाने वाली कीमत पर कोई प्रभाव नहीं पड़ता है; कीमत अन्य उप-विपणन में खरीदारों द्वारा निर्धारित की जाती है। इसलिए, खरीदारों के लिए अपना सही मूल्यांकन प्रकट करना एक [[प्रमुख रणनीति]] है। दूसरे शब्दों में, यह एक तथ्यभाषी यंत्रविन्यास है।

सहज रूप से, बड़ी संख्या के नियम द्वारा, यदि विपणन पर्याप्त रूप से बड़ा है तो अनुभवजन्य वितरण पर्याप्त रूप से वास्तविक वितरण के समान हैं, इसलिए हम परिकल्पना करते हैं कि आरएसईएम निकट-इष्टतम लाभ प्राप्त करेगा। हालांकि, यह सभी स्थितियों में अनिवार्य नहीं है। कुछ विशेष स्थितियों में यह सच भी प्रमाणित हुआ है।

सबसे सरल प्रकरण [[डिजिटल सामान की नीलामी]] है। वहां, चरण 4 सरल है और इसमें केवल प्रत्येक उप-विपणन में इष्टतम मूल्य की गणना करना सम्मिलित है। जिसमे इष्टतम मूल्य <math>M_L</math> पर <math>M_R</math> और इसके विपरीत लागू होता है। इसलिए, यंत्रविन्यास को अनियमित-प्रतिदर्शी इष्टतम मूल्य (आरएसओपी) कहा जाता है। यह प्रकरण सरल है क्योंकि यह सदैव संभव आवंटन की गणना करता है। अर्थात, एक तरफ से गणना की गई कीमत को दूसरी तरफ लागू करना सदैव संभव होता है। यह अनिवार्य नहीं है कि भौतिक वस्तुओं के प्रकरण में ऐसा ही हो।

डिजिटल सामानों की नीलामी में भी, आरएसओपी आवश्यक रूप से इष्टतम लाभ के अनुरूप नहीं होता है। यह केवल बंधे हुए मूल्यांकन धारणा के तहत अभिसरण करता है: प्रत्येक खरीदार के लिए, आइटम का मूल्यांकन 1 और के बीच होता है <math>h</math>, कहाँ <math>h</math> कुछ स्थिर है। इष्टतमता के लिए आरएसओपी की अभिसरण दर निर्भर करती है <math>h</math>. अभिसरण दर यंत्रविन्यास द्वारा विचार किए गए संभावित प्रस्तावों की संख्या पर भी निर्भर करता है।<ref name=Balcan08>{{Cite journal|doi=10.1016/j.jcss.2007.08.002|title=मशीन लर्निंग के माध्यम से तंत्र डिजाइन को एल्गोरिथम डिजाइन में कम करना|journal=Journal of Computer and System Sciences|volume=74|issue=8|pages=1245|year=2008|last1=Balcan|first1=Maria-Florina|author1-link= Maria-Florina Balcan |last2=Blum|first2=Avrim|author2-link=Avrim Blum|last3=Hartline|first3=Jason D.|last4=Mansour|first4=Yishay|doi-access=free}}</ref>
यह समझने के लिए कि एक प्रस्ताव क्या है, एक डिजिटल सामान की नीलामी पर विचार करें जिसमें खरीदारों का मूल्यांकन, डॉलर में, सीमित होने के लिए जाना जाता है। <math>[1,h]</math>. यदि यंत्रविन्यास केवल पूरे डॉलर की कीमतों का उपयोग करता है, तो केवल वही होते हैं <math>h</math> संभावित प्रस्ताव।

सामान्य तौर पर, अनुकूलन समस्या में केवल एक मूल्य से कहीं अधिक सम्मिलित हो सकता है। उदाहरण के लिए, हम कई अलग-अलग डिजिटल सामान बेचना चाह सकते हैं, जिनमें से प्रत्येक की कीमत अलग हो सकती है। इसलिए कीमत के बजाय हम ऑफर पर बात करते हैं। हम मानते हैं कि एक वैश्विक सेट है <math>G</math> संभावित प्रस्तावों की। हर प्रस्ताव के लिए <math>g\in G</math> और एजेंट <math>i</math>, <math>g(i)</math> वह राशि है जो एजेंट है <math>i</math> प्रस्ताव के साथ प्रस्तुत किए जाने पर भुगतान करता है <math>g</math>. डिजिटल सामान के उदाहरण में, <math>G</math> संभावित कीमतों का सेट है। हर संभव कीमत के लिए <math>p</math>, एक फलन है <math>g_p</math> ऐसा है कि <math>g_p(i)</math> या तो 0 है (यदि <math>v_i<p</math>) या <math>p</math> (अगर <math>v_i\geq p</math>).

हर सेट के लिए <math>S</math> एजेंटों की, प्रस्ताव पेश करने से यंत्रविन्यास का लाभ <math>g</math> एजेंटों को <math>S</math> है:
:<math>g(S) := \sum_{i\in S} g(i)</math>
और यंत्रविन्यास का इष्टतम लाभ है:
:<math>OPT_G(S) := \max_{g\in G} g(S)</math>
प्रत्येक उप-बाज़ार के लिए RMS की गणना की गई <math>M_s</math>, एक इष्टतम प्रस्ताव <math>g_s</math>, इस प्रकार गणना की गई:
::<math>g_s := \arg\max_{g\in G} g(M_s)</math>
प्रस्ताव <math>g_L</math> में खरीदारों पर लागू होता है <math>M_R</math>, अर्थात: प्रत्येक खरीदार <math>i\in M_R</math> किसने कहा कि <math>g_L(i)>0</math> प्रस्तावित आवंटन प्राप्त करता है और भुगतान करता है <math>g_L(i)</math>; प्रत्येक खरीदार में <math>M_R</math> किसने कहा कि <math>g_L(i)=0</math> प्राप्त न करें और कुछ भी भुगतान न करें। प्रस्ताव <math>g_R</math> में खरीदारों पर लागू होता है <math>M_L</math> एक समान तरीके से।

=== लाभ-ओरेकल योजना ===
प्रॉफिट ऑरेकल एक अन्य आरएसएम योजना है जिसका उपयोग बड़े विपणनों में किया जा सकता है।<ref>{{cite conference|title=इष्टतम परिमित समर्थन नीलामियों को डिजाइन करना और सीखना|year=2007|conference=SODA|author=Edith Elkind|author-link=Edith Elkind}}</ref> यह तब उपयोगी होता है जब हमारे पास एजेंटों के मूल्यांकन (जैसे गोपनीयता कारणों से) तक सीधी पहुंच नहीं होती है। हम केवल इतना कर सकते हैं कि एक नीलामी करें और इसके अपेक्षित लाभ पर नजर रखें। एकल-आइटम नीलामी में, जहाँ हैं <math>n</math> बोली लगाने वाले, और प्रत्येक बोली लगाने वाले के लिए अधिकतम हैं <math>K</math> संभावित मान (अज्ञात संभावनाओं के साथ अनियमित रूप से चयनित), अधिकतम-राजस्व नीलामी का उपयोग करके सीखा जा सकता है:
:<math>O(n^2 K^2)</math>
ऑरेकल-प्रॉफिट को कॉल करता है।

== छोटे विपणनों में आरएसएम ==
आरएसएम का सबसे खराब स्थिति में भी अध्ययन किया गया, जिसमें विपणन छोटा है। ऐसे स्थितियों में, हम एक निरपेक्ष गुणक सन्निकटन कारक प्राप्त करना चाहते हैं, जो विपणन के आकार पर निर्भर नहीं करता है।

=== विपणन आधा करना, डिजिटल सामान ===
इस सेटिंग में पहला शोध [[ एकल-पैरामीटर उपयोगिता |एकल-पैरामीटर उपयोगिता]] के साथ डिजिटल सामान की नीलामी के लिए था।<ref name=Goldberg01>{{Cite book|doi=10.1007/3-540-44676-1_35|chapter=Competitive Auctions for Multiple Digital Goods|title=Algorithms — ESA 2001|volume=2161|pages=416|series=Lecture Notes in Computer Science|year=2001|last1=Goldberg|first1=Andrew V.|last2=Hartline|first2=Jason D.|isbn=978-3-540-42493-2|citeseerx=10.1.1.8.5115}}</ref>
अनियमित-प्रतिदर्शी इष्टतम-मूल्य यंत्रविन्यास के लिए, कई तेजी से बेहतर सन्निकटनों की गणना की गई है:

* द्वारा,<ref name=Goldberg06>{{cite journal|doi=10.1016/j.geb.2006.02.003|title=प्रतिस्पर्धी नीलामी|journal=Games and Economic Behavior|volume=55|issue=2|pages=242|year=2006|last1=Goldberg|first1=Andrew V.|last2=Hartline|first2=Jason D.|last3=Karlin|first3=Anna R.|last4=Saks|first4=Michael|last5=Wright|first5=Andrew}}</ref> यंत्रविन्यास लाभ इष्टतम का कम से कम 1/7600 है।
* द्वारा,<ref name=Feige05>{{cite book|doi=10.1007/11600930_89|chapter=On the Competitive Ratio of the Random Sampling Auction|title=इंटरनेट और नेटवर्क अर्थशास्त्र|volume=3828|pages=878|series=Lecture Notes in Computer Science|year=2005|last1=Feige|first1=Uriel|last2=Flaxman|first2=Abraham|last3=Hartline|first3=Jason D.|last4=Kleinberg|first4=Robert|isbn=978-3-540-30900-0|citeseerx=10.1.1.136.2094}}</ref> यंत्रविन्यास लाभ इष्टतम का कम से कम 1/15 है।
* द्वारा,<ref name=Alaei09>{{Cite book|doi=10.1145/1566374.1566402|chapter=On random sampling auctions for digital goods|title=Proceedings of the tenth ACM conference on Electronic commerce - EC '09|pages=187|year=2009|last1=Alaei|first1=Saeed|last2=Malekian|first2=Azarakhsh|last3=Srinivasan|first3=Aravind|isbn=9781605584584|citeseerx=10.1.1.758.3195|s2cid=582565}}</ref> यंत्रविन्यास लाभ इष्टतम का कम से कम 1/4.68 है, और ज्यादातर स्थितियों में इष्टतम का 1/4 है, जो तंग है।

=== एकल-नमूना, भौतिक सामान ===
जब एजेंटों का मूल्यांकन कुछ तकनीकी नियमितता की स्थिति (मोनोटोन जोखिम दर कहा जाता है) को पूरा करता है, तो निम्नलिखित यंत्रविन्यास का उपयोग करके अधिकतम-लाभ नीलामी के लिए एक स्थिर-कारक सन्निकटन प्राप्त करना संभव है:<ref name=dhang15>{{cite journal|doi=10.1016/j.geb.2014.03.011 | volume=91 | title=एकल नमूने के साथ राजस्व अधिकतमकरण| journal=Games and Economic Behavior | pages=318–333| year=2015 | last1=Dhangwatnotai | first1=Peerapong | last2=Roughgarden | first2=Tim | last3=Yan | first3=Qiqi | doi-access=free }}</ref>
* एक एकल अनियमित एजेंट का नमूना लें और उसके मूल्य की क्वेरी करें (एजेंटों को एकल-पैरामीटर उपयोगिता माना जाता है)।
* अन्य एजेंटों पर, नमूने लिए गए एजेंट द्वारा निर्धारित आरक्षित मूल्य के साथ एक [[वीसीजी नीलामी]] चलाएँ।
इस यंत्रविन्यास का लाभ कम से कम है <math>{n-1 \over 4n}</math>, कहाँ <math>n</math> एजेंटों की संख्या है। यह 1/8 है जब दो एजेंट होते हैं, और एजेंटों की संख्या बढ़ने पर 1/4 की ओर बढ़ता है। इस योजना को एजेंटों के सबसेट पर बाधाओं को संभालने के लिए सामान्यीकृत किया जा सकता है जो एक साथ जीत सकते हैं (उदाहरण के लिए, आइटमों की केवल एक सीमित संख्या है)। यह विभिन्न विशेषताओं वाले एजेंटों को भी संभाल सकता है (जैसे युवा बनाम पुराने बोलीदाता)।

== [[नमूना जटिलता]] ==
एक अनियमित-प्रतिदर्शी यंत्रविन्यास की नमूना जटिलता इष्टतम कल्याण के उचित अनुमान को प्राप्त करने के लिए नमूना करने के लिए आवश्यक एजेंटों की संख्या है।

में परिणाम <ref name=dhang15/>एकल-आइटम नीलामियों के राजस्व-अधिकतमकरण की नमूना-जटिलता पर कई सीमाएं लागू करें:<ref name=cr15>{{cite conference|doi=10.1145/2591796.2591867|chapter=The sample complexity of revenue maximization|title=Proceedings of the 46th Annual ACM Symposium on Theory of Computing - STOC '14|pages=243|year=2014|last1=Cole|first1=Richard|last2=Roughgarden|first2=Tim|isbn=9781450327107
|arxiv=1502.00963}}</ref>
* एक के लिए <math>1/4</math>इष्टतम अपेक्षित राजस्व का अनुमान, नमूना-जटिलता है <math>1</math> - एक नमूना पर्याप्त है। यह तब भी सच है जब बोली लगाने वाले आई.आई.डी.<ref name=hr09>{{cite conference|doi=10.1145/1566374.1566407|chapter=Simple versus optimal mechanisms|title=Proceedings of the tenth ACM conference on Electronic commerce - EC '09|pages=225|year=2009|last1=Hartline|first1=Jason D.|last2=Roughgarden|first2=Tim|isbn=9781605584584}}</ref>
* एक के लिए <math>1-\epsilon</math>इष्टतम अपेक्षित राजस्व का अनुमान, जब बोली लगाने वाले i.i.d हैं या जब वस्तुओं (डिजिटल सामान) की असीमित आपूर्ति होती है, तो नमूना-जटिलता होती है <math>O(1/\epsilon^2)</math> जब एजेंटों के वितरण में मोनोटोन खतरा दर हो, और <math>O(1/\epsilon^3)</math> जब एजेंटों के वितरण नियमित होते हैं लेकिन मोनोटोन-हैज़र्ड-रेट नहीं होते हैं।

स्थिति तब और जटिल हो जाती है जब एजेंट i.i.d नहीं होते हैं (प्रत्येक एजेंट का मूल्य एक अलग नियमित वितरण से लिया जाता है) और माल की सीमित आपूर्ति होती है। जब से एजेंट आते हैं <math>k</math> विभिन्न वितरण, की नमूना जटिलता <math>1-\epsilon</math>-एकल-आइटम नीलामियों में इष्टतम अपेक्षित राजस्व का अनुमान है:<ref name=cr15/>* अधिक से अधिक <math>O({k^{10}\over \epsilon^7}\ln^3{k\over\epsilon})</math> - अनुभवजन्य मायर्सन नीलामी के एक प्रकार का उपयोग करना।
* कम से कम <math>\Omega({k\over \sqrt{\epsilon\ln k}})</math> (मोनोटोन-खतरा-दर नियमित मूल्यांकन के लिए) और कम से कम <math>\Omega({k\over \epsilon})</math> (मनमानी नियमित मूल्यांकन के लिए)।

<ref>{{cite conference|title=लगभग इष्टतम नीलामियों के छद्म आयाम पर|year=2015|conference=NIPS|url=http://papers.nips.cc/paper/5766-on-the-pseudo-dimension-of-nearly-optimal-auctions|arxiv=1506.03684|bibcode=2015arXiv150603684M}}</ref> एकल-पैरामीटर उपयोगिता एजेंटों (न केवल एकल-आइटम नीलामी), और मनमाने ढंग से नीलामी-यंत्रविन्यास (न केवल विशिष्ट नीलामी) के साथ मनमाना नीलामियों पर चर्चा करें। नमूना जटिलता के बारे में ज्ञात परिणामों के आधार पर, वे दिखाते हैं कि नीलामियों के किसी दिए गए वर्ग से अधिकतम-राजस्व नीलामी का अनुमान लगाने के लिए आवश्यक नमूनों की संख्या है:
:<math>O\bigg(({H\over \epsilon})^2(D \ln ({H\over \epsilon})+\ln({1\over\delta}))\bigg)</math>
कहाँ:
* एजेंटों का मूल्यांकन सीमित है <math>[1,H]</math>,
* नीलामियों के वर्ग का छद्म-[[वीसी आयाम]] अधिक से अधिक है <math>D</math>,
* आवश्यक सन्निकटन कारक है <math>1-\epsilon</math>,
* आवश्यक सफलता की संभावना है <math>1-\delta</math>.

विशेष रूप से, वे साधारण नीलामियों के एक वर्ग पर विचार करते हैं जिन्हें कहा जाता है<math>t</math>-स्तर की नीलामी: के साथ नीलामी <math>t</math> आरक्षित मूल्य (एक एकल आरक्षित मूल्य के साथ एक विकरी नीलामी 1-स्तरीय नीलामी है)। वे सिद्ध करते हैं कि इस वर्ग का छद्म कुलपति-आयाम है <math>O(nt \ln (nt))</math>, जो तुरंत उनकी सामान्यीकरण त्रुटि और नमूना-जटिलता पर बाध्यता का अनुवाद करता है। वे नीलामियों के इस वर्ग की प्रतिनिधित्व त्रुटि पर सीमा भी प्रमाणित करते हैं।

== ईर्ष्या ==
अनियमित-प्रतिदर्शी यंत्रविन्यास का एक नुकसान यह है कि यह ईर्ष्या-मुक्त नहीं है। उदाहरण के लिए, यदि दो उप-विपणनों में इष्टतम मूल्य <math>M_L</math> और <math>M_R</math> अलग हैं, तो प्रत्येक उप-विपणन में खरीदारों को एक अलग कीमत की पेशकश की जाती है। दूसरे शब्दों में, मूल्य भेदभाव है। यह निम्नलिखित अर्थों में अपरिहार्य है: कोई एकल-मूल्य रणनीति-प्रूफ नीलामी नहीं है जो इष्टतम लाभ का अनुमान लगाती हो।<ref name="Goldberg03">{{cite conference | url=http://dl.acm.org/citation.cfm?id=644145 | title=आम सहमति के माध्यम से प्रतिस्पर्धा| access-date=7 January 2016 | author=Andrew V. Goldberg and Jason D. Hartline | book-title=Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms | year=2003 | conference=SODA '03}}</ref>


== यह भी देखें ==
* [[बाजार अनुसंधान|विपणन अनुसंधान]]
* [[मूल्य निर्धारण]]
* आम सहमति का अनुमान - पूर्व-मुक्त यंत्रविन्यास डिजाइन के लिए एक वैकल्पिक दृष्टिकोण।

== संदर्भ ==
{{reflist}}

[[Category:Created On 01/06/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:तंत्र डिजाइन]]
[[Category:नमूनाकरण तकनीक]]