New Zealand

Miłosz Michalski (July 24th 2013). Computational Complexity in the Analysis of Quantum Operations, Open Systems, Entanglement and Quantum Optics, Andrzej Jamiolkowski, IntechOpen, DOI: 10.5772/56159.

Weiqi Li (December 12th 2019). Solution Attractor of Local Search System: A Method to Reduce Computational Complexity of the Traveling Salesman Problem [Online First], IntechOpen, DOI: 10.5772/intechopen.90521. 

Holger Jaenisch (August 16th 2010). Spatial Voting with Data Modeling, Sensor Fusion and its Applications, Ciza Thomas, IntechOpen, DOI: 10.5772/9960.

Hemaspaandra [22] celebrated the quite close relationship between computational social choice and computational complexity as a two-way street from which both areas benefited in the past, and expressed his hope that the areas become best friends forever. Later on, Rothe [38] celebrated the prominent Borda voting rule and surveyed recent advances on the complexity of problems related to the three most fundamental models of tampering with elections—namely, via manipulation, control, and bribery—and even related to using Borda beyond voting: in fair division and coalition formation in hedonic games. But now the party is over: no more celebration! Instead, we present a common criticism regarding computational social choice persistently making use of worst-case complexity. To overcome this shortcoming, we propose our blue sky idea of applying to problems from computational social choice the method of smoothed analysis due to Spielman and Teng [43, 44] and also
used by Bläser and Manthey [7], as some sort of a middle ground between the worst-case and the average-case analysis of algorithms.

AAMAS 2020

Towards Reality: Smoothed Analysis in Computational Social Choice

smoothed analysis

voting

social choice

computational complexity

The purpose of the AAAI conference is to promote research in artificial intelligence (AI) and scientific exchange among AI researchers, practitioners, scientists, and engineers in affiliated disciplines. 

AAAI 2021

technical paper

AAMAS is the leading scientific conference for research in autonomous agents and multi-agent systems. The AAMAS conference series was initiated in 2002 as the merging of three respected scientific meetings: the International Conference on Multi-Agent Systems (ICMAS), the International Workshop on Agent Theories, Architectures, and Languages (ATAL), and the International Conference on Autonomous Agents (AA). The aim of the joint conference is to provide a single, high-profile, internationally-respected archival forum for scientific research in the theory and practice of autonomous agents and multi-agent systems.

Browse keynotes, discussions, panels and over 300 presentations.


AAMAS is the leading scientific conference for research in autonomous agents and multi-agent systems. The AAMAS conference series was initiated in 2002 as the merging of three respected scientific meetings: the International Conference on Multi-Agent Systems (ICMAS), the International Workshop on Agent Theories, Architectures, and Languages (ATAL), and the International Conference on Autonomous Agents (AA). 

Forecasting the future is a notoriously difficult task. One way to address this challenge is to "hybridize" the forecasting process, combining forecasts from a crowd of humans, as well as one or more machine models. However, an open challenge remains in how to optimally aggregate inputs from these pools into a single forecast. We proposed anchor attention for this type of sequence summary problem. Each forecast is represented by a trainable embedding vector. An anchor attention score is used to determine input weights. We show that our method learned a good representation for both forecaster and question, and outperforms the current state-of-the-art aggregation approaches.

Anchor Attention for Hybrid Crowd Forecasts Aggregation

This paper presents a multi-robot long-term planning ap- proach under uncertainty on the duration of tasks. The proposed method- ology takes advantage of a novel modeling formalism for robot teams: generalized stochastic Petri nets with rewards (GSPNR). A GSPNR al- lows for unified modeling of action selection and uncertainty on the du- ration of action execution. At the same time, it allows for goal specifi- cation through the use of transition rewards and rewards per time unit. Our proposed approach exploits the well-defined semantics provided by Markov reward automata in order to synthesize policies for GSPNRs. It builds on a state-of-the-art method to compute the long-run average reward, extending it in order to allow for the extraction of the optimal policy. We provide an empirical evaluation of the proposed approach on a simulated multi-robot monitoring problem, evaluating its performance and scalability. The results show that, the obtained policy outperforms a carefully hand-crafted policy.


Long-Run Multi-Robot Planning with Uncertain Task Durations

Graph Neural Networks for Decentralized Path Planning

We consider the influence maximization problem (selecting k seeds in a network maximizing the expected total influence) on undirected graphs under the linear threshold model. On the one hand, we prove that the greedy algorithm always achieves a (1−(1−1/k)^k+Ω(1/k^3))-approximation, showing that the greedy algorithm does slightly better on undirected graphs than the generic (1−(1−1/k)^k) bound which also applies to directed graphs. On the other hand, we show that substantial improvement on this bound is impossible by presenting an example where the greedy algorithm can obtain at most a (1−(1−1/k)^k+O(1/k^0.2)) approximation. This result stands in contrast to the previous work on the independent cascade model. Like the linear threshold model, the greedy algorithm obtains a (1−(1−1/k)^k)-approximation on directed graphs in the independent cascade model. However, Khanna and Lucier showed that, in undirected graphs, the greedy algorithm performs substantially better: a (1−(1−1/k)^k+c) approximation for constant c>0. Our results show that, surprisingly, no such improvement occurs in the linear threshold model. Finally, we show that, under the linear threshold model, the approximation ratio (1−(1−1/k)^k) is tight if 1) the graph is directed or 2) the vertices are weighted. In other words, under either of these two settings, the greedy algorithm cannot achieve a (1−(1−1/k)^k+f(k))-approximation for any positive function f(k). The result in setting 2) is again in a sharp contrast to Khanna and Lucier's (1−(1−1/k)^k+c)-approximation result for the independent cascade model, where the (1−(1−1/k)^k+c) approximation guarantee can be extended to the setting where vertices are weighted. We also discuss extensions to more generalized settings including those with edge-weighted graphs.


Limitations of Greed: Influence Maximization in Undirected Networks Re-visited

MB-DPOP is an important complete algorithm for solving Distributed Constraint Optimization Problems (DCOPs) by exploiting a cycle-cut idea to implement memory-bounded inference. However, each cluster root in the algorithm is responsible for enumerating all the instantiations of its cycle-cut nodes, which would cause redundant inferences when its branches do not have the same cycle-cut nodes. Additionally, a large number of cycle-cut nodes and the iterative nature of MB-DPOP further exacerbate the pathology. As a result, MB-DPOP could suffer from huge coordination overheads and cannot scale up well. Therefore, we present RMB-DPOP which incorporates several novel mechanisms to reduce redundant inferences and improve the scalability of MB-DPOP. First, using the independence among the cycle-cut nodes in different branches, we distribute the enumeration of instantiations into different branches whereby the number of nonconcurrent instantiations reduces significantly and each branch can perform memory bounded inference asynchronously. Then, taking the topology into the consideration, we propose an iterative allocation mechanism to choose the cycle-cut nodes that cover a maximum of active nodes in a cluster and break ties according to their relative positions in a pseudo-tree. Finally, a caching mechanism is proposed to further reduce unnecessary inferences when the historical results are compatible with the current instantiations. We theoretically show that with the same number of cycle-cut nodes RMB-DPOP requires as many messages as MB-DPOP in the worst case and the experimental results show our superiorities over the state-of-the-art.


RMB-DPOP: Refining MB-DPOP by Reducing Redundant Inferences

A Novel Individually Rational Objective In Multi*Agent Multy-Armed Bandits: Algorithms and Regret Bounds

Goal reasoning has been attracting much attention in AI recently. Here, we consider how an agent changes its goals as a result of interaction with humans and peers. In particular, we draw upon a model developed in Behavioral Science, the Elementary Pragmatic Model (EPM). We show how the EPM principles can be incorporated into a sophisticated theory of goal change based on the Situation Calculus. The resulting logical theory supports agents with a wide variety of relational styles, including some that we may consider irrational or creative. This lays the foundations for building autonomous agents that interact with humans in a rich and realistic way, as required by advanced Human-AI collaboration applications


Goal Formation through Interaction in the Situation Calculus: A Formal Account Grounded in Behavioral Science

The Chamberlin-Courant (CC) family of committee selection rules aim to select a committee of size $k$ from a set of $m$ candidates to maximize the satisfaction of $n$ agents. The satisfaction of an agent from a committee depends only on the rank of her favorite candidate and is determined by a satisfaction function. Unfortunately, computing an optimal committee of size $k$ is hard in general, which has led to the development of approximation algorithms that select a committee of size $k$, which guarantees some fraction of the optimal satisfaction. However, there is often some flexibility in the size of the committee to be selected.

In this paper, we initiate the study of size-relaxed committee selection for the family of CC rules. Our main results are polynomial-time algorithms to select committees of size at most $k\cdot O(\log n)$, whose satisfaction is guaranteed to be at least that of the optimal committee of size $k$, and show that this is tight. We also provide a constant-factor approximation algorithm for a class of approval ballot based CC rules.


Size-Relaxed Committee Selection under the Chamberlin-Courant Rule

We investigate the representation of game-theoretic measures of network centrality using a framework that blends a social network representation with the formalism of cooperative skill games. We discuss the expressiveness of the new framework and highlight some of its advantages, including a fixed-parameter tractability result for computing centrality measures under such representations. As an application we introduce new network centrality measures that capture the extent to which neighbors of a certain node can help it complete relevant tasks.


It's Not Whom You Know, It's What You (or your friends) Can Do: Coalitional Frameworks for Network Centralities

This talk is about how to design differentially private algorithm in contextual dynamic pricing setting. 


Downloads

Next from AAMAS 2020

Anchor Attention for Hybrid Crowd Forecasts Aggregation

Similar lecture

The Smoothed Complexity of Computing Kemeny and Slater Rankings

.css-70qvj9{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;}Downloads

Next from AAMAS 2020

Anchor Attention for Hybrid Crowd Forecasts Aggregation

Similar lecture

The Smoothed Complexity of Computing Kemeny and Slater Rankings

Downloads