The most prominent way to establish trust in online markets such as eBay are reputation systems that publish buyer feedback about a seller’s past behavior. These systems, however, critically rely on assumptions that are rarely met in realworld marketplaces: first, it is assumed that there are no reporting costs and no benefits from lying so that buyers honestly report their private experiences. Second, it is assumed that every seller is long-lived, i.e. will continue to trade on the marketplace indefinitely and, third, it is assumed that sellers cannot whitewash, i.e. create new accounts once an old one is ran down. In my thesis, I address all of these assumptions and design incentive-compatible trust mechanisms with minimal common knowledge requirements.

Most real-world negotiation involves multiple interdependent issues, which makes an agent's utility functions complex. Traditional negotiation mechanisms, which were designed for linear utilities, do not fare well in nonlinear contexts. One of the main challenges in developing effective nonlinear negotiation protocols is scalability; it can be extremely difficult to find high-quality solutions when there are many issues, due to computational intractability. One reasonable approach to reducing computational cost, while maintaining good quality outcomes, is to decompose the contract space into several largely independent sub-spaces. In this paper, we propose a method for decomposing a contract space into sub-spaces based on the agent's utility functions. A mediator finds sub-contracts in each sub-space based on votes from the agents, and combines the sub-contracts to produce the final agreement. We demonstrate, experimentally, that our protocol allows high-optimality outcomes with greater scalability than previous efforts. We also address incentive compatibility issues. Any voting scheme introduces the potential for strategic non-truthful voting by the agents, and our method is no exception. For example, one of the agents may always vote truthfully, while the other exaggerates so that its votes are always "strong." It has been shown that this biases the negotiation outcomes to favor the exaggerator, at the cost of reduced social welfare. We employ the limitation of strong votes to the method of decomposing the contract space into several largely independent sub-spaces. We investigate whether and how this approach can be applied to the method of decomposing a contract space.

In many real world applications, the number of examples to learn from is plentiful, but we can only obtain limited information on each individual example. We study the possibilities of efficient, provably correct, large-scale learning in such settings. The main theme we would like to establish is that large amounts of examples can compensate for the lack of full information on each individual example. The type of partial information we consider can be due to inherent noise or from constraints on the type of interaction with the data source. In particular, we describe and analyze algorithms for budgeted learning, in which the learner can only view a few attributes of each training example, and algorithms for learning kernel-based predictors, when individual examples are corrupted by random noise.

Ontology-based data access is a powerful form of extending database technology, where a classical extensional database (EDB) is enhanced by an ontology that generates new intensional knowledge which may contribute to answer a query. Recently, the Datalog+/- family of ontology languages was introduced; in Datalog+/-, rules are tuple-generating dependencies (TGDs), i.e., Datalog rules with the possibility of having existentially-quantified variables in the head. In this paper we introduce a novel Datalog+/- language, namely sticky sets of TGDs, which allows for a wide class of joins in the body, while enjoying at the same time a low query-answering complexity. We establish complexity results for answering conjunctive queries under sticky sets of TGDs, showing, in particular, that ontological conjunctive queries can be compiled into first-order and thus SQL queries over the given EDB instance. We also show some extensions of sticky sets of TGDs, and how functional dependencies and so-called negative constraints can be added to a sticky set of TGDs without increasing the complexity of query answering. Our language thus properly generalizes both classical database constraints and most widespread tractable description logics.

We study the computational complexity of finding the next most preferred solution in some common formalisms for representing constraints and preferences. The problem is computationally intractable for CSPs, but is polynomial for tree-shaped CSPs and tree-shaped fuzzy CSPs. On the other hand, it is intractable for weighted CSPs, even under restrictions on the constraint graph. For CP-nets, the problem is polynomial when the CP-net is acyclic. This remains so if we add (soft) constraints that are tree-shaped and topologically compatible with the CP-net.

Analogy is heavily used in instructional texts. We introduce the concept of analogical dialogue acts (ADAs), which represent the roles utterances play in instructional analogies. We describe a catalog of such acts, based on ideas from structure-mapping theory. We focus on the operations that these acts lead to while understanding instructional texts, using the Structure-Mapping Engine (SME) and dynamic case construction in a computational model. We test this model on a small corpus of instructional analogies expressed in simplified English, which were understood via a semi-automatic natural language system using analogical dialogue acts. The model enabled a system to answer questions after understanding the analogies that it was not able to answer without them.

A general game player automatically learns to play arbitrary new games solely by being told their rules. For this purpose games are specified in the game description language GDL, a variant of Datalog with function symbols and a few known keywords. In its latest version GDL allows to describe nondeterministic games with any number of players who may have imperfect, asymmetric information. We analyse the epistemic structure and expressiveness of this language in terms of epistemic modal logic and present two main results: The operational semantics of GDL entails that the situation at any stage of a game can be characterised by a multi-agent epistemic (i.e., S5-) model; (2) GDL is sufficiently expressive to model any situation that can be described by a (finite) multi-agent epistemic model.

This paper develops and tests formulas for representing playing strength at chess by the quality of moves played, rather than by the results of games. Intrinsic quality is estimated via evaluations given by computer chess programs run to high depth, ideally so that their playing strength is sufficiently far ahead of the best human players as to be a `relatively omniscient' guide. Several formulas, each having intrinsic skill parameters s for `sensitivity' and c for `consistency', are argued theoretically and tested by regression on large sets of tournament games played by humans of varying strength as measured by the internationally standard Elo rating system. This establishes a correspondence between Elo rating and the parameters. A smooth correspondence is shown between statistical results and the century points on the Elo scale, and ratings are shown to have stayed quite constant over time. That is, there has been little or no `rating inflation'. The theory and empirical results are transferable to other rational-choice settings in which the alternatives have well-defined utilities, but in which complexity and bounded information constrain the perception of the utility values.

We have carefully instrumented a large portion of the population living in a university graduate dormitory by giving participants Android smart phones running our sensing software. In this paper, we propose the novel problem of predicting mobile application (known as “apps”) installation using social networks and explain its challenge. Modern smart phones, like the ones used in our study, are able to collect different social networks using built-in sensors. (e.g. Bluetooth proximity network, call log network, etc) While this information is accessible to app market makers such as the iPhone AppStore, it has not yet been studied how app market makers can use these information for marketing research and strategy development. We develop a simple computational model to better predict app installation by using a composite network computed from the different networks sensed by phones. Our model also captures individual variance and exogenous factors in app adoption. We show the importance of considering all these factors in predicting app installations, and we observe the surprising result that app installation is indeed predictable. We also show that our model achieves the best results compared with generic approaches.

A key problem in mechanism design is the construction of protocols that reach socially efficient decisions with minimal information revelation. This can reduce agent communication, and further, potentially increase privacy in the sense that agents reveal no more private information than is needed to determine an optimal outcome. This is not always possible: previous work has explored the tradeoff between communication cost and efficiency, and more recently, communication and privacy. We explore a third dimension: the tradeoff between privacy and efficiency. By sacrificing efficiency, we can improve the privacy of a variety of existing mechanisms. We analyze these tradeoffs in both second-price auctions and facility location problems (introducing new incremental mechanisms for facility location along the way). Our results show that sacrifices in efficiency can provide gains in privacy (and communication), in both the average and worst case.