|
1. Dov Monderer, Multipotential
Games We
introduce and analyze q-potential games and q-congestion games, where q is a
positive integer. A 1-potential (congestion) game is a potential (congestion)
game. We show that a game is a q-potential game if and only if it is (up to
an isomorphism) a q-congestion game. As a corollary we derive the result that
every game in strategic form is a q-congestion game for some q. It is further
shown that every q-congestion game is isomorphic to a q-network game, where
the network environment is defined by a directed graph with one origin and
one destination. In addition we discuss the issue of representing
q-congestion games with non-negative cost functions by congestion models with
non-negative and monotonic facility cost functions. |
|
Yakar Kannai, Strategic Behavior in Financial
Markets We
describe a financial market as a non-cooperative game in strategic form.
Agents may borrow or deposit money at a central bank and use the cash
available to them in order to purchase a commodity for immediate consumption.
They derive positive utility from consumption and from having cash reserves
at the end of the day, whereas being bankrupt entails negative utility. The
bank fixes interest rates. The existence of Nash equilibria
(both mixed and pure) of the ensuing is proved under various assumptions. In
particular, no agent is bankrupt at equilibrium. |
|
Uri
Rothblum, A Case Study of the Assignment of Students to Dormitories
Using a Stable Matching Model with an Entrance Criterion In
this paper we report a case study of the assignment of students to dormitories
at the Technion - Israel Institute of Technology.
Two criteria are applied: first, the privilege of getting on-campus housing
is determined by personal socio-economic parameters, and second, the priority
in the assignment of the students who gained on-campus housing privilege to
specific dorms is determined by academic seniority and academic excellence. A
modification of the classic stable matching model that allows for an
"entrance criterion" is developed and analyzed, including the
description of an algorithm which produces a stable outcome and a
characterization of the output of this algorithm. The algorithm was
implemented successfully for the assignment of students to dormitories at the
Technion toward the 2004/5 academic year. |
|
Alan
Miller, Separability in Group Identification We
study a model of group identification in which individuals’ opinions as to
the membership of a group are aggregated to form a list of the group’s
members. Potential aggregation rules are studied through the axiomatic
approach. We introduce two axioms, meet separability
and join separability, each of which requires the
list of members generated by the aggregation rule to be independent of
whether the question of membership in a group is separated into questions of
membership in two other groups. We use these axioms to characterize a class
of "one vote" rules, in which one opinion determines whether an
individual is considered to be a member of a group. We then use this
characterization to provide new axiomatizations of
the liberal rule, in which each individual determines for himself whether he
is a member of the group, as the only non-degenerate anonymous rule
satisfying the meet separability and join separability axioms. |
|
Elad Dokow, Aggregation of Binary Evaluations
We
study a general aggregation problem in which a society has to determine its
position (yes/no) 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. This
framework for the theory of aggregation was introduced by Wilson and further
developed by Rubinstein and Fishburn. Among other
things, it admits the modelling of preference
aggregation (where the issues are pairwise
comparisons and feasibility reflects rationality), and of judgment
aggregation (where the issues are propositions and feasibility reflects
logical consistency). We characterize those sets of feasible evaluations for
which the natural analogue of Arrow’s impossibility theorem holds true in
this framework. |
|
Amir Ronen, Prediction Games We
introduce a new class of mechanism design problems called prediction games.
There are n self interested agents. Each agent i
has a private input xi and a cost of accessing it. Given are a function f(x1,
. . . , xn) which predicts whether a certain event
will occur and an independent distribution on the agents’ inputs. Agents can
be rewarded in order to motivate them to access their inputs. The goal is to
design a mechanism (protocol) which in equilibrium predicts f(.) and pays in
expectation as little as possible. We investigate both, exact and approximate
versions of the problem and provide several upper and lower bounds. In
particular, we construct an optimal mechanism for every anonymous function
and show that any function can be approximated with a relatively small
payment. |
|
Itai Ashlagi, Resource Selection Games with
Unknown Number of Players In the
context of pre-Bayesian games we analyze resource selection systems with
unknown number of players. We prove the existence and uniqueness of symmetric
safety-level equilibrium in such games and show that in a linear model every
player benefits from the common ignorance about the number of players. In
order to analyze such games we generalize the theory of equilibrium in
general pre-Bayesian games. |
|
Eddie
Dekel, Non-Bayesian Testing of an Expert We
suggest a test for discovering whether a potential expert is informed of the
distribution of a stochastic process. In a non-Bayesian non-parametric
setting, the expert is asked to make a prediction which is tested against a
single realization of the stochastic process. It is shown that by testing the
expert with a “small” set of sequences, the test will assure that any
informed expert can pass the test with probability one with respect to the
actual distribution. Moreover, for the uninformed non-expert it is very
difficult to pass this test, in the sense that for any choice of a “small” set
of sequences, only a “small” set of measures will assign positive probability
to the given set. This technical result may in fact be of independent
interest. Hence “most” measures that a non-expert may predict will lead the
non-expert to fail the test. We define small as category 1 sets, described in
more detail in the paper. A
Category Test that Cannot be Manipulated In Dekel and Feinberg (2004) we
suggested a test for discovering whether a potential expert is informed of
the distribution of a stochastic process. This category test requires
predicting a category I set of outcomes. In this paper we show that under the
continuum hypothesis there is a category test that cannot be manipulated, i.e.,
such that no matter how the potential expert randomizes his prediction, there
will be realizations where he will fail to pass the test with probability 1. The
set of realizations where he fails can be made large a category II set. Moreover,
this result holds for the finite approximations of the category test where
the non-expert is failed in finite time and the expert is failed with small
probability. |
|
Joel
Guttman, Public Good Contributions, Signalling,
and the Evolution of Trust This
paper develops a theory of the evolution of preferences for honesty, trust,
and the voluntary provision of public goods in a society composed exclusively
of rational, Bayesian optimisers. Unlike
conventional evolutionary models, player types are not defined by their
strategies, but rather (as in standard economic theory) by their preferences.
Thus agents do not play fixed, .wired-in. strategies, but rather choose
strategies that maximise their expected utilities.
In each stage of his or her career, an agent decides (a) whether to honour trust in a bilateral market transaction, and (b)
whether to contribute to the provision of a non-excludable public good. We
study the evolution of a community consisting of ‘opportunists’, who simply maximise material payoffs, and ‘honest types’, who prefer
to honour trust and contribute to the provision of
public goods. While individual interactions are one-shot, agents know the
history of play of all others in the community. In equilibrium, opportunists
contribute (with positive probability) to the provision of the public good in
order to maintain reputations for being honest types, so as to be trusted in
their market transactions over the course of their careers. A novel result of
the model is that the presence of a public good enhances the evolutionary
stability of the honest type. |
|
Bezalel Peleg, Nash Consistent Representation
of Effectivity Functions Through Lottery Models
Effectivity functions for finitely many players and alternatives are
considered. It is shown that every monotonic and superadditive
effectivity function can be augmented with equal
chance lotteries to a finite lottery model - i.e., an effectivity
function that preserves the original effectivity in
terms of supports of lotteries - which has a Nash consistent representation.
In other words, there exists a finite game form which represents the lottery
model and which has a Nash equilibrium for any profile of utility functions,
where lotteries are evaluated by their expected utility. No additional
condition on the original effectivity function is
needed. |
|
Igal Milchtaich, The Equilibrium Existence
Problem in Finite Network Congestion Games An
open problem is presented related to the existence of pure strategy Nash
equilibrium (PNE) in network congestion games with
a finite number of non-identical players. In a network congestion game, the
strategy set of each player is the collection of all paths in a given network
that link the player’s origin and destination vertices. Choosing a path r creates
negative externalities for the other players whose paths have one or more
(directed) edges in common with r, since congestion increases the
costs of edges. The players’ choice of paths constitute a PNE
if, for each of them, an alternative path with a lower cost does not exist. A
network congestion game in which the players differ only in their
origin–destination pairs is a potential game (Rosenthal, 1973, International
Journal of Game Theory 2, 65–67; Monderer
and Shapley, 1996, Games and Economic Behavior 14,
124–143), which implies that, regardless of the exact functional form of the
cost functions, it has a PNE. A PNE
does not necessarily exist if players differ in (i)
the magnitude of the effect of congestion on the cost of each edge or (ii)
their contributions to it (Milchtaich, 1996, Games
and Economic Behavior 13, 111–124). In case (i),
the dependence of the cost of each edge on the number of users is player- as
well as edge-specific. In (ii), the cost is not player-specific (although it
may depend on the edge) but it is a function, not of the number of players
using the edge, but of their total weight, with each player i having a different weight wi.
In a network with parallel edges, in which the origin and the destination are
the only vertices two different paths have in common, a PNE
is known to exist even if the players differ in one of these aspects, but not
if they differ in both. However, for general network topologies, examples are
known, both for case (i) (Konishi,
2004, Transportation Science 38, 315–330) and for (ii) (Libman and Orda, 2001, Telecommunication
Systems 17, 385–409; Fotakis et al.,
2004, in Proceedings of the 31st International Colloquium on Automata,
Languages and Programming, 593–605), in which a PNE
does not exist. The problem is to characterize of the class of all network
topologies for which the existence of a PNE is
guaranteed even with player-specific costs, and the corresponding class for
player-specific weights. Some progress is solving this open problem is
reported. |
|
Eilon Solan, On a Markov Game with Incomplete
Information We
consider an example of a Markov game with lack of information on one side, that
was first introduced by Renault (2002). We compute both the value and optimal
strategies for a range of parameter values. |
|
Yuval
Heller, A
Minority-Proof Cheap-Talk Protocol Playing
a correlated strategy in a game requires a fair mediator that confidentially
receives some information from the players (their types), makes a secret
lottery and privately recommends each player how to play. In this paper we
deal with the question whether it is possible to play a correlated strategy
without a mediator, using only “cheap-talk” (non-binding, non-verifiable
communication without any influence on payoffs), in a way which is
“resistant” to coordinated deviations of sub-coalitions. Our main result
shows a general “cheap-talk” protocol that can implement any correlation, and
is resistant to coordinated deviations of any minority. Furthermore, we show
that this protocol is optimal, in the sense that there is no general
“cheap-talk” protocol that is resistant to deviations of half of the players.
|