We tested whether 3- and 4-year-olds (N = 88) can deduce individuals' credibility exclusively from situational cues such as game rules that reward competitive or cooperative behavior-and whether children's inferences are predicted by their executive function (EF) and theory of mind (ToM) skills. When presented with the game rules, children endorsed a partner's claims more often if the rules incentivized cooperation between participants and partners (e.g., by giving them prizes when trusting each other) versus when the rules incentivized deception (e.g., by giving prizes to partners who tricked the children). Notably, children's appropriate responses to partners' claims increased as their EF skills improved regardless of whether the rules supported trust or skepticism. ToM was not related to children's rule-based selectivity. Preschoolers' ability to make inferences based on cooperative versus competitive reward rules to determine whether the children's partner can be trusted is key to learning from individuals whose reputation or past behavior is completely unknown. In addition, findings of associations between EF and vigilance about others' claims contribute to the epistemological debate of whether people start in life as credulous learners.