
We introduce the problem of assigning resources to improve their utilization.
The motivation comes from settings where agents have uncertainty about their
own values for using a resource, and where it is in the interest of a group
that resources be used and not wasted. Done in the right way, improved
utilization maximizes social welfare balancing the utility of a high value
but unreliable agent with the group's preference that resources be used. We
introduce the family of contingent payment mechanisms (CP), which may charge an
agent contingent on use (a penalty). A CP mechanism is parameterized by a
maximum penalty, and has a dominantstrategy equilibrium. Under a set of
axiomatic properties, we establish welfareoptimality for the special case
CP(W), with CP instantiated for a maximum penalty equal to societal value W for
utilization. CP(W) is not dominated for expected welfare by any other
mechanism, and second, amongst mechanisms that always allocate the resource and
have a simple indirect structure, CP(W) strictly dominates every other
mechanism. The special case with no upper bound on penalty, the contingent
secondprice mechanism, maximizes utilization. We extend the mechanisms to
assign multiple, heterogeneous resources, and present a simulation study of the
welfare properties of these mechanisms.

Richman games are zerosum games, where in each turn players bid in order to
determine who will play next [Lazarus et al.'99]. We extend the theory to
impartial generalsum two player games called \emph{bidding games}, showing the
existence of pure subgameperfect equilibria (PSPE). In particular, we show
that PSPEs form a semilattice, with a unique and natural \emph{Bottom
Equilibrium}.
Our main result shows that if only two actions available to the players in
each node, then the Bottom Equilibrium has additional properties: (a) utilities
are monotone in budget; (b) every outcome is Paretoefficient; and (c) any
Paretoefficient outcome is attained for some budget.
In the context of combinatorial bargaining, we show that a player with a
fraction of X% of the total budget prefers her allocation to X% of the possible
allocations. In addition, we provide a polynomialtime algorithm to compute the
Bottom Equilibrium of a binary bidding game.

Without monetary payments, the GibbardSatterthwaite theorem proves that
under mild requirements all truthful social choice mechanisms must be
dictatorships. When payments are allowed, the VickreyClarkeGroves (VCG)
mechanism implements the valuemaximizing choice, and has many other good
properties: it is strategyproof, onto, deterministic, individually rational,
and does not make positive transfers to the agents. By Roberts' theorem, with
three or more alternatives, the weighted VCG mechanisms are essentially unique
for domains with quasilinear utilities. The goal of this paper is to
characterize domains of nonquasilinear utilities where "reasonable"
mechanisms (with VCGlike properties) exist. Our main result is a tight
characterization of the maximal non quasilinear utility domain, which we call
the largest parallel domain. We extend Roberts' theorem to parallel domains,
and use the generalized theorem to prove two impossibility results. First, any
reasonable mechanism must be dictatorial when the utility domain is
quasilinear together with any single nonparallel type. Second, for richer
utility domains that still differ very slightly from quasilinearity, every
strategyproof, onto and deterministic mechanism must be a dictatorship.

The robustness of multiagent systems can be affected by mistakes or
behavioral biases (e.g., riskaversion, altruism, tollsensitivity), with some
agents playing the "wrong game." This can change the set of equilibria, and may
in turn harm or improve the social welfare of agents in the system. We are
interested in bounding what we call the biased price of anarchy (BPoA) in
populations with diverse agent behaviors, which is the ratio between welfare in
the "wrong" equilibrium and optimal welfare.
We study nonatomic routing games, and derive an externality bound that
depends on a key topological parameter of the underlying network.
We then prove two general BPoA bounds for games with diverse populations: one
that relies on the network structure and the average bias of all agents in the
population, and one that is independent of the structure but depends on the
maximal bias. Both types of bounds can be combined with known results to derive
concrete BPoA bounds for a variety of specific behaviors (e.g., varied levels
of riskaversion).

Power companies such as Southern California Edison (SCE) uses Demand Response
(DR) contracts to incentivize consumers to reduce their power consumption
during periods when demand forecast exceeds supply. Current mechanisms in use
offer contracts to consumers independent of one another, do not take into
consideration consumers' heterogeneity in consumption profile or reliability,
and fail to achieve high participation.
We introduce DRVCG, a new DR mechanism that offers a flexible set of
contracts (which may include the standard SCE contracts) and uses VCG pricing.
We prove that DRVCG elicits truthful bids, incentivizes honest preparation
efforts, enables efficient computation of allocation and prices. With simple
fixedpenalty contracts, the optimization goal of the mechanism is an upper
bound on probability that the reduction target is missed. Extensive simulations
show that compared to the current mechanism deployed in by SCE, the DRVCG
mechanism achieves higher participation, increased reliability, and
significantly reduced total expenses.

We put forward a new model of congestion games where agents have uncertainty
over the routes used by other agents. We take a nonprobabilistic approach,
assuming that each agent knows that the number of agents using an edge is
within a certain range. Given this uncertainty, we model agents who either
minimize their worstcase cost (WCC) or their worstcase regret (WCR), and
study implications on equilibrium existence, convergence through adaptive play,
and efficiency. Under the WCC behavior the game reduces to a modified
congestion game, and welfare improves when agents have moderate uncertainty.
Under WCR behavior the game is not, in general, a congestion game, but we show
convergence and efficiency bounds for a simple class of games.

We consider a social choice problem where only a small number of people out
of a large population are sufficiently available or motivated to vote. A common
solution to increase participation is to allow voters use a proxy, that is,
transfer their voting rights to another voter. Considering social choice
problems on metric spaces, we compare voting with and without the use of
proxies to see which mechanism better approximates the optimal outcome, and
characterize the regimes in which proxy voting is beneficial. When voters'
opinions are located on an interval, both the median mechanism and the mean
mechanism are substantially improved by proxy voting. When voters vote on many
binary issues, proxy voting is better when the sample of active voters is too
small to provide a good outcome. Our theoretical results extend to situations
where available voters choose strategically whether to participate. We support
our theoretical findings with empirical results showing substantial benefits of
proxy voting on simulated and real preference data.

Consider Plurality with random tiebreaking. This paper uses standard
axiomatic extensions of preferences over elements to preferences over sets
(Kelly, Gardenfors, Responsiveness) to characterize all betterreplies of a
voter under stochastic dominance.

We consider iterative voting models and position them within the general
framework of acyclic games and game forms. More specifically, we classify
convergence results based on the underlying assumptions on the agent scheduler
(the order of players) and the action scheduler (which betterreply is played).
Our main technical result is providing a complete picture of conditions for
acyclicity in several variations of Plurality voting. In particular, we show
that (a) under the traditional lexicographic tiebreaking, the game converges
for any order of players under a weak restriction on voters' actions; and (b)
Plurality with randomized tiebreaking is not guaranteed to converge under
arbitrary agent schedulers, but from any initial state there is \emph{some}
path of betterreplies to a Nash equilibrium. We thus show a first separation
between restrictedacyclicity and weakacyclicity of game forms, thereby
settling an open question from [Kukushkin, IJGT 2011]. In addition, we refute
another conjecture regarding stronglyacyclic voting rules.

We consider a recent innovative theory by Chastain et al. on the role of sex
in evolution [PNAS'14]. In short, the theory suggests that the evolutionary
process of gene recombination implements the celebrated multiplicative weights
updates algorithm (MWUA). They prove that the population dynamics induced by
sexual reproduction can be precisely modeled by genes that use MWUA as their
learning strategy in a particular coordination game. The result holds in the
environments of \emph{weak selection}, under the assumption that the population
frequencies remain a product distribution.
We revisit the theory, eliminating both the requirement of weak selection and
any assumption on the distribution of the population. Removing the assumption
of product distributions is crucial, since as we show, this assumption is
inconsistent with the population dynamics. We show that the marginal allele
distributions induced by the population dynamics precisely match the marginals
induced by a multiplicative weights update algorithm in this general setting,
thereby affirming and substantially generalizing these earlier results.
We further revise the implications for convergence and utility or fitness
guarantees in coordination games. In contrast to the claim of Chastain et
al.[PNAS'14], we conclude that the sexual evolutionary dynamics does not entail
any property of the population distribution, beyond those already implied by
convergence.

Understanding the nature of strategic voting is the holy grail of social
choice theory, where gametheory, social science and recently computational
approaches are all applied in order to model the incentives and behavior of
voters.
In a recent paper, Meir et al.[EC'14] made another step in this direction, by
suggesting a behavioral gametheoretic model for voters under uncertainty. For
a specific variation of bestresponse heuristics, they proved initial existence
and convergence results in the Plurality voting system.
In this paper, we extend the model in multiple directions, considering voters
with different uncertainty levels, simultaneous strategic decisions, and a more
permissive notion of bestresponse. We prove that a voting equilibrium exists
even in the most general case. Further, any society voting in an iterative
setting is guaranteed to converge.
We also analyze an alternative behavior where voters try to minimize their
worstcase regret. We show that the two behaviors coincide in the simple
setting of Meir et al., but not in the general case.

It is well known that no reasonable voting rule is strategyproof. Moreover,
the common Plurality rule is particularly prone to strategic behavior of the
voters and empirical studies show that people often vote strategically in
practice. Multiple gametheoretic models have been proposed to better
understand and predict such behavior and the outcomes it induces. However,
these models often make unrealistic assumptions regarding voters' behavior and
the information on which they base their vote.
We suggest a new model for strategic voting that takes into account voters'
bounded rationality, as well as their limited access to reliable information.
We introduce a simple behavioral heuristic based on \emph{local dominance},
where each voter considers a set of possible world states without assigning
probabilities to them. This set is constructed based on prospective candidates'
scores (e.g., available from an inaccurate poll). In a \emph{voting
equilibrium}, all voters vote for candidates not dominated within the set of
possible states.
We prove that these voting equilibria exist in the Plurality rule for a broad
class of local dominance relations (that is, different ways to decide which
states are possible). Furthermore, we show that in an iterative setting where
voters may repeatedly change their vote, local dominancebased dynamics quickly
converge to an equilibrium if voters start from the truthful state. Weaker
convergence guarantees in more general settings are also provided.
Using extensive simulations of strategic voting on generated and real
preference profiles, we show that convergence is fast and robust, that emerging
equilibria are consistent across various starting conditions, and that they
replicate widely known patterns of human voting behavior such as Duverger's
law. Further, strategic voting generally improves the quality of the winner
compared to truthful voting.

We study competition between firms in labor markets, following a
combinatorial model suggested by Kelso and Crawford [1982]. In this model, each
firm is trying to recruit workers by offering a higher salary than its
competitors, and its production function defines the utility generated from any
actual set of recruited workers. We define two natural classes of production
functions for firms, where the first one is based on additive capacities
(weights), and the second on the influence of workers in a social network. We
then analyze the existence of pure subgame perfect equilibrium (PSPE) in the
labor market and its properties. While neither class holds the gross
substitutes condition, we show that in both classes the existence of PSPE is
guaranteed under certain restrictions, and in particular when there are only
two competing firms. As a corollary, there exists a Walrasian equilibrium in a
corresponding combinatorial auction, where bidders' valuation functions belong
to these classes.
While a PSPE may not exist when there are more than two firms, we perform an
empirical study of equilibrium outcomes for the case of weightbased games with
three firms, which extend our analytical results. We then show that stability
can in some cases be extended to coalitional stability, and study the
distribution of profit between firms and their workers in weightbased games.

Cooperative games model the allocation of profit from joint actions,
following considerations such as stability and fairness. We propose the
reliability extension of such games, where agents may fail to participate in
the game. In the reliability extension, each agent only "survives" with a
certain probability, and a coalition's value is the probability that its
surviving members would be a winning coalition in the base game. We study
prominent solution concepts in such games, showing how to approximate the
Shapley value and how to compute the core in games with few agent types. We
also show that applying the reliability extension may stabilize the game,
making the core nonempty even when the base game has an empty core.

We introduce a measure for the level of stability against coalitional
deviations, called \emph{stability scores}, which generalizes widely used
notions of stability in noncooperative games. We use the proposed measure to
compare various Nash equilibria in congestion games, and to quantify the effect
of game parameters on coalitional stability. For our main results, we apply
stability scores to analyze and compare the Generalized Second Price (GSP) and
VickreyClarkeGroves (VCG) ad auctions. We show that while a central result of
the ad auctions literature is that the GSP and VCG auctions implement the same
outcome in one of the equilibria of GSP, the GSP outcome is far more stable.
Finally, a modified version of VCG is introduced, which is group
strategyproof, and thereby achieves the highest possible stability score.

A key question in cooperative game theory is that of coalitional stability,
usually captured by the notion of the \emph{core}the set of outcomes such
that no subgroup of players has an incentive to deviate. However, some
coalitional games have empty cores, and any outcome in such a game is unstable.
In this paper, we investigate the possibility of stabilizing a coalitional
game by using external payments. We consider a scenario where an external
party, which is interested in having the players work together, offers a
supplemental payment to the grand coalition (or, more generally, a particular
coalition structure). This payment is conditional on players not deviating from
their coalition(s). The sum of this payment plus the actual gains of the
coalition(s) may then be divided among the agents so as to promote stability.
We define the \emph{cost of stability (CoS)} as the minimal external payment
that stabilizes the game.
We provide general bounds on the cost of stability in several classes of
games, and explore its algorithmic properties. To develop a better intuition
for the concepts we introduce, we provide a detailed algorithmic study of the
cost of stability in weighted voting games, a simple but expressive class of
games which can model decisionmaking in political bodies, and cooperation in
multiagent settings. Finally, we extend our model and results to games with
coalition structures.