_ Convention_ was immediately recognized as a major contribution to the subject and its significance has remained undiminished since its first publication in 1969. Lewis analyzes social conventions as regularities in the resolution of recurring coordination problems-situations characterized by interdependent decision processes in which common interests are at stake. Conventions are contrasted with other kinds of regularity, and conventions governing systems of communication are given special attention.

The 'Evolution of Cooperation' addresses a simple yet age-old question; If living things evolve through competition, how can cooperation ever emerge? Despite the abundant evidence of cooperation all around us, there existed no purely naturalistic answer to this question until 1979, when Robert Axelrod famously ran a computer tournament featuring a standard game-theory exercise called The Prisoner's Dilemma. To everyone's surprise, the program that won the tournament, named Tit for Tat, was not only the simplest but the most "cooperative" entrant. (...) This unexpected victory proved that cooperation - one might even say altruism - is mathematically possible and therefore needs no hidden hand or divine agent to create and sustain it. A great roadblock to the understanding of all sorts of behavior was at last removed. The updated edition includes an extensive new chapter on cooperation in cancer cells and among terrorist organizations. (shrink)

This book is an introduction to finite model theory which stresses the computer science origins of the area. In addition to presenting the main techniques for analyzing logics over finite models, the book deals extensively with applications in databases, complexity theory, and formal languages, as well as other branches of computer science. It covers Ehrenfeucht-Fraïssé games, locality-based techniques, complexity analysis of logics, including the basics of descriptive complexity, second-order logic and its fragments, connections with finite automata, fixed point logics, finite (...) variable logics, zero-one laws, and embedded finite models, and gives a brief tour of recently discovered applications of finite model theory. This book can be used both as an introduction to the subject, suitable for a one- or two-semester graduate course, or as reference for researchers who apply techniques from logic in computer science. (shrink)

A speaker wishes to persuade a listener to accept a certain request. The conditions under which the request is justified, from the listener’s point of view, depend on the values of two aspects. The values of the aspects are known only to the speaker and the listener can check the value of at most one. A mechanism specifies a set of messages that the speaker can send and a rule that determines the listener’s response, namely, which aspect he checks and (...) whether he accepts or rejects the speaker’s request. We study mechanisms that maximize the probability that the listener accepts the request when it is justified and rejects the request when it is unjustified, given that the speaker maximizes the probability that his request is accepted. We show that a simple optimal mechanism exists and can be found by solving a linear programming problem in which the set of constraints is derived from what we call the L-principle. (shrink)

In this paper I will discuss why (un) marked expressionstypically get an (un)marked interpretation: Horn''sdivision of pragmatic labor. It is argued that it is aconventional fact that we use language this way.This convention will be explained in terms ofthe equilibria of signalling games introduced byLewis (1969), but now in an evolutionary setting. Iwill also relate this signalling game analysis withParikh''s (1991, 2000, 2001) game-theoretical analysis ofsuccessful communication, which in turn is compared withBlutner''s: 2000) bi-directional optimality theory.