United Kingdom

In a multi-agent system where agents provide quantifiable work for each other on a voluntary basis, reputation mechanisms are incorporated to induce cooperation. Hereby agents assign their peers numerical scores based on their reported transaction histories. In such systems, adversaries can launch an attack by creating fake identities called Sybils, who report counterfeit transactions among one another, with the aim of increasing their own scores in the eyes of others. This  paper provides new results about the Sybil-proofness of reputation mechanisms. We revisit the impossibility result of Seuken and Parkes (2011), who show that strongly-beneficial Sybil attacks cannot be prevented on reputation mechanisms satisfying three particular requirements. We prove that, under a more rigorous set of definitions of Sybil attack benefit, this result no longer holds. We characterise  properties under which reputation mechanisms are susceptible to strongly-beneficial Sybil attacks. Building on our results, we propose a minimal set of requirements for reputation mechanisms to achieve resistance to such attacks, which are stronger   than the results by Cheng and Friedman (2005), who show Sybil-proofness of certain asymmetric reputation mechanisms.

AAMAS 2021

Achieving Sybil-Proofness in Distributed Work Systems

AAMAS is the largest and most influential conference in the area of agents and multiagent systems, bringing together researchers and practitioners in all areas of agent technology and providing and internationally renowned high-profile forum for publishing and finding out about the latest developments in the field. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).  

![](https://assets.underline.io/uploads/markdown_image/1/image/ce4604bd54468a006164d16e080204fb.jpg)

Please click on the button below to register for this event.

If you are registered and see this page please check the account email you are logged in with. It must be the same as for the registration.

If you still have trouble accessing the contact please contact support at aamas2021@underline.io 

technical paper

Institutions and investors face the constant challenge of making accurate decisions and predictions regarding how best they should distribute their endowments. The problem of achieving an optimal outcome at minimal cost has been extensively studied and resolved using several heuristics. However, these works fail to address how an external decision maker can target different types of fair behaviour and how limited information can shape this complex interplay. Here, we consider the well-known Ultimatum game in a spatial setting and propose a hierarchy of interference mechanisms based on the amount of information available to the external decision maker and desired standards of fairness. Our key findings show that asymmetric interactions have drastically different dynamics when compared to symmetric games, such as the Prisoner's Dilemma, and discuss why gathering information about the agents' behaviour allows for the most efficient investment strategies.

Promoting Fair Proposers, Fair Responders or Both? Cost-Efficient Interference in the Spatial Ultimatum Game

We tackle the problem of allocating teams to tasks. For that, we propose a novel allocation problem that matches teams with tasks based on the similarity between the competencies required by the tasks and the competencies offered by teams. We formally cast our problem as an optimisation problem, characterise the size of its search space and outline a heuristic approach to solve it.

Towards a Competence-Based Approach to Allocate Teams to Tasks

Liquid Democracy (LD) uses transitive delegations in voting. In its simplest form, it is used for binary decisions, however its promise holds also for more advanced voting settings. Here we consider LD in the context of Participatory Budgeting (PB), which is a direct democracy approach to budgeting, most usually done in municipal budgeting processes. In particular, we study Knapsack Voting, in which PB voters approve projects, such that the sum of costs of projects each voter approves must respect the budget limit. We observe possible inconsistencies, as the cost of voter-approved projects may go over the budget limit after resolving delegations. We offer ways to overcome them by studying the computational complexity of updating as few delegations as possible to arrive  after following all project delegations  to a consistent profile.

Preserving Consistency for Liquid Knapsack Voting

Search has played a fundamental role in computer game research since the very beginning.   And while online search has been commonly used in perfect information games such as Chess and Go, online search methods for imperfect information games have only been introduced relatively recently. This paper addresses the question of what is a sound online algorithm in an imperfect information setting of two-player zero-sum games? We argue that the fixed-strategy definitions of exploitability and epsilon-Nash equilibria are ill suited to measure the worst-case performance of an online algorithm. We thus formalize epsilon-soundness, a concept that connects the worst-case performance of an online algorithm to the performance of an epsilon-Nash equilibrium. Our definition of soundness and the consistency hierarchy finally provide appropriate tools to analyze online algorithms in repeated imperfect information games.  We thus inspect some of the previous online algorithms in a new light, bringing new insights into their worst case performance guarantees.

Sound Algorithms in Imperfect Information Games

Crowdfunding has become an effective way of raising capital for
developing and producing new products. In a typical crowdfunding campaign, a fundraiser (a seller) sets a product pre-buy price
and a campaign success threshold. Consumers can indicate their
willingness to pay the pre-buy price now, in exchange of a product
in the future. Only when the number of consumers who commit to
pre-buy exceeds the threshold, the crowdfunding is successful and
the seller gets the corresponding pre-buy payments.
A series of works has modeled crowdfunding as imperfect information games, where each player (potential contributor) has a
private valuation for the product, and has characterized the equilibrium behavior for some specific settings [1–4]. Other works focus
on the effectiveness or the moral hazard of the crowdfunding campaigns by regarding it as an option to raise money for either private
[5, 9, 10] or public projects [6–8].
However, the strategic aspect of crowdfunding from the seller’s
perspective hasn’t attracted its deserved attention. In this paper,
we take a mechanism design perspective and explore how a seller
can design crowdfunding campaigns to maximize his profit. In
addition to choosing the pre-buy price and the campaign success
threshold for a crowdfunding campaign, the seller in our paper can
consider two richer design variants: (1) choose two price-threshold
pairs where a pre-buy price discount is given when the number
of committed buyers exceeds the larger threshold, and (2) offer
two differentiating products (simplified vs. standard) and set two
success thresholds such that the advanced product will be delivered
if the larger threshold is reached. We examine the optimal profit
achieved in each scheme. Somewhat surprisingly, the richer design
variants may not improve the seller’s profit.

Optimal Crowdfunding Design

Conditional preference statements have been used to compactly represent preferences over combinatorial domains. They are at the core of CP-nets and their generalizations, and lexicographic preference trees. Several works have addressed the complexity of some queries (optimization, dominance in particular). We extend in this paper some of these results, and study other queries which have not been addressed so far, like equivalence, thereby contributing to a knowledge compilation map for languages bas­ed on conditional preference statements. We also introduce a new parameterised family of languages, which enables to balance expressiveness against the complexity of some queries.

A Knowledge Compilation Map for Conditional Preference Statements-based Languages

Multi-agent influence diagrams (MAIDs) are a popular form of graphical model that, for certain classes of games, have been shown to offer key complexity and explainability advantages over traditional extensive form game (EFG) representations. In this paper, we extend previous work on MAIDs by introducing the concept of a MAID subgame, as well as subgame perfect and trembling hand perfect equilibrium refinements. We then prove several equivalence results between MAIDs and EFGs. Finally, we describe an open source implementation for reasoning about MAIDs and computing their equilibria.

Equilibrium Refinements for Multi-Agent Influence Diagrams: Theory and Practice

This paper presents new algorithms and theoretical results for solutions to Multi-action Multi-armed Restless Bandits, an important but insufficiently studied generalization of traditional Multi-armed Restless Bandits (MARBs). Though MARBs are popular for modeling many problems, they are restricted to binary actions, i.e., "to act or not to act". This renders them unable to capture critical complexities faced by planners in real domains, such as a system manager balancing maintenance, repair, and job scheduling, or a health worker deciding among treatments for a given patient. Limited previous work on Multi-action MARBs has only been specialized to sub-problems. Here we derive multiple algorithms for use on general Multi-action MARBs using Lagrangian relaxation techniques, leading to the following contributions: (i) We develop BLam, a bound optimization algorithm which leverages problem convexity to quickly and provably converge to the well-performing Lagrange policy; (ii) We develop SampleLam, a fast sampling technique for estimating the Lagrange policy, and derive a concentration bound to investigate its convergence properties; (iii) We derive best and worst case computational complexities for our algorithms as well as our main competitor; (iv) We provide experimental results comparing our algorithms to baselines on simulated distributions, including one motivated by a real-world community health intervention task. Our approach achieves significant, up to ten-fold speedups over more general methods without sacrificing performance and is widely applicable across general Multi-action MARBs. Code is available at https://github.com/killian-34/MAMARB-Lagrange-Policies.

Beyond "To Act or Not to Act": Fast Lagrangian Approaches to General Multi-Action Restless Bandits

A key issue in artificial intelligence methods for interactive preference elicitation is choosing at each stage an appropriate query to the user, in order to find a near-optimal solution as quickly as possible. A theoretically attractive method is to choose a query that minimises max setwise regret (which corresponds to the worst case loss response in terms of value of information). We focus here on the situation in which the choices are represented explicitly in a database, and with a model of user utility as a weighted sum of the criteria; in this case when the user makes a choice, an agent learns a linear constraint on the unknown vector of weights. We develop an algorithmic method for computing minimax setwise regret for this form of preference model, by making use of a SAT solver with cardinality constraints to prune the search space, and computing max setwise regret using an extreme points method. Our experimental results demonstrate the feasibility of the approach and the very substantial speed up over the state of the art.

Efficient Exact Computation of Setwise Minimax Regret for Interactive Preference Elicitation

In this paper, we propose solid semantics  to obtain the most acceptable sets of arguments. Besides, we study the application of solid semantics in the field of judgement aggregation.

Achieving Sybil-Proofness in Distributed Work Systems

Downloads

Next from AAMAS 2021

Promoting Fair Proposers, Fair Responders or Both? Cost-Efficient Interference in the Spatial Ultimatum Game

Similar lecture

Agent Programming in the Cognitive Era (JAAMAS Track)

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Achieving Sybil-Proofness in Distributed Work Systems

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

Promoting Fair Proposers, Fair Responders or Both? Cost-Efficient Interference in the Spatial Ultimatum Game

Similar lecture

Agent Programming in the Cognitive Era (JAAMAS Track)

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Downloads