Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(8)
IT Strategy
Polynomial Time Algorithm
Pure Strategy Equilibrium
Pure Strategy Nash Equilibrium
Satisfiability
Upper and Lower Bounds
Utility Function
Pure Strategy Nash Equilibria
Subscribe
Academic
Publications
On the Impact of Strategy and Utility Structures on CongestionAverse Games
On the Impact of Strategy and Utility Structures on CongestionAverse Games,10.1007/9783642108419_61,Thomas Voice,Maria Polukarov,Andrew Byde,Nich
Edit
On the Impact of Strategy and Utility Structures on CongestionAverse Games
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
Thomas Voice
,
Maria Polukarov
,
Andrew Byde
,
Nicholas R. Jennings
Recent results regarding games with congestionaverse utilities (or, congestionaverse games—CAGs) have shown they possess some very desirable properties. Specifically, they have pure strategy Nash equilibria, which may be found by a
polynomial time
algorithm. However, these results were accompanied by a very limiting assumption that each player is capable of using any subset of its available set of resources. This is often unrealistic—for example, resources may have complementarities between them such that a minimal number of resources is required for any to be useful. To remove this restriction, in this paper we prove the existence and tractability of a
pure strategy equilibrium
for a much more general setting where each player is given a matroid over the set of resources, along with the (upper and lower) bounds on the size of a subset of resources to be selected, and its strategy space consists of all elements of this matroid that fit in the given size range. (This, in particular, includes the possibility of having a full matroid, or having a set of bases of a matroid.) Moreover, we show that if a player strategy space in a given CAG does not satisfy these matroid properties, then a
pure strategy equilibrium
need not exist, and in fact the determination of whether or not a game has a
pure strategy Nash equilibrium
is NPcomplete. We further prove analogous results for each of the congestionaverse conditions on utility functions, thus showing that current assumptions on strategy and utility structures in this model cannot be relaxed anymore.
Conference:
Workshop on Internet and Network Economics  WINE
, pp. 600607, 2009
DOI:
10.1007/9783642108419_61
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
eprints.ecs.soton.ac.uk
)
(
dx.doi.org
)
(
www.informatik.unitrier.de
)
More »
Citation Context
(1)
...We intend to examine games where computing Nash equilibria can be done in polynomial time, such as matroid congestion games [1] and congestionaverse games [6,
19
]...
Yoram Bachrach
,
et al.
The Good, The Bad and The Cautious: Safety Level Cooperative Games
References
(19)
Games with CongestionAverse Utilities
(
Citations: 2
)
Andrew Byde
,
Maria Polukarov
,
Nicholas R. Jennings
Conference:
Algorithmic Game Theory  SAGT
, pp. 220232, 2009
Computing Equilibria in Anonymous Games
(
Citations: 29
)
Constantinos Daskalakis
,
Christos H. Papadimitriou
Journal:
Computing Research Repository  CORR
, vol. abs/0710.5, pp. 8393, 2007
The complexity of pure Nash equilibria
(
Citations: 214
)
Alex Fabrikant
,
Christos H. Papadimitriou
,
Kunal Talwar
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 604612, 2004
Fast and Compact: A Simple Class of Congestion Games
(
Citations: 39
)
Samuel Ieong
,
Robert Mcgrew
,
Eugene Nudelman
,
Yoav Shoham
,
Qixiang Sun
Conference:
National Conference on Artificial Intelligence  AAAI
, pp. 489494, 2005
LocalEffect Games
(
Citations: 58
)
Kevin Leytonbrown
,
Moshe Tennenholtz
Conference:
International Joint Conference on Artificial Intelligence  IJCAI
, pp. 772780, 2003
Sort by:
Citations
(1)
The Good, The Bad and The Cautious: Safety Level Cooperative Games
Yoram Bachrach
,
Maria Polukarov
,
Nicholas R. Jennings
Conference:
Workshop on Internet and Network Economics  WINE
, pp. 432443, 2010