New Zealand


This paper is about modeling and verifying quantitative group trust. We present a formal analysis of this concept that allows us to express and reason about trust in multi-agent systems in a quantitative setting. We introduce GTL, the graded branching temporal logic that includes operators for quantitative aspects of trust within a group. A two-stage verification procedure of the logic is presented. The first stage is a transformation procedure, and the second stage is an indirect procedure that makes use of an existing model checking algorithm. Theoretical results about the soundness, completeness and complexity of the procedure are presented.

AAMAS 2022

Quantitative Group Trust: A Two-Stage Verification Approach

quantitative trust; group trust; model checking; 2-stage verification approach

AAMAS (International Conference on Autonomous Agents and Multiagent Systems) is the largest and most influential conference in the area of agents and multiagent systems. The aim of the conference is to bring together researchers and practitioners in all areas of agent technology and to provide a single, high-profile, internationally renowned forum for research in the theory and practice of autonomous agents and multiagent systems. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).

The AAMAS conference series was initiated in 2002 in Bologna, Italy as a joint event comprising the 6th International Conference on Autonomous Agents (AA), the 5th International Conference on Multiagent Systems (ICMAS), and the 9th International Workshop on Agent Theories, Architectures, and Languages (ATAL).

Subsequent AAMAS conferences have been held in Melbourne, Australia (July 2003), New York City, NY, USA (July 2004), Utrecht, The Netherlands (July 2005), Hakodate, Japan (May 2006), Honolulu, Hawaii, USA (May 2007), Estoril, Portugal (May 2008), Budapest, Hungary (May 2009), Toronto, Canada (May 2010), Taipei, Taiwan (May 2011), Valencia, Spain (June 2012), Minnesota, USA (May 2013), Paris, France (May 2014), Istanbul, Turkey (May 2015), Singapore (May 2016), São Paulo (2017) and Stockholm, Sweden (2018), Montreal (May 2019), Auckland (May 2020, Virtual), London (May 2021, Virtual).
<br>
<br>



A ticket is required to attend this event, please register using the link below:

https://aamas2022-conference.auckland.ac.nz/attending/registration/

Registration Is Required

AAMAS (International Conference on Autonomous Agents and Multiagent Systems) is the largest and most influential conference in the area of agents and multiagent systems. The aim of the conference is to bring together researchers and practitioners in all areas of agent technology and to provide a single, high-profile, internationally renowned forum for research in the theory and practice of autonomous agents and multiagent systems. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).

technical paper


Many research works in computational social choice assume a fixed set of voters in an election, and study the resistance of different voting rules against electoral manipulation. In recent years, however, a new technique known as {\it random sample voting} has been adopted in many multi-agent systems. One of the most prominent examples is blockchain. Many proof-of-stake based blockchain systems like Algorand will randomly select a subset of participants of the system to form a committee, and only the committee members will be involved in the decision of some important system parameters. This can be viewed as running an election where the voter committee (i.e., the voters whose votes will be counted) is randomly selected. It is generally expected that the introduction of such randomness should make the election more resistant to electoral manipulation, despite the lack of theoretical analysis. In this paper, we present a systematic study on the resistance of an election with a randomly selected voter committee against bribery. Since the committee is randomly generated, by bribing any fixed subset of voters, the designated candidate may or may not win. Consequently, we consider the problem of finding a feasible solution that maximizes the winning probability of the designated candidate. We show that for most voting rules, this problem becomes extremely difficult for the briber as even finding any non-trivial solution with non-zero objective value becomes NP-hard. However, for plurality and 1-veto, there exists a polynomial time approximation scheme which computes a near-optimal solution efficiently. The algorithm builds upon a novel integer programming formulation together with techniques from $n$-fold integer programming, which may be of separate interest.

How Hard is Bribery in Elections with Randomly Selected Voters


We consider a one-dimensional facility location setting, where there is a set of m facilities, a set of potential locations, and the goal is to build k facilities at these locations. Agents have approval preferences over ‘facility, location’ pairs, and may misreport their preferences if it is beneficial for them to do so. We consider both unit-demand agents and agents with additive demands, and the social objectives of coverage and utilitarianwelfare.We ask whether these social objectives can be satisfied in a computationally efficient and strategyproof way. We also initiate the study of proportional representation in the context of facility location. We show that the axiom of justified representation, which is used to capture proportionality in multiwinner voting with approval preferences, is not well-suited for the facility location setting, and provide a relaxation of this axiom that can handle incompatibilities and may be of broader interest.

Facility Location With Approval Preferences: Strategyproofness and Fairness


Online social media are being perceived as the new means that provide a platform of participation among citizens who are led to alternative spaces of political expression when traditional channels are strained. New technologies appear to have a transformational potential that can lead to social change and achieve deeper and wider mobilisation and participation in political processes. However, people are still facing challenges when seeking information, disseminating information, and engaging in online deliberation. Allowing every citizen to participate in the discussions and influence the final decision requires countless interactions that take considerable amounts of energy and time and could be cognitively demanding due to linguistic barriers or when the problems on the table are multidisciplinary. We envision in this blue sky paper that autonomous conversational agents could augment the deliberative capacities of citizens in online social media. To implement our vision, we will start by proposing an approach that quantifies deliberation in online discussions. Then, we will suggest an agent-based methodology to optimise deliberation across various discussion spaces. The suggested idea will pave the way to a form of democratic deliberation that is built on the cooperation of humans and agents to shape the future of democracy.

Augmented Democratic Deliberation: Can Conversational Agents Boost Deliberation in Social Media?


One of the most innovative aspects of blockchain technology consists in the introduction of an incentive layer to regulate the behavior of distributed protocols. The designer of a blockchain system faces therefore issues that are akin to those relevant for the design of economic mechanisms, and faces them in a computational setting.
From this perspective the paper argues for the importance of computational social choice in contributing theoretical foundations for blockchain technology. I identify challenges at the interface of current blockchain research and the area of computational social choice which, I argue, highlight the strong potential for cross-fertilization between the two research fields.

Social Choice Around the Block: On the Computational Social Choice of Blockchain


Mechanism design over social networks, whose goal is to incentivize agents to diffuse the information of a mechanism to their followers, as well as to report her true preferences, is one of the new trends in the literature of market design. In this paper, we reconsider the traditional house allocation problem with existing tenants from the perspective of mechanism design over social networks. Since our model is a generalization of the networked housing market investigated by Kawasaki et al. (2021), there is no mechanism that simultaneously satisfies strategy-proofness, individual rationality and Pareto efficiency for general social network structure. We therefore examine the case where the social network has a tree structure. We first show that, even under the restricted structure, a weaker welfare requirement called non-wastefulness cannot be achievable by any mechanism that satisfies strategy-proofness and individual rationality. We then show that a non-trivial modification of You Request My House - I Get Your Turn mechanism (YRMH-IGYT) works; it is individually rational, strategy-proof, and weakly non-wasteful. Furthermore, it also chooses an allocation in the strict core for neighbors and satisfies weak group strategy-proofness.

Strategy-Proof House Allocation with Existing Tenants over Social Networks


System optimum (SO) routing, wherein the total travel time of all users is minimized, is a holy grail for transportation authorities. However, SO routing may discriminate against users who incur much larger travel times than others to achieve high system efficiency, i.e., low total travel times. To address the inherent unfairness of SO routing, we study the ${\beta}$-fair SO problem whose goal is to minimize the total travel time while guaranteeing a ${\beta\geq 1}$ level of unfairness, which specifies the maximum possible ratio between the travel times of different users with shared origins and destinations. 

To obtain feasible solutions to the ${\beta}$-fair SO problem while achieving high system efficiency, we develop a new convex program, the Interpolated Traffic Assignment Problem (I-TAP), which interpolates between a fair and an efficient traffic-assignment objective. We evaluate the efficacy of I-TAP through theoretical bounds on the total system travel time and level of unfairness in terms of its interpolation parameter, as well as present a numerical comparison between I-TAP and a state-of-the-art algorithm on a range of transportation networks. The numerical results indicate that our approach is faster by several orders of magnitude as compared to the benchmark algorithm, while achieving higher system efficiency for most levels of unfairness. We further leverage the structure of I-TAP to develop two pricing mechanisms to collectively enforce the I-TAP solution in the presence of selfish homogeneous and heterogeneous users, respectively, that independently choose routes to minimize their own travel costs. We mention that this is the first study of pricing in the context of fair routing for general road networks (as opposed to, e.g., parallel road networks).

Balancing Fairness and Efficiency in Traffic Routing via Interpolated Traffic Assignment


The \emph{Magician Problem} (MP) and its generalization, the \emph{Generalized Magician Problem} (GMP), were introduced by Alaei \emph{et al.} (APPROX-RANDOM 2013) and Alaei (SICOMP 2014) and have been used as powerful ingredients in online-algorithm design for many hard problems such as the $k$-choice prophet inequality, mechanism design in Bayesian combinatorial auctions, and the generalized assignment problem. The adversarial model here is essentially that of an oblivious adversary. 

In this paper, we introduce generalizations of GMP (MP) under two different arrival settings (by making the adversary stronger): unknown independent identical distributions (UIID) and unknown adversarial distributions (UAD). Different adversary models capture a range of arrival patterns. For GMP under UIID, we show that a natural greedy algorithm $\Gre$ is optimal. For the case of MP under UIID, we show that $\Gre$ has an optimal performance of $1 - \frac{B^B}{B! e^B} \geq 1 - \frac{1}{\sqrt{2\pi B}}$, where $B$ is the budget, and show an application to online $B$-matching with stochastic rewards. For GMP under UAD, we present a simple algorithm, which is near-optimal among all non-adaptive algorithms. We consider the simple case of MP under UAD with $B=1$, and give an exact characterization of the respective optimal adaptive and optimal non-adaptive algorithms for any finite time horizon. We offer an example of MP under UAD on which there is a provable gap between the classical MP under adversarial order and MP under UAD even with a time horizon $T=4$.

The Generalized Magician Problem under Unknown Distributions and Related Applications


Given a Markov decision process (MDP) and a linear-time ($\omega$-regular or Linear Temporal Logic) specification, the controller synthesis problem aims to compute the optimal policy that satisfies the specification. Recently, problems that reason over the asymptotic behavior of systems have been proposed through the lens of steady-state planning. This entails finding a control policy for an MDP such that the Markov chain induced by the solution policy satisfies a given set of constraints on its steady-state distribution. This paper studies a generalization of the controller synthesis problem for a linear-time specification under steady-state constraints on the asymptotic behavior. We present an algorithm to find a deterministic policy satisfying omega-regular and steady-state constraints by characterizing the solutions as an integer linear program, and experimentally evaluate our approach.

Controller Synthesis for Omega-Regular and Steady-State Specifications


With the rising demand of deploying robot teams in autonomous warehouses and factories, the Multi-agent Path Finding (MAPF) problem has drawn more and more attention. However, the classical MAPF problem focuses on navigating agent teams to reach single goal locations while avoiding collisions, and thus it cannot plan the case in which each agent is associated with a sequence of goal locations, and precedence constraints across goal sequences should be respected. Planning with these goal sequences and precedence constraints is important in real-world multi-agent systems. For example, a mobile robot needs to move an inventory pod to several stations for delivering different packages, which is captured by a sequence of goal locations, and another robot can only pick up a package after it has been delivered to the corresponding station, which can be modeled as precedence constraints across goal sequences. In this paper, we formalize the Multi-Agent Path Finding with Precedence Dependency (MAPF-PD) problem along with two algorithms to systematically solve this problem: Conflict-Based Search with Precedence Dependency (CBS-PD) is a complete and optimal algorithm; and Priority-Based Search with Precedence Dependency (PBS-PD) is an incomplete and suboptimal algorithm but shows great scalability and obtains near-optimal solutions in practice. Our experimental results show that our algorithms can scale to dozens of agents with hundreds of goal locations and precedence constraints.

Multi-Agent Path Finding for Precedence-Constrained Goal Sequences


This extended abstract summarises the contributions from the journal article "Enabling BDI group plans with coordination middleware: semantics and implementation".

Quantitative Group Trust: A Two-Stage Verification Approach

Downloads

Next from AAMAS 2022

How Hard is Bribery in Elections with Randomly Selected Voters

Similar lecture

Resource-Aware Adaptation of Heterogeneous Strategies for Coalition Formation

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Quantitative Group Trust: A Two-Stage Verification Approach

.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 2022

How Hard is Bribery in Elections with Randomly Selected Voters

Similar lecture

Resource-Aware Adaptation of Heterogeneous Strategies for Coalition Formation

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Downloads