Internet and Network Economics

Name: Internet and Network Economics | 7th International Workshop, WINE 2011, Singapore, December 11-14, 2011, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

7th International Workshop, WINE 2011, Singapore, December 11-14, 2011, Proceedings

Ning Chen Edith Elkind Elias Koutsoupias(Herausgeber*in)

Springer (Verlag)

Erschienen am 2. Februar 2012

XII, 420 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-25510-6 (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
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

Systemvoraussetzungen

Als PDF speichern Als Link merken