Combining Qualitative and Quantitative Reasoning for Logic-based Games
Lead Research Organisation:
UNIVERSITY OF OXFORD
Department Name: Computer Science
Abstract
The use of game theoretic techniques in computer science is becoming ever more prevalent. One reason for this is that in many of the systems we want to build, participants cannot be assumed to be benevolent: instead, they must be assumed to be rational agents, acting in pursuit of their own personal goals. For such systems, game theory provides a natural analytical framework. In our work, we are interested in the automated analysis of such systems using techniques for model checking, which over the past two decades have proved to be enormously influential. In model checking, the idea is to express desirable system properties as logical formula, and then to check whether these properties actually hold of the given system. A key problem if we want to extend existing verification techniques to game theoretic settings is that the formalisms used in model checking do not allow us to directly represent the preferences or utilities of players (i.e., their goals). This project is directed at this problem. The basic idea is that we can use a formalism known as Lukasiewicz logic to express the "utility function" for players, which represent their preferences. Lukasiewicz logic is a non-classical, multiple-valued logic which has the attractive property that Lukasiewicz formulae can represent a very rich class of utility functions -- much richer than is possible using classical logic. The project will lay the theoretical groundwork for this new and exciting class of logically-specified games, and has the potential to greatly enrich the class of systems for which logic-based automated analysis techniques can be applied.
Planned Impact
Although the direct applications of our research are downstream, we
can nevertheless identify several possible beneficiaries, as follows.
* First, our results will benefit that part of the computing R&D
community who must design and build systems and protocols relating
to systems in which participants act in their self-interest. This
is, we believe a large community. For example, the designers of
online trading software must take economic considerations into
account when they design their software; the designers of social
media software and group decision-making software also need to take
into account the preferences and self-interested behaviour of
participants.
* Second, our results will benefit the growing international
community interested in multi-agent systems generally, and in the
automated analysis and verification of such systems in particular,
who will gain a better understanding of the logical analysis of game
theoretic systems.
* Third, we expect our results to benefit the wider logic
community: our work will further extend the range of frameworks that
are amenable to logical analysis, and provide results that others
can build on, and algorithms that can be refined and extended.
As noted above, our project will deliver new formal models,
formalisms, and algorithms directed at the automated analysis of
distributed systems containing participants acting in pursuit of
personal goals. The concrete benefits we expect of our project include:
* understanding of the applicability of logic in general, and
Lukasiewicz logic in particular, for the specification of game theoretic
settings and protocols;
* understanding of the kinds of domains for which logic-based game
theoretic analysis is feasible and valuable;
* the capability to capture using logic complex game theoretic
scenarios, far beyond what is currently possible; and
* the capability to automatically analyse game theoretic scenarios
and protocols
using a logical (Lukasiewicz) specification.
can nevertheless identify several possible beneficiaries, as follows.
* First, our results will benefit that part of the computing R&D
community who must design and build systems and protocols relating
to systems in which participants act in their self-interest. This
is, we believe a large community. For example, the designers of
online trading software must take economic considerations into
account when they design their software; the designers of social
media software and group decision-making software also need to take
into account the preferences and self-interested behaviour of
participants.
* Second, our results will benefit the growing international
community interested in multi-agent systems generally, and in the
automated analysis and verification of such systems in particular,
who will gain a better understanding of the logical analysis of game
theoretic systems.
* Third, we expect our results to benefit the wider logic
community: our work will further extend the range of frameworks that
are amenable to logical analysis, and provide results that others
can build on, and algorithms that can be refined and extended.
As noted above, our project will deliver new formal models,
formalisms, and algorithms directed at the automated analysis of
distributed systems containing participants acting in pursuit of
personal goals. The concrete benefits we expect of our project include:
* understanding of the applicability of logic in general, and
Lukasiewicz logic in particular, for the specification of game theoretic
settings and protocols;
* understanding of the kinds of domains for which logic-based game
theoretic analysis is feasible and valuable;
* the capability to capture using logic complex game theoretic
scenarios, far beyond what is currently possible; and
* the capability to automatically analyse game theoretic scenarios
and protocols
using a logical (Lukasiewicz) specification.
Organisations
People |
ORCID iD |
Michael Wooldridge (Principal Investigator) |
Publications

E. Marchioni
(2014)
Lukasiewicz Games

Marchioni E
(2019)
Lukasiewicz logics for cooperative games
in Artificial Intelligence

Marchioni E
(2015)
Lukasiewicz Games A Logic-Based Approach to Quantitative Strategic Interactions
in ACM Transactions on Computational Logic

Marchioni E
(2016)
On Deductive Interpolation for the Weak Nilpotent Minimum logic
in Fuzzy Sets and Systems

Marchioni E.
(2014)
Lukasiewicz games
in 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014
Description | In this project, we have substantially extended our understanding of the theory and practice of logic-based games: such games are an important component of the contemporary multi-agent systems community. Our results include: - new theoretical models of logic-based games - both cooperative and non-cooperative games - new solution concepts for logic-based games, for example showing how the core can be formulated for logic-based cooperative games; - new complexity results for logic-based games, comprehensively characterising the complexity of computing non-cooperative solution concepts such as Nash equilibrium, and cooperative solution concepts such as the core; - preliminary algorithms for computing solution concepts in logic-based games; - a portfolio of case studies, showing how these games can be used capture scenarios of interest. Our flagship contribution is a new game model called "Lukasiewicz Resource Games": this is a new cooperative game model in which agents contribute resources to tasks; the performance of a task is a function of the resources contributed to to it; and the payoff received by an agent is a function of the performance of the tasks. We contribute the model, show how it can be formulated using Lukasiewicz logic, present solution concepts, characterise the complexity of solution concepts, and present algorithms for solution concepts. This work is under review ("with 'minor corrections' recommendation) for AI journal, under the name "Lukasiewicz Logics for Cooperative Games". |
Exploitation Route | More case studies. More detailed understanding of the games that can be described using Lukasiewicz logic. Extensions to settings similar to Alternating-time Temporal Logic. |
Sectors | Aerospace Defence and Marine Digital/Communication/Information Technologies (including Software) Financial Services and Management Consultancy |
Description | Specialist Advisor for House of Lords Inquiry on Large Language Models (Sept-23-Feb 24) |
Geographic Reach | National |
Policy Influence Type | Participation in a guidance/advisory committee |
Impact | The inquiry made a list of recommendations to HMG, some of which are being implemented. |
URL | https://publications.parliament.uk/pa/ld5804/ldselect/ldcomm/54/5404.htm |
Description | Cheltenham Literary Festival |
Form Of Engagement Activity | A talk or presentation |
Part Of Official Scheme? | No |
Geographic Reach | National |
Primary Audience | Public/other audiences |
Results and Impact | Talk on AI at Cheltenham Literature Festival, Oct 2023. |
Year(s) Of Engagement Activity | 2023 |
URL | https://issuu.com/cheltenhamfestivals/docs/the_times_and_the_sunday_times_cheltenham_literatu?gad_so... |
Description | Extensive Press Interviews |
Form Of Engagement Activity | A press release, press conference or response to a media enquiry/interview |
Part Of Official Scheme? | No |
Geographic Reach | International |
Primary Audience | Public/other audiences |
Results and Impact | I am regularly interviewed by the press on topics around AI and technology, including: Al Jazeera, Australian Broadcasting Corporation (ABC), BBC TV Arabic Service, BBC TV News, BBC TV Politics Today, BBC Click Online, BBC R4 PM, BBC R4 Today Programme, BBC R4 Start the Week, BBC R4 World Today, BBC R5 Live (various shows), BBC R5 Naked Scientist, BBC Radio London, BBC Radio Ulster, BBC Science Focus, BBC World News, Business Insider, Canada Broadcasting Corporation, Channel 4 News, Daily Mail, Economist, Financial Times, Forbes, Fox News, Global Counsel, The Guardian, The Information, ITN Tonight Programme, ITV News, Jack FM, Japan Broadcasting Corporation (NHK: Nippon Ho ¯so ¯ Kyo ¯kai), LBC, MIT Technology Review, National Geographic, National Review, New Scientist, New Statesman, The Observer, Oxford Mail, RTE TV (Raidió Teilifís Éireann), Sky News, The Spectator, The Telegraph, The Times, Times Radio, Wall Street Journal, Washington Post. |
Year(s) Of Engagement Activity | 2021,2022,2023 |
Description | How the Light Gets in Festival |
Form Of Engagement Activity | A talk or presentation |
Part Of Official Scheme? | No |
Geographic Reach | National |
Primary Audience | Public/other audiences |
Results and Impact | Talk on AI at How the Light Gets In Festival, Sept 2023. Key popular philosophy festival. |
Year(s) Of Engagement Activity | 2023 |
URL | https://howthelightgetsin.org/festivals/london/the-big-ideas/speakers/michael-wooldridge |
Description | Royal Institution Christmas Lectures |
Form Of Engagement Activity | A broadcast e.g. TV/radio/film/podcast (other than news/press) |
Part Of Official Scheme? | No |
Geographic Reach | International |
Primary Audience | Public/other audiences |
Results and Impact | I gave the 2023 Royal Institution Christmas Lectures, in the 198th year of the series. Three one hour lectures on "The Truth about AI" aimed primarily at children, filmed in front of a live audience of school children and broadcast by BBC TV over the christmas period. Estimated audience > 1 million to date, expected to grow. Lectures now available to stream internationally. |
Year(s) Of Engagement Activity | 2023 |
URL | https://www.rigb.org/christmas-lectures |
Description | The Life Scientific - 30 min BBC R4 programme on my life and work |
Form Of Engagement Activity | A press release, press conference or response to a media enquiry/interview |
Part Of Official Scheme? | No |
Geographic Reach | National |
Primary Audience | Public/other audiences |
Results and Impact | The Life Scientific - 30 min BBC R4 programme on my life and work, focussing on origins of field of multi-agent systems. |
Year(s) Of Engagement Activity | 2023 |
URL | https://www.bbc.co.uk/programmes/m001tgk9 |
Description | Turing Lecture/Royal Institution Discourses Lecture |
Form Of Engagement Activity | A talk or presentation |
Part Of Official Scheme? | No |
Geographic Reach | International |
Primary Audience | Public/other audiences |
Results and Impact | Lecture on generative AI filmed at Royal Institution in front of audience of ~ 300 and now available on YouTube. Total viewing figures at time of writing in excess of 700,000. |
Year(s) Of Engagement Activity | 2023 |
URL | https://www.youtube.com/watch?v=b76gsOSkHB4 |