Algorithmic Game Theory

Name: Algorithmic Game Theory | 10th International Symposium, SAGT 2017, L'Aquila, Italy, September 12-14, 2017, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

10th International Symposium, SAGT 2017, L'Aquila, Italy, September 12-14, 2017, Proceedings

Vittorio Bilò Michele Flammini(Herausgeber*in)

Springer (Verlag)

Erschienen am 31. August 2017

XIX, 346 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-319-66700-3 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Intro
Preface
Organization
Abstracts
Position Ranking and Auctions for Online Marketplaces
Asymptotic Existence of Fair Divisions for Groups
Approximate Maximin Shares for Groups of Agents
On Black-Box Transformations in Downward-Closed Environments
Contents
Auctions
Liquid Price of Anarchy
1 Introduction
2 Model and Preliminaries
3 Simultaneous First Price Auctions
References
Tight Welfare Guarantees for Pure Nash Equilibria of the Uniform Price Auction
1 Introduction
2 Model and Definitions
3 Inefficiency Upper Bound
4 A Matching Lower Bound
5 Conclusions
References
Online Random Sampling for Budgeted Settings
1 Introduction
1.1 Model
1.2 Previous Techniques and Their Limitations
1.3 Our Results and Techniques
1.4 Additional Related Work
2 Online Implementation of Random Sampling Based Mechanisms
2.1 Truthfulness and Feasibility
3 Revenue Maximization for Additive Agents with Budgets
3.1 The Mechanism
3.2 A Constant Loss Due to the Impersonation Technique
3.3 Analysis of Our Mechanism
References
Liquid Welfare Maximization in Auctions with Multiple Items
1 Introduction
2 Greedy Algorithm
3 The Random Sampling Mechanism
3.1 Random Sampling and Large Market
3.2 Approximation Ratio
References
Computational Aspects of Games
On the Nucleolus of Shortest Path Games
1 Introduction
2 Preliminaries
2.1 Shortest Paths
2.2 Minimum Ratio Cycles
2.3 Network Flows and Linear Programming
3 The Core
4 The Nucleolus
5 The Nucleolus When the Core is Non-empty
5.1 An Alternative Description of the Core
5.2 The Nucleolus
6 The Nucleolus When the Core Is Empty
6.1 Computation of the Nucleolus
7 Complexity
References
Earning Limits in Fisher Markets with Spending-Constraint Utilities
1 Introduction
2 Preliminaries
3 Structure of Thrifty Equilibria
4 Algorithms to Compute Thrifty Equilibria
5 Nash Social Welfare in Additive Multi-unit Markets
References
Robustness Among Multiwinner Voting Rules
1 Introduction
2 Preliminaries
3 Robustness Levels of Multiwinner Rules
4 Computing Refinements of Robust Rules
5 Complexity of Computing the Robustness Radius
6 Beyond the Worst Case: An Experimental Evaluation
7 Conclusions
References
Computing Constrained Approximate Equilibria in Polymatrix Games
1 Introduction
2 Preliminaries
3 Decision Problems for Approximate Equilibria
4 Constrained Equilibria in Bounded Treewidth Games
4.1 An Algorithm to Find Approximate Nash Equilibria
4.2 Constrained Approximate Nash Equilibria
References
Group Activity Selection on Graphs: Parameterized Analysis
1 Introduction
2 Hardness
3 An FPT Algorithm for General Graphs
4 FPT Algorithm for Networks of Bounded Treewidth
References
The Real Computational Complexity of Minmax Value and Equilibrium Refinements in Multi-player Games
1 Introduction
1.1 The Existential Theory of the Reals
2 R-Completeness of Minmax Value in 3-Player Games
2.1 R-Completeness of Constrained Nash Equilibrium
3 R-Completeness of Equilibrium Refinements
3.1 Trembling Hand Perfect and Proper Equilibrium of Games in Strategic Form
3.2 Sequential Equilibrium of Games in Extensive Form
3.3 CURB Sets in Games in Strategic Form
References
Conditional Value-at-Risk: Structure and Complexity of Equilibria
1 Introduction
1.1 Conditional Value-at-Risk and its Equilibria
1.2 Results and Significance
1.3 Related Work and Comparison
2 (E + R)-Valuations
3 Conditional Value-at-Risk (CVaR)
3.1 Value-at-Risk (VaR)
3.2 Conditional Value-at-Risk (CVaR)
4 Properties of CVaR at Equilibrium
5 NP-Hardness from Optimal-Value Property
6 Strict Quasiconcavity and Extended Sharpe Ratio
7 Conclusion and Open Problems
References
Congestion Games, Network and Opinion Formation Games
Reconciling Selfish Routing with Social Good
1 Introduction
2 Preliminaries
3 Solution Concepts
4 Optimal -Flows: Complexity and Approximation
4.1 Existence and Complexity
4.2 Approximation Using Modified Potential Functions
References
Selfish Network Creation with Non-uniform Edge Cost
1 Introduction
1.1 Model and Notation
1.2 Related Work
1.3 Our Contribution
2 Hardness
3 Analysis of Equilibria
3.1 Bounding the Diameter of Equilibrium Networks
3.2 Price of Stability
3.3 Price of Anarchy
4 Dynamics
4.1 Dynamics in the deg(k)NCG
4.2 Dynamics in the Add-Only Model
5 Conclusion
References
Opinion Formation Games with Aggregation and Negative Influence
1 Introduction
2 Model and Preliminaries
3 Convergence of Average-Oriented Opinion Formation
4 The PoA of Symmetric Average-Oriented Games
5 Average-Oriented Games with Restricted Opinions
References
The Efficiency of Best-Response Dynamics
1 Introduction
1.1 Model and Problem Statement
1.2 Our Results
1.3 Related Work
2 Network Formation Games
2.1 Warmup: Symmetric Network Formation Games
2.2 Series of Parallel Paths (SPP) Networks
2.3 Local Rules for Extension Parallel (EP) Graphs
2.4 Weighted Symmetric Network Formation Games
References
Efficient Best Response Computation for Strategic Network Formation Under Attack
1 Introduction
2 Model
3 The Best Response Algorithm
3.1 Key Observations
3.2 Main Algorithm
3.3 Partner Selection for Components in CI
4 Conclusion
References
Path Deviations Outperform Approximate Stability in Heterogeneous Congestion Games
1 Introduction
2 Preliminaries
3 Heterogeneous Populations
4 Homogeneous Population
References
Mechanism Design, Incentives and Regret Minimization
Agent Incentives of Strategic Behavior in Resource Exchange
1 Introduction
2 Preliminary
3 Incentive Ratios of BD Mechanism on Trees
4 Conclusion
References
A 3-Player Protocol Preventing Persistence in Strategic Contention with Limited Feedback
1 Introduction
1.1 Our Contribution
1.2 Other Related Work
2 Model
3 A 3-Player Protocol that Prevents Persistence
3.1 Expected Latency for a Persistent Player
3.2 Expected Latency When All Players Use P(c, p)
3.3 Feasibility
References
Hedging Under Uncertainty: Regret Minimization Meets Exponentially Fast Convergence
1 Introduction
1.1 Our Results
1.2 Related Work
2 Preliminaries
3 Hedging Under Uncertainty
4 Rationality Analysis and Results
5 Conclusions
References
Resource Allocation
Tradeoffs Between Information and Ordinal Approximation for Bipartite Matching
1 Introduction
2 Model and Notation
3 One-Sided Ordinal Preferences
4 Two-Sided Ordinal Preferences
5 Total Ordering of Edge Weights
6 One-Sided Preferences with Restricted Edge Weights
References
Group Strategyproof Pareto-Stable Marriage with Indifferences via the Generalized Assignment Game
1 Introduction
2 Tiered-Slope Market
3 Stable Marriage with Indifferences
3.1 The Associated Tiered-Slope Market
3.2 Pareto-Stability
3.3 Group Strategyproofness
4 Efficient Implementation
References
The Spectrum of Equilibria for the Colonel Blotto and the Colonel Lotto Games
1 Introduction
1.1 Spectrum: Informal Introduction
2 Colonel Blotto, Colonel Lotto, and General Lotto Games
3 Analysis
4 Conclusions
References
On Proportional Allocation in Hedonic Games
1 Introduction
2 Model and Preliminaries
3 Existence and Computation
4 Lower Bounds
5 Hardness Results
References
Stable Marriage with Covering Constraints--A Complete Computational Trichotomy
1 Introduction
2 Preliminaries
3 Strong Parameterized Intractability of SMC
4 Polynomial-Time Approximation
5 SMC with Bounded Number of Distinguished Persons or Blocking Pairs
6 SMC with Preference Lists of Length at Most Two
References
Fairly Allocating Contiguous Blocks of Indivisible Items
1 Introduction
1.1 Related Work
2 Preliminaries
3 Proportionality
4 Equitability
5 Envy-Freeness
6 Price of Fairness
7 Conclusion and Future Work
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken