20 Search Results for "Lang, Jérôme"


Document
Determining a Slater Winner Is Complete for Parallel Access to NP

Authors: Michael Lampis

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)


Abstract
We consider the complexity of deciding the winner of an election under the Slater rule. In this setting we are given a tournament T = (V,A), where the vertices of V represent candidates and the direction of each arc indicates which of the two endpoints is preferable for the majority of voters. The Slater score of a vertex v ∈ V is defined as the minimum number of arcs that need to be reversed so that T becomes acyclic and v becomes the winner. We say that v is a Slater winner in T if v has minimum Slater score in T. Deciding if a vertex is a Slater winner in a tournament has long been known to be NP-hard. However, the best known complexity upper bound for this problem is the class Θ₂^p, which corresponds to polynomial-time Turing machines with parallel access to an NP oracle. In this paper we close this gap by showing that the problem is Θ₂^p-complete, and that this hardness applies to instances constructible by aggregating the preferences of 7 voters.

Cite as

Michael Lampis. Determining a Slater Winner Is Complete for Parallel Access to NP. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{lampis:LIPIcs.STACS.2022.45,
  author =	{Lampis, Michael},
  title =	{{Determining a Slater Winner Is Complete for Parallel Access to NP}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{45:1--45:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.45},
  URN =		{urn:nbn:de:0030-drops-158555},
  doi =		{10.4230/LIPIcs.STACS.2022.45},
  annote =	{Keywords: Slater winner, Feedback Arc Set, Tournaments}
}
Document
Fair Division (Dagstuhl Seminar 16232)

Authors: Yonatan Aumann, Jérôme Lang, and Ariel D. Procaccia

Published in: Dagstuhl Reports, Volume 6, Issue 6 (2016)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 16232 "Fair Division". The seminar was composed of technical sessions with regular talks, and discussion sessions distributed over the full week.

Cite as

Yonatan Aumann, Jérôme Lang, and Ariel D. Procaccia. Fair Division (Dagstuhl Seminar 16232). In Dagstuhl Reports, Volume 6, Issue 6, pp. 10-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@Article{aumann_et_al:DagRep.6.6.10,
  author =	{Aumann, Yonatan and Lang, J\'{e}r\^{o}me and Procaccia, Ariel D.},
  title =	{{Fair Division (Dagstuhl Seminar 16232)}},
  pages =	{10--25},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{6},
  editor =	{Aumann, Yonatan and Lang, J\'{e}r\^{o}me and Procaccia, Ariel D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.6.6.10},
  URN =		{urn:nbn:de:0030-drops-67255},
  doi =		{10.4230/DagRep.6.6.10},
  annote =	{Keywords: cake cutting, computational social choice, envy-freeness, fair division}
}
Document
07431 Abstracts Collection – Computational Issues in Social Choice

Authors: Ulle Endriss, Jérôme Lang, Francesca Rossi, and Tuomas Sandholm

Published in: Dagstuhl Seminar Proceedings, Volume 7431, Computational Issues in Social Choice (2007)


Abstract
From the 21st to the 26th of October 2007, the Dagstuhl Seminar 07431 on ``Computational Issues in Social Choice'' was held at the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their recent research, and ongoing work and open problems were discussed. The abstracts of the talks given during the seminar are collected in this paper. The first section summarises the seminar topics and goals in general. Links to full papers are provided where available.

Cite as

Ulle Endriss, Jérôme Lang, Francesca Rossi, and Tuomas Sandholm. 07431 Abstracts Collection – Computational Issues in Social Choice. In Computational Issues in Social Choice. Dagstuhl Seminar Proceedings, Volume 7431, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{endriss_et_al:DagSemProc.07431.1,
  author =	{Endriss, Ulle and Lang, J\'{e}r\^{o}me and Rossi, Francesca and Sandholm, Tuomas},
  title =	{{07431 Abstracts Collection – Computational Issues in Social Choice}},
  booktitle =	{Computational Issues in Social Choice},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7431},
  editor =	{Ulle Endriss and J\'{e}r\^{o}me Lang and Francesca Rossi and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07431.1},
  URN =		{urn:nbn:de:0030-drops-12736},
  doi =		{10.4230/DagSemProc.07431.1},
  annote =	{Keywords: Computational social choice, voting theory, fair division, mechanism design, coalition formation, complexity theory, preference representation, algorithms}
}
Document
07431 Executive Summary – Computational Issues in Social Choice

Authors: Ulle Endriss, Jérôme Lang, Francesca Rossi, and Tuomas Sandholm

Published in: Dagstuhl Seminar Proceedings, Volume 7431, Computational Issues in Social Choice (2007)


Abstract
Computational social choice is an interdisciplinary field of study at the interface of social choice theory and computer science, with knowledge flowing in either direction. On the one hand, computational social choice is concerned with importing concepts and procedures from social choice theory for solving questions that arise in computer science and AI application domains. This is typically the case for managing societies of autonomous agents, which calls for negotiation and voting procedures. On the other hand, computational social choice is concerned with importing notions and methods from computer science for solving questions originally stemming from social choice, for instance by providing new perspectives on the problem of manipulation and control in elections. This Dagstuhl Seminar has been devoted to the presentation of recent results and an exchange of ideas in this growing research field.

Cite as

Ulle Endriss, Jérôme Lang, Francesca Rossi, and Tuomas Sandholm. 07431 Executive Summary – Computational Issues in Social Choice. In Computational Issues in Social Choice. Dagstuhl Seminar Proceedings, Volume 7431, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{endriss_et_al:DagSemProc.07431.2,
  author =	{Endriss, Ulle and Lang, J\'{e}r\^{o}me and Rossi, Francesca and Sandholm, Tuomas},
  title =	{{07431 Executive Summary – Computational Issues in Social Choice}},
  booktitle =	{Computational Issues in Social Choice},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7431},
  editor =	{Ulle Endriss and J\'{e}r\^{o}me Lang and Francesca Rossi and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07431.2},
  URN =		{urn:nbn:de:0030-drops-12749},
  doi =		{10.4230/DagSemProc.07431.2},
  annote =	{Keywords: Computational social choice, voting theory, fair division, mechanism design, coalition formation, complexity theory, preference representation, algorithms}
}
Document
07351 Abstracts Collection – Formal Models of Belief Change in Rational Agents

Authors: Giacomo Bonanno, James Delgrande, Jérôme Lang, and Hans Rott

Published in: Dagstuhl Seminar Proceedings, Volume 7351, Formal Models of Belief Change in Rational Agents (2007)


Abstract
From 26.08. to 30.08.2007, the Dagstuhl Seminar 07351 ``Formal Models of Belief Change in Rational Agents'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Giacomo Bonanno, James Delgrande, Jérôme Lang, and Hans Rott. 07351 Abstracts Collection – Formal Models of Belief Change in Rational Agents. In Formal Models of Belief Change in Rational Agents. Dagstuhl Seminar Proceedings, Volume 7351, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{bonanno_et_al:DagSemProc.07351.1,
  author =	{Bonanno, Giacomo and Delgrande, James and Lang, J\'{e}r\^{o}me and Rott, Hans},
  title =	{{07351 Abstracts Collection – Formal Models of Belief Change in Rational Agents}},
  booktitle =	{Formal Models of Belief Change in Rational Agents},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7351},
  editor =	{Giacomo Bonanno and James Delgrande and J\'{e}r\^{o}me Lang and Hans Rott},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07351.1},
  URN =		{urn:nbn:de:0030-drops-12414},
  doi =		{10.4230/DagSemProc.07351.1},
  annote =	{Keywords: Belief change, rational agents, information economy, information processing}
}
Document
07351 Executive Summary – Formal Models of Belief Change in Rational Agents

Authors: Giacomo Bonanno, James Delgrande, Jérôme Lang, and Hans Rott

Published in: Dagstuhl Seminar Proceedings, Volume 7351, Formal Models of Belief Change in Rational Agents (2007)


Abstract
From August 26, 2007 to August 30, 2007, the Dagstuhl Seminar 07351 "Formal Models of Belief Change in Rational Agents" was held at the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. The Executive Summary describes the seminar topics and goals in general. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in the Proceedings. Links to extended abstracts or full papers are provided, if available.

Cite as

Giacomo Bonanno, James Delgrande, Jérôme Lang, and Hans Rott. 07351 Executive Summary – Formal Models of Belief Change in Rational Agents. In Formal Models of Belief Change in Rational Agents. Dagstuhl Seminar Proceedings, Volume 7351, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{bonanno_et_al:DagSemProc.07351.2,
  author =	{Bonanno, Giacomo and Delgrande, James and Lang, J\'{e}r\^{o}me and Rott, Hans},
  title =	{{07351 Executive Summary – Formal Models of Belief Change in Rational Agents}},
  booktitle =	{Formal Models of Belief Change in Rational Agents},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7351},
  editor =	{Giacomo Bonanno and James Delgrande and J\'{e}r\^{o}me Lang and Hans Rott},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07351.2},
  URN =		{urn:nbn:de:0030-drops-12018},
  doi =		{10.4230/DagSemProc.07351.2},
  annote =	{Keywords: Belief revision, iterated belief revision, update, merging, dynamic logic, epistemic logic,conditionals, social choice, game theory}
}
Document
From belief change to preference change

Authors: Jérôme Lang and Leendert van der Torre

Published in: Dagstuhl Seminar Proceedings, Volume 7351, Formal Models of Belief Change in Rational Agents (2007)


Abstract
There is a huge literature on belief change. In contrast, preference change has been considered only in a few recent papers. There are reasons for that: while there is to some extent a general agreement about the very meaning of belief change, this is definitely not so for preference change. We discuss here the possible meanings of preference change, arguing that we should at least distinguish between four paradigms: preferences evolving after some new fact has been learned, preferences evolving as a result of an evolution of the world, preferences evolving after the rational agent itself evolves, and preferences evolving per se. We then develop in more detail the first of these four paradigms (which we think is the most natural). We give some natural properties that we think preference change should fulfill and define several families of preference change operators, parameterized by a revision function on epistemic states and a semantics for interpreting preferences over formulas.

Cite as

Jérôme Lang and Leendert van der Torre. From belief change to preference change. In Formal Models of Belief Change in Rational Agents. Dagstuhl Seminar Proceedings, Volume 7351, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{lang_et_al:DagSemProc.07351.13,
  author =	{Lang, J\'{e}r\^{o}me and van der Torre, Leendert},
  title =	{{From belief change to preference change}},
  booktitle =	{Formal Models of Belief Change in Rational Agents},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7351},
  editor =	{Giacomo Bonanno and James Delgrande and J\'{e}r\^{o}me Lang and Hans Rott},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07351.13},
  URN =		{urn:nbn:de:0030-drops-12099},
  doi =		{10.4230/DagSemProc.07351.13},
  annote =	{Keywords: Beliefs, preferences, decision making, agents, preference revision}
}
Document
Belief Change with Noisy Sensing and Introspection

Authors: Steven Shapiro

Published in: Dagstuhl Seminar Proceedings, Volume 5321, Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics (2005)


Abstract
In this paper, we generalize the framework of Shapiro et al. [2000], where belief change due to sensing was combined with belief introspection in the situation calculus. In that framework, sensing was assumed to be infallible and the plausibilities of alternate situations (i.e., possible worlds) were fixed in the initial state, never to be updated. Here, we relax both assumptions. That is, we model noisy sensors whose readings may stray from reality and may return different values in subsequent readings. We also allow the plausibilities of situations to change over time, bringing the framework more in line with traditional models of belief change. We give some properties of our axiomatization and show that it does not suffer from the problems with combining sensing, introspection, and plausibility update described in Shapiro et al. [2000].

Cite as

Steven Shapiro. Belief Change with Noisy Sensing and Introspection. In Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics. Dagstuhl Seminar Proceedings, Volume 5321, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{shapiro:DagSemProc.05321.7,
  author =	{Shapiro, Steven},
  title =	{{Belief Change with Noisy Sensing and Introspection}},
  booktitle =	{Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5321},
  editor =	{James Delgrande and Jerome Lang and Hans Rott and Jean-Marc Tallon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05321.7},
  URN =		{urn:nbn:de:0030-drops-4632},
  doi =		{10.4230/DagSemProc.05321.7},
  annote =	{Keywords: Belief change, noisy sensing, theories of action, situation calculus.}
}
Document
05321 Abstracts Collection – Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics

Authors: James Delgrande, Jérôme Lang, Hans Rott, and Jean-Marc Tallon

Published in: Dagstuhl Seminar Proceedings, Volume 5321, Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics (2005)


Abstract
From 07.08.05 to 12.08.05, the Dagstuhl Seminar 05321 ``Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

James Delgrande, Jérôme Lang, Hans Rott, and Jean-Marc Tallon. 05321 Abstracts Collection – Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics. In Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics. Dagstuhl Seminar Proceedings, Volume 5321, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{delgrande_et_al:DagSemProc.05321.2,
  author =	{Delgrande, James and Lang, J\'{e}r\^{o}me and Rott, Hans and Tallon, Jean-Marc},
  title =	{{05321 Abstracts Collection – Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics}},
  booktitle =	{Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5321},
  editor =	{James Delgrande and Jerome Lang and Hans Rott and Jean-Marc Tallon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05321.2},
  URN =		{urn:nbn:de:0030-drops-3628},
  doi =		{10.4230/DagSemProc.05321.2},
  annote =	{Keywords: Belief revision, iterated belief revision, update, merging, dynamic logic, possibility theory, conditionals, social choice, distance, complexity}
}
Document
05321 – Panel on belief change

Authors: Isaac Levi, Giacomo Bonanno, Bernard Walliser, Didier Dubois, Hans Rott, James Delgrande, and Jérôme Lang

Published in: Dagstuhl Seminar Proceedings, Volume 5321, Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics (2005)


Abstract
This document gathers the panelists' contribution.

Cite as

Isaac Levi, Giacomo Bonanno, Bernard Walliser, Didier Dubois, Hans Rott, James Delgrande, and Jérôme Lang. 05321 – Panel on belief change. In Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics. Dagstuhl Seminar Proceedings, Volume 5321, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{levi_et_al:DagSemProc.05321.1,
  author =	{Levi, Isaac and Bonanno, Giacomo and Walliser, Bernard and Dubois, Didier and Rott, Hans and Delgrande, James and Lang, J\'{e}r\^{o}me},
  title =	{{05321 – Panel on belief change}},
  booktitle =	{Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5321},
  editor =	{James Delgrande and Jerome Lang and Hans Rott and Jean-Marc Tallon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05321.1},
  URN =		{urn:nbn:de:0030-drops-3580},
  doi =		{10.4230/DagSemProc.05321.1},
  annote =	{Keywords: Belief revision, iterated belief revision, update, merging, dynamic logic, possibility theory, conditionals, social choice, distance, complexity}
}
Document
05321 Executive Summary – Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics

Authors: James Delgrande, Jérôme Lang, Hans Rott, and Jean-Marc Tallon

Published in: Dagstuhl Seminar Proceedings, Volume 5321, Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics (2005)


Abstract
The area of belief change studies how a rational agent may maintain its beliefs when obtaining or perceiving new information about the environment. This new information could include properties of the actual world, occurrences of events, and, in the case of multiple agents, actions performed by other agents, as well as the beliefs and preferences of other agents. Not surprisingly, this area has been of interest to researchers in different communities. The initial research in belief change came from the philosophical community, wherein belief change was studied generally from a normative point of view (that is, providing axiomatic foundations about how rational agents should behave with respect to the information flux). Subsequently, computer scientists, especially in the artificial intelligence (AI) and the database (DB) communities, have been building on these results. Belief change, as studied by computer scientists, not only pays attention to behavioural properties characterising evolving databases or knowledge bases, but must also address computational issues such as how to represent beliefs states in a concise way and how to efficiently compute the revision of a belief state. More recently, the economics and game theory community, in particular the emerging field of cognitive economics, has become active in belief change research, adopting a normative point of view, like philosophers, but paying more attention to the ''cognitive plausibility'' or ''fitness'' of the belief change operators. The goal of the seminar was to bring together researchers from these areas, allowing for the identification and addressing of problems of common interest in this area, as well as providing a means to explore ways in which one area may contribute to another.

Cite as

James Delgrande, Jérôme Lang, Hans Rott, and Jean-Marc Tallon. 05321 Executive Summary – Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics. In Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics. Dagstuhl Seminar Proceedings, Volume 5321, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{delgrande_et_al:DagSemProc.05321.3,
  author =	{Delgrande, James and Lang, J\'{e}r\^{o}me and Rott, Hans and Tallon, Jean-Marc},
  title =	{{05321 Executive Summary – Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics}},
  booktitle =	{Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5321},
  editor =	{James Delgrande and Jerome Lang and Hans Rott and Jean-Marc Tallon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05321.3},
  URN =		{urn:nbn:de:0030-drops-3577},
  doi =		{10.4230/DagSemProc.05321.3},
  annote =	{Keywords: Belief revision, iterated belief revision, update, merging, dynamic logic, possibility theory, conditionals, social choice, distance, complexity}
}
Document
Actions and Belief Revision : A Computational Approach

Authors: Yi Jin and Michael Thielscher

Published in: Dagstuhl Seminar Proceedings, Volume 5321, Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics (2005)


Abstract
The classic AGM theory studies mathematically idealized models of belief revision in two aspects: the properties (i.e., the AGM postulates) a rational revision operator should satisfy; and how to mathematically construct concrete revision operators. In scenarios where new information arrives in sequence, rational revision operators should also respect postulates for iterated revision (e.g., the DP postulates). When applications are concerned, the idealization of the AGM theory has to be lifted, in particular, beliefs of an agent should be represented by a finite belief base. In this talk, we present a computational base revision operator, which satisfies the AGM postulates and some nice postulates for iterated revision. We will also give a formal assessment of the base revision operator in terms of its computational complexity and degree of syntax irrelevance.

Cite as

Yi Jin and Michael Thielscher. Actions and Belief Revision : A Computational Approach. In Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics. Dagstuhl Seminar Proceedings, Volume 5321, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{jin_et_al:DagSemProc.05321.5,
  author =	{Jin, Yi and Thielscher, Michael},
  title =	{{Actions and Belief Revision : A Computational Approach}},
  booktitle =	{Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics},
  pages =	{1--25},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5321},
  editor =	{James Delgrande and Jerome Lang and Hans Rott and Jean-Marc Tallon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05321.5},
  URN =		{urn:nbn:de:0030-drops-3599},
  doi =		{10.4230/DagSemProc.05321.5},
  annote =	{Keywords: Iterated Belief Revision, Belief Base Revision, Computational Complexity}
}
Document
A simple modal logic for belief revision

Authors: Giacomo Bonanno

Published in: Dagstuhl Seminar Proceedings, Volume 5321, Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics (2005)


Abstract
I propose a modal logic for belief revision based on three operators representing initial beliefs, information and revised beliefs. Three axioms are put forward that express three simple principles: (1) if the agent is informed of something that he considered possible initially, then he incorporates the information in his revised beliefs, (2) if the information received is not surprising then all previous beliefs are maintained (although new beliefs may be added) and (3) any new belief must be deducible from the initial beliefs and the information received. I show that these three axioms characterize the qualitative content of Bayes' rule. I also construct a logic which is sound and complete with respect to the class of frames that satisfy the qualitative Bayes rule. Some interesting theorems are derived for extensions of this logic, for example that the agent initially believes that he later will believe A if and only if he already believes A to start with. I then extend the framework to deal with iterated belief revision and the iterated version of Bayes rule.

Cite as

Giacomo Bonanno. A simple modal logic for belief revision. In Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics. Dagstuhl Seminar Proceedings, Volume 5321, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{bonanno:DagSemProc.05321.4,
  author =	{Bonanno, Giacomo},
  title =	{{A simple modal logic for belief revision}},
  booktitle =	{Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5321},
  editor =	{James Delgrande and Jerome Lang and Hans Rott and Jean-Marc Tallon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05321.4},
  URN =		{urn:nbn:de:0030-drops-3302},
  doi =		{10.4230/DagSemProc.05321.4},
  annote =	{Keywords: Belief revision, information, Bayes' rule, iterated revision}
}
Document
Belief change and dynamic logic

Authors: Hans van Ditmarsch

Published in: Dagstuhl Seminar Proceedings, Volume 5321, Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics (2005)


Abstract
In this paper we compare standard ways to perform belief change with attempts to model such change with dynamic modal operators. We address both belief expansion, belief contraction, belief revision, and update. Public announcement logic is an implementation of a belief expansion operator in a dynamic epistemic setting. The postulates of success and minimal change cannot be satisfied in their original AGM formulation. Dynamic doxastic logic provides various implementations of a belief revision operator in a dynamic epistemic setting. We provide an example of the application of such a dynamic doxastic semantics, which can also be seen as a realization of a proposal by Spohn. The purpose of this paper is to provide an overview of different approaches to dynamic logics for belief change, including some of our own contributions to the area, in a way that is accessible to an interdisciplinary audience. It does not contain new technical results not published elsewhere. However, the comparison of different approaches provides, we hope, new insights not seen before. A final version of this paper may include new technical results.

Cite as

Hans van Ditmarsch. Belief change and dynamic logic. In Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics. Dagstuhl Seminar Proceedings, Volume 5321, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{vanditmarsch:DagSemProc.05321.6,
  author =	{van Ditmarsch, Hans},
  title =	{{Belief change and dynamic logic}},
  booktitle =	{Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5321},
  editor =	{James Delgrande and Jerome Lang and Hans Rott and Jean-Marc Tallon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05321.6},
  URN =		{urn:nbn:de:0030-drops-3376},
  doi =		{10.4230/DagSemProc.05321.6},
  annote =	{Keywords: Belief revision, dynamic epistemic logic}
}
Document
Belief merging, judgment aggregation and some links with social choice theory

Authors: Daniel Eckert and Gabriella Pigozzi

Published in: Dagstuhl Seminar Proceedings, Volume 5321, Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics (2005)


Abstract
In this paper we explore the relation between three areas: judgment aggregation, belief merging and social choice theory. Judgment aggregation studies how to aggregate individual judgments on logically interconnected propositions into a collective decision on the same propositions. When majority voting is applied to some propositions (the premises) it may however give a different outcome than majority voting applied to another set of propositions (the conclusion). Starting from this so-called doctrinal paradox, the paper surveys the literature on judgment aggregation (and its relation to preference aggregation), and shows that the application of a well known belief merging operator can dissolve the paradox. Finally, the use of distances is shown to establish a link between belief merging and preference aggregation in social choice theory.

Cite as

Daniel Eckert and Gabriella Pigozzi. Belief merging, judgment aggregation and some links with social choice theory. In Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics. Dagstuhl Seminar Proceedings, Volume 5321, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{eckert_et_al:DagSemProc.05321.8,
  author =	{Eckert, Daniel and Pigozzi, Gabriella},
  title =	{{Belief merging, judgment aggregation and some links with social choice theory}},
  booktitle =	{Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5321},
  editor =	{James Delgrande and Jerome Lang and Hans Rott and Jean-Marc Tallon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05321.8},
  URN =		{urn:nbn:de:0030-drops-3330},
  doi =		{10.4230/DagSemProc.05321.8},
  annote =	{Keywords: Judgment aggregation, belief merging, preference aggregation, social choice theory}
}
  • Refine by Author
  • 9 Lang, Jérôme
  • 5 Delgrande, James
  • 5 Rott, Hans
  • 4 Bonanno, Giacomo
  • 2 Dubois, Didier
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 7 Belief revision
  • 4 dynamic logic
  • 4 iterated belief revision
  • 4 merging
  • 4 possibility theory
  • Show More...

  • Refine by Type
  • 20 document

  • Refine by Publication Year
  • 12 2005
  • 5 2007
  • 1 2006
  • 1 2016
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail