bluuebunny/crossref_metadata_2025 huggingface dataset:
Automatic Identification of Conceptual Metaphors With Limited Knowledge
Authors: Gandy Lisa , Allan Nadji , Atallah Mark , Frieder Ophir , Howard Newton , Kanareykin Sergey , Koppel Moshe , Last Mark , Neuman Yair , Argamon Shlomo
Published: June 2022

Full natural language understanding requires identifying and analyzing the meanings of metaphors, which are ubiquitous in both text and speech. Over the last thirty years, linguistic metaphors have been shown to be based on more general conceptual metaphors, partial semantic mappings between disparate conceptual domains. Though some achievements have been made in identifying linguistic metaphors over the last decade or so, little work has been done to date on automatically identifying conceptual metaphors. This paper describes research on identifying conceptual metaphors based on corpus data. Our method uses as little background knowledge as possible, to ease transfer to new languages and to mini- mize any bias introduced by the knowledge base construction process. The method relies on general heuristics for identifying linguistic metaphors and statistical clustering (guided by Wordnet) to form conceptual metaphor candidates. Human experiments show the system effectively finds meaningful conceptual metaphors.
SMILe: Shuffled Multiple-Instance Learning
Authors: Doran Gary , Ray Soumya
Published: June 2022

Resampling techniques such as bagging are often used in supervised learning to produce more accurate classifiers. In this work, we show that multiple-instance learning admits a different form of resampling, which we call "shuffling." In shuffling, we resample instances in such a way that the resulting bags are likely to be correctly labeled. We show that resampling results in both a reduction of bag label noise and a propagation of additional informative constraints to a multiple-instance classifier. We empirically evaluate shuffling in the context of multiple-instance classification and multiple-instance active learning and show that the approach leads to significant improvements in accuracy.
Optimal Coalition Structure Generation in Cooperative Graph Games
Authors: Bachrach Yoram , Kohli Pushmeet , Kolmogorov Vladimir , Zadimoghaddam Morteza
Published: June 2022

Representation languages for coalitional games are a key research area in algorithmic game theory. There is an inherent tradeoff between how general a language is, allowing it to capture more elaborate games, and how hard it is computationally to optimize and solve such games. One prominent such language is the simple yet expressive Weighted Graph Games (WGGs) representation (Deng and Papadimitriou, 1994), which maintains knowledge about synergies between agents in the form of an edge weighted graph. We consider the problem of finding the optimal coalition structure in WGGs. The agents in such games are vertices in a graph, and the value of a coalition is the sum of the weights of the edges present between coalition members. The optimal coalition structure is a partition of the agents to coalitions, that maximizes the sum of utilities obtained by the coalitions. We show that finding the optimal coalition structure is not only hard for general graphs, but is also intractable for restricted families such as planar graphs which are amenable for many other combinatorial problems. We then provide algorithms with constant factor approximations for planar, minor-free and bounded degree graphs.
A Morphogenetically Assisted Design Variation Tool
Authors: Adler Aaron , Yaman Fusun , Beal Jacob , Cleveland Jeffrey , Mostafa Hala , Mozeika Annan
Published: June 2022

The complexity and tight integration of electromechanical systems often makes them "brittle" and hard to modify in response to changing requirements. We aim to remedy this by capturing expert knowledge as functional blueprints, an idea inspired by regulatory processes that occur in natural morphogenesis. We then apply this knowledge in an intelligent design variation tool. When a user modifies a design, our tool uses functional blueprints to modify other components in response, thereby maintaining integration and reducing the need for costly search or constraint solving. In this paper, we refine the functional blueprint concept and discuss practical issues in applying it to electromechanical systems. We then validate our approach with a case study applying our prototype tool to create variants of a miniDroid robot and by empirical evaluation of convergence dynamics of networks of functional blueprints.
How Bad Is Selfish Voting?
Authors: Branzei Simina , Caragiannis Ioannis , Morgenstern Jamie , Procaccia Ariel
Published: June 2022

It is well known that strategic behavior in elections is essentially unavoidable; we therefore ask: how bad can the rational outcome be? We answer this question via the notion of the price of anarchy, using the scores of alternatives as a proxy for their quality and bounding the ratio between the score of the optimal alternative and the score of the winning alternative in Nash equilibrium. Specifically, we are interested in Nash equilibria that are obtained via sequences of rational strategic moves. Focusing on three common voting rules — plurality, veto, and Borda — we provide very positive results for plurality and very negative results for Borda, and place veto in the middle of this spectrum.
Greedy or Not? Best Improving versus First Improving Stochastic Local Search for MAXSAT
Authors: Whitley Darrell , Howe Adele , Hains Doug
Published: June 2022

Stochastic local search (SLS) is the dominant paradigm for incomplete SAT and MAXSAT solvers. Early studies on small 3SAT instances found that the use of “best improving” moves did not improve search compared to using an arbitrary “first improving” move. Yet SLS algorithms continue to use best improving moves. We revisit this issue by studying very large random and industrial MAXSAT problems. Because locating best improving moves is more expensive than first improving moves, we designed an “approximate best” improving move algorithm and prove that it is as efficient as first improving move SLS. For industrial problems the first local optima found using best improving moves are statistically significantly better than local optima found using first improving moves. However, this advantage reverses as search continues and algorithms must explore equal moves on plateaus. This reversal appears to be associated with critical variables that are in many clauses and that also yield large improving moves.
A Fast Pairwise Heuristic for Planning under Uncertainty
Authors: Khalvati Koosha , Mackworth Alan
Published: June 2022

POMDP (Partially Observable Markov Decision Process) is a mathematical framework that models planning under uncertainty. Solving a POMDP is an intractable problem and even the state of the art POMDP solvers are too computationally expensive for large domains. This is a major bottleneck. In this paper, we propose a new heuristic, called the pairwise heuristic, that can be used in a one-step greedy strategy to find a near optimal solution for POMDP problems very quickly. This approach is a good candidate for large problems where real-time solution is a necessity but exact optimality of the solution is not vital. The pairwise heuristic uses the optimal solutions for pairs of states. For each pair of states in the POMDP, we find the optimal sequence of actions to resolve the uncertainty and to maximize the reward, given that the agent is uncertain about which state of the pair it is in. Then we use these sequences as a heuristic and find the optimal action in each step of the greedy strategy using this heuristic. We have tested our method on the available large classical test benchmarks in various domains. The resulting total reward is close to, if not greater than, the total reward obtained by other state of the art POMDP solvers, while the time required to find the solution is always much less.
Robust Discrete Matrix Completion
Authors: Huang Jin , Nie Feiping , Huang Heng
Published: June 2022

Most existing matrix completion methods seek the matrix global structure in the real number domain and produce predictions that are inappropriate for applications retaining discrete structure, where an additional step is required to post-process prediction results with either heuristic threshold parameters or complicated mappings. Such an ad-hoc process is inefficient and impractical. In this paper, we propose a novel robust discrete matrix completion algorithm that produces the prediction from the collection of user specified discrete values by introducing a new discrete constraint to the matrix completion model. Our method achieves a high prediction accuracy, very close to the most optimal value of competitive methods with threshold values tuning. We solve the difficult integer programming problem via incorporating augmented Lagrangian method in an elegant way, which greatly accelerates the converge process of our method and provides the asymptotic convergence in theory. The proposed discrete matrix completion model is applied to solve three real-world applications, and all empirical results demonstrate the effectiveness of our method.
Continuous Conditional Random Fields for Efficient Regression in Large Fully Connected Graphs
Authors: Ristovski Kosta , Radosavljevic Vladan , Vucetic Slobodan , Obradovic Zoran
Published: June 2022

When used for structured regression, powerful Conditional Random Fields (CRFs) are typically restricted to modeling effects of interactions among examples in local neighborhoods. Using more expressive representation would result in dense graphs, making these methods impractical for large-scale applications. To address this issue, we propose an effective CRF model with linear scale-up properties regarding approximate learning and inference for structured regression on large, fully connected graphs. The proposed method is validated on real-world large-scale problems of image de-noising and remote sensing. In conducted experiments, we demonstrated that dense connectivity provides an improvement in prediction accuracy. Inference time of less than ten seconds on graphs with millions of nodes and trillions of edges makes the proposed model an attractive tool for large-scale, structured regression problems.
Supervised and Projected Sparse Coding for Image Classification
Authors: Huang Jin , Nie Feiping , Huang Heng , Ding Chris
Published: June 2022

Classic sparse representation for classification (SRC) method fails to incorporate the label information of training images, and meanwhile has a poor scalability due to the expensive computation for l_1 norm. In this paper, we propose a novel subspace sparse coding method with utilizing label information to effectively classify the images in the subspace. Our new approach unifies the tasks of dimension reduction and supervised sparse vector learning, by simultaneously preserving the data sparse structure and meanwhile seeking the optimal projection direction in the training stage, therefore accelerates the classification process in the test stage. Our method achieves both flat and structured sparsity for the vector representations, therefore making our framework more discriminative during the subspace learning and subsequent classification. The empirical results on 4 benchmark data sets demonstrate the effectiveness of our method.
Multiagent Knowledge and Belief Change in the Situation Calculus
Authors: Fang Liangda , Liu Yongmei
Published: June 2022

Belief change is an important research topic in AI. It becomes more perplexing in multi-agent settings, since the action of an agent may be partially observable to other agents. In this paper, we present a general approach to reasoning about actions and belief change in multi-agent settings. Our approach is based on a multi-agent extension to the situation calculus, augmented by a plausibility relation over situations and another one over actions, which is used to represent agents' different perspectives on actions. When an action is performed, we update the agents' plausibility order on situations by giving priority to the plausibility order on actions, in line with the AGM approach of giving priority to new information. We show that our notion of belief satisfies KD45 properties. As to the special case of belief change of a single agent, we show that our framework satisfies most of the classical AGM, KM, and DP postulates. We also present properties concerning the change of common knowledge and belief of a group of agents.
Context-Aware Collaborative Topic Regression with Social Matrix Factorization for Recommender Systems
Authors: Chen Chaochao , Zheng Xiaolin , Wang Yan , Hong Fuxing , Lin Zhen
Published: June 2022

Online social networking sites have become popular platforms on which users can link with each other and share information, not only basic rating information but also information such as contexts, social relationships, and item contents. However, as far as we know, no existing works systematically combine diverse types of information to build more accurate recommender systems. In this paper, we propose a novel context-aware hierarchical Bayesian method. First, we propose the use of spectral clustering for user-item subgrouping, so that users and items in similar contexts are grouped. We then propose a novel hierarchical Bayesian model that can make predictions for each user-item subgroup, our model incorporate not only topic modeling to mine item content but also social matrix factorization to handle ratings and social relationships. Experiments on an Epinions dataset show that our method significantly improves recommendation performance compared with six categories of state-of-the-art recommendation methods in terms of both prediction accuracy and recall. We have also conducted experiments to study the extent to which ratings, contexts, social relationships, and item contents contribute to recommendation performance in terms of prediction accuracy and recall.
Who Also Likes It? Generating the Most Persuasive Social Explanations in Recommender Systems
Authors: Wang Beidou , Ester Martin , Bu Jiajun , Cai Deng
Published: June 2022

Social explanation, the statement with the form of "A and B also like the item", is widely used in almost all the major recommender systems in the web and effectively improves the persuasiveness of the recommendation results by convincing more users to try. This paper presents the first algorithm to generate the most persuasive social explanation by recommending the optimal set of users to be put in the explanation. New challenges like modeling persuasiveness of multiple users, different types of users in social network, sparsity of likes, are discussed in depth and solved in our algorithm. The extensive evaluation demonstrates the advantage of our proposed algorithm compared with traditional methods.
Capturing Difficulty Expressions in Student Online Q&A Discussions
Authors: Yoo Jaebong , Kim Jihie
Published: June 2022

We introduce a new application of online dialogue analysis: supporting pedagogical assessment of online Q&A discussions. Extending the existing speech act framework, we capture common emotional expressions that often appear in student discussions, such as frustration and degree of certainty, and present a viable approach for the classification. We demonstrate how such dialogue information can be used in analyzing student discussions and identifying difficulties. In particular, the difficulty expressions are aligned to discussion patterns and student performance. We found that frustration occurs more frequently in longer discussions. The students who frequently express frustration tend to get lower grades than others. On the other hand, frequency of high certainty expressions is positively correlated with the performance. We expect such online dialogue analyses can become a powerful assessment tool for instructors and education researchers.
Trust Prediction with Propagation and Similarity Regularization
Authors: Zheng Xiaoming , Wang Yan , Orgun Mehmet , Zhong Youliang , Liu Guanfeng
Published: June 2022

Online social networks have been used for a variety of rich activities in recent years, such as investigating potential employees and seeking recommendations of high quality services and service providers. In such activities, trust is one of the most critical factors for the decision-making of users. In the literature, the state-of-the-art trust prediction approaches focus on either dispositional trust tendency and propagated trust of the pair-wise trust relationships along a path or the similarity of trust rating values. However, there are other influential factors that should be taken into account, such as the similarity of the trust rating distributions. In addition, tendency, propagated trust and similarity are of different types, as either personal properties or interpersonal properties. But the difference has been neglected in existing models. Therefore, in trust prediction, it is necessary to take all the above factors into consideration in modeling, and process them separately and differently. In this paper we propose a new trust prediction model based on trust decomposition and matrix factorization, considering all the above influential factors and differentiating both personal and interpersonal properties. In this model, we first decompose trust into trust tendency and tendency-reduced trust. Then, based on tendency-reduced trust ratings, matrix factorization with a regularization term is leveraged to predict the tendency-reduced values of missing trust ratings, incorporating both propagated trust and the similarity of users' rating habits. In the end, the missing trust ratings are composed with predicted tendency-reduced values and trust tendency values. Experiments conducted on a real-world dataset illustrate significant improvement delivered by our approach in trust prediction accuracy over the state-of-the-art approaches.
Combining Heterogenous Social and Geographical Information for Event Recommendation
Authors: Qiao Zhi , Zhang Peng , Cao Yanan , Zhou Chuan , Guo Li , Fang Binxing
Published: June 2022

With the rapid growth of event-based social networks (EBSNs) like Meetup, the demand for event recommendation becomes increasingly urgent. In EBSNs, event recommendation plays a central role in recommending the most relevant events to users who are likely to participate in. Different from traditional recommendation problems, event recommendation encounters three new types of information, i.e., heterogenous online+offline social relationships, geographical features of events and implicit rating data from users. Yet combining the three types of data for offline event recommendation has not been considered. Therefore, we present a Bayesian latent factor model that can unify these data for event recommendation. Experimental results on real-world data sets show the performance of our method.
Influence Maximization with Novelty Decay in Social Networks
Authors: Feng Shanshan , Chen Xuefeng , Cong Gao , Zeng Yifeng , Chee Yeow Meng , Xiang Yanping
Published: June 2022

Influence maximization problem is to find a set of seed nodes in a social network such that their influence spread is maximized under certain propagation models. A few algorithms have been proposed for solving this problem. However, they have not considered the impact of novelty decay on influence propagation, i.e., repeated exposures will have diminishing influence on users. In this paper, we consider the problem of influence maximization with novelty decay (IMND). We investigate the effect of novelty decay on influence propagation on real-life datasets and formulate the IMND problem. We further analyze the problem properties and propose an influence estimation technique. We demonstrate the performance of our algorithms on four social networks.
CoreCluster: A Degeneracy Based Graph Clustering Framework
Authors: Giatsidis Christos , Malliaros Fragkiskos , Thilikos Dimitrios , Vazirgiannis Michalis
Published: June 2022

Graph clustering or community detection constitutes an important task forinvestigating the internal structure of graphs, with a plethora of applications in several domains. Traditional tools for graph clustering, such asspectral methods, typically suffer from high time and space complexity. In thisarticle, we present CoreCluster, an efficient graph clusteringframework based on the concept of graph degeneracy, that can be used along withany known graph clustering algorithm. Our approach capitalizes on processing thegraph in a hierarchical manner provided by its core expansion sequence, anordered partition of the graph into different levels according to the k-coredecomposition. Such a partition provides a way to process the graph inan incremental manner that preserves its clustering structure, whilemaking the execution of the chosen clustering algorithm much faster due to thesmaller size of the graph's partitions onto which the algorithm operates.
Learning Parametric Models for Social Infectivity in Multi-Dimensional Hawkes Processes
Authors: Li Liangda , Zha Hongyuan
Published: June 2022

Efficient and effective learning of social infectivity presents a critical challenge in modeling diffusion phenomena in social networks and other applications.Existing methods require substantial amount of event cascades to guarantee the learning accuracy and they only consider time-invariant infectivity.Our paper overcomes those two drawbacks by constructing a more compact model and parameterizing the infectivity using time-varying features, thus dramatically reduces the data requirement, and enables the learning of time-varying infectivity which also takes into account the underlying network topology.We replace the pairwise infectivity in the multidimensional Hawkes processes with linear combinations of those time-varying features, and optimize the associated coefficients with lasso-type of regularization. To efficiently solve the resulting optimization problem, we employ the technique of alternating direction method of multipliers which allows independent updating of the individual coefficients by optimizing a surrogate function upper-bounding the original objective function. On both synthetic and real world data, the proposed method performs better than alternatives in terms of both recovering the hidden diffusion network and predicting the occurrence time of social events.
How Do Your Friends on Social Media Disclose Your Emotions?
Authors: Yang Yang , Jia Jia , Zhang Shumei , Wu Boya , Chen Qicong , Li Juanzi , Xing Chunxiao , Tang Jie
Published: June 2022

Extracting emotions from images has attracted much interest, in particular with the rapid development of social networks. The emotional impact is very important for understanding the intrinsic meanings of images. Despite many studies having been done, most existing methods focus on image content, but ignore the emotion of the user who published the image. One interesting question is: How does social effect correlate with the emotion expressed in an image? Specifically, can we leverage friends interactions (e.g., discussions) related to an image to help extract the emotions? In this paper, we formally formalize the problem and propose a novel emotion learning method by jointly modeling images posted by social users and comments added by their friends. One advantage of the model is that it can distinguish those comments that are closely related to the emotion expression for an image from the other irrelevant ones. Experiments on an open Flickr dataset show that the proposed model can significantly improve (+37.4% by F1) the accuracy for inferring user emotions. More interestingly, we found that half of the improvements are due to interactions between 1.0% of the closest friends.
Programming by Example Using Least General Generalizations
Authors: Raza Mohammad , Gulwani Sumit , Milic-Frayling Natasa
Published: June 2022

Recent advances in Programming by Example (PBE) have supported new applications to text editing, but existing approaches are limited to simple text strings. In this paper we address transformations in richly formatted documents, using an approach based on the idea of least general generalizations from inductive inference, which avoids the scalability issues faced by state-of-the-art PBE methods. We describe a novel domain specific language (DSL) that expresses transformations over XML structures describing richly formatted content, and a synthesis algorithm that generates a minimal program with respect to a natural subsumption ordering in our DSL. We present experimental results on tasks collected from online help forums, showing an average of 4.17 examples required for task completion.
Synthesis of Geometry Proof Problems
Authors: Alvin Chris , Gulwani Sumit , Majumdar Rupak , Mukhopadhyay Supratik
Published: June 2022

This paper presents a semi-automated methodology for generating geometric proof problems of the kind found in a high-school curriculum. We formalize the notion of a geometry proof problem and describe an algorithm for generating such problems over a user-provided figure. Our experimental results indicate that our problem generation algorithm can effectively generate proof problems in elementary geometry. On a corpus of 110 figures taken from popular geometry textbooks, our system generated an average of about 443 problems per figure in an average time of 4.7 seconds per figure.
Efficient Codes for Inverse Dynamics During Walking
Authors: Johnson Leif , Ballard Dana
Published: June 2022

Efficient codes have been used effectively in both computer science and neuroscience to better understand the information processing in visual and auditory encoding and discrimination tasks. In this paper, we explore the use of efficient codes for representing information relevant to human movements during locomotion. Specifically, we apply motion capture data to a physical model of the human skeleton to compute joint angles (inverse kinematics) and joint torques (inverse dynamics); then, by treating the resulting paired dataset as a supervised regression problem, we investigate the effect of sparsity in mapping from angles to torques. The results of our investigation suggest that sparse codes can indeed represent salient features of both the kinematic and dynamic views of human locomotion movements. However, sparsity appears to be only one parameter in building a model of inverse dynamics; we also show that the "encoding" process benefits significantly by integrating with the "regression" process for this task. In addition, we show that, for this task, simple coding and decoding methods are not sufficient to model the extremely complex inverse dynamics mapping. Finally, we use our results to argue that representations of movement are critical to modeling and understanding these movements.
An Agent-Based Model Studying the Acquisition of a Language System of Logical Constructions
Authors: Sierra-Santibanez Josefina
Published: June 2022

This paper presents an agent-based model that studies the emergence and evolution of a language system of logical constructions, i.e. a vocabulary and a set of grammatical constructions that allow the expression of logical combinations of categories. The model assumes the agents have a common vocabulary for basic categories, the ability to construct logical combinations of categories using Boolean functions, and some general purpose cognitive capacities for invention, adoption, induction and adaptation. But it does not assume the agents have a vocabulary for Boolean functions nor grammatical constructions for expressing such logical combinations of categories through language. The results of the experiments we have performed show that a language system of logical constructions emerges as a result of a process of self-organisation of the individual agents' interactions when these agents adapt their preferences for vocabulary and grammatical constructions to those they observe are used more often by the rest of the population, and that such a language system is transmitted from one generation to the next.
Learning Goal-Oriented Hierarchical Tasks from Situated Interactive Instruction
Authors: Mohan Shiwali , Laird John
Published: June 2022

Our research aims at building interactive robots and agents that can expand their knowledge by interacting with human users. In this paper, we focus on learning goal-oriented tasks from situated interactive instructions. Learning the structure of novel tasks and how to execute them is a challenging computational problem requiring the agent to acquire a variety of knowledge including goal definitions and hierarchical control information. We frame acquisition of novel tasks as an explanation-based learning (EBL) problem and propose an interactive learning variant of EBL for a robotic agent. We show that our approach can exploit information in situated instructions along with the domain knowledge to demonstrate fast generalization on several tasks. The knowledge acquired transfers across structurally similar tasks. Finally, we show that our approach seamlessly combines agent-driven exploration with instructions for mixed-initiative learning.
Intelligent System for Urban Emergency Management during Large-Scale Disaster
Authors: Song Xuan , Zhang Quanshi , Sekimoto Yoshihide , Shibasaki Ryosuke
Published: June 2022

The frequency and intensity of natural disasters has significantly increased over the past decades and this trend is predicted to continue. Facing these possible and unexpected disasters, urban emergency management has become the especially important issue for the whole governments around the world.In this paper, we present a novel intelligent system for urban emergency management during the large-scale disasters. The proposed systemstores and manages the global positioning system (GPS) records from mobile devices used by approximately 1.6 million people throughout Japan over one year. By mining and analyzing population movements after the Great East Japan Earthquake, our system can automatically learn a probabilistic model to better understand and simulate human mobility during the emergency situations. Based on the learning model, population mobility in various urban areas impacted by the earthquake throughout Japan can be automatically simulated or predicted. On the basis of such kind of system, it is easy for us to find some new features or population mobility patterns after the recent and unprecedented composite disasters, which are likely to provide valuable experience and play a vital role for future disaster management worldwide.
Robot Team Exploration with Communication Restrictions
Authors: Jensen Elizabeth
Published: June 2022

In the event of an earthquake or fire, search and rescue efforts may be delayed until it is safe for a human team to enter the area. A team of robots could enter in advance to provide maps, images and locations of interest to the human team, allowing them to prepare their approach when they can enter. In a disaster area, communication may also be limited. We have developed a set of distributed algorithms that make use of a small number of robots to fully explore an unknown environment even with restrictions on communication, team size, and available sensors. We show, through proofs and experiments, that the algorithm will allow the team of robots to fully explore the environment and maintain the necessary communication to return the information to the search and rescue team waiting outside.
Extending Tournament Solutions
Authors: Brandt Felix , Brill Markus , Harrenstein Paul
Published: June 2022

An important subclass of social choice functions, so-called majoritarian (or C1) functions, only take into account the pairwise majority relation between alternatives. In the absence of majority ties--e.g., when there is an odd number of agents with linear preferences--the majority relation is antisymmetric and complete and can thus conveniently be represented by a tournament. Tournaments have a rich mathematical theory and many formal results for majoritarian functions assume that the majority relation constitutes a tournament. Moreover, most majoritarian functions have only been defined for tournaments and allow for a variety of generalizations to unrestricted preference profiles, none of which can be seen as the unequivocal extension of the original function. In this paper, we argue that restricting attention to tournaments is justified by the existence of a conservative extension, which inherits most of the commonly considered properties from its underlying tournament solution.
Incentives for Truthful Information Elicitation of Continuous Signals
Authors: Radanovic Goran , Faltings Boi
Published: June 2022

We consider settings where a collective intelligence is formed by aggregating information contributed from many independent agents, such as product reviews, community sensing, or opinion polls. We propose a novel mechanism that elicits both private signals and beliefs. The mechanism extends the previous versions of the Bayesian Truth Serum (the original BTS, the RBTS, and the multi-valued BTS), by allowing small populations and non-binary private signals, while not requiring additional assumptions on the belief updating process. For priors that are sufficiently smooth, such as Gaussians, the mechanism allows signals to be continuous.
Item Bidding for Combinatorial Public Projects
Authors: Markakis Evangelos , Telelis Orestis
Published: June 2022

We present and analyze a mechanism for the Combinatorial Public Project Problem (CPPP). The problem asks to select k out of m available items, so as to maximize the social welfare for autonomous agents with combinatorial preferences (valuation functions) over subsets of items. The CPPP constitutes an abstract model for decision making by autonomous agents and has been shown to present severe computational hardness, in the design of truthful approximation mechanisms. We study a non-truthful mechanism that is, however, practically relevant to multi-agent environments, by virtue of its natural simplicity. It employs an Item Bidding interface, wherein every agent issues a separate bid for the inclusion of each distinct item in the outcome; the k items with the highest sums of bids are chosen and agents are charged according to a VCG-based payment rule. For fairly expressive classes of the agents' valuation functions, we establish existence of socially optimal pure Nash and strong equilibria, that are resilient to coordinated deviations of subsets of agents. Subsequently we derive tight worst-case bounds on the approximation of the optimum social welfare achieved in equilibrium. We show that the mechanism's performance improves with the number of agents that can coordinate, and reaches half of the optimum welfare at strong equilibrium.
Regret-Based Optimization and Preference Elicitation for Stackelberg Security Games with Uncertainty
Authors: Nguyen Thanh , Yadav Amulya , An Bo , Tambe Milind , Boutilier Craig
Published: June 2022

Stackelberg security games (SSGs) have been deployed in a number of real-world domains. One key challenge in these applications is the assessment of attacker payoffs, which may not be perfectly known. Previous work has studied SSGs with uncertain payoffs modeled by interval uncertainty and provided maximin-based robust solutions. In contrast, in this work we propose the use of the less conservative minimax regret decision criterion for such payoff-uncertain SSGs and present the first algorithms for computing minimax regret for SSGs. We also address the challenge of preference elicitation, using minimax regret to develop the first elicitation strategies for SSGs. Experimental results validate the effectiveness of our approaches.
On the Structure of Synergies in Cooperative Games
Authors: Procaccia Ariel , Shah Nisarg , Tucker Max
Published: June 2022

We investigate synergy, or lack thereof, between agents in cooperative games, building on the popular notion of Shapley value. We think of a pair of agents as synergistic (resp., antagonistic) if the Shapley value of one agent when the other agent participates in a joint effort is higher (resp. lower) than when the other agent does not participate. Our main theoretical result is that any graph specifying synergistic and antagonistic pairs can arise even from a restricted class of cooperative games. We also study the computational complexity of determining whether a given pair of agents is synergistic. Finally, we use the concepts developed in the paper to uncover the structure of synergies in two real-world organizations, the European Union and the International Monetary Fund.
Strategyproof Exchange with Multiple Private Endowments
Authors: Todo Taiki , Sun Haixin , Yokoo Makoto
Published: June 2022

We study a mechanism design problem for exchange economies where each agent is initially endowed with a set of indivisible goods and side payments are not allowed. We assume each agent can withhold some endowments, as well as misreport her preference. Under this assumption, strategyproofness requires that for each agent, reporting her true preference with revealing all her endowments is a dominant strategy, and thus implies individual rationality. Our objective in this paper is to analyze the effect of such private ownership in exchange economies with multiple endowments. As fundamental results, we first show that the revelation principle holds under a natural assumption and that strategyproofness and Pareto efficiency are incompatible even under the lexicographic preference domain. We then propose a class of exchange rules, each of which has a corresponding directed graph to prescribe possible trades, and provide necessary and sufficient conditions on the graph structure so that they satisfy strategyproofness.
Voting with Rank Dependent Scoring Rules
Authors: Goldsmith Judy , Lang Jérôme , Mattei Nicholas , Perny Patrice
Published: June 2022

Positional scoring rules in voting compute the score of an alternative by summing the scores for the alternative induced by every vote. This summation principle ensures that all votes contribute equally to the score of an alternative. We relax this assumption and, instead, aggregate scores by taking into account the rank of a score in the ordered list of scores obtained from the votes. This defines a new family of voting rules, rank-dependent scoring rules (RDSRs), based on ordered weighted average (OWA) operators, which, include all scoring rules, and many others, most of which of new. We study some properties of these rules, and show, empirically, that certain RDSRs are less manipulable than Borda voting, across a variety of statistical cultures.
Preference Elicitation and Interview Minimization in Stable Matchings
Authors: Drummond Joanna , Boutilier Craig
Published: June 2022

While stable matching problems are widely studied, little work has investigated schemes for effectively eliciting agent preferences using either preference (e.g., comparison) queries for interviews (to form such comparisons); and no work has addressed how to combine both. We develop a new model for representing and assessing agent preferences that accommodates both forms of information and (heuristically) minimizes the number of queries and interviews required to determine a stable matching. Our Refine-then-Interview (RtI) scheme uses coarse preference queries to refine knowledge of agent preferences and relies on interviews only to assess comparisons of relatively “close” options. Empirical results show that RtI compares favorably to a recent pure interview minimization algorithm, and that the number of interviews it requires is generally independent of the size of the market.
Role-Aware Conformity Modeling and Analysis in Social Networks
Authors: Zhang Jing , Tang Jie , Zhuang Honglei , Leung Cane , Li Juanzi
Published: June 2022

Conformity is the inclination of a person to be influenced by others. In this paper, we study how the conformity tendency of a person changes with her role, as defined by her structural properties in a social network. We first formalize conformity using a utility function based on the conformity theory from social psychology, and validate the proposed utility function by proving the existence of Nash Equilibria when all users in a network behave according to it. We then extend and incorporate the utility function into a probabilistic topic model, called the Role-Conformity Model (RCM), for modeling user behaviors under the effect of conformity. We apply the proposed RCM to several academic research networks, and discover that people with higher degree and lower clustering coefficient are more likely to conform to others. We also evaluate RCM through the task of word usage prediction in academic publications, and show significant improvements over baseline models.
Pay-As-You-Go OWL Query Answering Using a Triple Store
Authors: Zhou Yujiao , Nenov Yavor , Cuenca Grau Bernardo , Horrocks Ian
Published: June 2022

We present an enhanced hybrid approach to OWL query answering that combines an RDF triple-store with an OWL reasoner in order to provide scalable pay-as-you-go performance. The enhancements presented here include an extension to deal with arbitrary OWL ontologies, and optimisations that significantly improve scalability. We have implemented these techniques in a prototype system, a preliminary evaluation of which has produced very encouraging results.
Pathway Specification and Comparative Queries: A High Level Language with Petri Net Semantics
Authors: Anwar Saadat , Baral Chitta
Published: June 2022

Understanding biological pathways is an important activity in the biological domain for drug development. Due to the parallelism and complexity inherent in pathways, computer models that can answer queries about pathways are needed. A researcher may ask `what-if' questions comparing alternate scenarios, that require deeper understanding of the underlying model. In this paper, we present overview of such a system we developed and an English-like high level language to express pathways and queries. Our language is inspired by high level action and query languages and it uses Petri Net execution semantics.
Contraction and Revision over DL-Lite TBoxes
Authors: Zhuang Zhiqiang , Wang Zhe , Wang Kewen , Qi Guilin
Published: June 2022

Two essential tasks in managing Description Logic (DL) ontologies are eliminating problematic axioms and incorporating newly formed axioms. Such elimination and incorporation are formalised as the operations of contraction and revision in belief change.In this paper, we deal with contraction and revision for the DL-Lite family through a model-theoretic approach.Standard DL semantics yields infinite numbers of models for DL-Lite TBoxes, thus it is not practical to develop algorithms for contraction and revision that involve DL models. The key to our approach is the introduction of an alternative semantics called type semantics which is more succinct than DL semantics. More importantly, with a finite signature, type semantics always yields finite humber of models.We then define model-based contraction and revision for DL-Lite TBoxesunder type semantics and provide representation theorems for them.Finally, the succinctness of type semantics allows us to develop tractable algorithms for both operations.
The Most Uncreative Examinee: A First Step toward Wide Coverage Natural Language Math Problem Solving
Authors: Matsuzaki Takuya , Iwane Hidenao , Anai Hirokazu , Arai Noriko
Published: June 2022

We report on a project aiming at developing a system that solves a wide range of math problems written in natural language. In the system, formal analysis of natural language semantics is coupled with automated reasoning technologies including computer algebra, using logic as their common language. We have developed a prototype system that accepts as its input a linguistically annotated problem text. Using the prototype system as a reference point, we analyzed real university entrance examination problems from the viewpoint of end-to-end automated reasoning. Further, evaluation on entrance exam mock tests revealed that an optimistic estimate of the system’s performance already matches human averages on a few test sets.
Congestion Games for V2G-Enabled EV Charging
Authors: Lutati Benny , Levit Vadim , Grinshpoun Tal , Meisels Amnon
Published: June 2022

A model of the problem of charging and discharging electrical vehicles as a congestion game is presented. A generalization of congestion games - feedback congestion games (FCG) - is introduced. The charging of grid-integrated vehicles, which can also discharge energy back to the grid, is a natural FCG application. FCGs are proven to be exact potential games and therefore converge to a pure-strategy Nash equilibrium by an iterated better-response process. A compact representation and an algorithm that enable efficient best-response search are presented. A detailed empirical evaluation assesses the performance of the iterated best-response process. The evaluation considers the quality of the resulting solutions and the rate of convergence to a stable state. The effect of allowing to also discharge batteries using FCG is compared to scenarios that only include charging and is found to dramatically improve the predictability of the achieved solutions as well as the balancing of load.
Regret-Based Multi-Agent Coordination with Uncertain Task Rewards
Authors: Wu Feng , Jennings Nicholas
Published: June 2022

Many multi-agent coordination problems can be represented as DCOPs. Motivated by task allocation in disaster response, we extend standard DCOP models to consider uncertain task rewards where the outcome of completing a task depends on its current state, which is randomly drawn from unknown distributions. The goal of solving this problem is to find a solution for all agents that minimizes the overall worst-case loss. This is a challenging problem for centralized algorithms because the search space grows exponentially with the number of agents and is nontrivial for existing algorithms for standard DCOPs. To address this, we propose a novel decentralized algorithm that incorporates Max-Sum with iterative constraint generation to solve the problem by passing messages among agents. By so doing, our approach scales well and can solve instances of the task allocation problem with hundreds of agents and tasks.
Internally Stable Matchings and Exchanges
Authors: Liu Yicheng , Tang Pingzhong , Fang Wenyi
Published: June 2022

Stability is a central concept in exchange-based mechanismdesign. It imposes a fundamental requirement that no subsetof agents could beneficially deviate from the outcome pre-scribed by the mechanism. However, deployment of stabilityin an exchange mechanism presents at least two challenges.First, it reduces social welfare and sometimes prevents themechanism from producing a solution. Second, it might incurcomputational cost to clear the mechanism.In this paper, we propose an alternative notion of stability,coined internal stability, under which we analyze the socialwelfare bounds and computational complexity. Our contribu-tions are as follows: for both pairwise matchings and limited-length exchanges, for both unweighted and weighted graph-s, (1) we prove desirable tight social welfare bounds; (2) weanalyze the computational complexity for clearing the match-ings and exchanges. Extensive experiments on the kidney ex-change domain demonstrate that the optimal welfare underinternal stability is very close to the unconstrained optimal.
Theory of Cooperation in Complex Social Networks
Authors: Ranjbar-Sahraei Bijan , Bou Ammar Haitham , Bloembergen Daan , Tuyls Karl , Weiss Gerhard
Published: June 2022

This paper presents a theoretical as well as empirical study on the evolution of cooperation on complex social networks, following the continuous action iterated prisoner's dilemma (CAIPD) model. In particular, convergence to network-wide agreement is proven for both evolutionary networks with fixed interaction dynamics, as well as for coevolutionary networks where these dynamics change over time. Moreover, an extension to the CAIPD model is proposed that allows to model influence on the evolution of cooperation in social networks. As such, this work contributes to a better understanding of behavioral change on social networks, and provides a first step towards their active control.