Modelling Interaction, Dialog, Social Choice, and Vagueness

Summary

Practical Details

Timetable

Poster

CFSC

DiFoS

LINT

VAAG

Samson Abramsky, From Lawvere to Brandenburger-Keisler: interactive forms of diagonalization and self-reference

We analyze the Brandenburger-Keisler paradox in epistemic game theory, and show how it can be reduced to a one-person diagonal argument. We give a compositional account, which leads to simple multi-agent generalizations.

We also give a general approach to the construction of assumption complete models.

Dietmar Berwanger, Game metaphors in compositional design (slides)

The way in which the parts of a computational system interact resembles in many regards the behaviour of players in a game. In situations of pure conflict, the correspondence proved to be indeed faithful, giving raise to striking applications of game-theoretic methods in automated design. However, in situations that require coordination, the correspondence is less tight and requires new foundational insights. In this talk, we survey a few key promises, achievements, and limitations of the game-based approach to the design of complex systems.

Denis Bonnay and Paul Egré, Higher-order knowledge and higher-order vagueness

In this paper we discuss and relate two logical paradoxes about vagueness, which concern the semantics of operators such as "I know that", "clearly" and "definitely" when these operators are iterated. The first puzzle, originally due to Williamson (1992, 1994, 2000) concerns margin for error principles for inexact knowledge and their impact in modelling higher-order knowledge. The second puzzle, originally due to D. Graff Fara (2003) in discussions of supervaluationism, concerns so-called gap principles for definiteness operators and their impact in modelling higher-order vagueness.

Margin for error principles are principles of the form: if I know that P(x), then P must hold of every y within a given margin of error around x. Gap principles are principles of the form: if it is definitely the case that P(x), then it is not definitely the case that not P(y), for every y that is only slightly different from x. Williamson shows the incompatibility of margin for error principles with the iterative principle of positive introspection ('if I know p, then I know that I know p'). Fara shows the incompatibility of gap principles with an iterative rule of Definiteness-introduction ('from p, infer Definitely p').

In the first part of this paper, we focus on the margin for error paradox of Williamson and review the ingredients of a solution we articulated in several recent papers (Bonnay and Egré 2009, Bonnay and Egré in press). Our solution, which involves a modification of standard Kripke semantics, called Centered Semantics, basically rests on the idea that the paradox can be blocked if margins of error are allowed to vary with each new iteration of knowledge. We present the solution in the framework of Dynamic epistemic logic and argue that this is a plausible solution if knowledge iterations are viewed as a learning process rather than statically.

In the second part of the paper, we go on to discuss the correspondence between this approach to Williamson's paradox, and two recent solutions to Fara's paradox proposed by Pagin (in progress) and Cobreros (in press). Both of their approaches involve a rejection of the rule of D-introduction. Pagin's solution, in particular, handles "definitely" as an intensifier: on his approach, each further iteration of "definitely" will increase the overall standard relevant to assess similarity, but those increments may likewise vary from one level to the next. We conclude that the margin for error paradox and the gap paradox can be handled in essentially the same way, each time by calling into question the idea that the notion of similarity relevant to knowledge or definiteness is insensitive to the iteration of such operators.

Pietro Galliani, Dynamic Dependence Logic (slides)

Dynamic Semantics is a theoretical linguistics framework which may be roughly summarized by the motto "The meaning of a sentence does not lie in its truth conditions, but rather in the way it changes (the representation of) the information of the interpreter" (Groenendijk and Stokhof, 1991). In this talk, I will introduce a dynamic variant of Dependence Logic and discuss some of its properties.

Peter Gärdenfors, Why Language has to be vague (slides)

The starting-point is an an account of semantics that is not construed as a mapping of language to the world, but mapping between individual meaning spaces. The meanings of linguistic entities are established via a "meeting of minds." The concepts in the minds of communicating individuals are modeled as convex regions in conceptual spaces. However, since the continuous spaces of individuals is mediated in linguistic communication by discrete elements (or combinations fo such), the mapping between spaces will be an approximation. I will analyse the consequences of this view on semantics for the notion of vagueness.

Wilfrid Hodges, Four paradigms for logical games (slides)

In the words of Benedikt Loewe's request, I will give "a synthetizing talk, highlighting commonalities and differences" between four paradigms for logical games: obligationes, Lorenzen-style dialogue games, Ehrenfeucht-Fraisse games and Hintikka's Game-Theoretic Semantics.

Jean-François Laslier, Approval voting : Theories and experiments (slides)

This is a survey of recent adavances about Approval Voting. We expose experimental evidence about voter behavior, recent theories about strategic voting, and we observe that these theories fit quite well with the observations. Then we turn to the question of the strategic behavior of the political parties under this rule, about which we of course have no observation yet.

Claudia Lindner, Not Everyone Likes Mushrooms: Fair Division and Degrees of Guaranteed Envy-Freeness (slides)

Cake-cutting protocols aim at dividing a "cake" (i.e., a divisible resource) and assigning the resulting portions to several players in a way that each of the players feels to have received a "fair" amount of the cake. An important notion of fairness is envy-freeness: No player wishes to switch the portion of the cake received with another player's portion. Despite intense efforts in the past, it is still an open question whether there is a finite bounded envy-free cake-cutting protocol for an arbitrary number of players, and even for four players. We introduce the notion of degree of guaranteed envy-freeness (DGEF) as a measure of how good a cake-cutting protocol can approximate the ideal of envy-freeness while keeping the protocol finite bounded (trading being disregarded). We propose a new finite bounded proportional protocol for any number n ≥ 3 of players, and show that this protocol has a DGEF of 1 + ⌈ (n^2)/2 ⌉. Among known finite bounded cake-cutting protocols for an arbitrary number of players, this is the best DGEF currently known to hold. We will make the case that improving the DGEF even further is a tough challenge, and determine, for comparison, the DGEF of selected known finite bounded cake-cutting protocols.

Reshef Meir, Convergence to Equilibria in Plurality Voting (slides)

Multi-agent decision problems, in which independent agents have to agree on a joint plan of action or allocation of resources, are central to AI. In such situations, agents' individual preferences over available alternatives may vary, and they may try to reconcile these differences by voting. Based on the fact that agents may have incentives to vote strategically and misreport their real preferences, a number of recent papers have explored different possibilities for avoiding or eliminating such manipulations. In contrast to most prior work, this paper focuses on convergence of strategic behavior to a decision no voter will want to deviate from.

This is a joint work with Maria Polukarov, Jeffrey S. Rosenschein and Nick R. Jennings

Thomas Piecha, Dialogues, End-Rules and Definitional Reasoning (slides)

We present a dialogue calculus with an end-rule for complex formulas. In sequent calculi this end-rule corresponds to initial sequents with complex formulas. Equivalence can be proved for this dialogue calculus and the corresponding sequent calculus for propositional intuitionistic logic. This is of importance for reasoning about definitions of atomic formulas whose defining conditions are complex. In order to reason about such definitions we introduce definitional dialogues with an additional argumentation form. This approach also suggests an analysis of paradoxes.

Robert van Rooij, Being tolerant about vagueness (slides)

Remzi Sanver, Approval as in intrinsic part of preference (paper)

Approval Voting calls for an extension of the Arrovian preference aggregation model, by incorporating elements of cardinality and interpersonal comparability into individual preferences through assuming the existence of a common zero. We revisit Approval Voting as well as other concepts of Social Choice Theory within this extended model.

Stephanie Solt, Vagueness in quantity (slides)

Classic accounts of vagueness have focused on vague adjectives (thin, red, expensive) and nouns (heap). But vagueness is also pervasive in expressions of quantity and amount. This talk investigates two instances of vagueness in quantity: i) the context-sensitive and inherently vague quantifiers many, few, much and little; ii) the vague lower-bounded quantifier most, in contrast to its non-vague counterpart more than half. It is shown that expressions of type (i) lend themselves to an extension of recent accounts of gradable adjectives, invoking in particular the notion of a comparison class, but also bring up new issues relating to the derivation of proportional readings. The case study in (ii) proves trickier; it is shown that accounting for facts in the interpretation of the two quantifiers requires reference not only to their logical forms, but also to the possible verification strategies that result. Taken together, findings from this domain broaden our understanding of the mechanisms underlying vagueness in natural languages.

Luca Tranchini, Truth, Proofs and Dialogues. Some Remarks

The development of a proof-theoretic semantics is problematic in the light of the duality between canonical and non-canonical proofs. First, we draw an analogy between this duality and the relationship of the notions of truth of a sentence and truth of an open formula under an assignment in the Frege-Tarski semantics. We then consider the contrast between the notions of play and of strategy in the dialogical setting of Lorenzen. His approach seems to be a better way of turning the truth-conditional approach to meaning into a constructive one

Sara Uckelman, Dialogical Properties of Obligationes (slides)

The recent trend in logic has been to shift emphasis from static systems developed for purely theoretical reasons to dynamic systems designed for application to real world situations, such as modeling knowledge and belief, interaction, and reasoning in multi-agent systems. This emphasis on the situational and applied aspects of logic and reasoning is relatively new in contemporary logic, but it was the dominant approach to logic by logicians in the high Middle Ages, especially in mid-13th to mid-14th C. Medieval logic was not concerned so much with abstract logical systems valid for all subject matters and suited for dealing with, e.g., mathematical reasoning, but more so in techniques of reasoning that could be applied in real reasoning contexts, and thus which could vary from context to context. This pragmatic approach to logic was complimented with a strong interest in modeling dynamic, interactive systems, where reasoning is not an armchair process of a single agent but is instead a dispute or debate between two or more agents, each of which have different knowledge and different roles in the disputation.

The clearest example of the interactive nature of logic in the Middle Ages is the development of disputations de obligationibus. In an obligatio, two agents, the Opponent and the Respondent, engage in a turn based dialogue where the Opponent puts forward a proposition (or set of propositions) at each round, and the Respondent can either accept, deny, or doubt the proposition(s), in accord with certain rules that are fixed in advance. Many different variants of obligationes exist. These dialogues/disputations differ from modern dialogical approaches to logic (à la Lorenzen) in that they are not intended to give semantic meaning to the logical connectives, or to demonstrate the validity of a proposition. Instead, the rules of inference for reasoning must be known in advance by both the Opponent and the Respondent, and an obligational disputation about a sentence φ can be understood as testing the Respondent's ability to reason about φ, either propositionally (i.e., about the truth or falsity of φ) or at the meta-level (e.g., about whether φ is known or in doubt to him). As a result, when looking to model different types of obligationes with modern formal tools, ordinary game-based logics such as dialogical logic or game-theoretic semantics are going to be less appropriate than one might suspect given the superficial similarity between the three. Instead, we argue that, at the meta-level, obligationes are best understood as Abstract Dialogue Systems (such as those introduced by Prakken), and, at the object-level, the reasoning involved is a type of multi-agent Dynamic Epistemic Logic.

In this talk we will:

• Introduce the medieval theory of obligationes, providing examples of different rules for variants, and giving some applications of these rules to the solving of sophismata.
• Introduce the framework of Abstract Dialogue Systems and show how the rules for an obligatio can be seen as specifying a protocol for an ADS, thus giving a clear foundation for a meta-level view of obligationes, that is, from outside the disputation.
• Provide a multi-agent Dynamic Epistemic Logic framework to explicate the reasoning that takes place at the object-level, that is, within the disputation, and show how ordinary fragments of DEL can be extended to non-standard applications required to model reasoning within obligationes.

|

maintained by: Pietro Galliani ()