Multi-Agent Systems for Computational Economics and Finance Michael KampouridisPanagiotis KanellopoulosMaria Kyropoulou

2025-05-02 0 0 444.89KB 16 页 10玖币

侵权投诉

Multi-Agent Systems for

Computational Economics and Finance

Michael Kampouridis∗Panagiotis Kanellopoulos†Maria Kyropoulou‡

emistoklis Melissourgos§Alexandros A. Voudouris¶

School of Computer Science and Electronic Engineering

University of Essex

Abstract

In this article we survey the main research topics of our group at the University of Essex. Our

research interests lie at the intersection of theoretical computer science, articial intelligence, and

economic theory. In particular, we focus on the design and analysis of mechanisms for systems

involving multiple strategic agents, both from a theoretical and an applied perspective. We present

an overview of our group’s activities, as well as its members, and then discuss in detail past, present,

and future work in multi-agent systems.

1 e Group

e School of Computer Science and Electronic Engineering at the University of Essex (UoE) is the

home of many researchers actively working on the broad eld of Articial Intelligence. We are mem-

bers of the Centre for Computational Finance and Economic Agents (CCFEA) in UoE, and our research

spans various core areas of multi-agent systems (MAS), focusing primarily at the intersection of theo-

retical computer science, articial intelligence, nance and economics. Specically, our expertise is on

algorithmic game theory, computational social choice, machine learning and nancial engineering. We

have a strong publication track record that demonstrates our close working relationship, as well as our

national and international collaborations. Our relevant research is published in highly respected in-

ternational peer-reviewed journals and conferences, such as AAAI, IJCAI, AAMAS, EC, ICALP, STOC,

FOCS, Articial Intelligence Journal, Journal of Articial Intelligence Research, Games and Economic

Behavior, and more. We also participate as Program Commiee members in renowned international

conferences and have participated in the organisation of several international conferences and work-

shops, including the 15th International Symposium on Algorithmic Game eory (SAGT 2022) and

the 2022 IEEE Symposium on Computational Intelligence for Financial Engineering and Economics

(CIFEr).

We remark that our work is intertwined with industrial applications and we have been involved in

four Knowledge Transfer Partnerships funded by Innovate UK (total value exceeding £1M), as well as an

ESRC-funded project with Essex County Council. For example, in collaboration with a large healthcare

provider, we are studying more ecient ways to elicit preferences, match healthcare workers and

clients, and increase the number of shis that are covered. Our approach relies heavily on game theory,

mechanism design, and machine learning. In another case involving a leading law rm, we worked

∗Email: mkampo@essex.ac.uk

†Email: panagiotis.kanellopoulos@essex.ac.uk

‡Email: maria.kyropoulou@essex.ac.uk

§Email: themistoklis.melissourgos@essex.ac.uk

¶Email: alexandros.voudouris@essex.ac.uk

arXiv:2210.03540v1 [cs.GT] 7 Oct 2022

towards developing a pricing tool that predicts the cost of a requested piece of legal work and allocates

the most suitable lawyers to it, based on historical data. is is a fascinating and innovative research

direction linking once again machine learning and algorithmic game theory.

2 Core Areas of our Research

e study of multi-agent systems is a core area of Articial Intelligence and many dierent perspec-

tives and methodologies have been adopted, each contributing to the development of MAS. One key

area our group has focused on is the existence, computation and quality of equilibria in environments

where multiple intelligent agents act selshly aiming to optimize their personal agenda, which may

collide with the interests of others or the system designer’s objectives. Another class of problems

we have extensively studied falls within the area of computational social choice, where agents express

preferences over dierent outcomes and our goal is to make social decisions based on these prefer-

ences that satisfy desired properties, such as utilitarian eciency or fairness criteria. We have studied

game-theoretic and social choice seings in which the main objective is to provide the agents with the

necessary incentives to avoid strategic manipulations, an area known as mechanism design. Finally,

we have considered nancial applications both through the aforementioned frameworks as well as by

using Machine Learning. In the rest of this section we provide background on these topics, discuss our

contribution, and identify interesting directions for future research.

2.1 Existence, Computation, and ality of Equilibria

Strategic games emerge naturally in environments where rational and intelligent individuals partici-

pate. Games model situations where selsh entities aim to maximize their own payo without caring

about that of their competitors. Informally, a game consists of a set of agents, each having a set of

available actions. In such an MAS, a combination of the agents’ actions yields an outcome which is ex-

perienced by all agents; each agent has her own preference over the outcomes, oen expressed through

a valuation or utility function. A probability distribution over an agent’s actions is called a strategy,

while a combination of agent strategies in which no agent would get a beer (in expectation) outcome

by unilaterally deviating to a dierent strategy is called a Nash equilibrium [Nas51]. Such notions of

stability oen serve as predictions on the outcomes of the corresponding game, thus, have received a

great deal of aention from the community. Various other equilibrium notions have also been consid-

ered as solution concepts, depending on the game at hand.

ere are three main questions regarding equilibria in games: Is an equilibrium guaranteed to exist?,

how fast can we compute one (if it exists)?, and how good for the society are the equilibria reached compared

to a centrally enforced optimal state? e last question gives rise to the notions of price of anarchy

and price of stability that quantify how bad the worst (best, respectively) Nash equilibrium is when

compared to the state maximizing the aggregate welfare of the society (optimal social welfare). We

have studied these questions in many dierent and challenging types of games. In what follows, we

present some of our relevant work grouped by similarity of model.

Auctions. In a typical auction environment, there is a set of items for sale and a set of potential

buyers. e possible actions of the buyers consist of the potential bids they can place in the auction,

and the game is dened by a specic resolution method of the bids, which, given the bids, determines

the outcome. Consider, for example, the generalized second price (GSP) auction, which is the primary

auction used for monetizing the use of the Internet. In a quite inuential paper (see [CKK+15]) we

studied the space of equilibria under GSP and quantied the eciency loss that can arise under a

wide range of sources of uncertainty. We also focused on the revenue of the GSP auction, and studied

a Bayesian seing wherein the valuations of advertisers are drawn independently from a common

regular probability distribution [CKKK14].

In a combinatorial auction, an outcome consists of an allocation of the items to the agents and a

price for each agent’s bundle. One of the most prominent equilibrium notions for auctions, where we

require per-item prices, is that of a Walrasian equilibrium, which occurs when no agent prefers any

other bundle for the given set of prices and the market clears. Walrasian equilibria have the additional

desirable property of maximizing the social welfare, however they are not known to exist even for

very restricted valuations, as we showed in [DMS21]. In the same paper, we presented some special

cases for which existence of an equilibrium is guaranteed and provided polynomial time algorithms to

compute it.

Furthermore, we have analyzed the eciency of auctions in seings where the bidders have bud-

get constraints that limit the amount of payments they can aord. More specically, we have con-

sidered auctions for the allocation of divisible resources with bidders that have concave valuation

functions for fractions of the resources [CV21], position auctions (including the GSP auction men-

tioned above) [Vou19], and simultaneous combinatorial auctions with payment rules that are convex

combinations of the bids [Vou20].

We have also studied a series of questions related to the existence, eciency and computational

complexity of equilibria in two-stage games modelling seings where multiple vendors compete with

each other by oering similar products to unit-demand buyers who in turn have dierent preferences

over the vendors [CCK+17].

Congestion games. In a congestion game there is a set of resources and each agent can use a subset

of them, possibly under some restrictions. Each resource incurs a cost that is a function of the number

of agents that use it. Congestion games have been studied extensively due to the fact that they capture

many real-life applications and since they admit pure Nash equilibria.

In [CFK+11] we completely characterized the impact of selshness and greediness in singleton

congestion games, where each strategy consists of a single resource. In particular, we presented tight

bounds on the price of anarchy, as well as on the competitiveness of the greedy algorithm for the online

seing, when the objective is to minimize the total cost of all agents, as well as a tight upper bound

on the price of stability of congestion games with linear cost functions. We have also introduced a

seing where agents are partially altruistic and partially selsh and we have determined the impact

of this behavior on the overall system performance [CKK+10b]. In an aempt to mitigate the impact

of selsh behavior, we studied the question of how much the performance can be improved if agents

are forced to pay taxes for using resources, for the seing of atomic congestion games with linear cost

functions [CKK10a, CKK08].

A well-known special case of congestion games is that of task scheduling. In [GKK19] we consid-

ered the problem of scheduling tasks on strategic unrelated machines when no payments are allowed,

under the objective of minimizing the makespan. We adopted the monitoring paradigm where a ma-

chine is bound by her declarations and provided a (non-truthful) randomized algorithm whose pure

price of anarchy is considerably beer than the approximation ratio that can be achieved by any truth-

ful mechanism.

Scheduling tasks to machines is also the focus of [CKKP08]. Each task has a particular latency

requirement at each machine and may choose either to be assigned to some machine in order to get

serviced provided that her latency requirement is met, or not to participate in the assignment at all.

From a global perspective, one would aim to maximize the number of tasks that participate in the

assignment. However, tasks may behave selshly aiming to get serviced by some machine where her

latency requirement is met with no regard to overall system performance. We modelled this selsh

behavior as a strategic game, showed how to compute pure Nash equilibria eciently, and assessed

the impact of selshness on system performance.

Games on graphs. Segregation has been the subject of multidisciplinary research for more than

half a century, with most work focusing on omas Schelling’s model [Sch69, Sch71] involving two

dierent types of agents. Each agent occupies a node on a graph and is happy if a least some fraction

of her neighbors are of the same type; an unhappy agent either jumps to an unoccupied node or swaps

locations with another unhappy agent. In recent work, we considered Schelling’s model through the

lens of game theory, by assuming that agents choose their next location to maximize the fraction of

same-type neighbors. We have studied questions related to the existence, computation, and quality of

equilibria for many variants of Schelling games [EGI+19, KKV21a, KKV21b, AEGV20]. Besides this,

we have also studied the complexity of computing welfare-maximizing allocations [BSV21].

Regarding the classical stable matching problem, we considered its generalization that allows for

cardinal preferences (as opposed to ordinal) and fractional matchings (as opposed to integral) [CFKV21].

In this cardinal seing, stable fractional matchings can have much larger social welfare than stable in-

tegral ones. Our goal was to understand the computational complexity of nding an optimal (i.e.,

welfare-maximizing) stable fractional matching. We considered both exact and approximate stabil-

ity notions, and provided simple approximation algorithms with weak welfare guarantees; somewhat

surprisingly, achieving beer approximations is computationally hard.

Opinion formation is another important topic, where the objective is to study how the opinion of

an individual is aected by her social acquaintances. In this context, we have studied the existence

and quality of equilibria in games consisting of agents, each of whom has a personal belief that can be

represented by a real number, but may express a dierent opinion aiming to minimize the maximum

distance of her opinion from her belief and the most distant opinion expressed by any of her friends

[CKV22].

In graph-based hedonic games, a group of utility-maximizing agents have hedonic preferences over

the agents’ set, and wish to be partitioned into clusters so that they are grouped together with agents

they prefer. e agents correspond to nodes in a connected graph and their preferences are dened so

that shorter graph distance implies higher preference. In [KKPP21] we focused on fractional hedonic

games and social distance games and we proved improved bounds on the price of stability.

Security games. To decide the optimal strategy to commit to, the leader in a Stackelberg game can

use a variety of learning algorithms that operate by querying the best responses or the payos of the

follower. Consequently, the follower can potentially deceive the leader by responding as if her payos

are much dierent than what they actually are. In [BGH+21], we proved that it is always possible for

the follower to compute payos, and thus deceive the leader, that yield near-optimal utility, for various

scenarios about the learning interaction between leader and follower. In [EGO+21], we considered a

two-stage district-based voting manipulation scenario which leads to a Stackelberg game. First, an

aacker aempts to manipulate the election outcome in favor of a preferred candidate by changing

the vote counts in some districts. Aerwards, a defender has the ability to demand a recount in a subset

of the manipulated districts, thus restoring the vote counts therein to the original, true values.

An aacker-defender seing was also studied in [ADMS21] where multiple aackers try to inict

damage to nodes on a network, and a single defender tries to protect the nodes by probabilistically

patrolling induced connected subgraphs of the network. In that work we showed a general LP-based

algorithm for computing Nash equilibria and then focused on special cases of graphs. First we char-

acterized equilibria, and analyzed some of their properties, like the defense ratio; that is, the ratio of

all aackers over the expected number of the ones caught by the defender in equilibrium. We also

computed the (parameterized) value of the price of defense, i.e., the worst defense ratio over all possible

networks.

Investigating a signicantly challenging aspect of cryptocurrency, in [KKKT16] we focused on the

strategic considerations of miners participating in bitcoin’s protocol. We formulated and studied the

stochastic game underlying such strategic considerations and showed that, when each miner’s com-

putational power is relatively small, their best response matches the expected behavior of the bitcoin

designer. However, when a miner’s computational power is large, she deviates from the expected be-

havior, and other Nash equilibria arise. is work has served as a starting point for a long line of works

on blockchain protocols.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Multi-AgentSystemsforComputationalEconomicsandFinanceMichaelKampouridis*PanagiotisKanellopoulosMariaKyropoulouemistoklisMelissourgos§AlexandrosA.Voudouris¶SchoolofComputerScienceandElectronicEngineeringUniversityofEssexAbstractInthisarticlewesurveythemainresearchtopicsofourgroupattheUniversityofE...

展开>> 收起<<

Multi-Agent Systems for Computational Economics and Finance Michael KampouridisPanagiotis KanellopoulosMaria Kyropoulou.pdf

共16页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Multi-Agent Systems for Computational Economics and Finance Michael KampouridisPanagiotis KanellopoulosMaria Kyropoulou

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: