Imperial College London

Professor Nick Jennings

Central FacultyOffice of the Provost

Vice-Provost (Research and Enterprise)
 
 
 
//

Contact

 

+44 (0)20 7594 8458n.jennings Website CV

 
 
//

Assistant

 

Ms Emma Neave +44 (0)20 7594 8458

 
//

Location

 

4.10Faculty BuildingSouth Kensington Campus

//

Summary

 

Publications

Publication Type
Year
to

679 results found

Pruna RT, Polukarov M, Jennings NR, 2019, Loss aversion in an agent-based asset pricing model, Quantitative Finance, ISSN: 1469-7688

A well-defined agent-based asset pricing model able to match the widely observed properties of financial time series is valuable for testing the implications of various biases associated with investors' behaviour. Extending one of the most successful models in capturing traders behaviour, we present a new behavioural agent-based asset pricing model. Specifically, we introduce a well-known behavioural bias in the model, loss aversion, and evaluate its implications. First, measuring how close the simulated time series are to its empirical counterparts, we show that the model with loss aversion better matches and explains the properties of real-world financial data, compared with the base model without the behavioural bias. Secondly, we assess the impact of different levels of loss aversion not only on the agents' switching mechanisms, but also on the properties of the time series generated by the model. We demonstrate how for different levels of the loss aversion parameter, the biased agents tend to be driven out of the market at different points in time. Since even the simplest strategies have been shown to survive the competition in an agent-based setting, we can link our findings with the behavioural finance literature, which states that investors' systematic biases lead to unexpected market behaviour, instabilities and systematic errors. Finally, we provide an in-depth analysis of the simulated time series and show the resulting dynamics replicate a rich set of the stylized facts including: absence of autocorrelation, heavy tails, volatility clustering and conditional heavy tails of returns, long memory of absolute returns, as well as volume–volatility relations, gain–loss asymmetry, power-law behaviour and long memory of volume.

Journal article

Wu F, Zilberstein S, Jennings NR, 2019, Stochastic multi-agent planning with partial state models

© 2019 Association for Computing Machinery. People who observe a multi-agent team can often provide valuable information to the agents based on their superior cognitive abilities to interpret sequences of observations and assess the overall situation. The knowledge they possess is often difficult to be fully represent using a formal model such as DEC-POMDP. To deal with this, we propose an extension of the DEC-POMDP that allows states to be partially specified and benefit from expert knowledge, while preserving the partial observability and decentralized operation of the agents. In particular, we present an algorithm for computing policies based on history samples that include human labeled data in the form of reward reshaping. We also consider ways to minimize the burden on human experts during the labeling phase. The results offer the first approach to incorporating human knowledge in such complex multi-agent settings. We demonstrate the benefits of our approach using a disaster recovery scenario, comparing it to several baseline approaches.

Conference paper

Manino E, Long T-T, Jennings NR, 2019, On the efficiency of data collection for multiple Naive Bayes classifiers, ARTIFICIAL INTELLIGENCE, Vol: 275, Pages: 356-378, ISSN: 0004-3702

Journal article

Bi F, Stein S, Gerding E, Jennings N, La Porta Tet al., 2019, A truthful online mechanism for resource allocation in fog computing, Pacific Rim International Conference on Artificial Intelligence (PRICAI), Publisher: Springer International Publishing, Pages: 363-376, ISSN: 0302-9743

Fog computing is a promising Internet of Things (IoT) paradigm in which data is processed near its source. Here, efficient resource allocation mechanisms are needed to assign limited fog resources to competing IoT tasks. To this end, we consider two challenges: (1) near-optimal resource allocation in a fog computing system; (2) incentivising self-interested fog users to report their tasks truthfully. To address these challenges, we develop a truthful online resource allocation mechanism called flexible online greedy. The key idea is that the mechanism only commits a certain amount of computational resources to a task when it arrives. However, when and where to allocate resources stays flexible until the completion of the task. We compare our mechanism to four benchmarks and show that it outperforms all of them in terms of social welfare by up to 10% and achieves a social welfare of about 90% of the offline optimal upper bound.

Conference paper

Serafino P, Ventre C, Tran-Thanh L, Zhang J, An B, Jennings Net al., 2019, Social cost guarantees in smart route guidance, 16th Pacific Rim International Conference on Artificial Intelligence, Cuvu, Yanuca Island, Fiji, August 26–30, 2019, Proceedings, Part II, Publisher: Springer International Publishing, Pages: 482-495, ISSN: 0302-9743

We model and study the problem of assigning traffic in an urban road network infrastructure. In our model, each driver submits their intended destination and is assigned a route to follow that minimizes the social cost (i.e., travel distance of all the drivers). We assume drivers are strategic and try to manipulate the system (i.e., misreport their intended destination and/or deviate from the assigned route) if they can reduce their travel distance by doing so. Such strategic behavior is highly undesirable as it can lead to an overall suboptimal traffic assignment and cause congestion. To alleviate this problem, we develop moneyless mechanisms that are resilient to manipulation by the agents and offer provable approximation guarantees on the social cost obtained by the solution. We then empirically test the mechanisms studied in the paper, showing that they can be effectively used in practice in order to compute manipulation resistant traffic allocations.

Conference paper

Truong NV-Q, Stein S, Tran-Thanh L, Jennings NRet al., 2019, What prize is right? How to learn the optimal structure for crowdsourcing contests, Pacific Rim International Conference on Artificial Intelligence (PRICAI), Publisher: Springer International Publishing, Pages: 85-97, ISSN: 0302-9743

In crowdsourcing, one effective method for encouraging par-ticipants to perform tasks is to run contests where participants compete against each other for rewards. However, there are numerous ways to implement such contests in specific projects. They could vary in their structure (e.g., performance evaluation and the number of prizes) and parameters (e.g., the maximum number of participants and the amount of prize money). Additionally, with a given budget and a time limit, choosing incentives (i.e., contest structures with specific parameter values) that maximise the overall utility is not trivial, as their respective effectiveness in a specific project is usually unknown a priori. Thus, in this paper, we propose a novel algorithm, BOIS (Bayesian-optimisation-based incentive selection), to learn the optimal structure and tune its parameters effectively. In detail, the learning and tuning problems are solved simultaneously by using online learning in combination with Bayesian optimisation. The results of our extensive simulations show that the performance of our algorithm is up to 85% of the optimal and up to 63% better than state-of-the-art benchmarks.

Conference paper

Ghafur S, Grass E, Jennings N, Darzi Aet al., 2019, The challenges of cybersecurity in health care: the UK National Health Service as a case study, The Lancet Digital Health, Vol: 1, Pages: e10-e12, ISSN: 2589-7500

Journal article

Rahwan I, Cebrian M, Obradovich N, Bongard J, Bonnefon J-F, Breazeal C, Crandall JW, Christakis NA, Couzin ID, Jackson MO, Jennings NR, Kamar E, Kloumann IM, Larochelle H, Lazer D, McElreath R, Mislove A, Parkes DC, Pentland AS, Roberts ME, Shariff A, Tenenbaum JB, Wellman Met al., 2019, Machine behaviour, Nature, Vol: 568, Pages: 477-486, ISSN: 0028-0836

Machines powered by artificial intelligence increasingly mediate our social, cultural, economic and political interactions. Understanding the behaviour of artificial intelligence systems is essential to our ability to control their actions, reap their benefits and minimize their harms. Here we argue that this necessitates a broad scientific research agenda to study machine behaviour that incorporates and expands upon the discipline of computer science and includes insights from across the sciences. We first outline a set of questions that are fundamental to this emerging field and then explore the technical, legal and institutional constraints on the study of machine behaviour.

Journal article

Bi F, Stein S, Gerding E, Jennings N, La Porta Tet al., 2019, Truthful Online Mechanism for Allocating Fog Computing Resources, 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), Publisher: ASSOC COMPUTING MACHINERY, Pages: 1829-1831

Conference paper

Jennings N, 2018, Human-Artificial Intelligence Partnerships, 6th International Conference on Human-Agent Interaction (HAI), Publisher: ASSOC COMPUTING MACHINERY, Pages: 2-2

Conference paper

Jennings N, Zhang Y, Guo Q, An B, Tran-Thanh Let al., 2019, Optimal Interdiction of Urban Criminals with the Aid of Real-Time Information, 33rd AAAI Conference on Artificial Intelligence, Publisher: AAAI

Conference paper

Khan MM, Long T-T, Ramchurn SD, Jennings NRet al., 2018, Speeding up GDL-based message passing algorithms for large-scale DCOPs, Computer Journal, Vol: 61, Pages: 1639-1666, ISSN: 0010-4620

This paper develops a new approach to speed up Generalized Distributive Law (GDL) based message passing algorithms that are used to solve large-scale Distributed Constraint Optimization Problems (DCOPs) in multi-agent systems. In particular, we significantly reduce computation and communication costs in terms of convergence time for algorithms such as Max-Sum, Bounded Max-Sum, Fast Max-Sum, Bounded Fast Max-Sum, BnB Max-Sum, BnB Fast Max-Sum and Generalized Fast Belief Propagation. This is important since it is often observed that the outcome obtained from such algorithms becomes outdated or unusable if the optimization process takes too much time. Specifically, the issue of taking too long to complete the internal operation of a DCOP algorithm is even more severe and commonplace in a system where the algorithm has to deal with a large number of agents, tasks and resources. This, in turn, limits the practical scalability of such algorithms. In other words, an optimization algorithm can be used in larger systems if the completion time can be reduced. However, it is challenging to maintain the solution quality while minimizing the completion time. Considering this trade-off, we propose a generic message passing protocol for GDL-based algorithms that combines clustering with domain pruning, as well as the use of a regression method to determine the appropriate number of clusters for a given scenario. We empirically evaluate the performance of our method in a number of settings and find that it brings down the completion time by around 37–85% (1.6–6.5 times faster) for 100–900 nodes, and by around 47–91% (1.9–11 times faster) for 3000–10 000 nodes compared to the current state-of-the-art.

Journal article

Robu V, Vinyals M, Rogers A, Jennings Net al., 2018, Efficient buyer groups with prediction-of-use electricity tariffs, IEEE Transactions on Smart Grid, Vol: 9, Pages: 4468-4479, ISSN: 1949-3061

Current electricity tariffs do not reflect the real costs that a customer incurs to a supplier, as units are charged at the same rate, regardless of the consumption pattern. In this paper, we propose a prediction-of-use (POU) tariff that better reflects the predictability cost of a customer. Our tariff asks customers to pre-commit to a baseline consumption, and charges them based on both their actual consumption and the deviation from the anticipated baseline. First, we study, from a cooperative game theory perspective, the cost game induced by a single such tariff, and show customers would have an incentive to minimize their risk, by joining together when buying electricity as a grand coalition. Second, we study the efficient (i.e., cost-minimizing) structure of buying groups for the more realistic setting when multiple , competing POU tariffs are available. We propose a polynomial time algorithm to compute the efficient buyer groups, and validate our approach experimentally, using a large-scale data set of domestic consumers in the U.K.

Journal article

Manino E, Tran-Thanh L, Jennings NR, 2018, On the efficiency of data collection for crowdsourced classification, Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18), Publisher: Lawrence Erlbaum Associates, Inc., Pages: 1568-1575, ISSN: 1045-0823

The quality of crowdsourced data is often highly variable. For this reason, it is common to collect redundant data and use statistical methods to aggregate it. Empirical studies show that the policies we use to collect such data have a strong impact on the accuracy of the system. However, there is little theoretical understanding of this phenomenon. In this paper we provide the first theoretical explanation of the accuracy gap between the most popular collection policies: the non-adaptive uniform allocation, and the adaptive uncertainty sampling and information gain maximisation. To do so, we propose a novel representation of the collection process in terms of random walks. Then, we use this tool to derive lower and upper bounds on the accuracy of the policies. With these bounds, we are able to quantify the advantage that the two adaptive policies have over the non-adaptive one for the first time.

Conference paper

Mosaddek Khan MD, Tran-Thanh L, Jennings NR, 2018, A generic domain pruning technique for GDL-based DCOP algorithms in cooperative multi-agent systems, International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018, Publisher: International Foundation for Autonomous Agents and MultiAgent Systems (IFAAMAS)., Pages: 1595-1603, ISSN: 2523-5699

Generalized Distributive Law (GDL) based message passing algorithms, such as Max-Sum and Bounded Max-Sum, are often used to solve distributed constraint optimization problems in cooperative multi-agent systems (MAS). However, scalability becomes a challenge when these algorithms have to deal with constraint functions with high arity or variables with a large domain size. In either case, the ensuing exponential growth of search space can make such algorithms computationally infeasible in practice. To address this issue, we develop a generic domain pruning technique that enables these algorithms to be effectively applied to larger and more complex problems. We theoretically prove that the pruned search space obtained by our approach does not affect the outcome of the algorithms. Moreover, our empirical evaluation illustrates a significant reduction of the search space, ranging from 33% to 81%, without affecting the solution quality of the algorithms, compared to the state-of-the-art.

Conference paper

Mosaddek Khan MD, Yeoh W, Tran-Thanh L, Jennings NRet al., 2018, A near-optimal node-to-agent mapping heuristic for GDL-based DCOP algorithms in multi-agent systems, International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018, Publisher: International Foundation for Autonomous Agents and MultiAgent Systems (IFAAMAS), Pages: 1613-1621, ISSN: 2523-5699

Distributed Constraint Optimization Problems (DCOPs) can be used to model a number of multi-agent coordination problems. The conventional DCOP model assumes that the subproblem that each agent is responsible for (i.e. the mapping of nodes in the constraint graph to agents) is part of the model description. While this assumption is often reasonable, there are many applications where there is some flexibility in making this assignment. In this paper, we focus on this gap and make the following contributions: (1) We formulate this problem as an optimization problem, where the goal is to find an assignment that minimizes the completion time of the DCOP algorithm (e.g. Action-GDL or Max-Sum) that operates on this mapping. (2) We propose a novel heuristic, called MNA, that can be executed in a centralized or decentralized manner. (3) Our empirical evaluation illustrates a substantial reduction in completion time, ranging from 16% to 40%, without affecting the solution quality of the algorithms, compared to the current state of the art. In addition, we observe empirically that the completion time obtained from our approach is near-optimal; it never exceeds more than 10% of what can be achieved from the optimal node-to-agent mapping.

Conference paper

Truong NVQ, Tran-Thanh L, Stein S, Jennings NRet al., 2018, Adaptive incentive selection for crowdsourcing contests, International Foundation for Autonomous Agents and MultiAgent Systems (IFAAMAS), Publisher: International Foundation for Autonomous Agents and MultiAgent Systems (IFAAMAS), Pages: 2100-2102, ISSN: 2523-5699

Conference paper

Zhao D, Lit B, Xu J, Haot D, Jennings NRet al., 2018, Selling multiple items via social networks, International Joint Conference on Autonomous Agents and Multiagent Systems, Publisher: International Foundation for Autonomous Agents and MultiAgent Systems (IFAAMAS), Pages: 68-76, ISSN: 2523-5699

We consider a market where a seller sells multiple units of a comm odity in a social network. Each node/buyer In the social network can only directly communicate with her neighbours. i.e. the seller can only sell the commodity to her neighbours if she could not find a way to inform other buyers. In this paper, we design a novel prom otion mechanism that incentivizes all buyers, who are aware of the sale, to invite all their neighbours to join the sale, even though there is no guarantee that their efforts will be paid. While tradit ional sale promotions such as sponsored search auctions cannot guarantee a positive return for the advertiser (the seUer), our mecha nism guarantees that the seller's revenue is better than not using the advertising. More importantly, the seller does not need to pay if the advertising is not beneficial to her.

Conference paper

Luo Y, Jennings NR, 2018, A differential privacy mechanism with network effects for crowdsourcing systems, International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018, Publisher: International Foundation for Autonomous Agents and MultiAgent Systems (IFAAMAS), Pages: 1998-2000, ISSN: 2523-5699

In crowdsourcing systems, it is important for the crowdsource campaign initiator to incentivize users to share their data to produce results of the desired computational accuracy. This problem becomes especially challenging when users are concerned about the privacy of their data. To overcome this challenge, existing work often aims to provide users with differential privacy guarantees to incentivize privacy-sensitive users to share their data. However, this work neglects the network effect that a user enjoys greater privacy protection when he aligns his participation behaviour with that of other users. To explore the network effect and provide a suitable differential privacy guarantee, we design PINE (Privacy Incentivization with Network Effects). PLNE is a mechanism that maximizes the initiator's payoff while providing participating users with privacy protections.

Conference paper

Luo Y, Jennings NR, 2018, A Differential Privacy Mechanism with Network Effects for Crowdsourcing Systems Extended Abstract, 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), Publisher: ASSOC COMPUTING MACHINERY, Pages: 1998-2000

Conference paper

Stein S, Eshghi S, Maghsudi S, Tassiulas L, Bellamy RKE, Jennings NRet al., 2018, Influence maximisation beyond organisational boundaries, SmartWorld, Ubiquitous Intelligence & Computing, Advanced & Trusted Computed, Scalable Computing & Communications, Cloud & Big Data Computing, Internet of People and Smart City Innovation (SmartWorld/SCALCOM/UIC/ATC/CBDCom/IOP/SCI), Publisher: IEEE

We consider the problem of choosing influential members within a social network, in order to disseminate a message as widely as possible. While this so-called problem of influence maximisation has been widely studied, little work considers partially-observable networks, where only part of a network is visible to the decision maker. Yet, this is critical in many applications, where an organisation needs to distribute its message far beyond its boundaries and beyond its usual sphere of influence. In this paper, we show that existing algorithms are not sufficient to handle such scenarios. To address this, we propose a set of novel adaptive algorithms that perform well in partially observable settings, achieving an up to 18% improvement on the non-Adaptive state of the art.

Conference paper

Zenonos A, Stein S, Jennings NR, 2018, Coordinating measurements for environmental monitoring in uncertain participatory sensing settings, The Journal of Artificial Intelligence Research, Vol: 61, Pages: 433-474, ISSN: 1076-9757

Environmental monitoring allows authorities to understand the impact of potentially harmful phenomena, such as air pollution, excessive noise and radiation. Recently, there has been considerable interest in participatory sensing as a paradigm for such large-scale data collection because it is cost-effective and able to capture more fine-grained data than traditional approaches that use stationary sensors scattered in cities. In this approach, ordinary citizens (non-expert contributors) collect environmental data using low-cost mobile devices. However, these participants are generally self-interested actors that have their own goals and make local decisions about when and where to take measurements. This can lead to highly ineffcient outcomes, where observations are either taken redundantly or do not provide sufficient information about key areas of interest. To address these challenges, it is necessary to guide and to coordinate participants, so they take measurements when it is most informative. To this end, we develop a computationally-effcient coordination algorithm (adaptive Best-Match) that suggests to users when and where to take measurements. Our algorithm exploits probabilistic knowledge of human mobility patterns, but explicitly considers the uncertainty of these patterns and the potential unwillingness of people to take measurements when requested to do so. In particular, our algorithm uses a local search technique, clustering and random simulations to map participants to measurements that need to be taken in space and time. We empirically evaluate our algorithm on a real-world human mobility and air quality dataset and show that it outperforms the current state of the art by up to 24% in terms of utility gained.

Journal article

Jennings N, Verame J, Ramchurn SD, Fischer J, Crabtree A, Rodden T, Costanza Eet al., 2018, Learning from the veg box: Designing unpredictability in agency delegation, Proc. SIGCHI Conf. on Human Factors in Computing Systems

Conference paper

Alkayal ES, Jennings NR, Abulkhair MF, 2018, Survey of Task Scheduling in Cloud Computing based on Particle Swarm Optimization, International Conference on Electrical and Computing Technologies and Applications (ICECTA), Publisher: IEEE, Pages: 263-268

Particle Swarm Optimization (PSO) is a metaheuristic algorithm applied to optimize many cloud-computing problems. Task scheduling is a critical problem in the cloud computing that needs to be optimized. Several research studies have been conducted to improve cloud-computing task scheduling using PSO algorithms. This paper analyzes this work in terms of its objectives and orientation. Finally, it identifies the key areas that require further research.

Conference paper

Beck Z, Luke Teacy WT, Rogers A, Jennings NRet al., 2017, Collaborative online planning for automated victim search in disaster response, Robotics and Autonomous Systems, Vol: 100, Pages: 251-266, ISSN: 0921-8890

Collaboration is essential for effective performance by groups of robots in disaster response settings. Here we are particularly interested in heterogeneous robots that collaborate in complex scenarios with incomplete, dynamically changing information. In detail, we consider an automated victim search setting, where unmanned aerial vehicles (UAVs) with different capabilities work together to scan for mobile phones and find and provide information about possible victims near these phone locations. The state of the art for such collaboration is robot control based on independent planning for robots with different tasks and typically incorporates uncertainty with only a limited scope. In contrast, in this paper, we take into account complex relations between robots with different tasks. As a result, we create a joint, full-horizon plan for the whole robot team by optimising over the uncertainty of future information gain using an online planner with hindsight optimisation. This joint plan is also used for further optimisation of individual UAV paths based on the long-term plans of all robots. We evaluate our planner’s performance in a realistic simulation environment based on a real disaster and find that our approach finds victims 25% faster compared to current state-of-the-art approaches.

Journal article

Jennings N, Zenonos A, Stein S, 2017, A trust-based coordination system for participatory sensing applications, 5th Int. Conf. on Human Computation and Crowdsourcing, Publisher: AAAI, Pages: 226-234

Participatory sensing (PS) has gained significant attention asa crowdsourcing methodology that allows ordinary citizens(non-expert contributors) to collect data using low-cost mobiledevices. In particular, it has been useful in the collectionof environmental data. However, current PS applicationssuffer from two problems. First, they do not coordinate themeasurements taken by their users, which is required to maximisesystem efficiency. Second, they are vulnerable to maliciousbehaviour. In this context, we propose a novel algorithmthat simultaneously addresses both of these problems. Specifically,we use heteroskedastic Gaussian Processes to incorporateusers’ trustworthiness into a Bayesian spatio-temporalregression model. The model is trained with measurementstaken by participants, thus it is able to estimate the value ofthe phenomenon at any spatio-temporal location of interestand also learn the level of trustworthiness of each user. Giventhis model, the coordination system is able to make informeddecisions concerning when, where and who should take measurementsover a period of time. We empirically evaluate ouralgorithm on a real-world human mobility and air qualitydataset, where malicious behaviour is synthetically produced,and show that our algorithm outperforms the current state ofthe art by up to 60.4% in terms of RMSE while having a reasonableruntime.

Conference paper

Pruna RT, Polukarov M, Jennings NR, 2017, Avoiding regret in an agent-based asset pricing model, Finance Research Letters, Vol: 24, Pages: 273-277, ISSN: 1544-6123

We use an agent-based asset pricing model to test the implications of the disposition effect (avoiding regret) on investors' interactions and price settings. We show that it has a direct impact on the returns series produced by the model, altering important stylized facts such as its heavy tails and volatility clustering. Moreover, we show that the horizon over which investors compute their wealth has no effect on the dynamics produced by the model.

Journal article

Alkayal ES, Jennings NR, Abulkhair MF, 2017, Automated Negotiation using Parallel Particle Swarm Optimization for Cloud Computing Applications, International Conference on Computer and Applications (ICCA), Publisher: IEEE, Pages: 26-35

Conference paper

Jennings N, Meir R, Polukarov M, Rosenschein JSet al., 2017, Iterative voting and acyclic games, Artificial Intelligence, Vol: 252, Pages: 100-122, ISSN: 1872-7921

Multi-agent decision problems, in which independent agents have to agree on a joint plan of action or allocation of resources, are central to artificial intelligence. In such situations, agents' individual preferences over available alternatives may vary, and they may try to reconcile these differences by voting.We consider scenarios where voters cannot coordinate their actions, but are allowed to change their vote after observing the current outcome, as is often the case both in offline committees and in online voting. Specifically, we are interested in identifying conditions under which such iterative voting processes are guaranteed to converge to a Nash equilibrium state—that is, under which this process is acyclic. We classify convergence results based on the underlying assumptions about the agent scheduler (the order in which the agents take their actions) and the action scheduler (the actions available to the agents at each step). By so doing, we position iterative voting models within the general framework of acyclic games and game forms.In more detail, our main technical results provide a complete picture of conditions for acyclicity in several variations of Plurality voting. In particular, we show that (a) under the traditional lexicographic tie-breaking, the game converges from any state and for any order of agents, under a weak restriction on voters' actions; and that (b) Plurality with randomized tie-breaking is not guaranteed to converge under arbitrary agent schedulers, but there is always some path of better replies from any initial state of the game to a Nash equilibrium. We thus show a first separation between order-free acyclicity and weak acyclicity of game forms, thereby settling an open question from [Kukushkin 2011]. In addition, we refute another conjecture of Kukushkin regarding strongly acyclic voting rules, by proving the existence of strongly acyclic separable game forms.

Journal article

Stein S, Eshghi S, Maghsudi S, Tassiulas L, Bellamy RKE, Jennings NRet al., 2017, Heuristic algorithms for influence maximization in partially observable social networks, 3rd International Workshop on Social Influence Analysis (SocInf 2017), Pages: 20-32, ISSN: 1613-0073

We consider the problem of selecting the most influential members within a social network, in order to disseminate a message as widely as possible. This problem, also referred to as seed selection for influence maximization, has been under intensive investigation since the emergence of social networks. Nonetheless, a large body of existing research is based on the assumption that the network is completely known, whereas little work considers partially observable networks. Yet, due to many issues including the extremely large size of current networks and privacy considerations, assuming full knowledge of the network is rather unrealistic. Despite this, an influencer often wishes to distribute its message far beyond the boundaries of the known network. In this preliminary study, we propose a set of novel heuristic algorithms that specifically target nodes at this boundary, in order to maximize influence across the whole network. We show that these algorithms outperform the state of the art by up to 38% in networks with partial observability.

Conference paper

This data is extracted from the Web of Science and reproduced under a licence from Thomson Reuters. You may not copy or re-distribute this data in whole or in part without the written consent of the Science business of Thomson Reuters.

Request URL: http://wlsprd.imperial.ac.uk:80/respub/WEB-INF/jsp/search-html.jsp Request URI: /respub/WEB-INF/jsp/search-html.jsp Query String: respub-action=search.html&id=00341208&limit=30&person=true