|
Description
We study the notion of excludability in repeated games with vector payoffs, when one of the players is restricted to strategies with bounded computational capacity. We show that a closed set is excludable by Player 2 when Player 1 is restricted to using only bounded-recall strategies if and only if it does not contain a convex approachable set. We provide partial results when Player 1 is restricted to using strategies that can be implemented by automata.
Key words: repeated games; vector payoffs; Blackwell's approachability; excludability; bounded-recall strategies; finite automata
MSC2000 subject classification: Primary: 91A20, 91A05
OR/MS subject classification: Primary: games/group decisions; secondary: noncooperative
History: Received September 9, 2003; revised March 15, 2005, and November 2, 2005.
1. Introduction. In a seminal paper, Blackwell [2] introduced and studied the notions of approachability and excludability in repeated games with vector payoffs. These notions are analogues to the max-min and the min-max levels in repeated games with scalar payoffs.
In repeated games with vector payoffs the outcome of players' actions is not a scalar utility for each player, but rather a vector in some Euclidean space. A set of vectors is approachable by Player 1 if he has a strategy that guarantees, with arbitrarily high probability, that the average (vector) payoff is asymptotically close to the set, regardless of the strategy employed by Player 2. A set is excludable by Player 2 if she has a strategy that guarantees, with arbitrarily high probability, that the average payoff is asymptotically bounded away from the set, regardless of the strategy used by Player 1.
Blackwell [2] provided a geometric condition that guarantees that a set is approachable, and proved that any convex set is either approachable by Player 1, or excludable by Player 2. Hou [5] and Spinat [14] fully characterized the family of approachable sets. Both proved that if a closed set is minimally (w.r.t. set inclusion) approachable, then it satisfies Blackwell's geometric condition. Vieille [15] studied the notions of weak approachability and weak excludability, which were also introduced by Blackwell [2], and proved that any set is either weakly approachable or weakly excludable. For partial results on weak approachability for two-dimensional games where both players have two actions, see Hou [4].
Our objective is to study repeated games with vector payoffs when one of the players is restricted to strategies with bounded computational capacity. Two classes of such strategies were extensively studied in the literature: those that can be implemented by finite automata (see, e.g., Neyman [9], Rubinstein [11], Ichiishi et al. [6]), and those with bounded recall--that is, strategies that may condition only on actions that were played in the last t stages, for some fixed integer t (see, e.g., Lehrer [7], Aumann and Sorin [1]).
In a companion paper (Lehrer and Solan [8]), we study the notions of approachability with automata and with bounded-recall strategies. We characterized the sets that are approachable by Player 1 if he may only use strategies that can be implemented by automata, or bounded-recall strategies (and Player 2 is not restricted). We proved that the following three statements are equivalent for closed sets.
* F is approachable with automata by Player 1.
* F is approachable with bounded-recall strategies by Player 1.
* F contains a convex set that is approachable by Player 1.
In the present paper we concentrate on the notions of excludability against automata and against bounded-recall strategies. A set is excludable against automata (respectively, against bounded- recall strategies) by Player 2 if she has a strategy that ensures that when Player 1 plays a finite automaton (respectively, a bounded-recall strategy), the long-run average payoff is bounded away from the set.
Our first result is a complete characterization of the sets that are excludable against bounded-recall strategies: A closed set is excludable against bounded-recall strategies by a player if and only if it is not approachable with bounded-recall strategies by that player--namely, if and only if it does not contain any convex set that is approachable by the player.
We then provide partial results concerning sets that are excludable against automata. We do not know whether any set that is not approachable with automata by Player 1 is excludable against automata by Player 2. Solving this problem will reveal whether the two notions related to strategies with bounded computational capacity are equivalent.
2. The model and the main results. In this section we define the model of repeated games with vector payoffs, and two types of bounded computational capacity strategies. We then define the notion of excludability against such strategies, and finally, we state our results.
2.1. Repeated games with vector payoffs. A two-player repeated game with vector payoffs is a triplet (I, J, U), where I and J are finite sets of actions of the players, and U = [([u.sub.i,j]).sub.i[member of]I, j[member of]J is a d-dimensional vector-payoff matrix: [u.sub.i, j] [member of] [R.sup.d] for every i [member of] I and j [member of] J. We assume w.l.o.g, that all the payoffs are in the unit ball of [R.sub.d]. We denote by [DELTA](I) and [DELTA](J) the players' mixed action sets (that is, the sets of probability distributions over I and J, respectively). By L and J we denote the sets of mixed strategies in the repeated game of the Players 1 and 2, respectively.
The pair ([i.sub.k], [j.sub.k]) denotes the joint action played by Players 1 and 2 at stage k. The average (vector) payoff up to stage n is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].
2.2. On bounded computational capacity strategies. Let t be a natural number. A t-bounded-recall strategy of Player 1 is a pair (m, [sigma]), where m [member of] [(I x J).sup.t] and [sigma]: [(I x J).sup.t] [right arrow] [DELTA](I). When playing a t-bounded-recall strategy (m, [sigma]), at any stage Player 1 plays [sigma]([omega]), where [omega] is the string of the last t joint actions. He starts the game with the (virtual) memory m. Thus, at the first stage he plays the mixed action [sigma](m), at the second stage he plays [sigma](m', [i.sub.1], [j.sub.1]), where m' are the last t - 1 coordinates of m and ([i.sub.1], [j.sub.1]) is the realized pair of actions of the two players at the first stage, and so on. (1)
A bounded-recall strategy is a strategy that is t-bounded recall for some t [member of] N. We denote by [L.sub.BR] the set of all bounded-recall strategies of Player 1.
A (nondeterministic) automaton A is given by (i) a finite set of states; (ii) a probability distribution over the set of states, according to which the initial state is chosen; (iii) a finite set of inputs; (iv) a finite set of outputs; (v) a function that assigns to every state a probability distribution over outputs; and finally (vi) a transition rule that assigns to every state and every input a probability distribution over states.
When the set of outputs coincides with the set I of actions of Player 1, and the set of inputs coincides with the set I x J of action pairs, an automaton implements a strategy of Player 1 as follows. The initial state of the automaton is chosen according to the initial distribution given in (ii). At every stage, as a function of the current state an action of Player 1 is chosen by the probability distribution given in (v), and a new state is chosen as a function of the pair of actions played (by both players), according to the probability distribution given in (vi). [L.sub.A] denotes the set of Player l's strategies that can be implemented by an automaton.
Observe that every t-bounded-recall strategy can be implemented by an automaton with [[absolute value of I x J].sup.t] states.
2.3. Excludability against bounded-capacity strategies. Let d(x,y)
denote the Euclidean distance between the points x and y in [R.sup.d]. For every set F in [R.sub.d] and every x [member of] [R.sup.d], let d(x, F) = [inf.sub.y[member of]F] d(x, y) be the distance between x and F. For every [sigma] > 0, let B(F, [delta]) = {x [member of] [R.sup.d]: d(x, F) [less than or equal to] [sigma]} be the closed set of all points that are [delta]-close to F.
Blackwell... |
Looking for additional articles?
Click here
to search our database of over 3 million articles.
|
