False-name-proofness in Online Mechanisms

False-name manipulations • In highly anonymous environments such as the Internet, an agent can pretend to be multiple agents. • A mechanism is false-name-proof (FNP) if for each agent, truthful telling by using a single identifier (although he can use multiple identifiers) is a dominant strategy. – In combinatorial auctions, even theoretically well-founded Vickrey-Clarke-Groves mechanism is not FNP (i.e., vulnerable against false-name manipulations). Online Mechanism Design • Mechanism Design has focused on static (offline) environments. – All agents arrive and depart simultaneously. • In real electronic markets, each agent arrives and departs over time. • Mechanism must make decisions dynamically without knowledge of the future. Summary • This is the first work that deals with false-name manipulations in online mechanisms. • We identified a simple condition called (value, time, identifier)-monotonicity, which fully characterizes FNP online auction mechanisms. • Based on the characterization, we developed a new FNP online auction mechanism. – An application of Bruss’s optimal stopping strategy to online auction