Stochastic games
We are interested in situations of stochastic control
with more than one controller. The objective of the
controllers might be different, which leads to the
framework of stochastic games. We are especially interested
in problems arrising from queueing applications, where
the information available to different controllers might be
different, where the natural setting is of an infinite
state space, and where costs are typically unbounded.
Computation and analysis of such problems required
the development of new theoretical tools. We are able
in some applications to obtain the structure of optimal policies
and the value function.
Papers on Applications:
E. Altman and
G. Koole
,
Stochastic scheduling games with Markov decision arrival processes
,
Journal Computers and Mathematics with Appl.
,
Vol. 26, No. 6, pp. 141-148, 1993.
E. Altman
,
Monotonicity of optimal policies in a zero sum game:
a flow control model
,
Advances of dynamic games and applications,
Annals of the International Society of Dynamic Games,
Birkhauser, Vol. 1,
,
p. 269-286, 1994.
E. Altman
,
Flow control using the theory of zero-sum Markov games
,
IEEE Trans. Automatic Control
,
Vol.
39, No. 4, pp. 814-818, 1994.
E. Altman and A. Hordijk
,
Zero-sum Markov games and worst-case
optimal control of queueing systems
,
invited paper,
QUESTA
, Vol. 21,
special issue on optimization of queueing systems, pp. 415-447, 1995.
E. Altman and N. Shimkin
,
Individually Optimal Dynamic Routing
in a Processor Sharing System: Stochastic Game Analysis
,
EE Pub No. 849
,
August 1992. A later version
can be found in
Operations Research
, pp. 776--784, 1998.
E. Altman and N. Shimkin
,
Worst-case and Nash routing policies in
parallel queues with uncertain service allocations
,
IMA Preprint No. 1120
,
Institute for Mathematics and Applications,
University of Minnesota, Minneapolis, USA, 1993.
E. Altman
,
A Markov game approach for optimal routing
into a queueing network
,
INRIA report No. 2178
,
1994.
E. Altman
,
Non zero-sum stochastic games in
admission, service and routing control in queueing systems
,
QUESTA
,
Vol. 3, pp. 259-279, 1996.
E. Altman
,
Applications of dynamic games in queues
submitted to
Annals of the International Society of Dynamic Games
,
A. Nowak (editor).
E. Altman and R. Hassin,
,
Non-Threshold Equilibrium for Customers Joining an M/G/1 Queue
Non-Threshold Equilibrium for Customers Joining an M/G/1 Queue
,
Saint-Petersburg, Russia, July, 2002.
E. Altman,
T. Jimenez
,
R. Nunez Queija and
U. Yechiali
,
Optimal routing among ./M/1 queues with partial information,
INRIA Research Report RR-4985.
final version in
,
Stochastic Models,
Vol. 20, number 2, pp. 149-172, 2004.
E. Altman
,
Applications of dynamic games in queues
,
Advances in Dynamic Games, Vol. 7,
pp. 309-342, Birkhauser, Boston, Basel, Berlin,
2005.
Theoretical papers on approximations
M. Tidball and E. Altman
,
Approximations in dynamic zero-sum games, I
,
SIAM J. Control and Optimization
,
Vol. 34, No. 1, pp. 311-328, 1996.
M. Tidball,
O. Pourtallier
and E. Altman
,
Approximations in dynamic zero-sum games, II
,
INRIA report No. RR-2348,
to appear in
SIAM J. Control and Optimization
,
1997.
E. Altman, E. Feinberg, J. Filar, V. Gaitsgory,
,
Perturbed zero-sum games with applications to stochastic and repeated games,
,
Advances of dynamic games and applications
,
(E. Altman and O. Popurtallier Edts.) pp. 165-181, 2001.
E. Altman,
O. Pourtallier
,
A. Haurie, F. Moresino,
,
Approximating Nash equilibria in nonzero-sum games
,
International Game Theory Review,
Vol 2, Nos. 2-3, pp. 155-172, 2000.
A. Nowak and E. Altman
,
Epsilon-equlibria for stochastic games with uncountable state space
and unbounded costs
,
SIAM Journal on Control and Optimization,
Vol 40, No. 6, pp. 1821-1839, 2002.
Other Theoretical papers
[3.1]
E. Altman, A. Hordijk and F. M. Spieksma
,
Contraction conditions for average and $\alpha$-discount
optimality in countable state Markov games with unbounded
rewards
,
Math. of Oper. Research
,
Vol. 22, No. 3, pp. 588-618, Aug. 1997.
[3.2]
E. Altman and V. A. Gaitsgory
,
A hybrid (differential-stochastic) zero-sum game with
fast stochastic part
,
Annals of the International Society of Dynamic Games
,
Vol. 3, pp. 47-59, 1995.
[3.3]
E. Altman, E. A. Feinberg and A. Shwartz
,
Weighted discounted stochastic games with perfect information
,
Annals of the International Society of Dynamic Games
,
vol. 5, Birkhauser,
V. Gaitsgory, J. Filar and K. Mizukami, editors, pp.
213-221, 2000.
[3.4]
E. Altman and A. Shwartz
,
Constrained Markov Games: Nash Equilibria
,
Annals of the International Society of Dynamic Games
,
vol. 5, Birkhauser,
V. Gaitsgory, J. Filar and K. Mizukami, editors, pp.
303-323, 2000.
[3.5]
E. Altman,
T. Basar,
Z. Pan,
,
Piecewise-deterministic differential games and dynamic teams
with hybrid controls
,
Annals of the International Society of Dynamic Games
,
vol. 5, Birkhauser,
V. Gaitsgory, J. Filar and K. Mizukami, editors, pp.
223-256, 2000.
[3.6]
E. Altman, K. Avrachenkov,
R. Marquez , and G. Miller
,
Zero-sum constrained stochastic games with
independent state processes
, Math. Meth. Oper. Res., Vol. 62, pp. 375-386, Dec. 2005.
[3.7] E. Altman,
K. Avrachenkov,
N. Bonneau,
M. Debbah,
R. El-Azouzi
and D. Sadoc Menasche,
"Constrained
Cost-Coupled Stochastic Games with Independent State Processes"
Operations Research Letters,
Vol 36, pp 160-164, 2008.
available on Arxiv (pdf).
[3.8] Eitan Altman, Saswati Sarkar and Eilon Solan,
Constrained Markov games with
transition probabilities controlled by a single player,
SMCtools'07, Oct 26, 2007, Nantes, France.
[3.9]
Eitan Altman, Tamer Basar and Francesco De Pellegrini,
,
"Optimal Control in Two-Hop Relay Routing",
,,
IEEE CDC, Beijing, Dec 2009.
[3.10] Eitan Altman, and Eilon Solan,
Constrained Games:
the impact of the attitude to adversary's constraints",,
IEEE Transactions on Automatic Control,
vol.54, no.10, pp.2435-2440, Oct. 2009
Slides of some talks:
Tutorial talk:
Applications of Dynamic Games in Queues
,
(
pdf file
),
presented at the 9th International
Symposium on Dynamic Games and Applications
December 18-21, 2000, Adelaide, South Australia.
Back to my
English Web page
.
Some links to WEB cites on game theory:
The International Society of Dyancim Games - ISDG
,
Economics Working Paper Archive, section
Game Theory and Information (C7,D8)
,
International Journal of Game Theory
.