ग्राफिकल निर्भरताओं के लिए सुधारित मैकेनिज्म और भविष्यवक्ता विषमताएँ

पिछले दो दशकों में, राजस्व-आशय नीलामी डिज़ाइन और भविष्यवक्ता विषमताओं जैसे स्टोकास्टिक समस्याओं में महत्वपूर्ण प्रगति हुई है, जो पारंपरिक रूप से n स्वतंत्र यादृच्छिक चर के साथ मॉडल की जाती हैं ताकि n वस्तुओं के मानों का प्रतिनिधित्व किया जा सके। हालाँकि, कई अनुप्रयोगों में, स्वतंत्रता का यह अनुमान अक्सर वास्तविकता से भटक जाता है। मनमाने सहसंबंधों के साथ जुड़े मजबूत असंभवता परिणामों को देखते हुए, हाल के शोध ने हल्की निर्भरता के मॉडल के तहत इन समस्याओं का अन्वेषण करने की दिशा में ध्यान केंद्रित किया है। इस कार्य में, हम मार्कोव यादृच्छिक क्षेत्रों (MRFs) के लोकप्रिय ग्राफिकल मॉडल के ढांचे के भीतर, इष्टतम नीलामी और भविष्यवक्ता विषमता समस्याओं का अध्ययन करते हैं, जो जटिल निर्भरता संरचनाओं को पकड़ने की इसकी क्षमता से प्रेरित है। विशेष रूप से, एकल खरीदार को n वस्तुओं को बेचने की समस्या के लिए, ताकि राजस्व को अधिकतम किया जा सके, हम दिखाते हैं कि SRev और BRev का अधिकतम एक O () -approximation है, जो उप-संवहनीय खरीदारों के लिए इष्टतम राजस्व के लिए है, जहाँ आधारभूत MRF का अधिकतम भारित डिग्री है। यह Cai और Oikonomou (EC 2021) द्वारा औदातिक और इकाई-डिमांड खरीदारों के लिए (O () ) -approximation परिणामों पर एक सामान्यीकरण और एक बहुगुणात्मक सुधार है। हम भविष्यवक्ता विषमता समस्या के लिए भी एक समान बहुगुणात्मक सुधार प्राप्त करते हैं, जो समस्याओं के लिए एक सममित ऊपरी सीमा प्रदर्शित करते हुए ओसंपात्मक रूप से इष्टतम है।