In multiagent systems, strategic settings are often analyzed under the assumption that players choose their strategies simultaneously. However, this model is not always realistic. many settings, one player able to commit a strategy before other makes decision. Such models synonymously referred as leadership, commitment, or Stackelberg models, and optimal play in such significantly different from where selected simultaneously.The recent surge interest computing game-theoretic solutions has so...

In multiagent settings where the agents have different preferences, preference aggregation is a central issue. Voting general method for aggregation, but seminal results shown that all voting protocols are manipulable. One could try to avoid manipulation by using determining beneficial hard. Especially among computational agents, it reasonable measure this hardness complexity. Some earlier work has been done in area, was assumed number of voters and candidates unbounded. Such lose relevance...

Noncooperative game theory provides a normative framework for analyzing strategic interactions. However, the toolbox to be operational, solutions it defines will have computed. In this paper, we provide single reduction that 1) demonstrates NP-hardness of determining whether Nash equilibria with certain natural properties exist, and 2) #P-hardness counting (or connected sets equilibria). We also show 3) pure-strategy Bayes-Nash equilibrium exists is NP-hard, 4) in stochastic (Markov)...

There has been significant recent interest in game-theoretic approaches to security, with much of the research focused on utilizing leader-follower Stackelberg game model. Among major applications are ARMOR program deployed at LAX Airport and IRIS use by US Federal Air Marshals (FAMS). The foundational assumption for using games is that security forces (leaders), acting first, commit a randomized strategy; while their adversaries (followers) choose best response after surveillance this...

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 assume that defender (security personnel) can commit to a mixed strategy, so-called Stackelberg model. As pointed out by Kiekintveld et al. (2009), these generally, multiple resources need be assigned targets, resulting an exponential number pure strategies defender. In this paper,...

Usually a voting rule requires agents to give their preferences as linear orders. However, in some cases it is impractical for an agent order over all the alternatives. It has been suggested let submit partial orders instead. Then, given rule, profile of orders, and alternative (candidate) c, two important questions arise: first, still possible c win, second, guaranteed win? These are winner necessary problems, respectively. Each these problems further divided into sub-problems: determining...

When a firm can recognize its previous customers, it may use information about their past purchases to price discriminate. We study model with monopolist and continuum of heterogeneous consumers, where consumers have the ability maintain anonymity avoid being identified as possibly at cost. freely anonymity, they all individually choose do so, which results in highest profit for monopolist. Increasing cost benefit but only up point, after effect is reversed. show that if or an independent...

In response to the Mumbai attacks of 2008, police have started schedule a limited number inspection checkpoints on road network throughout city. Algorithms for similar security-related scheduling problems been proposed in recent literature, but security networked domains when targets varying importance remains an open problem at large. this paper, we cast as attacker-defender zero-sum game. The strategy spaces both players are exponentially large, so requires development novel, scalable...

We generalize the classic problem of fairly allocating indivisible goods to fair public decision making, in which a must be made on several social issues simultaneously, and, unlike setting, can provide positive utility multiple players. extend popular fairness notion proportionality (which is not guaranteeable) our more general and introduce three novel relaxations --- up one issue, round robin share, pessimistic proportional share that are also interesting allocation setting. show Maximum...

The generality of decision and game theory has enabled domain-independent progress in AI research. For example, a better algorithm for finding good policies (PO)MDPs can be instantly used variety applications. But such general is lacking when it comes to moral making. applications with component, are we then forced build systems based on many ad-hoc rules? In this paper discuss possible ways avoid conclusion.

We determine the communication complexity of common voting rules. The rules (sorted by their from low to high) are plurality, plurality with runoff, single transferable vote (STV), Condorcet, approval, Bucklin, cup, maximin, Borda, Copeland, and ranked pairs. For each rule, we first give a deterministic protocol an upper bound on number bits communicated in it; then, lower (even nondeterministic) requirements rule. bounds match for all except STV maximin.