Search

Social agents with finitely nested opponent models are vulnerable to manipulation by agents with deeper reasoning and more sophisticated opponent modelling. This imbalance, rooted in logic and the theory of recursive modelling frameworks, cannot be solved directly. We propose a computational framework, $\aleph$-IPOMDP, augmenting model-based RL agents' Bayesian inference with an anomaly detection algorithm and an out-of-belief policy. Our mechanism allows agents to realize they are being deceived, even if they cannot understand how, and to deter opponents via a credible threat. We test this framework in both a mixed-motive and zero-sum game. Our results show the $\aleph$ mechanism's effectiveness, leading to more equitable outcomes and less exploitation by more sophisticated agents. We discuss implications for AI safety, cybersecurity, cognitive science, and psychiatry., Comment: 11 pages, 5 figures

Symbolic music segmentation is the process of dividing symbolic melodies into smaller meaningful groups, such as melodic phrases. We proposed an unsupervised method for segmenting symbolic music. The proposed model is based on an ensemble of temporal prediction error models. During training, each model predicts the next token to identify musical phrase changes. While at test time, we perform a peak detection algorithm to select segment candidates. Finally, we aggregate the predictions of each of the models participating in the ensemble to predict the final segmentation. Results suggest the proposed method reaches state-of-the-art performance on the Essen Folksong dataset under the unsupervised setting when considering F-Score and R-value. We additionally provide an ablation study to better assess the contribution of each of the model components to the final results. As expected, the proposed method is inferior to the supervised setting, which leaves room for improvement in future research considering closing the gap between unsupervised and supervised methods.

Committee decisions are complicated by a deadline, e.g., the next start of a budget, or the beginning of a semester. In committee hiring decisions, it may be that if no candidate is supported by a strong majority, the default is to hire no one - an option that may cost dearly. As a result, committee members might prefer to agree on a reasonable, if not necessarily the best, candidate, to avoid unfilled positions. In this paper, we propose a model for the above scenario - Consensus Under a Deadline (CUD)- based on a time-bounded iterative voting process. We provide convergence guarantees and an analysis of the quality of the final decision. An extensive experimental study demonstrates more subtle features of CUDs, e.g., the difference between two simple types of committee member behavior, lazy vs.~proactive voters. Finally, a user study examines the differences between the behavior of rational voting bots and real voters, concluding that it may often be best to have bots play on the voters' behalf.

All-pay auctions, a common mechanism for various human and agent interactions, suffers, like many other mechanisms, from the possibility of players' failure to participate in the auction. We model such failures, and fully characterize equilibrium for this class of games, we present a symmetric equilibrium and show that under some conditions the equilibrium is unique. We reveal various properties of the equilibrium, such as the lack of influence of the most-likely-to-participate player on the behavior of the other players. We perform this analysis with two scenarios: the sum-profit model, where the auctioneer obtains the sum of all submitted bids, and the max-profit model of crowdsourcing contests, where the auctioneer can only use the best submissions and thus obtains only the winning bid. Furthermore, we examine various methods of influencing the probability of participation such as the effects of misreporting one's own probability of participating, and how influencing another player's participation chances changes the player's strategy.

We consider iterative voting models and position them within the general framework of acyclic games and game forms. More specifically, we classify convergence results based on the underlying assumptions on the agent scheduler (the order of players) and the action scheduler (which better-reply is played). Our main technical result is providing 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 for any order of players under a weak restriction on voters' actions; and (b) Plurality with randomized tie-breaking is not guaranteed to converge under arbitrary agent schedulers, but from any initial state there is \emph{some} path of better-replies to a Nash equilibrium. We thus show a first separation between restricted-acyclicity and weak-acyclicity of game forms, thereby settling an open question from [Kukushkin, IJGT 2011]. In addition, we refute another conjecture regarding strongly-acyclic voting rules., Comment: some of the results appeared in preliminary versions of this paper: Convergence to Equilibrium of Plurality Voting, Meir et al., AAAI 2010; Strong and Weak Acyclicity in Iterative Voting, Meir, COMSOC 2016

Peer reviews, evaluations, and selections are a fundamental aspect of modern science. Funding bodies the world over employ experts to review and select the best proposals from those submitted for funding. The problem of peer selection, however, is much more general: a professional society may want to give a subset of its members awards based on the opinions of all members; an instructor for a Massive Open Online Course (MOOC) or an online course may want to crowdsource grading; or a marketing company may select ideas from group brainstorming sessions based on peer evaluation. We make three fundamental contributions to the study of peer selection, a specific type of group decision-making problem, studied in computer science, economics, and political science. First, we propose a novel mechanism that is strategyproof, i.e., agents cannot benefit by reporting insincere valuations. Second, we demonstrate the effectiveness of our mechanism by a comprehensive simulation-based comparison with a suite of mechanisms found in the literature. Finally, our mechanism employs a randomized rounding technique that is of independent interest, as it solves the apportionment problem that arises in various settings where discrete resources such as parliamentary representation slots need to be divided proportionally., Comment: 1 Figure, Source Code available at https://github.com/nmattei/peerselection

It is well known that no reasonable voting rule is strategyproof. Moreover, the common Plurality rule is particularly prone to strategic behavior of the voters and empirical studies show that people often vote strategically in practice. Multiple game-theoretic models have been proposed to better understand and predict such behavior and the outcomes it induces. However, these models often make unrealistic assumptions regarding voters' behavior and the information on which they base their vote. We suggest a new model for strategic voting that takes into account voters' bounded rationality, as well as their limited access to reliable information. We introduce a simple behavioral heuristic based on \emph{local dominance}, where each voter considers a set of possible world states without assigning probabilities to them. This set is constructed based on prospective candidates' scores (e.g., available from an inaccurate poll). In a \emph{voting equilibrium}, all voters vote for candidates not dominated within the set of possible states. We prove that these voting equilibria exist in the Plurality rule for a broad class of local dominance relations (that is, different ways to decide which states are possible). Furthermore, we show that in an iterative setting where voters may repeatedly change their vote, local dominance-based dynamics quickly converge to an equilibrium if voters start from the truthful state. Weaker convergence guarantees in more general settings are also provided. Using extensive simulations of strategic voting on generated and real preference profiles, we show that convergence is fast and robust, that emerging equilibria are consistent across various starting conditions, and that they replicate widely known patterns of human voting behavior such as Duverger's law. Further, strategic voting generally improves the quality of the winner compared to truthful voting.

We consider how selfish agents are likely to share revenues derived from maintaining connectivity between important network servers. We model a network where a failure of one node may disrupt communication between other nodes as a cooperative game called the vertex Connectivity Game (CG). In this game, each agent owns a vertex, and controls all the edges going to and from that vertex. A coalition of agents wins if it fully connects a certain subset of vertices in the graph, called the primary vertices. Power indices measure an agents ability to affect the outcome of the game. We show that in our domain, such indices can be used to both determine the fair share of the revenues an agent is entitled to, and identify significant possible points of failure affecting the reliability of communication in the network. We show that in general graphs, calculating the Shapley and Banzhaf power indices is #P-complete, but suggest a polynomial algorithm for calculating them in trees. We also investigate finding stable payoff divisions of the revenues in CGs, captured by the game theoretic solution of the core, and its relaxations, the epsilon-core and least core. We show a polynomial algorithm for computing the core of a CG, but show that testing whether an imputation is in the epsilon-core is coNP-complete. Finally, we show that for trees, it is possible to test for epsilon-core imputations in polynomial time.

A key question in cooperative game theory is that of coalitional stability, usually captured by the notion of the \emph{core}--the set of outcomes such that no subgroup of players has an incentive to deviate. However, some coalitional games have empty cores, and any outcome in such a game is unstable. In this paper, we investigate the possibility of stabilizing a coalitional game by using external payments. We consider a scenario where an external party, which is interested in having the players work together, offers a supplemental payment to the grand coalition (or, more generally, a particular coalition structure). This payment is conditional on players not deviating from their coalition(s). The sum of this payment plus the actual gains of the coalition(s) may then be divided among the agents so as to promote stability. We define the \emph{cost of stability (CoS)} as the minimal external payment that stabilizes the game. We provide general bounds on the cost of stability in several classes of games, and explore its algorithmic properties. To develop a better intuition for the concepts we introduce, we provide a detailed algorithmic study of the cost of stability in weighted voting games, a simple but expressive class of games which can model decision-making in political bodies, and cooperation in multiagent settings. Finally, we extend our model and results to games with coalition structures., Comment: 20 pages; will be presented at SAGT'09

This paper examines the integration of computational complexity into game theoretic models. The example focused on is the Prisoner's Dilemma, repeated for a finite length of time. We show that a minimal bound on the players' computational ability is sufficient to enable cooperative behavior. In addition, a variant of the repeated Prisoner's Dilemma game is suggested, in which players have the choice of opting out. This modification enriches the game and suggests dominance of cooperative strategies. Competitive analysis is suggested as a tool for investigating sub-optimal (but computationally tractable) strategies and game theoretic models in general. Using competitive analysis, it is shown that for bounded players, a sub-optimal strategy might be the optimal choice, given resource limitations., Comment: Proceedings of the First International Conference on Multiagent Systems (ICMAS95), : 276-282, 1995

The system presented here shows the feasibility of modeling the knowledge involved in a complex musical activity by integrating sub-symbolic and symbolic processes. This research focuses on the question of whether there is any advantage in integrating a neural network together with a distributed artificial intelligence approach within the music domain. The primary purpose of our work is to design a model that describes the different aspects a user might be interested in considering when involved in a musical activity. The approach we suggest in this work enables the musician to encode his knowledge, intuitions, and aesthetic taste into different modules. The system captures these aspects by computing and applying three distinct functions: rules, fuzzy concepts, and learning. As a case study, we began experimenting with first species two-part counterpoint melodies. We have developed a hybrid system composed of a connectionist module and an agent-based module to combine the sub-symbolic and symbolic levels to achieve this task. The technique presented here to represent musical knowledge constitutes a new approach for composing polyphonic music., Comment: 21 pages, 3 figures, Preliminary versions presented at International Computer Music Conference, pp. 133-140, Hong Kong (China), August 1996 and AAAI Spring Symposium, 1999