NDLI: Complexity of (iterated) dominance

Please wait, while we are loading the content...

Ranking systems: the PageRank axioms

Graceful service degradation (or, how to know your payment is late)

Dynamic and secure B2B e-contract update management

On the computational power of iterative auctions

Multi-unit auctions with budget-constrained bidders

Fairness and optimality in congestion games

Information markets vs. opinion pools: an empirical comparison

Content availability, pollution and poisoning in file sharing peer-to-peer networks

Communication complexity of common voting rules

Complexity of (iterated) dominance

Optimal design of English auctions with discrete bid levels

True costs of cheap labor are hard to measure: edge deletion and VCG payments in graphs

Hidden-action in multi-hop routing

A price-anticipating resource allocation mechanism for distributed shared clusters

Inefficiency in provisioning interconnected communication networks

Privacy-preserving credit checking

Secure distributed human computation

Online auctions with re-usable goods

From optimal limited to unlimited supply auctions

Robust solutions for combinatorial auctions

Marginal contribution nets: a compact representation scheme for coalitional games

First-price path auctions

Towards truthful mechanisms for binary demand games: a general framework

Self-selection, slipping, salvaging, slacking, and stoning: the impacts of negative feedback at eBay

Cost sharing in a job scheduling problem using the Shapley value

On decentralized incentive compatible mechanisms

ICE: an iterative combinatorial exchange

Congestion games with failures

Integrating tradeoff support in product search tools for e-commerce sites

Nearly optimal multi attribute auctions

Weak monotonicity suffices for truthfulness on convex domains

Complexity of (iterated) dominance

Content Provider	ACM Digital Library
Author	Conitzer, Vincent Sandholm, Tuomas
Abstract	We study various computational aspects of solving games using dominance and iterated dominance. We first study both strict and weak dominance (not iterated), and show that checking whether a given strategy is dominated by some mixed strategy can be done in polynomial time using a single linear program solve. We then move on to iterated dominance. We show that determining whether there is some path that eliminates a given strategy is NP-complete with iterated weak dominance. This allows us to also show that determining whether there is a path that leads to a unique solution is NP-complete. Both of these results hold both with and without dominance by mixed strategies. (A weaker version of the second result (only without dominance by mixed strategies) was already known [7].) Iterated strict dominance, on the other hand, is path-independent (both with and without dominance by mixed strategies) and can therefore be done in polynomial time.We then study what happens when the dominating strategy is allowed to place positive probability on only a few pure strategies. First, we show that finding the dominating strategy with minimum support size is NP-complete (both for strict and weak dominance). Then, we show that iterated strict dominance becomes path-dependent when there is a limit on the support size of the dominating strategies, and that deciding whether a given strategy can be eliminated by iterated strict dominance under this restriction is NP-complete (even when the limit on the support size is 3).Finally, we study Bayesian games. We show that, unlike in normal form games, deciding whether a given pure strategy is dominated by another pure strategy in a Bayesian game is NP-complete (both with strict and weak dominance); however, deciding whether a strategy is dominated by some mixed strategy can still be done in polynomial time with a single linear program solve (both with strict and weak dominance). Finally, we show that iterated dominance using pure strategies can require an exponential number of iterations in a Bayesian game (both with strict and weak dominance).
Starting Page	88
Ending Page	97
Page Count	10
File Format	PDF
ISBN	1595930493
DOI	10.1145/1064009.1064019
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2005-06-05
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	(iterated) dominance Game theory
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in