Države, ki jih pesti problem dvojnih državljanstev, poskušajo ponavadi zmanjšati število dvojnih državljanov z medsebojnimi dogovori ali večstranskimi konvencijami. To so v svojem predlogu zakona priznali tudi poslanci Ljudske stranke, ki so zapisali, da »v mednarodni praksi države rešujejo probleme v zvezi z dvojnim državljanstvom tako, da med seboj sklepajo sporazume, s katerimi določajo način za odpravo dvojnega državljanstva, ali pa se dogovorijo, katera od držav ima pravico uveljavljati svojo suverenost nad osebo, ki ima dvojno državljanstvo«. Primerov reševanja te problematike je veliko. Nekdanja Jugoslavija je na primer z nekdanjo Sovjetsko zvezo leta 1956 sklenila posebno konvencijo, ki je določala, da morajo dvojni državljani v enem letu v veleposlaništvih Jugoslavije ali Sovjetske zveze dati izjave, katero državljanstvo bodo obdržali. Tisti, ki se niso opredelili, so lahko obdržali samo državljanstvo države, v kateri so imeli stalno prebivališče. Podobne sporazume so sklenile tudi druge države, na primer Madžarska in Bolgarija, Bolgarija in Sovjetska zveza, Češkoslovaška in Poljska, Madžarska in Poljska. Najpomembnejši večstranski sporazum o odpravljanju dvojnega državljanstva je konvencija o zmanjševanju primerov večkratnih državljanstev in o vojaški obveznosti v primeru večkratnih državljanstev, ki so jo podpisale članice Sveta Evrope v Strasbourgu leta 1963. Konvencija določa, da bodo državljani, ki prostovoljno pridobijo državljanstvo druge podpisnice, izgubili prejšnje državljanstvo in »ne bodo upravičeni obdržati prejšnjega državljanstva«. Možne so tudi drugačne rešitve; Danska je z Avstrijo in Nemčijo sklenila pogodbo o izmenjavi podatkov o naturalizaciji, dvojno državljanstvo pa v teh dveh državah urejajo notranji zakoni. S podobnimi pogodbami je mogoče rešiti tudi največji problem - služenje v oboroženih silah. Jugoslavija se je na primer zavezala, da bo vsem državljanom ZDA, ki imajo tudi jugoslovansko državljanstvo, ob izdaji vstopnega vizuma izdala tudi izstopni vizum, da torej s temi državljani v času bivanja v Jugoslaviji ne bo ravnala kot s svojimi državljani (in jih vpoklicala v vojsko). Sporazume o služenju vojaškega roka dvojnih državljanov so podpisale še druge države. Italija je podpisala takšen sporazum z Nizozemsko, Francija z Izraelom, Finska pa z Argentino.