Sachverhalt: A. Der 1967 geborene A._ war ab 1. Oktober 2012 für die B._ AG tätig. Diese Arbeit wurde ihm von der C._ AG vermittelt. Diese kündigte das Arbeitsverhältnis am 5. März 2013 mündlich auf den 12. März 2013. Am 5. März 2013 meldete sich A._ bei der Arbeitslosenversicherung an und machte Arbeitslosenentschädigung ab 13. März 2013 geltend. Mit Verfügung vom 22. April 2013 stellte das Regionale Arbeitsvermittlungszentrum (RAV) Obwalden Nidwalden A._ wegen ungenügender persönlicher Arbeitsbemühungen vor der Arbeitslosigkeit für die Dauer von zwölf Tagen in der Anspruchsberechtigung ein, da er in den drei Monaten vor der Arbeitslosigkeit keine Arbeitsbemühungen nachweisen konnte. Daran hielt das RAV auf Einsprache hin fest (Einspracheentscheid vom 22. Mai 2013). B. Das Verwaltungsgericht des Kantons Nidwalden hiess die dagegen erhobene Beschwerde mit Entscheid vom 16. Dezember 2013 insofern teilweise gut, als es die Dauer der Einstellung in der Anspruchsberechtigung auf vier Tage reduzierte. C. Das Staatssekretariat für Wirtschaft (SECO) führt Beschwerde in öffentlich-rechtlichen Angelegenheiten und beantragt, es sei der vorinstanzliche Entscheid aufzuheben und der Einspracheentscheid des RAV vom 22. Mai 2013 zu bestätigen. Das kantonale Gericht und A._ schliessen auf Abweisung der Beschwerde. Das RAV verzichtet auf eine Stellungnahme.