We consider allocation rules that choose both a public outcome and transfers, based on the agents' reported valuations of the outcomes. Under a given allocation rule, a bribing situation exists when one agent could pay another to misreport his valuations, resulting in a net gain to both agents. A rule is bribe-proof if such opportunities never arise (including the case in which the briber and bribee are the same agent). The central result is that under a bribe-proof rule, regardless of the domain of admissible valuations, the payoff to any one agent is a continuous function of any other agent's reported valuations. We then show that on connected domains of valuation functions, if either the set of outcomes is finite or each agent's set of admissible valuations is smoothly connected, then an agent's payoff is a constant function of other agents' reported valuations. Finally, under the additional assumption of a standard richness condition on the set of admissible valuations, a bribe-proof rule must be a constant function.