We consider a coordination game between an informed sender and an uninformed
decision maker, the receiver, who communicate over a noisy channel. The
sender's strategy, called a code, maps states of nature to signals. The
receiver's best response is to decode the received channel output as the state
with highest expected receiver payoff. Given this decoding, an equilibrium or
"Nash code" results if the sender encodes every state as prescribed. We show
two theorems that give sufficient conditions for Nash codes. First, a
receiver-optimal code defines a Nash code.

We study a general aggregation problem in which a society has to determine
its position on each of several issues, based on the positions of the members
of the society on those issues. There is a prescribed set of feasible
evaluations, i.e., permissible combinations of positions on the issues. Among
other things, this framework admits the modeling of preference aggregation,
judgment aggregation, classification, clustering and facility location. An
important notion in aggregation of evaluations is strategy-proofness.

Queueing networks are typically modelled assuming that the arrival process is
exogenous, and unaffected by admission control, scheduling policies, etc. In
many situations, however, users choose the time of their arrival strategically,
taking delay and other metrics into account. In this paper, we develop a
framework to study such strategic arrivals into queueing networks. We start by
deriving a functional strong law of large numbers (FSLLN) approximation to the
queueing network.

In this paper we analyze judgement aggregation problems in which a group of
agents independently votes on a set of complex propositions that has some
interdependency constraint between them(e.g., transitivity when describing
preferences). We consider the issue of judgement aggregation from the
perspective of approximation. That is, we generalize the previous results by
studying approximate judgement aggregation.

We study the design and approximation of optimal crowdsourcing contests.
Crowdsourcing contests can be modeled as all-pay auctions because entrants must
exert effort up-front to enter. Unlike all-pay auctions where a usual design
objective would be to maximize revenue, in crowdsourcing contests, the
principal only benefits from the submission with the highest quality.

We study a market for private data in which a data analyst wishes to publicly
release a statistic computed over a database of private information. The
statistic we focus on is the inner product of the database entries with a
publicly known weight vector. Individuals that own the data incur a cost for
their loss of privacy quantified in terms of the differential-privacy guarantee
given by the analyst at the time of the release. To properly incentivize
individuals, the analyst must compensate them for the cost they incur.

We consider the problem of distributed convergence to efficient outcomes in
coordination games through dynamics based on aspiration learning. Under
aspiration learning, a player continues to play an action as long as the
rewards received exceed a specified aspiration level. Here, the aspiration
level is a fading memory average of past rewards, and these levels also are
subject to occasional random perturbations.

Intrusion Detection Systems (IDSs) are becoming essential to protecting
modern information infrastructures. The effectiveness of an IDS is directly
related to the computational resources at its disposal. However, it is
difficult to guarantee especially with an increasing demand of network capacity
and rapid proliferation of attacks. On the other hand, modern intrusions often
come as sequences of attacks to reach some predefined goals. It is therefore
critical to identify the best default IDS configuration to attain the highest
possible overall protection within a given resource budget.

A major achievement of mechanism design theory is a general method for the
construction of truthful mechanisms called VCG (Vickrey, Clarke, Groves). When
applying this method to complex problems such as combinatorial auctions, a
difficulty arises: VCG mechanisms are required to compute optimal outcomes and
are, therefore, computationally infeasible. However, if the optimal outcome is
replaced by the results of a sub-optimal algorithm, the resulting mechanism
(termed VCG-based) is no longer necessarily truthful.

We investigate complexity issues related to pure Nash equilibria of strategic
games. We show that, even in very restrictive settings, determining whether a
game has a pure Nash Equilibrium is NP-hard, while deciding whether a game has
a strong Nash equilibrium is SigmaP2-complete. We then study practically
relevant restrictions that lower the complexity. In particular, we are
interested in quantitative and qualitative restrictions of the way each players
payoff depends on moves of other players.

In this paper we study the approximate learnability of valuations commonly
used throughout economics and game theory for the quantitative encoding of
agent preferences. We provide upper and lower bounds regarding the learnability
of important subclasses of valuation functions that express
no-complementarities. Our main results concern their approximate learnability
in the distributional learning (PAC-style) setting.

BitTorrent is a widely-deployed, peer-to-peer file transfer protocol
engineered with a "tit for tat" mechanism that encourages cooperation.
Unfortunately, there is little incentive for nodes to altruistically provide
service to their peers after they finish downloading a file, and what altruism
there is can be exploited by aggressive clients like Bit- Tyrant. This
altruism, called seeding, is always beneficial and sometimes essential to
BitTorrent's real-world performance.

We study a routing game in which one of the players unilaterally acts
altruistically by taking into consideration the latency cost of other players
as well as his own. By not playing selfishly, a player can not only improve the
other players' equilibrium utility but also improve his own equilibrium
utility. To quantify the effect, we define a metric called the Value of
Unilateral Altruism (VoU) to be the ratio of the equilibrium utility of the
altruistic user to the equilibrium utility he would have received in Nash
equilibrium if he were selfish.

Transmitters of a multiple access channel are assumed to freely choose their
power control strategy in order to be energy-efficient. We show that in a
stochastic game framework, we can develop energy-efficient distributed control
strategies which only require partial knowledge of the entire system.
Achievable utility equilibrium region is characterized and based on
time-sharing, an explicit power control strategy is proposed.

We introduce the Knapsack Game, in which $m$ identical resources are to be
allocated among $n$ selfish agents. Each agent requests some number of
resources $x_i$ and specifies its true valuation $v_i(x_i)$ for receiving them,
to a central entity. We assume that the valuation functions exhibit diminishing
marginal returns. The pairs $(x_i, v_i(x_i))$ can be thought of as size-value
pairs defining a knapsack problem with capacity $m$.

In two-player finite-state stochastic games of partial observation on graphs,
in every state of the graph, the players simultaneously choose an action, and
their joint actions determine a probability distribution over the successor
states. We consider reachability objectives where player 1 tries to ensure a
target state to be visited almost-surely or positively. On the basis of
information, the game can be one-sided with either (a)player 1 or (b)player 2
having partial observation, or two-sided with both players having partial
observation.

With the recent technological feasibility of electronic commerce over the
Internet, much attention has been given to the design of electronic markets for
various types of electronically-tradable goods. Such markets, however, will
normally need to function in some relationship with markets for other related
goods, usually those downstream or upstream in the supply chain. Thus, for
example, an electronic market for rubber tires for trucks will likely need to
be strongly influenced by the rubber market as well as by the truck market.

Much work in AI deals with the selection of proper actions in a given (known
or unknown) environment. However, the way to select a proper action when facing
other agents is quite unclear. Most work in AI adopts classical game-theoretic
equilibrium analysis to predict agent behavior in such settings. This approach
however does not provide us with any guarantee for the agent. In this paper we
introduce competitive safety analysis.

Scoring rules for eliciting expert predictions of random variables are
usually developed assuming that experts derive utility only from the quality of
their predictions (e.g., score awarded by the rule, or payoff in a prediction
market). We study a more realistic setting in which (a) the principal is a
decision maker and will take a decision based on the expert's prediction; and
(b) the expert has an inherent interest in the decision. For example, in a
corporate decision market, the expert may derive different levels of utility
from the actions taken by her manager.

We consider coalitional games with transferable utilities (TU) characterized
by unknown but bounded and time-varying coalitions' values and call them robust
dynamic coalitional TU games. In the assumption that the game is played over
time a Game Designer (GD) allocates the reward to the players so to make the
grand coalition stable, in an average sense, on the long run. We highlight
three main contributions.

We provide a Polynomial Time Approximation Scheme for the multi-dimensional
unit-demand pricing problem, when the buyer's values are independent (but not
necessarily identically distributed). For all epsilon>0, we obtain a
(1+epsilon)-factor approximation to the optimal revenue in time polynomial,
when the values are sampled from Monotone Hazard Rate (MHR) distributions,
quasi-polynomial, when sampled from regular distributions, and polynomial in
n^poly(log r), when sampled from general distributions supported on a set [u, r
* u].

We consider coalition formation games in which each player has preferences
over the other players and his preferences over coalitions are based on the
best player ($\mathcal{B}$-/B-hedonic games) or the worst player
($\mathcal{W}$/W-hedonic games) in the coalition. We show that for
$\mathcal{B}$-hedonic games, an individually stable partition is guaranteed to
exist and can be computed efficiently. Similarly, there exists a
polynomial-time algorithm which returns a Nash stable partition (if one exists)
for $\mathcal{B}$-hedonic games with strict preferences.

An unknown positive number of items arrive at independent uniformly
distributed times in the interval [0,1] to a selector, whose task is to pick
online the last one. We show that under the assumption of an adversary
determining the number of items, there exists a game-theoretical equilibrium,
in other words the selector and the adversary both possess optimal strategies.
The probability of success of the selector with the optimal strategy is
estimated numerically to 0.352917000207196.

We consider Markov Decision Processes (MDPs) with mean-payoff parity and
energy parity objectives. In system design, the parity objective is used to
encode \omega-regular specifications, and the mean-payoff and energy objectives
can be used to model quantitative resource constraints. The energy condition
requires that the resource level never drops below 0, and the mean-payoff
condition requires that the limit-average value of the resource consumption is
within a threshold.

In this paper, we study the Nash dynamics of strategic interplays of n buyers
in a matching market setup by a seller, the market maker. Taking the standard
market equilibrium approach, upon receiving submitted bid vectors from the
buyers, the market maker will decide on a price vector to clear the market in
such a way that each buyer is allocated an item for which he desires the most
(a.k.a., a market equilibrium solution). While such equilibrium outcomes are
not unique, the market maker chooses one (maxeq) that optimizes its own
objective --- revenue maximization.

The focus of the iWIGP workshop is the interrelation between interactions,
games and protocols. How does computer science deal with nondeterministic
interactions where the actions a system takes are not (completely) determined
by the interactions the system is involved in? In computer science,
nondeterministic interactions are usually described by protocols. However,
these interactions can also be viewed as games.

The Honey-Bee game is a two-player board game that is played on a connected
hexagonal colored grid or (in a generalized setting) on a connected graph with
colored nodes. In a single move, a player calls a color and thereby conquers
all the nodes of that color that are adjacent to his own current territory.
Both players want to conquer the majority of the nodes. We show that winning
the game is PSPACE-hard in general, NP-hard on series-parallel graphs, but easy
on outerplanar graphs.

Partial-monitoring games are a mathematical framework for sequential decision
problems with imperfect feedback: The learner repeatedly chooses an action, the
nature responds with an outcome, and then the learner suffers a loss and
receives a feedback signal, both of which are fixed functions of the action and
the outcome. The goal of the learner is to minimize his total cumulative loss.
We make progress towards classification of these games based on their minimax
expected regret.

This paper develops a game-theoretic framework for the design and analysis of
a new class of incentive schemes called intervention schemes. We formulate
intervention games, propose a solution concept of intervention equilibrium, and
prove its existence in a finite intervention game. We apply our framework to
resource sharing scenarios in wireless communications, whose non-cooperative
outcomes without intervention yield suboptimal performance. We derive
analytical results and analyze illustrative examples in the cases of imperfect
and perfect monitoring.

This article investigates selfish behavior in games where players are
embedded in a social context. A framework is presented which allows us to
measure the Windfall of Friendship, i.e., how much players benefit (compared to
purely selfish environments) if they care about the welfare of their friends in
the social network graph. As a case study, a virus inoculation game is
examined. We analyze the corresponding Nash equilibria and show that the
Windfall of Friendship can never be negative.

This paper shows that in suitable markets, even with out-of-equilibrium trade
allowed, a simple price update rule leads to rapid convergence toward the
equilibrium. In particular, this paper considers a Fisher market repeated over
an unbounded number of time steps, with the addition of finite sized warehouses
to enable non-equilibrium trade. The main result is that suitable tatonnement
style price updates lead to convergence in a significant subset of markets
satisfying the Weak Gross Substitutes property.

This paper studies a class of incentive schemes based on intervention, where
there exists an intervention device that is able to monitor the actions of
users and to take an action that affects the payoffs of users. We consider the
case of perfect monitoring, where the intervention device can immediately
observe the actions of users without errors. We also assume that there exist
actions of the intervention device that are most and least preferred by all the
users and the intervention device, regardless of the actions of users.

In this paper new algorithm for calculating power indices is described. The
complexity class of the problem is #P-complete and even calculating power index
of the biggest player is NP-hard task. Constructed algorithm is a mix of ideas
of two algorithms: Klinz & Woeginger partitioning algorithm and Mann & Shapley
generating functions algorithm.

This short note exhibits a truthful-in-expectation $O(\frac {\log m} {\log
\log m})$-approximation mechanism for combinatorial auctions with subadditive
bidders that uses polynomial communication.

Building on ideas from online convex optimization, we propose a general
framework for the design of efficient securities markets over very large
outcome spaces. The challenge here is computational. In a complete market, in
which one security is offered for each outcome, the market institution can not
efficiently keep track of the transaction history or calculate security prices
when the outcome space is large. The natural solution is to restrict the space
of securities to be much smaller than the outcome space in such a way that
securities can be priced efficiently.

We study {\em bottleneck congestion games} where the social cost is
determined by the worst congestion of any resource. These games directly relate
to network routing problems and also job-shop scheduling problems. In typical
bottleneck congestion games, the utility costs of the players are determined by
the worst congested resources that they use. However, the resulting Nash
equilibria are inefficient, since the price of anarchy is proportional on the
number of resources which can be high. Here we show that we can get smaller
price of anarchy with the bottleneck social cost metric.

Routing games are used to to understand the impact of individual users'
decisions on network efficiency. Most prior work on routing games uses a
simplified model of network flow where all flow exists simultaneously, and
users care about either their maximum delay or their total delay. Both of these
measures are surrogates for measuring how long it takes to get all of a user's
traffic through the network. We attempt a more direct study of how competition
affects network efficiency by examining routing games in a flow over time
model.

Games on graphs with omega-regular objectives provide a natural model for
reactive systems. In this paper, we consider generalized reachability games:
given k subsets of vertices, the objective is to reach one vertex of each
subset. We show that solving generalized reachability games is PSPACE-complete
in general. In the special case where reachability sets are singletons, the
problem becomes polynomial. The case where reachability sets have size 2 is
still open.

In Newcomb's paradox you choose to receive either the contents of a
particular closed box, or the contents of both that closed box and another one.
Before you choose though, an antagonist uses a prediction algorithm to deduce
your choice, and fills the two boxes based on that deduction. Newcomb's paradox
is that game theory's expected utility and dominance principles appear to
provide conflicting recommendations for what you should choose.

Considering the interaction through mutual interference of the different
radio devices, the channel selection (CS) problem in decentralized parallel
multiple access channels can be modeled by strategic-form games. Here, we show
that the CS problem is a potential game (PG) and thus the fictitious play (FP)
converges to a Nash equilibrium (NE) either in pure or mixed strategies.

We present a formal model for studying fashion trends, in terms of three
parameters of fashionable items: (1) their innate utility; (2) individual
boredom associated with repeated usage of an item; and (3) social influences
associated with the preferences from other people. While there are several
works that emphasize the effect of social influence in understanding fashion
trends, in this paper we show how boredom plays a strong role in both
individual and social choices.

Increasing user engagement is constant challenge for Intelligent Tutoring
Systems researchers. A current trend in the ITS field is to increase engagement
of proven learning systems by integrating them within games, or adding in game
like components. Incorporating proven learning methods within a game based
environment is expected to add to the overall experience without detracting
from the original goals, however, the current study demonstrates two important
issues with regard to ITS design. First, effective designs from the physical
world do not always translate into the digital world.

MiBoard (Multiplayer Interactive Board Game) is an online, turn-based board
game, which is a supplement of the iSTART (Interactive Strategy Training for
Active Reading and Thinking) application. MiBoard is developed to test the
hypothesis that integrating game characteristics (point rewards, game-like
interaction, and peer feedback) into the iSTART trainer will significantly
improve its effectiveness on students' learning. It was shown by M. Rowe that a
physical board game did in fact enhance students' performance.

In this paper, inspired by the work of Megiddo on the formation of
preferences and strategic analysis, we consider an early market model studied
in the field of economic theory, in which each trader's utility may be
influenced by the bundles of goods obtained by her social neighbors. The goal
of this paper is to understand and characterize the impact of social influence
on the complexity of computing and approximating market equilibria.

In WiFi networks, mobile nodes compete for accessing a shared channel by
means of a random access protocol called Distributed Coordination Function
(DCF). Although this protocol is in principle fair, since all the stations have
the same probability to transmit on the channel, it has been shown that unfair
behaviors may emerge in actual networking scenarios because of non-standard
configurations of the nodes.

For revenue maximization in single-dimensional Bayesian settings, Chawla et
al. STOC10 [CHMS10] recently showed that sequential posted-price mechanisms
(SPMs), though simple in form, can perform surprisingly well compared to
Myerson's optimal mechanism. In this paper, we show that what underlies SPMs'
good performance is certain submodularity of auctions, and the small
correlation gap of submodular functions.

We design algorithms for computing approximately revenue-maximizing {\em
sequential posted-pricing mechanisms (SPM)} in $K$-unit auctions, in a standard
Bayesian model. A seller has $K$ copies of an item to sell, and there are $n$
buyers, each interested in only one copy, who have some value for the item. The
seller must post a price for each buyer, the buyers arrive in a sequence
enforced by the seller, and a buyer buys the item if its value exceeds the
price posted to it. The seller does not know the values of the buyers, but have
Bayesian information about them.

A longstanding idea in the literature on human cooperation is that
cooperation should be reinforced when conditional cooperators are more likely
to interact. In the context of social networks, this idea implies that
cooperation should fare better in highly clustered networks such as cliques
than in networks with low clustering such as random networks.

We study the properties of Braess's paradox in the context of the model of
congestion games with flow over time introduced by Koch and Skutella. We
compare them to the well known properties of Braess's paradox for Wardrop's
model of games with static flows. We show that there are networks which do not
admit Braess's paradox in Wardrop's model, but which admit it in the model with
flow over time. Moreover, there is a topology that admits a much more severe
Braess's ratio for this model.

We present a direct reduction from k-player games to 2-player games that
preserves approximate Nash equilibrium. Previously, the computational
equivalence of computing approximate Nash equilibrium in k-player and 2-player
games was established via an indirect reduction. This included a sequence of
works defining the complexity class PPAD, identifying complete problems for
this class, showing that computing approximate Nash equilibrium for k-player
games is in PPAD, and reducing a PPAD-complete problem to computing approximate
Nash equilibrium for 2-player games.

We consider the problem of designing truthful auctions, when the bidders'
valuations have a public and a private component. In particular, we consider
combinatorial auctions where the valuation of an agent $i$ for a set $S$ of
items can be expressed as $v_if(S)$, where $v_i$ is a private single parameter
of the agent, and the function $f$ is publicly known. Our motivation behind
studying this problem is two-fold: (a) Such valuation functions arise naturally
in the case of ad-slots in broadcast media such as Television and Radio.

Capacitated Caching (CC) Games are motivated by P2P and web caching
applications, and involve nodes on a network making strategic choices regarding
the content to replicate in their caches. Caching games were introduced by Chun
et al (PODC 2004), who analyzed the uncapacitated case leaving the capacitated
version as an open direction.

Classic decision-theory is based on the maximum expected utility (MEU)
principle, but crucially ignores the resource costs incurred when determining
optimal decisions. Here we propose an axiomatic framework for bounded
decision-making that considers resource costs. Agents are formalized as
probability measures over input-output streams. We postulate that any such
probability measure can be assigned a corresponding conjugate utility function
based on three axioms: utilities should be real-valued, additive and monotonic
mappings of probabilities.

Simulation and bisimulation metrics for stochastic systems provide a
quantitative generalization of the classical simulation and bisimulation
relations. These metrics capture the similarity of states with respect to
quantitative specifications written in the quantitative {\mu}-calculus and
related probabilistic logics. We first show that the metrics provide a bound
for the difference in long-run average and discounted average behavior across
states, indicating that the metrics can be used both in system verification,
and in performance evaluation.

Wireless Sensor Networks (WSN) support data collection and distributed data
processing by means of very small sensing devices that are easy to tamper and
cloning: therefore classical security solutions based on access control and
strong authentication are difficult to deploy. In this paper we look at the
problem of assessing security of node localization.

We consider a market with a set of unit demand buyers and a set of
heterogeneous goods. We assume that the utility of each buyer $i$ from a good
$j$ can be any arbitrary but continuous and decreasing function of price of $j$
and is not necessarily quasi-linear (note that we can model any \emph{smooth
budget constraint} in this form). We give a constructive proof for the
existence of Walrasian equilibria and show that set of Walrasian equilibria
form a complete lattice.

Calibrated strategies can be obtained by performing strategies that have no
internal regret in some auxiliary game. Such strategies can be constructed
explicitly with the use of Blackwell's approachability theorem, in an other
auxiliary game. We establish the converse: a strategy that approaches a convex
$B$-set can be derived from the construction of a calibrated strategy.

The solution of parity games over pushdown graphs (Walukiewicz '96) was the
first step towards an effective theory of infinite-state games. It was shown
that winning strategies for pushdown games can be implemented again as pushdown
automata. We continue this study and investigate the connection between game
presentations and winning strategies in altogether six cases of game arenas,
among them realtime pushdown systems, visibly pushdown systems, and counter
systems.

A Nash equilibrium has become important solution concept for analyzing the
decision making in Game theory. In this paper, we consider the problem of
computing Nash equilibria of a subclass of generic finite normal form games. We
define "rational payoff irrational equilibria games" to be the games with all
rational payoffs and all irrational equilibria. We present a purely algebraic
method for computing all Nash equilibria of these games that uses knowledge of
Galois groups.

We conduct a computational analysis of partitions in additively separable
hedonic games that satisfy standard criteria of fairness and optimality. We
show that computing a partition with maximum egalitarian or utilitarian social
welfare is NP-hard in the strong sense whereas a Pareto optimal partition can
be computed in polynomial time when preferences are strict. Perhaps
surprisingly, \emph{checking} whether a given partition is Pareto optimal is
coNP-complete in the strong sense, even when preferences are symmetric and
strict.

We give a novel proof of the existence of Nash equilibria in all finite games
without using fixed point theorems or path following arguments. Our approach
relies on a new notion intermediate between Nash and correlated equilibria
called exchangeable equilibria, which are correlated equilibria with certain
symmetry and factorization properties. We prove these exist by a duality
argument, using Hart and Schmeidler's proof of correlated equilibrium existence
as a first step.

An evolutionary game-theoretic analysis for a version of the $p$-beauty prize
game is given for the two-player, finite population, and infinite population
cases. Winning strategies are characterized in terms of iterative thinking
relative to the population.

We propose and analyze a broad family of games played by resource-constrained
players, which are characterized by the following central features: 1) each
user has a multi-dimensional action space, subject to a single sum resource
constraint; 2) each user's utility in a particular dimension depends on an
additive coupling between the user's action in the same dimension and the
actions of the other users; and 3) each user's total utility is the sum of the
utilities obtained in each dimension.

Escalation is a typical feature of infinite games. Therefore tools conceived
for studying infinite mathematical structures, namely those deriving from
coinduction are essential. Here we use coinduction, or backward coinduction (to
show its connection with the same concept for finite games) to study carefully
and formally the infinite games especially those called dollar auctions, which
are considered as the paradigm of escalation.

We study bargaining games between suppliers and manufacturers in a network
context. Agents wish to enter into contracts in order to generate surplus which
then must be divided among the participants. Potential contracts and their
surplus are represented by weighted edges in our bipartite network. Each agent
in the market is additionally limited by a capacity representing the number of
contracts which he or she may undertake.

We consider budget constrained combinatorial auctions where bidder $i$ has a
private value $v_i$, a budget $b_i$, and is interested in all the items in
$S_i$. The value to agent $i$ of a set of items $R$ is $|R \cap S_i| \cdot
v_i$. Such auctions capture adword auctions, where advertisers offer a bid for
ads in response to an advertiser-dependent set of adwords, and advertisers have
budgets. It is known that even of all items are identical and all budgets are
public it is not possible to be truthful and efficient.

We introduce a general technique for obtaining approximately optimal truthful
mechanisms implementing general social welfare functions without payments. We
combine a differentially private mechanism, which induces efficiency but does
not guarantee truthfulness, with a probabilistic mechanism that is truthful yet
inefficient. The combined mechanism enjoys the best of both worlds -
truthfulness and efficiency. We demonstrate the applicability of our results
for addressing open problems in facility location and in the pricing of goods.

We consider network contribution games, where each agent in a social network
has a budget of effort that he can contribute to different collaborative
projects. Depending on the contribution of the involved agents a project will
flourish or drown, and to measure the success we use a reward function for each
project. Every agent is trying to maximize the reward from all projects that it
is involved in. We consider pairwise equilibria of this game, and characterize
the existence, computational complexity, and quality of equilibrium based on
the types of reward functions involved.

Social sciences are different in the east and in the west, because of
difference in culture. Indian policeman's dilemma (IPD) represents the internal
conflict between emotion and profession of a typical Indian police officer. It
is a one-person game that has been represented as a two-person game in the
normal form. Here we have proposed a game theoretic model of the conflict,
which is a static game of incomplete information. There are two Nash
equilibrium (NE) points in this game signifying two completely opposing
behavior by the policeman involved.

We analytically study a CSMA-based network with heterogeneous nodes in this
paper. In the network, each nodes has its own throughput demand to a common
base station and the MAC protocol considered is a virtual CSMA by the RTS/CTS
handshake mechanism. Each node individually chooses its probability of sending
a RTS packet, and the probability vector of all nodes will determine the
average throughput and power consumption of each node. The set of all possible
throughput demands of nodes that can be met in the network is called the
feasible throughput region.

We study auctions with additive valuations where agents have a limit on the
number of items they may receive. We refer to this setting as {\em capacitated
allocation games.} We seek truthful and envy free mechanisms that maximize the
social welfare. {\sl I.e.}, where agents have no incentive to lie and no agent
seeks to exchange outcomes with another. In 1983, Leonard showed that VCG with
Clarke Pivot payments (which is known to be truthful, individually rational,
and have no positive transfers), is also an envy free mechanism for the special
case of $n$ items and $n$ unit capacity agents.

We address the problem of fair division, or cake cutting, with the goal of
finding truthful mechanisms. In the case of a general measure space ("cake")
and non-atomic, additive individual preference measures - or utilities - we
show that there exists a truthful "mechanism" which ensures that each of the k
players gets at least 1/k of the cake. This mechanism also minimizes risk for
truthful players. Furthermore, in the case where there exist at least two
different measures we present a different truthful mechanism which ensures that
each of the players gets more than 1/k of the cake.

We show that for many classes of symmetric two-player games, the simple
decision rule "imitate-the-best" can hardly be beaten by any other decision
rule. We provide necessary and sufficient conditions for imitation to be
unbeatable and show that it can only be beaten by much in games that are of the
rock-scissors-paper variety.

The adoption of market-based principles in resource management systems for
computational infrastructures such as grids and clusters allows for matching
demand and supply for resources in a utility maximizing manner. As such, they
offer a promise of producing more efficient resource allocations, compared to
traditional system-centric approaches that do not allow consumers and providers
to express their valuations for computational resources.

We study strategy improvement algorithms for mean-payoff and parity games. We
describe a structural property of these games, and we show that these
structures can affect the behaviour of strategy improvement. We show how
awareness of these structures can be used to accelerate strategy improvement
algorithms. We call our algorithms non-oblivious because they remember
properties of the game that they have discovered in previous iterations. We
show that non-oblivious strategy improvement algorithms perform well on
examples that are known to be hard for oblivious strategy improvement.

We study two-player security games which can be viewed as sequences of
nonzero-sum matrix games played by an Attacker and a Defender. The evolution of
the game is based on a stochastic fictitious play process. Players do not have
access to each other's payoff matrix. Each has to observe the other's actions
up to present and plays the action generated based on the best response to
these observations.

We present a new model for reasoning about the way information is shared
among friends in a social network, and the resulting ways in which it spreads.
Our model formalizes the intuition that revealing personal information in
social settings involves a trade-off between the benefits of sharing
information with friends, and the risks that additional gossiping will
propagate it to people with whom one is not on friendly terms.

The Nash equilibrium point of the transmission probabilities in a slotted
ALOHA system with selfish nodes is analyzed. The system consists of a finite
number of heterogeneous nodes, each trying to minimize its average transmission
probability (or power investment) selfishly while meeting its average
throughput demand over the shared wireless channel to a common base station
(BS). We use a game-theoretic approach to analyze the network under two
reception models: one is called power capture, the other is called signal to
interference plus noise ratio (SINR) capture.

It is frequently suggested that predictions made by game theory could be
improved by considering computational restrictions when modeling agents. Under
the supposition that players in a game may desire to balance maximization of
payoff with minimization of strategy complexity, Rubinstein and co-authors
studied forms of Nash equilibrium where strategies are maximally simplified in
that no strategy can be further simplified without sacrificing payoff.

We investigate the power of randomness in the context of a fundamental
Bayesian optimal mechanism design problem--a single seller aims to maximize
expected revenue by allocating multiple kinds of resources to "unit-demand"
agents with preferences drawn from a known distribution. When the agents'
preferences are single-dimensional Myerson's seminal work [Myerson '81] shows
that randomness offers no benefit--the optimal mechanism is always
deterministic.

The existing literature on Bayesian optimal auctions focuses on optimizing
the \emph{expected revenue} of the seller, and is appropriate for risk-neutral
sellers. In this paper, we identify good mechanisms for \emph{risk-averse}
sellers. As is standard in the economics literature, we model the risk-aversion
of a seller by endowing the seller with a monotone, concave utility function.
We then seek robust mechanisms that are universally approximately optimal for
all sellers, no matter what their levels of risk-aversion are.

This paper presents a technique for approximating, up to any precision, the
set of subgame-perfect equilibria (SPE) in discounted repeated games. The
process starts with a single hypercube approximation of the set of SPE. Then
the initial hypercube is gradually partitioned on to a set of smaller adjacent
hypercubes, while those hypercubes that cannot contain any point belonging to
the set of SPE are simultaneously withdrawn.

Iterated regret minimization has been introduced recently by J.Y. Halpern and
R. Pass in classical strategic games. For many games of interest, this new
solution concept provides solutions that are judged more reasonable than
solutions offered by traditional game concepts -- such as Nash equilibrium --.
Although computing iterated regret on explicit matrix game is conceptually and
computationally easy, nothing is known about computing the iterated regret on
games whose matrices are defined implicitly using game tree, game DAG or, more
generally game graphs.

Auctions play an important role in electronic commerce, and have been used to
solve problems in distributed computing. Automated approaches to designing
effective auction mechanisms are helpful in reducing the burden of traditional
game theoretic, analytic approaches and in searching through the large space of
possible auction mechanisms. This paper presents an approach to automated
mechanism design (AMD) in the domain of double auctions. We describe a novel
parametrized space of double auctions, and then introduce an evolutionary
search method that searches this space of parameters.

We consider the problem of revenue-optimal dynamic mechanism design in
settings where agents' types evolve over time as a function of their (both
public and private) experience with items that are auctioned repeatedly over an
infinite horizon. A central question here is understanding what natural
restrictions on the environment permit the design of optimal mechanisms (note
that even in the simpler static setting, optimal mechanisms are characterized
only under certain restrictions).

Within the context of games on networks S. Goyal [1, pg. 39] posed the
following problem. Under any arbitrary but fixed topology, does there exist at
least one pure Nash equilibrium that exhibits a positive relation between the
cardinality of a player's set of neighbors and its utility payoff? In this
paper we present a class of topologies in which pure Nash equilibria with the
above property do not exist.

Two-player zero-sum games are a well-established model for synthesising
controllers that optimise some performance criterion. In such games one player
represents the controller, while the other describes the (adversarial)
environment, and controller synthesis corresponds to computing the optimal
strategies of the controller for a given criterion. Asarin and Maler initiated
the study of quantitative games on (non-probabilistic) timed automata by
synthesising controllers which optimise the time to reach a final state.

We study the design of truthful mechanisms that do not use payments for the
generalized assignment problem (GAP) and its variants. An instance of the GAP
consists of a bipartite graph with jobs on one side and machines on the other.
Machines have capacities and edges have values and sizes; the goal is to
construct a welfare maximizing feasible assignment. In our model of private
valuations, motivated by impossibility results, the value and sizes on all
job-machine pairs are public information; however, whether an edge exists or
not in the bipartite graph is a job's private information.

This paper derives a model of screening contracts in the presence of positive
network effects when building an electronic commerce network (e-commerce)
between a large firm and a small and medium sized enterprise (SME) supplier
based on Compte (2008). Compte (2008) main insight is that when several
potential candidates compete for the task, the principal will in general
improve the performance of his firm by inducing the member candidates to assess
their competence before signing the contract (through an appropriate choice of
contracts).

If a two-player social welfare maximization problem does not admit a PTAS, we
prove that any maximal-in-range truthful mechanism that runs in polynomial time
cannot achieve an approximation factor better than 1/2. Moreover, for the
k-player version of the same problem, the hardness of approximation improves to
1/k under the same two-player hardness assumption.

This paper proposes the Potluck Problem as a model for the behavior of
independent producers and consumers under standard economic assumptions, as a
problem of resource allocation in a multi-agent system in which there is no
explicit communication among the agents.

The fundamental laws of quantum world upsets the logical foundation of
classic physics. They are completely counter-intuitive with many bizarre
behaviors. However, this paper shows that they may make sense from the
perspective of a general decision-optimization principle for cooperation. This
principle also offers a generalization of Nash equilibrium, a key concept in
game theory, for better payoffs and stability of game playing.

We consider the online linear programming problem where the constraint matrix
is revealed column by column along with the objective function. We provide a
1-o(1) competitive algorithm for this surprisingly general class of online
problems under the assumption of random order of arrival and some mild
conditions on the right-hand-side input. Our learning-based algorithm works by
dynamically updating a threshold price vector at geometric time intervals, the
price learned from the previous steps is used to determine the decision for the
current step.

We consider massively dense ad hoc networks and study their continuum limits
as the node density increases and as the graph providing the available routes
becomes a continuous area with location and congestion dependent costs. We
study both the global optimal solution as well as the non-cooperative routing
problem among a large population of users where each user seeks a path from its
origin to its destination so as to minimize its individual cost. Finally, we
seek for a (continuum version of the) Wardrop equilibrium.

In this paper we consider an extension to the classical definition of
congestion games (CG) in which multiple users share the same set of resources
and their payoff for using any resource is a function of the total number of
users sharing it. The classical congestion games enjoy some very appealing
properties, including the existence of a Nash equilibrium and that every
improvement path is finite and leads to such a NE (also called the finite
improvement property or FIP), which is also a local optimum to a potential
function.

An average-time game is played on the infinite graph of configurations of a
finite timed automaton. The two players, Min and Max, construct an infinite run
of the automaton by taking turns to perform a timed transition. Player Min
wants to minimise the average time per transition and player Max wants to
maximise it. A solution of average-time games is presented using a reduction to
average-price game on a finite graph. A direct consequence is an elementary
proof of determinacy for average-time games.

In this paper, we present the first approximation algorithms for the
celebrated problem of designing revenue optimal Bayesian incentive compatible
auctions when there are multiple (heterogeneous) items and when bidders can
have arbitrary demand and budget constraints. Our mechanisms are surprisingly
simple: We show that a sequential all-pay mechanism is a 4 approximation to the
revenue of the optimal ex-interim truthful mechanism with discrete correlated
type space for each bidder.

Zoonosis refers to the transmission of infectious diseases from animal to
human. The increasing number of zoonosis incidence makes the great losses to
lives, including humans and animals, and also the impact in social economic. It
motivates development of a system that can predict the future number of
zoonosis occurrences in human. This paper analyses and presents the use of
Seasonal Autoregressive Integrated Moving Average (SARIMA) method for
developing a forecasting model that able to support and provide prediction
number of zoonosis human incidence.

Stackelberg Pricing Games is a two-level combinatorial pricing problem
studied in the Economics, Operation Research, and Computer Science communities.
In this paper, we consider the decade-old shortest path version of this problem
which is the first and most studied problem in this family.

The performance of two pivoting algorithms, due to Lemke and Cottle and
Dantzig, is studied on linear complementarity problems (LCPs) that arise from
infinite games, such as parity, average-reward, and discounted games. The
algorithms have not been previously studied in the context of infinite games,
and they offer alternatives to the classical strategy-improvement algorithms.
The two algorithms are described purely in terms of discounted games, thus
bypassing the reduction from the games to LCPs, and hence facilitating a better
understanding of the algorithms when applied to games.

We consider the problem of maximizing the probability of hitting a
strategically chosen hidden virtual network by placing a wiretap on a single
link of a communication network. This can be seen as a two-player win-lose
(zero-sum) game that we call the wiretap game. The value of this game is the
greatest probability that the wiretapper can secure for hitting the virtual
network. The value is shown to equal the reciprocal of the strength of the
underlying graph.

We present a new methodology for computing approximate Nash equilibria for
two-person non-cooperative games based upon certain extensions and
specializations of an existing optimization approach previously used for the
derivation of fixed approximations for this problem. In particular, the general
two-person problem is reduced to an indefinite quadratic programming problem of
special structure involving the $n \times n$ adjacency matrix of an induced
simple graph specified by the input data of the game, where $n$ is the number
of players' strategies.

We present an incentive model for route distribution in the context of path
vector routing protocols and we focus on the Border Gateway Protocol (BGP). BGP
is the de-facto protocol for interdomain routing on the Internet. We model BGP
route distribution and computation using a game in which a BGP speaker
advertises its prefix to its direct neighbors promising them a reward for
further distributing the route deeper into the network, the neighbors do the
same thing with their neighbors, and so on.

The Stackelberg Minimum Spanning Tree Game is a two-level combinatorial
pricing problem introduced at WADS'07. The game is played on a graph
(representing a network), whose edges are colored either red or blue, and where
the red edges have a given fixed cost (representing the competitor's prices).
The first player chooses an assignment of prices to the blue edges, and the
second player then buys the cheapest spanning tree, using any combination of
red and blue edges. The goal of the first player is to maximize the total price
of purchased blue edges.

We study the computational complexity of central analysis problems for
One-Counter Markov Decision Processes (OC-MDPs), a class of finitely-presented,
countable-state MDPs. OC-MDPs are equivalent to a controlled extension of
(discrete-time) Quasi-Birth-Death processes (QBDs), a stochastic model studied
heavily in queueing theory and applied probability. They can thus be viewed as
a natural ``adversarial'' version of a classic stochastic model. Alternatively,
they can also be viewed as a natural probabilistic/controlled extension of
classic one-counter automata.

We study envy-free mechanisms for scheduling tasks on unrelated machines
(agents) that approximately minimize the makespan. For indivisible tasks, we
put forward an envy-free poly-time mechanism that approximates the minimal
makespan to within a factor of $O(\log m)$, where $m$ is the number of
machines. We also show a lower bound of $\Omega(\log m / \log\log m)$. This
improves the recent result of Hartline {\sl et al.} \cite{Ahuva:2008} who give
an upper bound of $(m+1)/2$, and a lower bound of $2-1/m$.