Prophet inequality
ઓનલાઈન અલ્ગોરિધમ્સ અને ઓપ્ટિમલ સ્ટોપિંગના સિદ્ધાંતમાં, પયગંબર અસમાનતા એ નિર્ણય લેવાની પ્રક્રિયાના અપેક્ષિત મૂલ્ય પર બંધાયેલ છે જે જાણીતા સંભાવના વિતરણોમાંથી રેન્ડમ ઇનપુટ્સના ક્રમને સંભાળે છે, જે અપેક્ષિત મૂલ્યને સંબંધિત છે જે "પયગંબર" દ્વારા પ્રાપ્ત કરી શકાય છે જે સમય પહેલા તમામ ઇનપુટ્સ (અને માત્ર તેમના વિતરણો નહીં) જાણે છે. આ અસમાનતાઓ એલ્ગોરિધમિક મિકેનિઝમ ડિઝાઇન અને ગાણિતિક નાણાના સિદ્ધાંતમાં લાગુ પડે છે. સિંગલ આઇટમ ક્લાસિકલ સિંગલ-આઇટમ પ્રોફેટ અસમાનતા દ્વારા પ્રકાશિત કરવામાં આવી હતી, તેના ચુસ્ત સ્વરૂપનો શ્રેય ડી. જે. એચ. (બેન) ગાર્લિંગને આપવામાં આવ્યો હતો. તે એવી પ્રક્રિયાની ચિંતા કરે છે જેમાં જાણીતા વિતરણોમાંથી રેન્ડમ ચલોનો ક્રમ આવે છે. જ્યારે દરેક આવે છે, ત્યારે નિર્ણય લેવાની પ્રક્રિયાએ નક્કી કરવું જોઈએ કે તેને સ્વીકારવું કે પ્રક્રિયા બંધ કરવી, અથવા તેને નકારી કાઢવી કે પછી ક્રમમાં આગામી ચલ પર જવું. પ્રક્રિયાનું મૂલ્ય એકલ સ્વીકૃત ચલ છે, જો ત્યાં એક હોય, અથવા અન્યથા શૂન્ય હોય. એવું માની શકાય છે કે તમામ ચલ બિન-નકારાત્મક છે; અન્યથા, શૂન્ય દ્વારા નકારાત્મક મૂલ્યોને બદલવાથી પરિણામમાં ફેરફાર થતો નથી. દાખલા તરીકે, આ નાણાકીય પરિસ્થિતિઓનું ઉદાહરણ બની શકે છે, જેમાં ચલ વસ્તુઓ ચોક્કસ કિંમતે કેટલીક અવિભાજ્ય વસ્તુ ખરીદવાની ઓફર કરે છે, અને વિક્રેતાએ નક્કી કરવું પડશે કે કઈ (જો કોઈ હોય તો) ઓફર સ્વીકારવી. એક પ્રબોધક, ચલોનો સંપૂર્ણ ક્રમ જાણીને, દેખીતી રીતે તેમાંથી સૌથી મોટું પસંદ કરી શકે છે, આ પ્રક્રિયાના કોઈપણ ચોક્કસ ઉદાહરણ માટે મૂલ્ય પ્રાપ્ત કરી શકે છે, અને અપેક્ષિત મૂલ્ય પ્રબોધક અસમાનતા આ પ્રક્રિયા માટે ઓનલાઇન અલ્ગોરિધમનું અસ્તિત્વ જણાવે છે, જેનું અપેક્ષિત મૂલ્ય ઓછામાં ઓછું અડધું છે, જે પ્રબોધકનું છેઃ કોઈ પણ અલ્ગોરિધમ બધા વિતરણો માટે વધુ અપેક્ષિત મૂલ્ય પ્રાપ્ત કરી શકતું નથી. દરેક ચલને થ્રેશોલ્ડ અલ્ગોરિધમ દ્વારા ઓછામાં ઓછી સંભાવના સાથે ધ્યાનમાં લેવામાં આવશે અને જો તે માનવામાં આવે તો તે વધારામાં ફાળો આપશે, તેથી અપેક્ષાની રેખીયતા દ્વારા અપેક્ષિત વધારાને ઓછામાં ઓછું વિતરણની મધ્યમાં ગોઠવવામાં આવે છે જેથી અને અપેક્ષિત વધારાની આ બાઉન્ડમાં ઉમેરવાથી, અને શરતો એકબીજાને રદ કરે છે, જે દર્શાવે છે કે થ્રેશોલ્ડ અલ્ગોરિધમની આ સેટિંગ માટે ઓછામાં ઓછું એક અલગ થ્રેશોલ્ડનું અપેક્ષિત મૂલ્ય પ્રાપ્ત થાય છે, તે પણ ઓછામાં ઓછું આ જ અપેક્ષિત મૂલ્ય પ્રાપ્ત કરે છે. સામાન્યીકરણ અન્ય ઑનલાઇન દૃશ્યોમાં એકલ-વસ્તુ પયગંબરની અસમાનતાના વિવિધ સામાન્યીકરણ જાણીતા છે, અને તેને પયગંબરની અસમાનતા પણ કહેવામાં આવે છે. સ્પર્ધાત્મક વિશ્લેષણ સાથે સરખામણી પ્રોફેટ અસમાનતાઓ ઓનલાઇન અલ્ગોરિધમ્સના સ્પર્ધાત્મક વિશ્લેષણ સાથે સંબંધિત છે, પરંતુ બે રીતે અલગ પડે છે. પ્રથમ, મોટાભાગનું સ્પર્ધાત્મક વિશ્લેષણ સૌથી ખરાબ કેસ ઇનપુટ્સ ધારે છે, જે ગણતરી કરેલ મૂલ્ય અને શ્રેષ્ઠ મૂલ્ય વચ્ચેના ગુણોત્તરને વધારવા માટે પસંદ કરવામાં આવે છે જે ભવિષ્યના જ્ઞાન સાથે પ્રાપ્ત થઈ શકે છે, જ્યારે પ્રબોધક અસમાનતાઓ માટે ઇનપુટનું થોડું જ્ઞાન, તેનું વિતરણ, જાણીતું હોવાનું માનવામાં આવે છે. અને બીજું, ચોક્કસ સ્પર્ધાત્મક ગુણોત્તર હાંસલ કરવા માટે, ઓનલાઇન અલ્ગોરિધમે તમામ ઇનપુટ્સ પર શ્રેષ્ઠ પ્રદર્શનના તે ગુણોત્તરમાં પ્રદર્શન કરવું આવશ્યક છે. તેના બદલે, એક પયગંબર અસમાનતા માત્ર અપેક્ષા મુજબના પ્રદર્શનને મર્યાદિત કરે છે, જ્યાં સુધી સરેરાશ સારી હોય ત્યાં સુધી કેટલાક ઇનપુટ સિક્વન્સ ખરાબ પ્રદર્શન ઉત્પન્ન કરવાની મંજૂરી આપે છે. સંદર્ભો બાહ્ય કડીઓ મેટ્રોઇડ પ્રોફેટ અસમાનતાઓ અને મિકેનિઝમ ડિઝાઇન, મેટ્રોઇડ યુનિયન પ્રોફેટ અસમાનતાનું આર્થિક દૃશ્ય ઓનલાઇન અલ્ગોરિધમ્સ અનુક્રમિક પ્રયોગો મિકેનિઝમ ડિઝાઇન