Repeated game
રમત સિદ્ધાંતમાં, પુનરાવર્તિત રમત એ એક વ્યાપક સ્વરૂપની રમત છે જેમાં કેટલીક બેઝ ગેમ (જેને સ્ટેજ ગેમ કહેવાય છે) ની સંખ્યાબંધ પુનરાવર્તનો હોય છે. સ્ટેજ ગેમ સામાન્ય રીતે સારી રીતે અભ્યાસ કરાયેલ 2-વ્યક્તિ રમતોમાંની એક છે. પુનરાવર્તિત રમતો એ વિચારને મેળવે છે કે ખેલાડીએ અન્ય ખેલાડીઓની ભાવિ ક્રિયાઓ પર તેમની વર્તમાન ક્રિયાની અસરને ધ્યાનમાં લેવી પડશે; આ અસરને કેટલીકવાર તેમની પ્રતિષ્ઠા કહેવામાં આવે છે. સિંગલ સ્ટેજ ગેમ અથવા સિંગલ શોટ ગેમ એ પુનરાવર્તિત ન થતી રમતોના નામ છે. પુનરાવર્તિત રમતના વાસ્તવિક જીવનના ઉદાહરણ માટે, એક બીજાને અડીને આવેલા બે ગેસ સ્ટેશનોનો વિચાર કરો. તેઓ જાહેરમાં કિંમતો પોસ્ટ કરીને સ્પર્ધા કરે છે અને સમાન અને સતત સીમાંત કિંમત સી (ગેસોલિનની જથ્થાબંધ કિંમત) ધરાવે છે. ધારો કે જ્યારે તેઓ બંને પી = 10 ચાર્જ કરે છે, ત્યારે તેમનો સંયુક્ત નફો મહત્તમ થાય છે, પરિણામે દરેક માટે ઊંચો નફો થાય છે. આ તેમના માટે શ્રેષ્ઠ પરિણામ હોવા છતાં, તેઓ વિચલિત થવા માટે પ્રેરિત છે. કિંમતમાં સામાન્ય ઘટાડો કરીને, કોઈપણ વ્યક્તિ તેમના તમામ સ્પર્ધકોના ગ્રાહકોને ચોરી શકે છે, તેમની આવક (લગભગ) બમણી કરી શકે છે. પી = સી, જ્યાં તેમનો નફો શૂન્ય છે, તે આ નફાના વિચલન વિના એકમાત્ર કિંમત છે. બીજા શબ્દોમાં કહીએ તો, કિંમત નિર્ધારણ સ્પર્ધાની રમતમાં, એકમાત્ર નેશ સંતુલન બિનકાર્યક્ષમ છે (ગેસ સ્ટેશનો માટે) જે બંને પી = સી ચાર્જ કરે છે. આ એક અપવાદ કરતાં વધુ નિયમ છેઃ તબક્કાવાર રમતમાં, નેશ સંતુલન એ એકમાત્ર પરિણામ છે જે એજન્ટ સતત ક્રિયાપ્રતિક્રિયામાં પ્રાપ્ત કરી શકે છે, અને તે સામાન્ય રીતે તેમના માટે બિનકાર્યક્ષમ હોય છે. આનું કારણ એ છે કે એજન્ટો માત્ર તેમના પોતાના અંગત હિતોથી ચિંતિત હોય છે અને તેમની ક્રિયાઓ સ્પર્ધકો માટે જે લાભો અથવા ખર્ચ લાવે છે તેની ચિંતા કરતા નથી. બીજી બાજુ, નજીકના અન્ય ગેસ સ્ટેશન હોવા છતાં પણ ગેસ સ્ટેશનો નફો કરે છે. સૌથી નિર્ણાયક કારણોમાંનું એક એ છે કે તેમની ક્રિયાપ્રતિક્રિયા એકતરફી નથી. આ સ્થિતિને પુનરાવર્તિત રમતો દ્વારા દર્શાવવામાં આવે છે, જેમાં બે ગેસ સ્ટેશનો અનિશ્ચિત સમય શ્રેણી t = 0,1,2, માં કિંમત (સ્ટેજ રમતો) માટે સ્પર્ધા કરે છે. મર્યાદિત વિરુદ્ધ અનંત પુનરાવર્તિત રમતો પુનરાવર્તિત રમતોને વ્યાપક રીતે બે વર્ગોમાં વિભાજિત કરી શકાય છે, મર્યાદિત અને અનંત, રમત કેટલા સમય સુધી રમવામાં આવે છે તેના આધારે. મર્યાદિત રમતો તે છે જેમાં બંને ખેલાડીઓ જાણે છે કે રમત ચોક્કસ (અને મર્યાદિત) રાઉન્ડમાં રમવામાં આવી રહી છે, અને તે પછી રમત ચોક્કસપણે સમાપ્ત થાય છે. સામાન્ય રીતે, મર્યાદિત રમતો બેકવર્ડ ઇન્ડક્શન દ્વારા ઉકેલી શકાય છે. અનંત રમતો તે છે જેમાં રમત અનંત સંખ્યામાં રમવામાં આવે છે. અનંત સંખ્યામાં રાઉન્ડ ધરાવતી રમત પણ (રમવાની વ્યૂહરચનાની દ્રષ્ટિએ) એવી રમતની સમકક્ષ હોય છે જેમાં રમતના ખેલાડીઓને ખબર નથી હોતી કે રમત કેટલા રાઉન્ડ માટે રમવામાં આવી રહી છે. અનંત રમતો (અથવા અજ્ઞાત સંખ્યામાં પુનરાવર્તિત થતી રમતો) ને બેકવર્ડ ઇન્ડક્શન દ્વારા ઉકેલી શકાતી નથી કારણ કે બેકવર્ડ ઇન્ડક્શન શરૂ કરવા માટે કોઈ "છેલ્લો રાઉન્ડ" નથી. જો દરેક રાઉન્ડમાં રમાતી રમત સમાન હોય તો પણ, તે રમતને મર્યાદિત અથવા અનંત વખત પુનરાવર્તિત કરવાથી, સામાન્ય રીતે, ખૂબ જ અલગ પરિણામો (સંતુલન), તેમજ ખૂબ જ અલગ શ્રેષ્ઠ વ્યૂહરચનાઓ તરફ દોરી શકે છે. અનંત પુનરાવર્તિત રમતો સૌથી વધુ અભ્યાસ કરાયેલ પુનરાવર્તિત રમતો એવી રમતો છે જે અનંત સંખ્યામાં પુનરાવર્તિત થાય છે. પુનરાવર્તિત કેદીઓની મૂંઝવણની રમતોમાં, એવું જોવા મળે છે કે પસંદગીની વ્યૂહરચના સ્ટેજ ગેમની નેશ વ્યૂહરચના રમવાની નથી, પરંતુ સહકાર આપવાની અને સામાજિક રીતે મહત્તમ વ્યૂહરચના રમવાની છે. અનંત પુનરાવર્તિત રમતમાં વ્યૂહરચનાનો એક આવશ્યક ભાગ એ છે કે જે ખેલાડીઓ આ સહકારી વ્યૂહરચનાથી વિચલિત થાય છે તેમને સજા કરવી. સજા એવી વ્યૂહરચના રમી શકે છે જે બાકીની રમત માટે બંને ખેલાડીઓને ઓછી ચૂકવણી તરફ દોરી જાય છે (જેને ટ્રિગર વ્યૂહરચના કહેવાય છે). એક ખેલાડી સામાન્ય રીતે સામાજિક રીતે મહત્તમ વ્યૂહરચના રમવાને બદલે પોતાનો પુરસ્કાર વધારવા માટે સ્વાર્થી વર્તન કરવાનું પસંદ કરી શકે છે. જો કે, જો તે જાણીતું હોય કે અન્ય ખેલાડી ટ્રિગર વ્યૂહરચનાને અનુસરી રહ્યો છે, તો પછી ખેલાડી ભવિષ્યમાં ઓછી ચૂકવણી મેળવવાની અપેક્ષા રાખે છે જો તેઓ આ તબક્કે વિચલિત થાય. અસરકારક ટ્રિગર વ્યૂહરચના એ સુનિશ્ચિત કરે છે કે હવે સ્વાર્થી વર્તન કરવા અને ભવિષ્યમાં અન્ય ખેલાડીની સજાનો સામનો કરવા કરતાં ખેલાડીને સહકાર આપવાની વધુ ઉપયોગીતા છે. સિદ્ધાંતોમાં ઘણા પરિણામો છે જે પુનરાવર્તિત રમતોમાં સામાજિક રીતે શ્રેષ્ઠ સંતુલન કેવી રીતે પ્રાપ્ત કરવું અને જાળવવું તેની સાથે વ્યવહાર કરે છે. આ પરિણામોને સામૂહિક રીતે "લોક પ્રમેયો" કહેવામાં આવે છે. પુનરાવર્તિત રમતનું એક મહત્વપૂર્ણ લક્ષણ એ છે કે ખેલાડીની પસંદગીઓને કેવી રીતે મોડલ કરી શકાય છે. ઘણી જુદી જુદી રીતો છે જેમાં પસંદગી સંબંધને અનંત પુનરાવર્તિત રમતમાં મોડેલિંગ કરી શકાય છે, પરંતુ બે મુખ્ય રીતો છેઃ માધ્યમોની મર્યાદા-જો રમત પરિણામોના માર્ગમાં પરિણમે છે અને ખેલાડી i પાસે મૂળભૂત-રમત ઉપયોગિતા કાર્ય છે, તો ખેલાડી i ની ઉપયોગિતા છેઃ ડિસ્કાઉન્ટિંગ-જો ખેલાડી i નું રમતનું મૂલ્યાંકન ડિસ્કાઉન્ટ પરિબળ પર આધાર રાખીને સમય સાથે ઘટતું જાય છે, તો ખેલાડી ઉપયોગિતા છેઃ પૂરતા પ્રમાણમાં દર્દી ખેલાડીઓ માટે (દા. ત. ) ના ઉચ્ચ પર્યાપ્ત મૂલ્યો ધરાવતા લોકો, તે સાબિત કરી શકે છે કે દરેક વ્યૂહરચના કે જે મિનિમેક્સ ચૂકવણી કરતાં વધુ વળતર ધરાવે છે તે નેશ સંતુલન હોઈ શકે છે-વ્યૂહરચનાઓનો એક ખૂબ મોટો સમૂહ. મર્યાદિત રીતે પુનરાવર્તિત રમતો પુનરાવર્તિત રમતો તાત્કાલિક લાભ અને લાંબા ગાળાના પ્રોત્સાહનો વચ્ચેની ક્રિયાપ્રતિક્રિયાના અભ્યાસ માટે પરવાનગી આપે છે. મર્યાદિત રીતે પુનરાવર્તિત રમત એ રમત છે જેમાં એક જ એક-શોટની તબક્કાની રમત સંખ્યાબંધ અલગ સમય ગાળાઓ અથવા રાઉન્ડમાં વારંવાર રમવામાં આવે છે. દરેક સમયગાળાને 0 <t ≤ T દ્વારા અનુક્રમિત કરવામાં આવે છે જ્યાં T એ સમયગાળાની કુલ સંખ્યા છે. ખેલાડીની અંતિમ ચૂકવણી એ દરેક રાઉન્ડમાંથી તેમની ચૂકવણીનો સરવાળો છે. નિશ્ચિત અને જાણીતા સમય ગાળા સાથે પુનરાવર્તિત રમતો માટે, જો સ્ટેજ ગેમમાં અનન્ય નેશ સંતુલન હોય, તો પુનરાવર્તિત રમતમાં દરેક રાઉન્ડમાં સ્ટેજ ગેમ સંતુલન રમવાની એક અનન્ય સબગેમ સંપૂર્ણ નેશ સંતુલન વ્યૂહરચના રૂપરેખા હોય છે. આ બેકવર્ડ ઇન્ડક્શન દ્વારા અનુમાન કરી શકાય છે. અગાઉના રાઉન્ડમાં શું થયું તે ધ્યાનમાં લીધા વિના અનન્ય સ્ટેજ ગેમ નેશ સંતુલન છેલ્લા રાઉન્ડમાં રમવું આવશ્યક છે. આ જાણીને, ખેલાડીઓને બીજાથી છેલ્લા રાઉન્ડમાં વિશિષ્ટ સ્ટેજ ગેમ નેશ સંતુલનથી વિચલિત થવા માટે કોઈ પ્રોત્સાહન મળતું નથી, અને તેથી આ તર્ક રમતના પ્રથમ રાઉન્ડમાં લાગુ કરવામાં આવે છે. રમતનું તેના અંતિમ બિંદુથી આ 'ગૂંચ કાઢવું' ચેઇનસ્ટોર વિરોધાભાસમાં જોઇ શકાય છે. જો સ્ટેજ રમતમાં એક કરતાં વધુ નેશ સંતુલન હોય, તો પુનરાવર્તિત રમતમાં બહુવિધ સબગેમ સંપૂર્ણ નેશ સંતુલન હોઈ શકે છે. જ્યારે નેશ સંતુલન છેલ્લા રાઉન્ડમાં રમવું આવશ્યક છે, ત્યારે બહુવિધ સંતુલનની હાજરી પુરસ્કાર અને સજાની વ્યૂહરચનાઓની સંભાવનાનો પરિચય આપે છે જેનો ઉપયોગ અગાઉના રાઉન્ડમાં સ્ટેજ ગેમ નેશ સંતુલનથી વિચલનને ટેકો આપવા માટે થઈ શકે છે. બીજી બાજુ, સમયગાળાની અજ્ઞાત અથવા અનિશ્ચિત સંખ્યા સાથે મર્યાદિત પુનરાવર્તિત રમતો, એવું માનવામાં આવે છે કે જાણે તે અનંત પુનરાવર્તિત રમત હોય. આ રમતોમાં બેકવર્ડ ઇન્ડક્શન લાગુ કરવું શક્ય નથી. મર્યાદિત રીતે પુનરાવર્તિત રમતોમાં સહકારના ઉદાહરણો ઉદાહરણ 1: બહુવિધ નેશ ઇક્વિલિબ્રિયા સાથે બે તબક્કાની પુનરાવર્તિત રમત ઉદાહરણ 1 બહુવિધ શુદ્ધ વ્યૂહરચના સાથે બે તબક્કાની પુનરાવર્તિત રમત દર્શાવે છે. કારણ કે આ સંતુલન ખેલાડી 2 માટે ચૂકવણીની દ્રષ્ટિએ નોંધપાત્ર રીતે અલગ પડે છે, ખેલાડી 1 રમતના બહુવિધ તબક્કાઓ પર વ્યૂહરચનાની દરખાસ્ત કરી શકે છે જેમાં ખેલાડી 2 માટે સજા અથવા પુરસ્કારની સંભાવનાનો સમાવેશ થાય છે. ઉદાહરણ તરીકે, ખેલાડી 1 પ્રસ્તાવ મૂકી શકે છે કે તેઓ પ્રથમ રાઉન્ડમાં (એ, એક્સ) રમે. જો ખેલાડી 2 પ્રથમ રાઉન્ડમાં પાલન કરે છે, તો ખેલાડી 1 તેમને બીજા રાઉન્ડમાં સંતુલન (એ, ઝેડ) રમીને પુરસ્કાર આપશે, જે બે રાઉન્ડ (7,9) માં કુલ વળતર આપશે. જો ખેલાડી 2 સંમત (એ, એક્સ) રમવાને બદલે પ્રથમ રાઉન્ડમાં (એ, ઝેડ) તરફ વળે છે, તો ખેલાડી 1 બીજા રાઉન્ડમાં (બી, વાય) સંતુલન રમીને તેમને સજા કરવાની ધમકી આપી શકે છે. આ પછીની પરિસ્થિતિ વળતર (5,7) આપે છે, જેનાથી બંને ખેલાડીઓની સ્થિતિ વધુ ખરાબ થઈ જાય છે. આ રીતે, ભવિષ્યના તબક્કામાં સજાની ધમકી પ્રથમ તબક્કામાં સહયોગી, બિન-સંતુલન વ્યૂહરચનાને પ્રોત્સાહન આપે છે. કારણ કે કોઈપણ મર્યાદિત રીતે પુનરાવર્તિત રમતનો અંતિમ રાઉન્ડ, તેના સ્વભાવથી, ભવિષ્યની સજાના જોખમને દૂર કરે છે, છેલ્લા રાઉન્ડમાં શ્રેષ્ઠ વ્યૂહરચના હંમેશા રમતના સંતુલનમાંથી એક હશે. ઉદાહરણ 1 માં દર્શાવવામાં આવેલી રમતમાં સંતુલન વચ્ચેની ચૂકવણીનો તફાવત સજા/પુરસ્કારની વ્યૂહરચનાને વ્યવહારુ બનાવે છે (રમતની વ્યૂહરચના પર સજા અને પુરસ્કારના પ્રભાવ વિશે વધુ જાણવા માટે, 'સજા અને પુરસ્કાર માટેની જાહેર વસ્તુઓની રમત' જુઓ). ઉદાહરણ 2: યુનિક નેશ ઇક્વિલિબ્રિયમ સાથે બે તબક્કાની પુનરાવર્તિત રમત ઉદાહરણ 2 'એક અનન્ય નેશ ઇક્વિલિબ્રિયમ સાથે બે તબક્કાની પુનરાવર્તિત રમત દર્શાવે છે. કારણ કે અહીં માત્ર એક જ સંતુલન છે, રમતના બીજા રાઉન્ડમાં સજાની ધમકી આપવા અથવા પુરસ્કાર આપવાનું વચન આપવા માટે કોઈ પણ ખેલાડી માટે કોઈ પદ્ધતિ નથી. જેમ કે, સબગેમ સંપૂર્ણ નેશ સંતુલન તરીકે ટેકો આપી શકાય તેવી એકમાત્ર વ્યૂહરચના એ છે કે રમતની અનન્ય નેશ સંતુલન વ્યૂહરચના (ડી, એન) દરેક રાઉન્ડમાં રમવી. આ કિસ્સામાં, તેનો અર્થ એ છે કે બે તબક્કાઓ (n = 2) માટે દરેક તબક્કા માટે (D, N) રમવું, પરંતુ તે કોઈપણ મર્યાદિત સંખ્યામાં તબક્કાઓ n "માટે સાચું રહેશે. અર્થઘટન કરવા માટેઃ આ પરિણામનો અર્થ એ છે કે જાણીતા, મર્યાદિત સમય ક્ષિતિજની હાજરી રમતના દરેક રાઉન્ડમાં સહકારને બગાડે છે. પુનરાવર્તિત રમતોમાં સહકાર ત્યારે જ શક્ય છે જ્યારે રાઉન્ડની સંખ્યા અનંત અથવા અજ્ઞાત હોય. પુનરાવર્તિત રમતો ઉકેલવી સામાન્ય રીતે, લોક પ્રમેયો દ્વારા પૂરી પાડવામાં આવેલી વ્યૂહરચનાઓનો ઉપયોગ કરીને પુનરાવર્તિત રમતો સરળતાથી હલ કરવામાં આવે છે. જટિલ પુનરાવર્તિત રમતો વિવિધ તકનીકોનો ઉપયોગ કરીને ઉકેલી શકાય છે, જેમાંથી મોટાભાગની રેખીય બીજગણિત અને કાલ્પનિક રમતમાં વ્યક્ત કરવામાં આવેલી વિભાવનાઓ પર ભારે આધાર રાખે છે. એવું અનુમાન કરી શકાય છે કે તમે અનંત પુનરાવર્તિત રમતોમાં સંતુલન ચૂકવણીની લાક્ષણિકતા નક્કી કરી શકો છો. બે ચૂકવણીઓ વચ્ચે ફેરબદલ દ્વારા, જેમ કે a અને f, સરેરાશ ચૂકવણી રૂપરેખા a અને f વચ્ચે ભારિત સરેરાશ હોઈ શકે છે. અપૂર્ણ માહિતી પુનરાવર્તિત રમતોમાં કેટલીક અપૂર્ણ માહિતી શામેલ હોઈ શકે છે. અપૂર્ણ માહિતી સાથે પુનરાવર્તિત રમતોની શરૂઆત ઓમેન અને માસ્લર દ્વારા કરવામાં આવી હતી. જ્યારે એક ખેલાડીને જાણ કરવામાં આવે અને બીજાને ન હોય તેવી પરિસ્થિતિનો સામનો કરવો સરળ હોય છે, અને જ્યારે દરેક ખેલાડી દ્વારા પ્રાપ્ત માહિતી સ્વતંત્ર હોય, ત્યારે બંને બાજુની અપૂર્ણ માહિતી અને સ્વતંત્ર ન હોય તેવા સંકેતો સાથે શૂન્ય-રકમની રમતોનો સામનો કરવો શક્ય છે. સંદર્ભો બાહ્ય કડીઓ કાલ્પનિક રમતનો ઉપયોગ કરીને પોકર માટે રમત-સૈદ્ધાંતિક ઉકેલ પુનરાવર્તિત રમતો અને ચેઇનસ્ટોર પેરાડોક્સ રમત સિદ્ધાંત રમત વર્ગો પર પુનરાવર્તિત રમતો પર રમત સિદ્ધાંત નોંધે છે