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.

Publications

10 25 50
publication icon
E. Marchioni (2014) Lukasiewicz Games

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

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

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

publication icon
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