United Kingdom

We investigate the problem of computing the probability of winning in an election where voter attendance is uncertain. More precisely, we study the setting where, in addition to a total ordering of the candidates, each voter is associated with a probability of attending the poll, and the attendances of different voters are probabilistically independent. We show that the probability of winning can be computed in polynomial time for the plurality and veto rules. However, it is computationally hard (#P-hard) for various other rules, including k-approval and k-veto for $k&gt;1$, Borda, Condorcet, and Maximin. For some of these rules, it is even hard to find a multiplicative approximation since it is already hard to determine whether this probability is nonzero. In contrast, we devise a fully polynomial-time randomized approximation scheme (FPRAS) for the complement probability, namely the probability of losing, for every positional scoring rule (with polynomial scores), as well as for the Condorcet rule.

AAMAS 2021

Probabilistic Inference of Winners in Elections by Independent Random Voters

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 

We investigate the problem of computing the probability of winning in an election where voter attendance is uncertain. More precisely, we study the setting where, in addition to a total ordering of the candidates, each voter is associated with a probability of attending the poll, and the attendances of different voters are probabilistically independent. We show that the probability of winning can be computed in polynomial time for the plurality and veto rules. However, it is computationally hard (#P-hard) for various other rules, including k-approval and k-veto for $k>1$, Borda, Condorcet, and Maximin. For some of these rules, it is even hard to find a multiplicative approximation since it is already hard to determine whether this probability is nonzero. In contrast, we devise a fully polynomial-time randomized approximation scheme (FPRAS) for the complement probability, namely the probability of losing, for every positional scoring rule (with polynomial scores), as well as for the Condorcet rule.

technical paper

We present a methodology to robustly estimate the competitive equilibria (CE) of combinatorial markets under the assumption that buyers do not know their precise valuations for bundles of goods, but instead can only provide noisy estimates. We first show tight lower- and upper-bounds on the buyers' utility loss, and hence the set of CE, given a uniform approximation of one market by another. We then present two probably-approximately-correct algorithms for learning CE with finite-sample guarantees. The first is a baseline and the second leverages a connection between the first welfare theorem of economics and uniform approximations to adaptively prune value queries when it is determined that they are provably not part of a CE. Extensive experimentation shows that pruning achieves better estimates than the baseline with far fewer samples.

Learning Competitive Equilibria in Noisy Combinatorial Markets

A key problem in network analysis is the influence maximization problem, which consists of finding a set S of at most k seed users in a social network, such that the spread of information from S is maximized. We investigate the problem of choosing the best set of seeds when there exists an unknown pre-existing set of seed nodes. Our work extends the one of Chen and Teng (WWW'17) who introduced the so-called Shapley centrality of a node to measure the efficiency of nodes acting as seeds within a pre-existing but unknown set of seeds. We instead consider the question: Which set of cardinality k to target in this kind of scenario? The resulting optimization problem reveals very challenging, that is, assuming common computational complexity conjectures, we obtain strong hardness of approximation results. Nevertheless, we design a greedy algorithm which achieves an approximation factor of 1-1/e k  -ε for any ε > 0, showing that not all is lost in settings where k is bounded.

Maximizing Influence-Based Group Shapley Centrality

In this work we present a novel succinct representation for large partially observed cooperative games. The proposed representation exploits estimates over marginal contributions to form compact rules representing collaboration patterns with uncertain value. Specifically, given an initial set of MC-nets rules that use prior beliefs over values instead of the actual ones, we propose two types of merging that lead to a new set of even more compact rules.

A Succinct Representation Scheme for Cooperative Games under Uncertainty

Complex networks and reputation systems are fundamental mechanisms to sustain cooperation in populations of self-regarding agents. These mechanisms are typically studied in isolation. In online social platforms, however, behavioral dynamics are likely to result from their combination. Here we investigate the relationship between social networks and reputation-based cooperation (in a Prisoner’s Dilemma setting) in large populations. We develop a new evolutionary game-theoretical model and study dynamics in networks with varying degrees of community structure. We show that networks exhibiting modular structures hamper global cooperation: reputation-based group identities emerge in different communities and strategies that uniquely cooperate with in-group members fixate, sustaining polarization and group bias. Global cooperation is recovered provided that inter-community edges are added.

Social Network Interventions to Prevent Reciprocity-driven Polarization

Off-policy evaluation (OPE) is the problem of evaluating new policies using historical data obtained from a different policy. In the recent OPE context, most studies have focused on single-player cases, and not on multi-player cases. In this study, we propose OPE estimators constructed by the doubly robust and double reinforcement learning estimators in two-player zero-sum Markov games. The proposed estimators project exploitability that is often used as a metric for determining how close a policy profile (i.e., a tuple of policies) is to a Nash equilibrium in two-player zero-sum games. We prove the exploitability estimation error bounds for the proposed estimators. We then propose the methods to find the best candidate policy profile by selecting the policy profile that minimizes the estimated exploitability from a given policy profile class. We prove the regret bounds of the policy profiles selected by our methods. Finally, we demonstrate the effectiveness and performance of the proposed estimators through experiments.

Off-Policy Exploitability-Evaluation in Two-Player Zero-Sum Markov Games

The study of exploration in the domain of decision making has a long history but remains actively debated. From the vast literature that addressed this topic for decades under various points of view (e.g., developmental psychology, experimental design, artificial intelligence), intrinsic motivation emerged as a concept that can practically be transferred to artificial agents. Especially, in the recent field of Deep Reinforcement Learning (RL), agents implement such a concept (mainly using a novelty argument) in the shape of an exploration bonus, added to the task reward, that encourages visiting the whole environment. This approach is supported by the large amount of theory on RL for which convergence to optimality assumes exhaustive exploration. Yet, Human Beings and mammals do not exhaustively explore the world and their motivation is not only based on novelty but also on various other factors (e.g., curiosity, fun, style, pleasure, safety, competition, etc.). They optimize for life-long learning and train to learn transferable skills in playgrounds without obvious goals. They also apply innate or learned priors to save time and stay safe. For these reasons, we propose to learn an exploration bonus from demonstrations that could transfer these motivations to an artificial agent with little assumptions about their rationale. Using an inverse RL approach, we show that complex exploration behaviors, reflecting different motivations, can be learnt and efficiently used by RL agents to solve tasks for which exhaustive exploration is prohibitive.

Show Me the Way: Intrinsic Motivation from Demonstrations

Cross-Entropy Method (CEM) is a gradient-free direct policy search method, which has greater stability and is insensitive to hyper-parameter tuning. CEM bears similarity to population-based evolutionary methods, but, rather than using a population it uses a distribution over candidate solutions (policies in our case). Usually, a natural exponential family distribution such as multivariate Gaussian is used to parameterize the policy distribution. Using a multivariate Gaussian limits the quality of CEM policies as the search becomes confined to a less representative subspace. We address this drawback by using an adversarially-trained hypernetwork, enabling a richer and complex representation of the policy distribution. To achieve better training stability and faster convergence, we use a multivariate Gaussian CEM policy to guide our adversarial training process. Experiments demonstrate that our approach outperforms state-of-the-art CEM-based methods by $15.8%$ in terms of rewards while achieving faster convergence. Results also show that our approach is less sensitive to hyper-parameters than other deep-RL methods such as REINFORCE, DDPG and DQN.

Learning Complex Policy Distribution with CEM Guided Adversarial Hypernetwork

We consider exploration tasks in which an autonomous mobile robot incrementally builds maps of initially unknown indoor environments. In such tasks, the robot makes a sequence of decisions on where to move next that, usually, are based on knowledge about the observed parts of the environment.   In this paper, we present an approach that exploits a prediction of the geometric structure of the unknown parts of an environment to improve exploration performance. In particular, we leverage an existing method that reconstructs the layout of an environment starting from a partial grid map and that predicts the shape of partially observed rooms on the basis of geometric features representing the regularities of the indoor environment. Then, we originally employ the predicted layout to estimate the amount of new area the robot would observe from candidate locations in order to inform the selection of the next best location and to early stop the exploration when no further relevant area is expected to be discovered. Experimental activities show that our approach is able to exploit the predicted layout of partially observed rooms in order to speed up the exploration.

Exploration of Indoor Environments through Predicting the Layout of Partially Observed Rooms

We present an ascending-price mechanism for a multi-sided market with a variety of participants, such as manufacturers, logistics agents, insurance providers, and assemblers. Each deal in the market may consist of a combination of agents from separate categories, and different such combinations are simultaneously allowed. This flexibility lets multiple intersecting markets be resolved as a single global market. Our mechanism is obviously-truthful, strongly budget-balanced, individually rational, and attains almost the optimal gain-from-trade when the market is sufficiently large.

A Global Multi-Sided Market with Ascending-Price Mechanism

Trading mechanisms play a fundamental role in the health of financial markets. For example, it is believed that continuous double auctions constitute fertile soil for predatory behaviour and toxic order flows. To this end, frequent call markets have been proposed as an alternative design choice to address the latency arbitrage opportunities built in those markets. This paper studies the extent to which adaptive rules to define the length of the clearing intervals affect the performance of frequent call markets.

Probabilistic Inference of Winners in Elections by Independent Random Voters

Downloads

Next from AAMAS 2021

Learning Competitive Equilibria in Noisy Combinatorial Markets

Similar lecture

Strategyproof Facility Location Mechanisms on Discrete Trees

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Probabilistic Inference of Winners in Elections by Independent Random Voters

.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

Learning Competitive Equilibria in Noisy Combinatorial Markets

Similar lecture

Strategyproof Facility Location Mechanisms on Discrete Trees

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Downloads