Algorithmic Game Theory

Name: Algorithmic Game Theory | 4th International Symposium, SAGT 2011, Amalfi, Italy, October 17-19, 2011. Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

4th International Symposium, SAGT 2011, Amalfi, Italy, October 17-19, 2011. Proceedings

Giuseppe Persiano(Herausgeber*in)

Springer (Verlag)

Erschienen am 5. Oktober 2011

XI, 327 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-24829-0 (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

Title
Preface
Organization
Table of Contents
Invited Talks
Computational Game Theory
Computation and Incentives of Competitive Equilibria in a Matching Market
Introduction
First Approaches
Future Challenges
References
Session 1: Auctions and Advertising
Repeated Budgeted Second Price Ad Auction
Introduction
The Model
Pure Nash Equilibrium
Properties of a Pure Nash Equilibrium
Critical Bid
PNE Existence: Special Cases
PNE Existence: General Case
Repeated Budget Auction
Bidding Strategies and Dynamics
Convergence
Simulations
References
Prompt Mechanism for Ad Placement over Time
Introduction
The Model
The Gravity Algorithm
Truthfulness
Promptness
Approximation Ratio
Big Ads Approximation Ratio
Small Ads Approximation Ratio
Concluding Remarks
References
The Multiple Attribution Problem in Pay-Per-Conversion Advertising
Introduction
Inefficiency of the Last- Impression Attribution Scheme
The Model
The Ad Allocation Problem
Computing the Values
The General Recurrence
Closed-form Solution for Constant R
Pricing and Publisher Fairness
The Uniform Pricing Method
Publisher Fairness
Fair Payments via Max-Flow Min-Cut
Conclusion
References
On Communication Protocols That Compute Almost Privately
Introduction
Economic Motivation
Summary of Our Contributions
Summary of Prior Related Works
Privacy-Preserving Computation
Binary Space Partition (Bsp)
The Model and Basic Definitions
Two-Party Approximate Privacy Model of FJS10
Dissection Protocols and Tiling Functions for 2-Party Computation
Two-Party Dissection Protocol for Tiling Functions
Boolean Tiling Functions
Average and Worst Case Par for Non-Boolean Tiling Functions
Extensions of the Basic Two-Party Setup
Non-tiling Functions
Multi-party Computation
Analysis of the Bisection Protocol for Two Functions
References
Session 2: Quality of Solutions
Dynamic Inefficiency: Anarchy without Stability
Introduction
Our Results
Preliminaries
Dynamic Inefficiency in Job Scheduling
Random Walk Dynamic
Conclusion
References
Throw One's Cake - and Eat It Too
Introduction
Definitions and Preliminaries
Utilitarian Welfare
Egalitarian Welfare
Pareto-Dominant Partial Divisions
Discussion and Open Problems
References
The Price of Optimum in a Matching Game
Introduction
Related Work
Motivation, Organization and Results
The Strategic Game and the Optimization Problem
Feasible Solutions
Complexity and Approximation
Conclusion
References
Pareto Optimality in Coalition Formation
Introduction
Preliminaries
Perfection and Pareto Optimality
The Preference Refinement Algorithm
Computational Results
General Hedonic Games
Roommate Games
W-Hedonic Games
B-Hedonic Games
Conclusions
References
Session 3: Externalities
Externalities among Advertisers in Sponsored Search
Introduction
A Model for Externalities in Keyword Auctions
An Exact Algorithm Based on Color Coding
O(c)-Approximation Algorithms for Positive Externalities
On the GSP Mechanism with Externalities
References
Peer Effects and Stability in Matching Markets
Introduction
Model and Notation
Existence of Stable Matchings
Efficiency of Stable Matchings
Related Models
Discussion of Results
Concluding Remarks
References
Steady Marginality: A Uniform Approach to Shapley Value for Games with Externalities
Introduction
Definitions and Notation
Axiomatic Characterization
Constant-Coalition Games
Uniqueness of the Value
A Comparison of Various Marginality Definitions
Conclusions
References
Session 4: Mechanism Design
Scheduling without Payments
Introduction
Model
The Case of a Single Task
Truthful Mechanisms for One Task
An Optimal Truthful Mechanism
Extension to Many Tasks and Discussion
References
Combinatorial Agency of Threshold Functions
Introduction
Model
Transition Behavior of the Optimal Contract
Price of Unaccountability
Composition of Anonymous Technologies
Majority-of-ANDs
Majority of ORs
AND of Majority
References
Lower Bound for Envy-Free and Truthful Makespan Approximation on Related Machines
Introduction
Preliminaries
Lower Bound on Anonymous Mechanisms
Characterizing Scalable Mechanisms on Two Machines
Payments for Known Allocation Rules
References
A Truthful Mechanism for Value-Based Scheduling in Cloud Computing
Introduction
Definitions and Notation
Approximation Algorithm for BFS
LP Relaxation of BFS with Deadline Valuation Functions
Extension to General Valuation Functions
Decomposing an Optimal MND Fractional Solution
Truthfulness-in-Expectation
The Fractional VCG Mechanism
A New Efficient Truthful-in-Expectation Mechanism
References
Session 5: Complexity
Random Bimatrix Games Are Asymptotically Easy to Solve
Introduction
Games and Nash Equilibria
Notation
Bimatrix Games
Nash Equilibria and Approximate Nash Equilibria
Random Bimatrix Games
Approximate Nash Equilibria in Random Games
Well-Supported Nash Equilibria in Random Games
References
Complexity of Rational and Irrational Nash Equilibria
Introduction
Definitions and Preliminaries
Complexity of NASH-EQUIVALENCE and RATIONAL NASH
Complexity of NASH-REDUCTION and IRRATIONAL NASH
Epilogue
References
Diffusion in Social Networks with Competing Products
Introduction
Background
Contributions
Preliminaries
Reachable Outcomes
Unavoidable Outcomes
Unique Outcomes
Product Adoption in Networks without Unique Outcomes
Conclusions and Future Work
References
Session 6: Network Games
A Clustering Coefficient Network Formation Game
Introduction
Related Work
Preliminaries
A (Partial) Catalog of CC Game Nash Equilibria
General Properties of CC Game Nash Equilibria
The Price of Anarchy
Intractability of Best Responses
References
On the Existence of Pure Strategy Nash Equilibria in Integer-Splittable Weighted Congestion Games
Introduction
Related Work
Our Contribution
The Model
Non-existence of PSNE
Convex Increasing ISWCGs
Violating the Finite Improvement Property
Nash Equilibria
Conclusions
References
On Dynamics in Basic Network Creation Games
Introduction
Related Work
Model and Definitions
Our Contribution
Playing on a Tree
Improving Response Dynamics on Trees
Best Response Dynamics on Trees
Computing a Best Response on Trees
Playing on General Graphs
Best Response Dynamics on General Graphs
Computing a Best Response in General Graphs
References
Session 7: Pricing
Pricing Exotic Derivatives Using Regret Minimization
Introduction
Preliminaries
Arbitrage-Free Bounds
Price Bounds for a Variety of Options
Convex Path-Independent Derivatives
Empirical Results
References
Strategic Pricing in Next-Hop Routing with Elastic Demands
Introduction
Model
Uniform Nash Equilibrium and Price of Stability
Computing a Good Nash Equilibrium
Reasonable Assumptions and Price of Anarchy
Non-linear Utility and Price Functions
References
Session 8: Routing Games
Weakly-Acyclic (Internet) Routing Games
Introduction
Weakly-Acyclic Games
(Internet) Routing Games
Our Contributions: Weakly-Acyclic Routing Games
Organization
Model
Weakly-Acyclic Games
(Internet) Routing Games
Illustration: Simple Weakly-Acyclic Routing Games
Routing Games with Byzantine Players
Routing Policies
Positive Result
Backup Routing Games
Commercial Backup-Routing Games
Positive Result
References
Efficiency of Restricted Tolls in Non-atomic Network Routing Games
Introduction
Preliminaries
Computing Optimal -Restricted Tolls
Characterization of Inducible Flows for Single-Commodity Networks
Computing Optimal Tolls in Parallel-Arc Networks
General Efficiency of -Restricted Tolls
References
Stochastic Selfish Routing
Introduction
The Model
Exogenous Standard Deviations
Endogenous Standard Deviations
Succinct Representations of Equilibria
Price of Anarchy
Conclusions and Open Problems
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken