Internet and Network Economics
7th International Workshop, WINE 2011, Singapore, December 11-14, 2011, Proceedings
Published on 2. February 2012
XII, 420 pages
978-3-642-25510-6 (ISBN)
Description
This book constitutes the refereed proceedings of the 7th International Workshop on Internet and Network Economics, WINE 2011, held in Singapore, in December 2011. The 31 revised full papers and 5 revised short papers presented together with the abstracts of 3 papers about work in progress were carefully reviewed and selected from 100 submissions. The papers are organized in topical sections on algorithmic game theory, algorithmic mechanism design, computational advertising, computational social choice, convergence and learning in games, economics aspects of security and privacy, information and attention economics, network games and social networks.
More details
Other editions
Additional editions
Ning Chen | Edith Elkind | Elias Koutsoupias
Internet and Network Economics
7th International Workshop, WINE 2011, Singapore, December 11-14, 2011, Proceedings
Book
11/2011
Springer
€53.49
Shipment within 7-9 days
Content
- Intro
- Title Page
- Preface
- Organization
- Table of Contents
- Full Papers
- The Snowball Effect of Uncertainty in Potential Games
- Introduction
- Consensus Games
- Lower Bound and Upper Bound for Perturbation Model
- Tight Bound for Byzantine Players
- Set-Covering Games and Extensions
- Upper Bound for Improved-Response
- Lower Bound for Improved-Response
- Lower Bound for Best-Response
- Open Questions
- References
- Approximation Algorithm for Security Games with Costly Resources
- Introduction
- Notations and Preliminaries
- Approximation Algorithm
- Targets with Big Threshold Requirements
- Targets with Small Threshold Requirements
- Conclusion
- References
- On Allocations with Negative Externalities
- Introduction
- Our Results
- Related Work
- Notations and Preliminaries
- The Pessimistic Nash Equilibrium
- Nash Equilibrium with Relaxed Prices
- The Best Nash Equilibrium
- Conclusion
- References
- An Improved 2-Agent Kidney Exchange Mechanism
- Introduction
- An Unsuccessful Attempt: Flip-and-Match
- Our Mechanism: Weight-and-Match
- Lower Bounds
- Discussion and Open Problems
- References
- Optimal Pricing in Social Networks with Incomplete Information
- Introduction
- Related Work
- Model and Solution Concept
- The Main Algorithm
- Outline of Our Line Sweep Algorithm
- Diagonal Dominant Case
- General Case
- Extensions
- References
- On the Approximation Ratio of $k$ -Lookahead Auction
- Introduction
- Preliminary
- The Approximation Ratio
- Tightness of Analysis
- Discussion and Open Questions
- References
- Decision Markets with Good Incentives
- Introduction
- Related Work
- Prediction Markets: Background and Notation
- Decision Market Model
- Decision Market Incentives
- Myopic Incentive Compatibility
- A Simple Construction for Strictly Proper Decision Markets
- Strictly Proper Decision Markets Have Full Support
- Decision Markets with Good Incentives
- Extensions
- Approximating Deterministic Decisions
- Expected Utility Maximizing Decision Rules
- A Correspondence between Decision Markets and Prediction Markets
- Conclusion
- References
- A Global Characterization of Envy-Free Truthful Scheduling of Two Tasks
- Introduction
- Constraints Due to Envy-Freeness
- Characterization of Envy-Free Truthful Mechanisms
- Counterexample with Singularity
- Task Scheduling
- Additive Combinatorial Auctions
- References
- Truth, Envy, and Truthful Market Clearing Bundle Pricing
- Introduction
- Model and Preliminaries
- VCG Mechanisms
- Gross Substitutes and Capacitated Valuations
- Envy-Free and Incentive Compatible Assignments with Capacities
- Discussion and Open Problems
- References
- Simple, Optimal and Efficient Auctions
- Introduction
- Related Work
- Preliminaries
- The Regular, Independent Case
- The Non-regular, i.i.d. Case
- References
- Prior-Independent Multi-parameter Mechanism Design
- Introduction
- Preliminaries
- Settings and Definitions
- VCG
- Myerson's Optimal Mechanism for Single-Parameter Environments
- Reduction from UMMA Environments to Single-Parameter Environments
- Bulow-Klemperer Type Results
- Prior-Independent Mechanism for UMMA
- Unit-Demand Multi-item Auction with Unit Supply
- Unit-Demand Multi-unit Multi-item Auction
- References
- Discrete Choice Models of Bidder Behavior in Sponsored Search
- Introduction
- The Model
- Sponsored Search
- Discrete Choice
- Data Description
- Regression Results
- Model Evaluation
- Baseline Models
- Estimation Results
- Conclusion
- References
- Social Learning in a Changing World
- Introduction
- Classical Approaches and Results
- Rationality and Bounded Rationality
- Informal Statement of the Model
- Informal Statement of Results
- Previous Work
- Notation, Formal Models, and Results
- Dynamics Models
- Steady States and Efficient Learning
- Statement of the Main Results
- Preliminary Analysis
- Understanding Best-Response Dynamics
- Complete Graph Case
- Proofs
- Conclusion
- References
- Budget-Balanced and Nearly Efficient Randomized Mechanisms: Public Goods and beyond
- Introduction
- Model
- Public Project
- General Domains
- Discussion
- References
- Online Stochastic Weighted Matching: Improved Approximation Algorithms
- Introduction
- Preliminaries
- A 0.667-Competitive Algorithm for Weighted Graphs
- A 0.7036-Approximation for Unweighted Graphs
- Optimal Online Algorithms for Simple Graphs
- References
- On Strategy-Proof Allocation without Payments or Priors
- Introduction
- Preliminaries and the Model
- An Upper Bound for Multiple Agents
- Allocation between Two Agents
- An Upper Bound for Swap-Dictatorial Mechanisms
- Relation between Swap-Dictatorial and Strategy-Proof Mechanisms
- Bounded Valuation
- Conclusions and Future Research
- References
- Demand Allocation Games: Integrating Discrete and Continuous Strategy Spaces
- Introduction
- The Model
- Existence of Pure Nash Equilibria
- Two Player Demand Allocation Games
- Examples
- References
- Controlling Infection by Blocking Nodes and Links Simultaneously
- Introduction
- Our Model for Infection Control
- Related Work
- Approximation Algorithm for MGNS($d$ )
- Hardness of Approximation for GNS ($d$ )
- Polynomial Algorithm for MGNS($d$ ) on Trees
- Conclusions and Future Research
- References
- A General Framework for Computing Optimal Correlated Equilibria in Compact Games (Extended Abstract)
- Introduction
- Problem Formulation
- Correlated Equilibrium
- The Deviation-Adjusted Social Welfare Problem
- The Coarse Deviation-Adjusted Social Welfare Problem
- The Deviation-Adjusted Social Welfare Problem for Specific Representations
- Reduced Forms
- Linear Reduced Forms
- Representations with Action-Specific Structure
- References
- Buy-Sell Auction Mechanisms in Market Equilibrium
- Introduction
- Market Model
- A Primal-Dual Framework
- Algorithmic Framework
- Analysis
- Conclusions
- References
- Behavioral Conflict and Fairness in Social Networks
- Introduction
- Related Literature
- Experimental Design
- Results
- Collective Wealth and Tipping
- Conflict and Fairness
- Downward Rigidity of Tips
- Individual Nodes
- Conclusion
- References
- Efficient Ranking in Sponsored Search
- Introduction
- The Model
- Main Condition
- Exponential Families
- Natural Exponential Families
- Lognormal Distribution
- Empirical Data Analysis
- Data Description
- Hierarchical Model
- Discussion
- References
- The Complexity of Approximate Nash Equilibrium in Congestion Games with Negative Delays
- Introduction
- Preliminaries and Results
- Negative Games
- Increasing Delay Functions
- Monotone Delay Functions
- Games without Sign Restriction
- References
- OnWorst-Case Allocations in the Presence of Indivisible Goods
- Introduction
- Related Work and Contribution
- Definitions and Preliminaries
- The Algorithm
- Mechanism Design
- Deterministic Algorithms
- Randomized Algorithms
- On the Complexity of Finding Better Allocations
- Future Work
- References
- Natural Models for Evolution on Networks
- Introduction
- All-or-Nothing vs. Aggregation
- The Model of Lieberman, Hauert, and Nowak (An All-or-Nothing Approach)
- An Evolutionary Model of Mutual Influences (An Aggregation Approach)
- Analysis of the All-or-Nothing Model
- A Generic Upper Bound Approach
- Upper and Lower Bounds Depending on Degrees
- The Undirected Suppressor
- Analysis of the Aggregation Model
- Potential and Convergence in General Undirected Graphs
- Analysis of the Complete Graph
- Invasion Control Mechanisms
- Control of Invasion in Phases
- Continuous Control of Invasion
- References
- Approximate Judgement Aggregation
- Introduction
- Previous Works
- Connection to Property Testing
- Techniques
- The Model
- Binary Functions
- Agenda Examples
- Truth-Functional Agendas
- Non Truth-Functional Agendas
- Motivation
- Summary and Future Work
- References
- Liquidity-Sensitive Automated Market Makers via Homogeneous Risk Measures
- Introduction
- Background
- Cost Functions and Risk Measures
- Link to Online Learning
- The OPRS Cost Function
- Desiderata, Dual Spaces, and an Impossibility Result
- Desiderata and Their Combinations
- Dual Space Equivalences
- Shaping the Dual Space
- Curvature
- Divergence from Probability Simplex
- A New Family of Liquidity-Sensitive Market Makers
- Conclusions and Future Work
- References
- Manipulating Stochastically Generated Single-Elimination Tournaments for Nearly All Players
- Introduction
- Condorcet Random Model - Formal Definition
- Kings That Are also SE Winners
- Condorcet Random Model
- Improving the Result for the GCR Model through Perfect Matchings
- Conclusions
- References
- Computing Nash Equilibria of Action-Graph Games via Support Enumeration
- Introduction
- Technical Background
- Action-Graph Games
- Support-Enumeration Method
- SEM for AGGs
- Conditional Dominance
- TGS Feasibility Program
- Asymptotic Analysis of SEM for AGGs
- Further Speedups for k-Symmetric Games
- Experimental Evaluation
- Experimental Setup
- Results
- Conclusion
- References
- Heavy Traffic Approximation of Equilibria in Resource Sharing Games
- Introduction
- Resource Sharing Game
- Nash Equilibrium
- Characterizing Processing Times
- Existence of NE
- Heavy Traffic Approximation: Job Level
- Approximating the Processing Time
- Heavy Traffic Equilibrium
- Heavy Traffic Approximation: Class Level
- Sensitivity, Efficiency and Revenue
- Sensitivity
- Efficiency
- Revenue
- References
- An NTU Cooperative Game Theoretic View of Manipulating Elections
- Introduction
- Preliminaries
- Manipulation Model
- Main Results
- Conclusions and Future Work
- References
- Short Papers
- The Price of Civil Society
- Introduction
- Model and Notation
- Main Results
- Atomic Games
- Nonatomic Games
- Extensions and Future Work
- References
- The Robust Price of Anarchy of Altruistic Games
- Introduction
- Altruistic Games and the Robust Price of Anarchy
- Cost-Sharing Games
- Utility Games
- Congestion Games
- References
- Revenue Enhancement in Ad Auctions
- Introduction
- Model and Preliminaries
- Ad Auctions
- VCG and GSP
- Known Properties of GSP
- Generalized Next Price Auctions
- Boosting Revenue via Randomization
- Discussion
- References
- Bilinear Games: Polynomial Time Algorithms for Rank Based Subclasses
- Introduction
- Bilinear Games and Nash Equilibria
- Rank-1 Games and Polynomial Time Algorithm
- Algorithm
- FPTAS for Rank-k Games
- FPTAS for Approximate NE
- FPTAS for Relative Approximate NE
- Games with a Low Rank Matrix
- References
- Extending Characterizations of Truthful Mechanisms from Subdomains to Domains
- Introduction
- Definitions and Preliminaries
- Our Results
- Conclusion and Future Directions
- References
- Working Papers
- Optimal Multi-period Pricing with Service Guarantees Working Paper
- Pricing and Efficiency in the Market for IP Addresses Working Paper
- A Note on the Incompatibility of Strategy-Proofness and Pareto-Optimalityin Quasi-Linear Settings with Public Budgets Working Paper
- Author Index
