We study a problem of dynamic allocation without money. Agents have arrivals and departures and strict preferences over items. Strategyproofness requires the use of an arrival-priority serial-dictatorship (APSD) mechanism, which is ex post Pareto efficient but has poor ex ante efficiency as measured through average rank efficiency. We introduce the scoring-rule (SR) mechanism, which biases in favor of allocating items that an agent values above the population consensus. The SR mechanism is not strategyproof but has tolerable manipulability in the sense that: (i) if every agent optimally manipulates, it reduces to APSD, and (ii) it significantly outperforms APSD for rank efficiency when only a fraction of agents are strategic. The performance of SR is also robust to mistakes by agents that manipulate on the basis of inaccurate information about the popularity of items.

Auction processes have been a well-established research Different from one-shot combinatorial auctions, the main theme in economics and recently become an emerging research issue of a dynamic auction is whether the procedure can lead topic in AI due to a set of related computational challenges to an equilibrium state (Walrasian equilibrium) at which all (Cramton et al. 2006). It is well-known that the problem the selling items are effectively allocated to the buyers (equilibrium of winner determination in a combinatorial auction is allocation) and the price of each bundle of items NPcomplete (Rothkopf et al. 1998; Sandholm 2002). However, gives the buyers their best values (equilibrium price). It most of the discussions on the computational issues has been observed that without certain assumptions on buyers' of combinatorial auctions are based on one-shot sealed-bid value functions, there is no guarantee for a dynamic mechanisms. This paper aims to make a contribution towards auction to converge toward an equilibrium (Gul and Stacchetti the discussions on dynamic procedures of combinatorial 1999). Kelso and Crawford (1982) proposed a condition, auctions.

In many auctions, agents bid more aggressively than self-interest would prescribe. This can be explained by spite, where the agent's utility not only increases in the agent's surplus but also decreases as the other bidders' surpluses increase. Spite can stem from long-term benefits from making competitors worse off and from inherent psychological effects. There have been important recent game-theoretic analyses of spiteful bidding assuming all agents are equally spiteful. We present, to our knowledge, the first auction analysis in the more realistic setting where bidders may be spiteful to different extents. We show that the equilibrium bidding function can still be written in the same form — except that the spite factor is replaced by an expressed spite factor. This leads to bidders expressing spites that are higher or lower than their true spite depending on others' spite. Perhaps surprisingly, in the two-bidder case, the mapping from true spite to expressed spite is the same across all common auction mechanisms. Furthermore, even with two bidders, important properties of symmetric-spite settings cease to hold: the allocation can be inefficient and the revenue ranking may reverse between first- and second-price auctions. We also show that in sealed-bid auctions under asymmetric valuation distributions, there can be a "bargaining problem" in selecting bids. Finally, we study the generalization where agents can have different extents of spite toward different other bidders.

In distributed work systems, individual users perform work for other users. A significant challenge in these systems is to provide proper incentives for users to contribute as much work as they consume, even when monitoring is not possible. We formalize the problem of designing "incentive-compatible accounting mechanisms" that measure the net contributions of users, despite relying on voluntary reports. We introduce the Drop-Edge Mechanism that removes any incentive for a user to manipulate via misreports about work contributed or consumed. We prove that Drop-Edge provides a good approximation to a user's net contribution, and is accurate in the limit as the number of users grows. We demonstrate very good welfare properties in simulation compared to an existing, manipulable mechanism. In closing, we show the power of sybil attacks in accounting mechanisms and discuss our ongoing work, including a real-world implementation and evaluation of the Drop-Edge Mechanism in a BitTorrent client.

Recent work has demonstrated that several trust and reputation models can be exploited by malicious agents with cyclical behaviour. In each cycle, the malicious agent with cyclical behaviour first regains a high trust value after a number of cooperations and then abuses its gained trust by engaging in a bad transaction. Using a game theoretic formulation, Salehi-Abari and White have proposed the AER model that is resistant to exploitation by cyclical behaviour. Their simulation results imply that FIRE, Regret, and a model due to Yu and Singh, can always be exploited with an appropriate value for the period of cyclical behaviour. Furthermore, their results demonstrate that this is not so for the proposed adaptive scheme. This paper provides a mathematical analysis of the properties of five trust models when faced with cyclical behaviour of malicious agents. Three main results are proven. First, malicious agents can always select a cycle period that allows them to exploit the four models of FIRE, Regret, Probabilistic models, and Yu and Singh indefinitely. Second, malicious agents cannot select a single, finite cycle period that allows them to exploit the AER model forever. Finally, the number of cooperations required to achieve a given trust value increases monotonically with each cycle. In addition to the mathematical analysis, this paper empirically shows how malicious agents can use the theorems proven in this paper to mount efficient attacks on trust models.

Computer agents are increasingly deployed in settings in which they make decisions with people, such as electronic commerce, collaborative interfaces, and cognitive assistants. However, the scientific evaluation of computational strategies for human-computer decision-making is a costly process, involving time, effort and personnel. This paper investigates the use of Peer Designed Agents (PDA) — computer agents developed by human subjects — as a tool for facilitating the evaluation process of automatic negotiators that were developed by researchers. It compared the performance between automatic negotiators that interacted with PDAs to automatic negotiators that interacted with actual people in different domains. The experiments included more than 300 human subjects and 50 PDAs developed by students. Results showed that the automatic negotiators outperformed PDAs in the same situations in which they outperformed people, and that on average, they exhibited the same measure of generosity towards their negotiation partners. These patterns were significant for all types of domains, and for all types of automated negotiators, despite the fact that there were individual differences between the behavior of PDAs and people. The study thus provides an empirical proof that PDAs can alleviate the evaluation process of automatic negotiators, and facilitate their design.

Recently, algorithms for computing game-theoretic solutions have been deployed in real-world security applications, such as the placement of checkpoints and canine units at Los Angeles International Airport. These algorithms assume that the defender (security personnel) can commit to a mixed strategy, a so-called Stackelberg model. As pointed out by Kiekintveld et al. (2009), in these applications, generally, multiple resources need to be assigned to multiple targets, resulting in an exponential number of pure strategies for the defender. In this paper, we study how to compute optimal Stackelberg strategies in such games, showing that this can be done in polynomial time in some cases, and is NP-hard in others.

Many computational problems in game theory, such as finding Nash equilibria, are algorithmically hard to solve. This limitation forces analysts to limit attention to restricted subsets of the entire strategy space. We develop algorithms to identify rationally closed subsets of the strategy space under given size constraints. First, we modify an existing family of algorithms for rational closure in two-player games to compute a related rational closure concept, called formations , for n -player games. We then extend these algorithms to apply in cases where the utility function is partially specified, or there is a bound on the size of the restricted profile space. Finally, we evaluate the performance of these algorithms on a class of random games.

Intentions have been widely studied in AI, both in the context of decision-making within individual agents and in multi-agent systems. Work on intentions in multi-agent systems has focused on joint intention models, which characterise the mental state of agents with a shared goal engaged in teamwork. In the absence of shared goals, however, intentions play another crucial role in multi-agent activity: they provide a basis around which agents can mutually coordinate activities. Models based on shared goals do not attempt to account for or explain this role of intentions. In this paper, we present a formal model of multi-agent systems in which belief-desire-intention agents choose their intentions taking into account the intentions of others. To understand rational mental states in such a setting, we formally define and investigate notions of multi-agent intention equilibrium, which are related to equilibrium concepts in game theory.

We consider problems where several individuals each need to make a yes/no choice regarding a number of issues and these choices then need to be aggregated into a collective choice. Depending on the application at hand, different combinations of yes/no may be considered rational. We can describe such rationality assumptions in terms of a propositional formula. The question then arises whether or not a given aggregation procedure will lift the rationality assumptions from the individual to the collective level, i.e., whether the collective choice will be rational whenever all individual choices are. To address this question, for each of a number of simple fragments of the language of propositional logic, we provide an axiomatic characterisation of the class of aggregation procedures that will lift all rationality assumptions expressible in that fragment.