Computing the market maker price of a security in a combinatorial prediction market is #P-hard. We devise a fully polynomial randomized approximation scheme (FPRAS) that computes the price of any security in disjunctive normal form (DNF) within an ε multiplicative error factor in time polynomial in 1ε and the size of the input, with high probability and under reasonable assumptions. Our algorithm is a Monte-Carlo technique based on importance sampling. The algorithm can also approximately price securities represented in conjunctive normal form (CNF) with additive error bounds. To illustrate the applicability of our algorithm, we show that many securities in Yahoo!'s popular combinatorial prediction market game called Predictalot can be represented by DNF formulas of polynomial size.

In many of the possible applications as well as the theoretical models of computational social choice,the agents’ preferences are represented as partialorders. In this paper, we extend the maximum likelihood approach for defining “optimal” voting rules to this setting. We consider distributions in which the pairwise comparisons / incomparabilities between alternatives are drawn i.i.d. We call suchmodels pairwise-independentmodels and show that they correspond to a class of voting rules that we call pairwise scoring rules. This generalizes rulessuch as Kemeny and Borda. Moreover, we show that Borda is the only pairwise scoring rule that satisfies neutrality, when the outcome space is the set of all alternatives. We then study which voting rules defined for linear orders can be extended to partial orders via our MLE model. We show that any weakly neutral outcome scoring rule (includingany ranking/candidate scoring rule) based onthe weighted majority graph can be represented as the MLE of a weakly neutral pairwise-independent model. Therefore, all such rules admit natural extensionsto profiles of partial orders. Finally, we propose a specific MLE model π k for generating a set of k winning alternatives, and study the computational complexity of winner determination for the MLE of π k .

We propose a novel online planning algorithm for ad hoc team settings — challenging situations in which an agent must collaborate with unknown teammates without prior coordination. Our approach is based on constructing and solving a series of stage games, and then using biased adaptive play to choose actions. The utility function in each stage game is estimated via Monte-Carlo tree search using the UCT algorithm. We establish analytically the convergence of the algorithm and show that it performs well in a variety of ad hoc team domains.

In multi-issue automated negotiation against unknown opponents, a key part of effective negotiation is the choice of concession strategy. In this paper, we develop a principled concession strategy, based on Gaussian processes predicting the opponent's future behaviour. We then use this to set the agent's concession rate dynamically during a single negotiation session. We analyse the performance of our strategy and show that it outperforms the state-of-the-art negotiating agents from the 2010 Automated Negotiating Agents Competition, in both a tournament setting and in self-play, across a variety of negotiation domains.

Note that this extra to make decisions about which plans are used to information is included as a preference rather than a goal, achieve their goals. Usually the choice of which as it is acceptable to satisfy the goal without satisfying the plan to use to achieve a particular goal is left up preference. For example, if the user prefers to fly on Dodgy to the system to determine. In this paper we show Airlines, but no such flights are available, then specifying this how preferences, which can be set by the user of the as a preference means that the user can still have a holiday; system, can be incorporated into the BDI execution specifying this as a goal would mean that the user refuses to process and used to guide the choices made.

We present the notion of Social Instruments as mechanisms that facilitate the emergence of conventions from repeated interactions between members of a society. Specifically, we focus on two social instruments: rewiring and observation. Our main goal is to provide agents with tools that allow them to leverage their social network of interactions when effectively addressing coordination and learning problems, paying special attention to dissolving meta-stable subconventions. Initial experiments throw some light on how Self-Reinforcing Substructures (SRS) in the network prevent full convergence, resulting in reduced convergence rates. The use of an effective composed social instrument (observation + rewiring) allow agents to eliminate the subconventions that otherwise remained meta-stable.

In this paper we conceptualize abstract argumentation in terms of successful and unsuccessful attacks, such that arguments are accepted when there are no successful attacks on them. We characterize the relation between attack semantics and Dung's approach, and we define an SCC recursive algorithm for attack semantics using attack labelings.

Typical solutions for agents assessing trust relies on the circulation of information on the individual level, i.e. reputational images, subjective experi- ences, statistical analysis, etc. This work presents an alternative approach, inspired to the cognitive heuristics enabling humans to reason at a categorial level. The approach is envisaged as a crucial ability for agents in order to: (1) estimate trustworthiness of unknown trustees based on an ascribed mem- bership to categories; (2) learn a series of emer- gent relations between trustees observable proper- ties and their effective abilities to fulfill tasks in sit- uated conditions. On such a basis, categorization is provided to recognize signs (Manifesta) through which hidden capabilities (Kripta) can be inferred. Learning is provided to refine reasoning attitudes needed to ascribe tasks to categories. A series of ar- chitectures combining categorization abilities, indi- vidual experiences and context awareness are eval- uated and compared in simulated experiments.

Forming effective coalitions is a major research challenge in AI and multi-agent systems (MAS). Thus, coalitional games, including Coalition Structure Generation (CSG), have been attracting considerable attention from the AI research community. Traditionally, the input of a coalitional game is a black-box function called a characteristic function. A range of previous studies have found that many problems in coalitional games tend to be computationally intractable when the input is a black-box function. Recently, several concise representation schemes for a characteristic function have been proposed. Although these schemes are effective for reducing the representation size, most problems remain computationally intractable. In this paper, we develop a new concise representation scheme based on the idea of agent types. Intuitively, a type represents a set of agents, which are recognized as having the same contribution. This representation can be exponentially more concise than existing concise representation schemes. Furthermore, this idea can be used in conjunction with existing schemes to further reduce the representation size. Moreover, we show that most of the problems in coalitional games, including CSG, can be solved in polynomial time in the number of agents, assuming the number of possible types is fixed.

Envy-freeness is a well-known fairness concept for analyzing mechanisms. Its traditional definition requires that no individual envies another individual. However, an individual (or a group of agents) may envy another group, even if she (or they) does not envy another individual. In mechanisms with monetary transfer, such as combinatorial auctions, considering such fairness requirements, which are refinements of traditional envy-freeness, is meaningful and brings up a new interesting research direction in mechanism design. In this paper, we introduce two new concepts of fairness called envy-freeness of an individual toward a group, and envy-freeness of a group toward a group. They are natural extensions of traditional envy-freeness. We discuss combinatorial auction mechanisms that satisfy these concepts. First, we characterize such mechanisms by focusing on their allocation rules. Then we clarify the connections between these concepts and three other properties: the core, strategy-proofness, and false-name-proofness.