Sachverhalt:
A.
A._ erstattete am 9. Februar 2016 Strafanzeige gegen X._ wegen Betrugs und Widerhandlung gegen das Bundesgesetz gegen den unlauteren Wettbewerb (UWG; SR 241). Dieser soll im Rahmen einer Geschäftsbeziehung entgeltliche Leistungen von A._ bezogen haben, ohne je den Willen gehabt zu haben, diese zu bezahlen.
B.
Am 17. März 2016 nahm das Untersuchungsamt St. Gallen das Verfahren betreffend Widerhandlung gegen das UWG nicht an die Hand. Diese Verfügung erwuchs unangefochten in Rechtskraft. Am 3. Juni 2016 verfügte das Untersuchungsrichteramt St. Gallen auch hinsichtlich des Straftatbestands des Betrugs die Nichtanhandnahme des Verfahrens. Dagegen erhob A._ Beschwerde, welche die Anklagekammer des Kantons St. Gallen am 5. Oktober 2016 abwies.
C.
A._ beantragt mit Beschwerde in Strafsachen, der Entscheid der Anklagekammer vom 5. Oktober 2016 sei aufzuheben und die Staatsanwaltschaft sei anzuweisen, die Untersuchung an die Hand zu nehmen. Eventualiter sei die Sache zu neuer Beurteilung an die Anklagekammer zurückzuweisen.
D.
Die Anklagekammer und die Staatsanwaltschaft des Kantons St. Gallen verweisen auf den angefochtenen Entscheid und verzichten auf eine Stellungnahme. X._ lässt sich vernehmen und beantragt, der Beschwerde sei keine Folge zu geben und A._ sei zum Kostenersatz zu verurteilen. Dieser hält in seiner Replik an seiner Auffassung fest.

Erwägungen:
1.
Die Privatklägerschaft ist zur Beschwerde in Strafsachen nur berechtigt, wenn der angefochtene Entscheid sich auf die Beurteilung ihrer Zivilansprüche auswirken kann (Art. 81 Abs. 1 lit. b Ziff. 5 BGG). In erster Linie geht es um Ansprüche auf Schadenersatz und Genugtuung gemäss <ref-law>, die üblicherweise vor den Zivilgerichten geltend gemacht werden müssen. Richtet sich die Beschwerde gegen die Einstellung oder Nichtanhandnahme eines Verfahrens, hat die Privatklägerschaft nicht notwendigerweise bereits vor den kantonalen Behörden Zivilansprüche geltend gemacht. In jedem Fall muss sie im Verfahren vor Bundesgericht darlegen, aus welchen Gründen sich der angefochtene Entscheid inwiefern auf welche Zivilforderung auswirken kann. Das Bundesgericht stellt an die Begründung der Legitimation strenge Anforderungen. Genügt die Beschwerde diesen nicht, kann darauf nur eingetreten werden, wenn aufgrund der Natur der untersuchten Straftat ohne Weiteres ersichtlich ist, um welche Zivilforderung es geht (<ref-ruling> E. 1.1 S. 4 f. mit Hinweisen).
Diesen Anforderungen genügt der Beschwerdeführer nicht, da er sich nicht zu seiner Beschwerdelegitimation äussert. Jedoch können die von ihm angezeigten Straftaten offensichtlich zu Zivilforderungen im Sinne von <ref-law> führen. Ferner konstituierte er sich in seiner Strafanzeige vom 9. Februar 2016 als Privatkläger und machte zivilrechtliche Ansprüche in der Höhe von mindestens Fr. 18'762.55 geltend. Auf die Beschwerde ist einzutreten.
2.
2.1. Der Beschwerdeführer wendet ein, die Vorinstanz stelle den Sachverhalt unvollständig fest beziehungsweise verletze seinen Anspruch auf rechtliches Gehör, indem sie sich zu verschiedenen seiner Vorbringen nicht äussere.
2.2. Der in <ref-law> garantierte Anspruch auf rechtliches Gehör verpflichtet das Gericht, die Parteivorbringen tatsächlich zu hören, zu prüfen und in der Entscheidfindung zu berücksichtigen. Die Begründung muss deshalb zumindest kurz die wesentlichen Überlegungen nennen, von denen sich das Gericht hat leiten lassen und auf die es seinen Entscheid stützt. Dagegen wird nicht verlangt, dass sich die Begründung mit allen Parteistandpunkten einlässlich auseinandersetzt und jedes einzelne Vorbringen ausdrücklich widerlegt (<ref-ruling> E. 5.2 S. 70 f.; <ref-ruling> E. 3.2.4 S. 41; <ref-ruling> E. 2.2 S. 183; je mit Hinweisen).
2.3. Der angefochtene Entscheid genügt den dargelegten Begründungsanforderungen. Die Vorinstanz war insbesondere nicht gehalten, sich zu der Mutmassung des Beschwerdeführers zu äussern, wonach der Beschwerdegegner sehr wahrscheinlich einer dubiosen Bewegung angehöre, die unter anderem den Rechtsstaat nicht als solchen anerkenne, und dieser deshalb nie leistungswillig gewesen sei. Der Beschwerdeführer stützt seine Auffassung insbesondere auf eine wirre E-Mail des Beschwerdegegners, die dieser an die Polizei sandte. Inwiefern sich daraus ergeben sollte, dass der Beschwerdegegner in Bezug auf die geschäftliche Beziehung mit dem Beschwerdeführer nie über einen Leistungswillen verfügte, ist nicht ersichtlich. Soweit der Beschwerdeführer seinen Standpunkt mit einer Aktennotiz vom 5. Dezember 2016 seines österreichischen Anwalts über Informationen, die dieser von der dortigen Verfassungsschutzbehörde erhalten haben will, oder mittels einer Abfrage vom 24. August 2017 beim Zentralen Melderegister des Bundesministeriums für Inneres der Republik Österreich zu untermauern versucht, ist er damit nicht zu hören. Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>), was in der Beschwerde darzulegen ist. Hierbei handelt es sich um unechte Noven. Echte Noven, d.h. Tatsachen, die sich zugetragen haben, nachdem vor der Vorinstanz keine neuen Tatsachen mehr vorgetragen werden durften, sind vor Bundesgericht unbeachtlich (<ref-ruling> E. 1.2 S. 22 f.; <ref-ruling> E. 3.1.2 S. 123; <ref-ruling> E. 5.2.4 S. 229; je mit Hinweisen). Nicht einzugehen ist auf die Rüge des Beschwerdeführers, die Vorinstanz setze sich nicht mit den tatsächlichen Vorbringen seiner Eingaben vom 23. August 2016 und 12. September 2016 auseinander. Er legt nicht dar, auf welche weiteren Vorbringen die Vorinstanz nicht eingegangen sein soll. Die Beschwerde genügt insoweit den Begründungsanforderungen nicht (vgl. Art. 42 Abs. 2 i.V.m. <ref-law>).
3.
3.1. Der Beschwerdeführer rügt sinngemäss, die Vorinstanz verletze <ref-law>. Es liege kein sachverhaltsmässig und rechtlich klarer Fall vor, weshalb keine Nichtanhandnahmeverfügung hätte ergehen dürfen.
3.2. Nach <ref-law> eröffnet die Staatsanwaltschaft eine Untersuchung, wenn sich aus den Informationen und Berichten der Polizei, aus der Strafanzeige oder aus ihren eigenen Feststellungen ein hinreichender Tatverdacht ergibt. Sie verzichtet auf die Eröffnung, wenn sie sofort eine Nichtanhandnahmeverfügung oder einen Strafbefehl erlässt (<ref-law>). Gemäss <ref-law> verfügt die Staatsanwaltschaft die Nichtanhandnahme, sobald aufgrund der Strafanzeige oder des Polizeirapports feststeht, dass die fraglichen Straftatbestände oder die Prozessvoraussetzungen eindeutig nicht erfüllt sind (lit. a), Verfahrenshindernisse bestehen (lit. b) oder aus den in <ref-law> genannten Gründen auf eine Strafverfolgung zu verzichten ist (lit. c).
Die Frage, ob ein Strafverfahren über eine Nichtanhandnahme erledigt werden kann, beurteilt sich nach dem aus dem Legalitätsprinzip abgeleiteten Grundsatz "in dubio pro duriore" (<ref-law> sowie Art. 2 Abs. 1 i.V.m. Art. 319 Abs. 1 und Art. 324 Abs. 1 StPO; <ref-ruling> E. 4.2 S. 91). Danach darf eine Nichtanhandnahme durch die Staatsanwaltschaft gestützt auf <ref-law> nur in sachverhaltsmässig und rechtlich klaren Fällen ergehen. Im Zweifelsfall, wenn die Gründe der Nichtanhandnahme nicht mit absoluter Sicherheit gegeben sind, muss das Verfahren eröffnet werden (vgl. <ref-ruling> E. 2.3 S. 287 f.). Der Grundsatz "in dubio pro duriore" ist unter Würdigung der im Einzelfall gegebenen Umstände zu handhaben. Die Staatsanwaltschaft und die Beschwerdeinstanz verfügen insoweit über einen gewissen Spielraum, den das Bundesgericht nur mit Zurückhaltung überprüft (zur Verfahrenseinstellung: <ref-ruling> E. 4.1.1 f./ 4.2 S. 90 f., 186 E. 4.1 S. 190; je mit Hinweisen).
3.3. Den Tatbestand des Betrugs im Sinne von <ref-law> erfüllt, wer in der Absicht, sich oder einen andern unrechtmässig zu bereichern, jemanden durch Vorspiegelung oder Unterdrückung von Tatsachen arglistig irreführt und so den Irrenden zu einem Verhalten bestimmt, wodurch dieser sich selbst oder einen andern am Vermögen schädigt. Nach der Rechtsprechung ist die Vorspiegelung des Leistungswillens grundsätzlich arglistig im Sinne von <ref-law>, weil sie eine innere Tatsache betrifft, die vom Vertragspartner ihrem Wesen nach nicht direkt überprüft werden kann. Arglist kann bei einfachen falschen Angaben gegeben sein, wenn eine weitere Überprüfung nicht handelsüblich ist, etwa weil sie sich im Alltag als unverhältnismässig erweist und die konkreten Verhältnisse eine nähere Abklärung nicht nahelegen oder gar aufdrängen und dem Opfer diesbezüglich der Vorwurf der Leichtfertigkeit nicht gemacht werden kann. Mit einer engen Auslegung des Betrugstatbestands würden die sozialadäquate Geschäftsausübung und damit der Regelfall des Geschäftsalltags betrugsrechtlich nicht geschützt. Selbst ein erhebliches Mass an Naivität des Geschädigten hat nicht in jedem Fall zur Folge, dass der Täter straflos ausgeht (<ref-ruling> E. 2.2.2 S. 154 ff. mit Hinweisen).
3.4. Die Vorinstanz führt aus, der der Strafanzeige zugrunde liegende Sachverhalt stehe im Zusammenhang mit der Geschäftstätigkeit zwischen dem Beschwerdeführer und dem Beschwerdegegner. Hinreichend konkrete Anhaltspunkte dafür, dass der Beschwerdegegner wahrheitswidrig vorgespiegelt habe, leistungswillig zu sein, seien weder ersichtlich noch genügend dargetan. Daran vermöchten sowohl die Hinweise des Beschwerdeführers auf zivilrechtliche Entscheide und Grundlagen, die von diesem geltend gemachten Vermutungen und zivilrechtlichen Beweislastverteilungen, als auch die eingereichten eidesstattlichen Erklärungen verschiedener Personen nichts zu ändern. Letzteren käme im Strafverfahren grundsätzlich ohnehin kein Beweiswert zu.
3.5. Entgegen der Auffassung der Vorinstanz liegt kein sachverhaltsmässig und rechtlich klarer Fall von Straflosigkeit vor. So ist unbestritten, dass der Beschwerdeführer im Rahmen einer Geschäftsbeziehung mit dem Beschwerdegegner gewisse Leistungen erbracht hat, für die er offenbar nicht bezahlt worden ist. Die Art der angeblich unbezahlt gebliebenen und erbrachten Leistungen (u.a. Gestaltung einer Informationsbroschüre, Design von Visitenkarten, Gestaltung eines Logos, Erstellung von Referenzvideos) lässt nicht klarerweise auf unentgeltliche Erbringung derselben schliessen. Daran ändert nichts, dass diese im Zusammenhang mit dem Aufbau eines neuen Geschäfts erbracht worden sein sollen. Vielmehr liegen insofern gegensätzliche Standpunkte vor, für die jeweils verschiedene weitere Personen als Zeugen angeführt werden. Auch wenn die Vorinstanz den diesbezüglich vom Beschwerdeführer eingereichten eidesstattlichen Erklärungen keinen Beweiswert zumisst, hätte sie zumindest prüfen müssen, ob diese als sinngemässe Beweisanträge um Einvernahme der fraglichen Personen entgegengenommen werden können. Dies gilt umso mehr, als auch die Vorinstanz ausführt, selbst ein schriftlicher Bericht im Sinne von <ref-law>, dessen Qualität den eingereichten eidesstattlichen Erklärungen nicht zukomme, vermöchte eine Einvernahme nur ganz ausnahmsweise zu ersetzen. Ohne Einvernahme der Direktbeteiligten und allenfalls weiterer Personen, die sachdienliche Aussagen machen könnten, kann im vorliegenden Fall nicht von offensichtlicher Straflosigkeit ausgegangen werden.
3.6. Nicht gefolgt werden kann auch der Eventualbegründung der Vorinstanz, wonach der Beschwerdeführer sich durch ein Minimum an Aufmerksamkeit selber hätte schützen und den Irrtum durch ein Minimum an zumutbarer Vorsicht hätte vermeiden können. Wie er zutreffend vorbringt, sieht das Schweizer Recht keine Formvorschriften vor für eine Provisionsvereinbarung respektive einen Mäklervertrag, einen Werkvertrag oder einen Auftrag (vgl. Art. 363 ff., Art. 394 ff. sowie Art. 412 Abs. 2 OR). Ein besonders leichtfertiges Verhalten lässt sich demnach nicht darin erblicken, dass der Beschwerdeführer gemäss eigener Darstellung während mehr als eines Jahres Leistungen erbracht haben will, ohne eine schriftliche Vereinbarung zu treffen. Dass eine geschäftserfahrene Person auf Schriftlichkeit der (angeblich) getroffenen Vereinbarungen beharrt oder die Zusammenarbeit beendet hätte, dürfte in dieser Absolutheit kaum gültig sein. Der Beschwerdeführer wendet diesbezüglich sodann überzeugend ein, als Jungunternehmer sei er auf Aufträge angewiesen und er wolle Kunden nicht vergraulen, indem er auf Schriftlichkeit bestehe. Im Übrigen ist nicht ersichtlich, gestützt worauf die Vorinstanz davon ausgeht, der Beschwerdeführer sei geschäftserfahren. Zuzustimmen ist ihr, dass der Beschwerdeführer Kostenvorschüsse hätte verlangen und die Bonität seines Geschäftspartners hätte abklären können. Allerdings wird auch unter dem Gesichtspunkt der Opfermitverantwortung nicht verlangt, dass der Getäuschte die grösstmögliche Sorgfalt walten lässt und alle erdenklichen Vorkehren trifft. Arglist scheidet lediglich aus, wenn er die grundlegendsten Vorsichtsmassnahmen nicht beachtet. Der Beschwerdeführer weist darauf hin, es sei nicht üblich, für die Art von Arbeiten, welche er verrichtet habe, Kostenvorschüsse zu verlangen. Sodann habe das Unternehmen des Beschwerdegegners damals bereits seit über acht Jahren existiert und aus dem Handelsregister sei nichts ersichtlich gewesen, was die Bonität infrage gestellt hätte. Ein klarerweise leichtfertiges Verhalten des Beschwerdeführers liegt mit Blick auf die gesamten Umstände somit nicht vor.
3.7. Schliesslich mag es zwar zutreffen, dass es im Kern um eine zivilrechtliche Angelegenheit zwischen dem Beschwerdeführer und dem Beschwerdegegner geht. Trifft aber der Vorwurf zu, dass Letzterer von Anfang an Leistungen bezogen hat ohne gleichzeitig willig zu sein, diese zu vergüten, liegt ein hinreichend konkreter Anhaltspunkt für ein strafrechtlich relevantes Verhalten vor, weshalb die Zuständigkeit der Strafbehörden nicht von vornherein verneint werden kann.
4.
Die Beschwerde ist gutzuheissen und der angefochtene Entscheid ist aufzuheben. Damit erübrigt es sich, auf die weiteren Rügen des Beschwerdeführers einzugehen. Die Sache ist zur Neuregelung der Kosten- und Entschädigungsfolgen an die Vorinstanz sowie zur Eröffnung einer Strafuntersuchung an die Staatsanwaltschaft zurückzuweisen.
Bei diesem Verfahrensausgang hat der unterliegende Beschwerdegegner die hälftigen Verfahrenskosten zu tragen (Art. 66 Abs. 1 und 4 BGG) und dem Beschwerdeführer gemeinsam mit dem Kanton St. Gallen unter solidarischer Haftung eine angemessene Entschädigung für das bundesgerichtliche Verfahren auszurichten (Art. 68 Abs. 2 und 4 i.V.m. <ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen, der Entscheid der Anklagekammer des Kantons St. Gallen vom 5. Oktober 2016 aufgehoben und die Sache an die Anklagekammer zur Neuregelung der Kosten- sowie Entschädigungsfolgen und an die Staatsanwaltschaft des Kantons St. Gallen zur Eröffnung einer Strafuntersuchung zurückgewiesen.
2.
Der Beschwerdegegner hat Gerichtskosten von Fr. 1'000.-- zu bezahlen.
3.
Der Beschwerdegegner und der Kanton St. Gallen haben den Beschwerdeführer für das bundesgerichtliche Verfahren unter solidarischer Haftung mit je Fr. 1'500.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und der Anklagekammer des Kantons St. Gallen schriftlich mitgeteilt.
Lausanne, 21. September 2017
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Die Gerichtsschreiberin: Andres