NDLI: Extensive-form game abstraction with bounds

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

Centrality, gossip, and diffusion of information in networks

Strategic trading in informationally complex environments

Generalized second price auction with probabilistic broad match

A dynamic network game for the adoption of new technologies

Clinching auctions beyond hard budget constraints

Individual security and network design

Optimal mechanisms with simple menus

Efficient voting via the top-k elicitation scheme: a probabilistic approach

Optimal allocation without money: an engineering approach

Adaptive contract design for crowdsourcing markets: bandit algorithms for repeated principal-agent problems

Reasoning about optimal stable matchings under partial information

The wisdom of smaller, smarter crowds

Incentivized optimal advert assignment via utility decomposition

Towards a better measure of business proximity: topic modeling for analyzing M As

Local computation mechanism design

Extensive-form game abstraction with bounds

Fair enough: guaranteeing approximate maximin shares

Routing and staffing when servers are strategic

Network formation games with heterogeneous players and the internet structure

On the efficiency of the walrasian mechanism

Long-run learning in games of cooperation

Pragmatic algorithmic game theory

Mechanism with unique learnable equilibria

Buying private data without verification

Recency, records and recaps: learning and non-equilibrium behavior in a simple decision problem

Incentivizing exploration

Expressiveness and robustness of first-price position auctions

Characterizing strategic cascades on networks

Deferred-acceptance auctions and radio spectrum reallocation

Cryptographically blinded games: leveraging players' limitations for equilibria and profit

Modularity and greed in double auctions

A local-dominance theory of voting equilibria

Two-sided matching with one-sided preferences

Removing arbitrage from wagering mechanisms

Manipulation of stable matchings using minimal blacklists

Revealing and incorporating implicit communities to improve recommender systems

Strategyproof allocation of discrete jobs on multiple machines

Why marketplace experimentation is harder than it seems: the role of test-control interference

Reallocation mechanisms

Bounds for the query complexity of approximate equilibria

Price of anarchy for auction revenue

Multiplicative bidding in online advertising

Simple approximate equilibria in large games

Strategy-proofness, investment efficiency, and marginal returns: an equivalence

Strategic information platforms: selective disclosure and the price of "free"

Simultaneous bayesian auctions and computational complexity

Differentially private and incentive compatible recommendation system for the adoption of network goods

Dynamically eliciting unobservable information

Optimal auctions for correlated buyers with sampling

Optimising trade-offs among stakeholders in ad auctions

The polarizing effect of network influences

The performance of deferred-acceptance auctions

The complexity of fairness through equilibrium

Duality and optimality of auctions for uniform distributions

Universal pareto dominance and welfare for plausible utility functions

Dynamic matching market design

Information aggregation in exponential family markets

Managing congestion in decentralized matching markets

Trick or treat: putting peer prediction to the test

Time-inconsistent planning: a computational problem in behavioral economics

Whole page optimization: how page elements interact with the position auction

Knightian self uncertainty in the vcg mechanism for unrestricted combinatorial auctions

Finding approximate nash equilibria of bimatrix games via payoff queries

Mechanism design for data science

Cournot competition in networked markets

Asymptotically truthful equilibrium selection in large congestion games

Optimal impartial selection

Level-0 meta-models for predicting human behavior in games

Contract complexity

A dynamic model of certification and reputation

Bandits with concave rewards and convex knapsacks

An axiomatic approach to characterizing and relaxing strategyproofness of one-sided matching mechanisms

Optimizing prices in descending clock auctions

Re-incentivizing discovery: mechanisms for partial-progress sharing in research

Approximate revenue maximization in interdependent value settings

Neutrality and geometry of mean voting

Misdirected search effort in a matching market: causes, consequences and a partial solution

A general volume-parameterized market making framework

Size versus truthfulness in the house allocation problem

Corporate prediction markets: evidence from google, ford, and firm X

Optimal contest design for simple agents

The empirical implications of privacy-aware choice

Extensive-form game abstraction with bounds

Content Provider	ACM Digital Library
Author	Sandholm, Tuomas Kroer, Christian
Abstract	Abstraction has emerged as a key component in solving extensive-form games of incomplete information. However, lossless abstractions are typically too large to solve, so lossy abstraction is needed. All prior lossy abstraction algorithms for extensive-form games either 1) had no bounds on solution quality or 2) depended on specific equilibrium computation approaches, limited forms of abstraction, and only decreased the number of information sets rather than nodes in the game tree. We introduce a theoretical framework that can be used to give bounds on solution quality for any perfect-recall extensive-form game. The framework uses a new notion for mapping abstract strategies to the original game, and it leverages a new equilibrium refinement for analysis. Using this framework, we develop the first general lossy extensive-form game abstraction method with bounds. Experiments show that it finds a lossless abstraction when one is available and lossy abstractions when smaller abstractions are desired. While our framework can be used for lossy abstraction, it is also a powerful tool for lossless abstraction if we set the bound to zero. Prior abstraction algorithms typically operate level by level in the game tree. We introduce the extensive-form game tree isomorphism and action subset selection problems, both important problems for computing abstractions on a level-by-level basis. We show that the former is graph isomorphism complete, and the latter NP-complete. We also prove that level-by-level abstraction can be too myopic and thus fail to find even obvious lossless abstractions.
Ending Page	638
Page Count	18
Starting Page	621
File Format	PDF
ISBN	9781450325653
DOI	10.1145/2600057.2602905
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-06-01
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Extensive-form game Abstraction Equilibrium finding
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