Nonmanipulable Collective Decision-Making for Games

Nonmanipulable Collective Decision-Making for Games

Rob LeGrand (Angelo State University, USA), Timothy Roden (Angelo State University, USA) and Ron K. Cytron (Washington University in St. Louis, USA)
DOI: 10.4018/978-1-4666-1634-9.ch004


This chapter explores a new approach that may be used in game development to help human players and/or non-player characters make collective decisions. The chapter describes how previous work can be applied to allow game players to form a consensus from a simple range of possible outcomes in such a way that no player can manipulate it at the expense of the other players. Then, the text extends that result and shows how nonmanipulable consensus can be found in higher-dimensional outcome spaces. The results may be useful when developing artificial intelligence for non-player characters or constructing frameworks to aid cooperation among human players.
Chapter Preview

Background Ideas

The core ideas of this chapter, while new, are based in extant work from fields such as computer science, mathematics, political science and economics.

Mechanism Design

Returning to the above wargame example, if a team of players is trying to agree on a coastal attack point, their preferred points could simply be averaged to give the consensus point, but doing so sometimes rewards insincerity on the parts of the players. The field of mechanism design (Nisan, 2007) has evolved to find decision-making mechanisms that satisfy particular properties, often some kind of immunity or resistance to strategic manipulation.

Strategic manipulation is a common problem in collective decision-making. It is well known that voters can gain advantage under most voting systems by voting insincerely (Gibbard, 1973; Satterthwaite, 1975). Examples include voting for an alternative that is not a voter’s first choice and ranking alternatives untruthfully. Traditionally, this problem is discussed in political science, but more recently the techniques of computer science have been applied with success (Bartholdi, Tovey & Trick 1989, Conitzer & Sandholm, 2003; Elkind & Lipmaa, 2005; Procaccia & Rosenschein, 2006). In this chapter we explore a particular approach to creating manipulation-resistant mechanisms.

Complete Chapter List

Search this Book: