Sachverhalt:
A.
X._ (geb. 1973) stammt aus dem Libanon. Im März 1999 reiste er in die Schweiz ein und heiratete eine ursprünglich aus Thailand stammende, 17 Jahre ältere Schweizer Bürgerin, worauf er eine Aufenthaltsbewilligung erhielt. Die Ehe wurde im September des darauffolgenden Jahres geschieden, worauf das Migrationsamt des Kantons Zürich mit Verfügung vom 11. Januar 2001 eine Verlängerung der Aufenthaltsbewilligung von X._ verweigerte. Im Februar 2001 heiratete X._ seine erste Ehefrau erneut. Im Dezember 2005 erteilte ihm das Migrationsamt die Niederlassungsbewilligung. Im Januar 2008 wurde die Ehe erneut geschieden. Im August 2009 heiratete X._ die libanesische Staatsangehörige Y._ (geb. 1989); dieser Ehe entstammt ein gemeinsames Kind (geb. 27. Juni 2010).
B.
Im Oktober 2009 und erneut im Juli 2010 ersuchte Y._ für sich selbst und für das gemeinsame Kind um die Erteilung einer Einreisebewilligung zum Verbleib beim Ehemann bzw. beim Vater. Dieses Gesuch wies das Migrationsamt mit Verfügung vom 21. Dezember 2010 ab; zugleich widerrief es die Niederlassungsbewilligung vom X._ und setzte ihm eine Frist zum Verlassen der Schweiz bis Ende März 2011. Der dagegen erhobene Rekurs an die Sicherheitsdirektion des Kantons Zürich blieb erfolglos. Dagegen hiess das Verwaltungsgericht des Kantons Zürich die Beschwerde X._s am 19. Juni 2013 gut.
C.
Gegen dieses Urteil führt das Bundesamt für Migration am 10.September 2013 Beschwerde in öffentlich-rechtlichen Angelegenheiten und beantragt dessen Aufhebung.
Während das Verwaltungsgericht auf eine Vernehmlassung verzichtet, beantragt die Sicherheitsdirektion die Gutheissung der Beschwerde; X._ beantragt deren Abweisung; ausserdem stellt er ein Gesuch um aufschiebende Wirkung, dem der Instruktionsrichter mit Verfügung vom 12. Februar 2014 sinngemäss entsprochen hat.

Erwägungen:
1.
1.1. Das Bundesamt für Migration ist auf dem Gebiet des Ausländerrechts befugt, gegen kantonal letztinstanzliche richterliche Entscheide mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht zu gelangen (Art. 89 Abs. 2 lit. a BGG in Verbindung mit Art. 14 Abs. 2 der Organisationsverordnung vom 17. November 1999 für das Eidgenössische Justiz- und Polizeidepartement [OV-EJPD; SR 172.213.1]; <ref-ruling> E. 1.1 S. 203 mit Hinweisen). Seine Beschwerdemöglichkeit dient der richtigen und einheitlichen Anwendung des Bundesrechts; sie setzt kein hierüber hinausgehendes spezifisches schutzwürdiges (öffentliches) Interesse voraus. Immerhin muss ein mit Blick auf die einheitliche Anwendung des Bundesrechts in vergleichbaren Fällen zureichendes Interesse an der Beurteilung der aufgeworfenen Probleme bestehen (vgl. <ref-ruling>E. 1.2.1 S. 341 f.; <ref-ruling>E. 1 S. 195 f.; Urteil 2C_888/2011 vom 20. Juni 2012 E. 1 mit Hinweisen). Der hier im Streit liegende Widerruf der Niederlassungsbewilligung gestützt auf Art. 63 des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (Ausländergesetz, AuG; SR 142.20) fällt nicht unter die Ausnahmeklausel von Art. 83 lit. c BGG, weshalb die Beschwerde ans Bundesgericht grundsätzlich möglich ist. Es stellt eine Aufgabe des Bundesamts dar, in diesem Rahmen eine einheitliche Handhabung dieses Tatbestands sicherzustellen, weshalb seine Beschwerdebefugnis zu bejahen ist. Auf die frist- und formgerecht eingereichte Beschwerde (vgl. Art. 42 und 100 Abs. 1 BGG) ist deshalb einzutreten.
1.2. Das Bundesgericht prüft die Anwendung von Bundesrecht mit Einschluss des Verfassungs- und Völkerrechts mit freier Kognition (Art. 95 lit. a und b BGG). Es legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Art. 105 Abs. 1 BGG); es kann die Sachverhaltsfeststellung der Vorinstanz berichtigen oder ergänzen, wenn sie offensichtlich unrichtig, d.h. willkürlich ist oder wenn sie auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 und Art. 105 Abs. 1 und 2 BGG). Macht der Beschwerdeführer sachverhaltliche Annahmen geltend, die von den vorinstanzlichen Feststellungen abweichen, muss er substanziiert darlegen, inwiefern die Voraussetzungen einer Ausnahme gemäss Art. 105 Abs. 2 BGG gegeben sind. Andernfalls können solche Vorbringen nicht berücksichtigt werden. Entsprechende Mängel müssen in der Beschwerde substanziiert aufgezeigt und gerügt werden (Art. 106 Abs. 2 BGG). Demzufolge genügt es nicht, einen von den tatsächlichen Feststellungen der Vorinstanz abweichenden Sachverhalt zu behaupten. Auf rein appellatorische Kritik an den vorinstanzlichen Sachverhaltsfeststellungen oder an deren Beweiswürdigung tritt das Bundesgericht nicht ein (<ref-ruling> E. 5.1 S. 356; <ref-ruling> E. 3 S. 104 f.; <ref-ruling> E. 2.2 S. 41). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (Art. 99 Abs. 1 BGG).
2.
Das Bundesamt für Migration ist der Auffassung, es gebe genügend Hinweise, wonach es sich bei der ersten Ehe des Beschwerdeführers um eine Scheinehe gehandelt habe. Es treffe zwar zu, dass die Niederlassungsbewilligung nach der höchstrichterlichen Rechtsprechung nicht mehr widerrufen werden könne, wenn die Behörden sie in Kenntnis des fraglichen Verhaltens des Ausländers erteilt habe. Richtig sei auch, dass die Zürcher Migrationsbehörden im Zeitpunkt der Erteilung der Niederlassungsbewilligung von der Scheidung und der kurz darauf erfolgten Wiederverheiratung des Beschwerdeführers gewusst hätten, doch seien die damals vorliegenden "Indizien und Vorbehalte" nicht ausreichend für eine Bewilligungsverweigerung gewesen. Erst mit der (zweiten) Scheidung des Beschwerdeführers von seiner ersten Ehefrau und der nachfolgenden Heirat im Libanon mit Y._, mit der er nun einen Sohn habe, und dem in der Folge eingereichten Familiennachzugsgesuch seien sämtliche entscheidrelevanten Tatsachen zum Vorschein gekommen.
3.
Nach Art. 42 Abs. 1 und 3 AuG haben ausländische Ehegatten von Schweizerinnen und Schweizern Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung, wenn sie mit diesen zusammenwohnen, und nach einem ordnungsgemässen und ununterbrochenen Aufenthalt von fünf Jahren steht den Ehegatten ein Anspruch auf Erteilung der Niederlassungsbewilligung zu. Es ist zu beachten, dass diese Ansprüche nicht voraussetzungslos gelten; vielmehr erlöschen sie, wenn Widerrufsgründe nach Art. 63 AuG vorliegen (Art. 51 Abs. 1 lit. b AuG). Der Widerrufsgrund von Art. 63 Abs. 1 lit. a in Verbindung mitArt. 62 lit. a AuG ist erfüllt, wenn der Ausländer im Bewilligungsverfahren falsche Angaben macht oder wesentliche Tatsachen verschweigt. Nach Art. 90 lit. a AuG ist der Ausländer verpflichtet, der Behörde über alles, was für den Bewilligungsentscheid massgebend sein kann, wahrheitsgetreu Auskunft zu geben (vgl. <ref-ruling> E. 4.1 S. 9;Urteile 2C_214/2013 vom 14. Februar 2014 E. 2.2; 2C_161/2013 vom 3. September 2013 E. 2.2.1).
Allerdings sollen Niederlassungsbewilligungen nur nach nochmaliger eingehender Prüfung des bisherigen Verhaltens des Ausländers erteilt werden (Art. 60 der Verordnung vom 24. Oktober 2007 über Zulassung, Aufenthalt und Erwerbstätigkeit [VZAE; SR 142.201]; vgl. zur früheren Rechtslage auch Art.11 Abs. 1 der Vollziehungsverordnung vom 1.März 1949 zum ANAG [ANAV; AS 1949 I 228]). Sind der kantonalen Ausländerbehörde die wesentlichen Umstände, die auf eine Scheinehe hinweisen könnten, im Zeitpunkt der Gesuchseinreichung bekannt und erteilt sie die Niederlassungsbewilligung dennoch, ohne weitere Abklärungen zu treffen, fällt ein späterer Widerruf gestützt auf die bereits bekannten Sachumstände ausser Betracht (Urteil 2C_303/2011 vom 7. März 2012 E. 4; vgl. zum alten Recht Urteile 2A.346/2004 vom 10. Dezember 2004 E. 2.2; 2A.57/2002 vom 20. Juni 2002 E. 2.2). Diese Rechtslage ist zwischen den Parteien unbestritten.
4.
4.1. Die Vorinstanz hat festgestellt, es lägen durchaus Hinweise auf eine Scheinehe vor. Allerdings habe das Migrationsamt vor der Erteilung der Niederlassungsbewilligung nie eine Abklärung der ehelichen Verhältnisse eingeleitet; die Aufenthaltsbewilligung habe es gar nach der ersten Scheidung und der zweiten Heirat mit der gleichen Frau ohne Ermittlungen wieder erteilt, obwohl ihm die für eine Scheinehe sprechenden Indizien bereits damals bekannt gewesen seien. Demgegenüber hat das Verwaltungsgericht keinerlei Hinweise festgestellt, wonach die Ehe des Beschwerdeführers auch zum Zeitpunkt der Erteilung der Niederlassungsbewilligung nur formal bestanden haben soll. Diese Feststellungen sind nicht offensichtlich unrichtig und daher für das Bundesgericht verbindlich (Art. 105 BGG; oben E. 1.2).
In seiner Beschwerde hält das Bundesamt für Migration zwar dafür, im vorliegenden Fall würden sich genügend stichhaltige Hinweise ergeben, die für eine Scheinehe sprechen würden. Es bestreitet aber nicht, dass diese Umstände, soweit sie sich vor Erteilung der Aufenthalts- wie auch der Niederlassungsbewilligung ereignet haben, dem Migrationsamt bekannt waren. Es ist aber der Auffassung, nach Erteilung der Niederlassungsbewilligung eingetretene Sachumstände liessen quasi retrospektiv Gewissheit darüber entstehen, dass der Beschwerdeführer eine Scheinehe eingegangen sei. Es handelt sich dabei um die (zweite) Scheidung von seiner Schweizer Ehefrau, die spätere Verheiratung mit einer Landsfrau und das aus dieser Verbindung entsprungene Kind sowie das in der Folge eingereichte Familiennachzugsgesuch.
4.2. Dieser Auffassung kann nicht gefolgt werden: Zunächst hat die Ehe des Beschwerdeführers nach dem Erhalt der Niederlassungsbewilligung noch mehr als zwei Jahre angedauert und weder hat das Verwaltungsgericht festgestellt noch wird vom Bundesamt für Migration behauptet, die Eheleute hätten sich wesentlich früher getrennt. Angesichts dieser Zeitspanne kann im Scheitern dieser Ehe kein Indiz für eine Scheinehe gesehen werden. Dasselbe gilt für die wiederum gut anderthalb Jahre später (im August 2009) erfolgte neue Heirat. Es ist nicht unüblich, nach dem Scheitern einer Beziehung nach einiger Zeit eine neue Ehe einzugehen, und da die jetzige Frau des Beschwerdeführers erst 1989 geboren wurde, ist zudem auszuschliessen, dass er mit ihr zum Zeitpunkt der Eheschlüsse mit seiner ersten Frau bereits eine Paarbeziehung pflegte. Welche Bedeutung dem aus dieser aktuellen Beziehung stammenden und im Juni 2010 geborenen Kind im vorliegenden Zusammenhang zukommen soll, ist unerfindlich, wurde dieses doch offensichtlich nach erfolgtem Eheschluss und lange nach Ende der Beziehung des Beschwerdeführers zu seiner ehemaligen Schweizer Partnerin geboren. Schliesslich erachtet das Bundesamt für Migration das Familiennachzugsgesuch als "entscheidrelevante Tatsache". Allerdings ist auch hier nicht leicht zu erkennen, welche Rückschlüsse dieses Gesuch auf die Qualität der früheren Ehe des Beschwerdeführers haben soll, ist es doch völlig normal, dass ein in der Schweiz niedergelassener Ausländer, der mit einer anderen ausländischen Person die Ehe eingeht und Vater wird, seine Familie in die Schweiz nachziehen will.
4.3. Zusammenfassend ergibt sich, dass ein Widerruf der Niederlassungsbewilligung des Beschwerdeführers zum heutigen Zeitpunkt nicht (mehr) in Betracht fällt, da den Behörden die nicht von der Hand zu weisenden Hinweise auf eine Scheinehe bei Bewilligungserteilung bekannt waren und sein seitheriges Verhalten keine solchen Rückschlüsse zulässt. Damit erweist sich die Beschwerde des Bundesamts für Migration als unbegründet. Sie ist abzuweisen.
5.
Bei diesem Verfahrensausgang sind keine Gerichtskosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Das Bundesamt für Migration hat den Beschwerdegegner für das bundesgerichtliche Verfahren aber mit Fr. 2'500.-- zu entschädigen (Art. 68 Abs. 1 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Es werden keine Gerichtskosten erhoben.
3.
Das Bundesamt für Migration hat den Beschwerdegegner für das bundesgerichtliche Verfahren mit Fr. 2'500.-- zu entschädigen.
4.
Dieses Urteil wird den Verfahrensbeteiligten und dem Verwaltungsgericht des Kantons Zürich, 2. Kammer, schriftlich mitgeteilt.
Lausanne, 18. März 2014
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Seiler
Die Gerichtsschreiberin: Hänni