Graphical game theory
રમત સિદ્ધાંતમાં, રમતનું વર્ણન કરવાની સામાન્ય રીતો સામાન્ય સ્વરૂપ અને વ્યાપક સ્વરૂપ છે. ગ્રાફિકલ સ્વરૂપ એ સહભાગીઓ વચ્ચેની ક્રિયાપ્રતિક્રિયાનો ઉપયોગ કરીને રમતની વૈકલ્પિક સઘન રજૂઆત છે. દરેક વ્યૂહરચના ધરાવતા ખેલાડીઓ સાથેની રમતનો વિચાર કરો. અમે ખેલાડીઓને ગ્રાફમાં નોડ્સ તરીકે રજૂ કરીશું જેમાં દરેક ખેલાડીનું યુટિલિટી ફંક્શન હોય છે જે ફક્ત તેના અને તેના પડોશીઓ પર આધાર રાખે છે. કારણ કે ઉપયોગિતા કાર્ય ઓછા અન્ય ખેલાડીઓ પર આધાર રાખે છે, ગ્રાફિકલ રજૂઆત નાની હશે. ઔપચારિક વ્યાખ્યા ગ્રાફિકલ રમતને આલેખ દ્વારા રજૂ કરવામાં આવે છે, જેમાં દરેક ખેલાડીને નોડ દ્વારા રજૂ કરવામાં આવે છે, અને બે ગાંઠો વચ્ચે એક ધાર હોય છે અને તેમના ઉપયોગિતા કાર્યો વ્યૂહરચના પર આધારિત હોય છે જે અન્ય ખેલાડી પસંદ કરશે. દરેક નોડમાં એક કાર્ય હોય છે, જ્યાં શિરોબિંદુની ડિગ્રી હોય છે. ખેલાડીની ઉપયોગિતાને તેની વ્યૂહરચના તેમજ તેના પડોશીઓના કાર્ય તરીકે સ્પષ્ટ કરે છે. રમતના પ્રતિનિધિત્વનું કદ સામાન્ય ખેલાડીઓની રમત માટે, જેમાં દરેક ખેલાડીની સંભવિત વ્યૂહરચનાઓ હોય, સામાન્ય સ્વરૂપ પ્રતિનિધિત્વનું કદ હશે. આ રમત માટે ગ્રાફિકલ રજૂઆતનું કદ એ છે કે ગ્રાફમાં મહત્તમ નોડ ડિગ્રી ક્યાં છે. જો, તો પછી ગ્રાફિકલ રમતની રજૂઆત ઘણી ઓછી છે. એક ઉદાહરણ એવા કિસ્સામાં કે જ્યાં દરેક ખેલાડીનું ઉપયોગિતા કાર્ય માત્ર એક અન્ય ખેલાડી પર આધાર રાખે છેઃ આલેખની મહત્તમ ડિગ્રી 1 છે, અને રમતને કદના કાર્યો (કોષ્ટકો) તરીકે વર્ણવી શકાય છે. તેથી, ઇનપુટનું કુલ કદ હશે. રમતમાં નેશ સંતુલન શોધવું પ્રતિનિધિત્વના કદમાં ઘાતાંકીય સમય લે છે. જો રમતની ગ્રાફિકલ રજૂઆત વૃક્ષ હોય, તો આપણે બહુપદી સમયમાં સંતુલન શોધી શકીએ છીએ. સામાન્ય કિસ્સામાં, જ્યાં નોડની મહત્તમ ડિગ્રી 3 અથવા વધુ હોય, ત્યાં સમસ્યા એન. પી.-પૂર્ણ હોય છે. વધુ વાંચન માઈકલ કેયર્ન્સ (2007) "ગ્રાફિકલ ગેમ્સ". માઈકલ કેયર્ન્સમાં, માઈકલ એલ. લિટમેન અને સતિંદર સિંહ (2001) "ગ્રાફિકલ મોડલ્સ ફોર ગેમ થિયરી". રમત સિદ્ધાંત આલેખ સિદ્ધાંત