Algorithmic Game Theory
4th International Symposium, SAGT 2011, Amalfi, Italy, October 17-19, 2011. Proceedings
Published on 5. October 2011
XI, 327 pages
978-3-642-24829-0 (ISBN)
Description
This book constitutes the refereed proceedings of the Fourth International Symposium on Algorithmic Game Theory, SAGT 2011, held in Amalfi, Italy, in October 2011. The 26 revised full papers presented together with 2 invited lectures were carefully reviewed and selected from 65 submissions. The papers are organized in topical sections on auctions and advertising, quality of solutions, externalities, mechanism design, complexity, network games, pricing, as well as routing games.
More details
Other editions
Additional editions
Giuseppe Persiano
Algorithmic Game Theory
4th International Symposium, SAGT 2011, Amalfi, Italy, October 17-19, 2011. Proceedings
Book
10/2011
Springer
€53.49
Shipment within 7-9 days
Content
- 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
