NDLI: Decentralized Dynamics and Fast Convergence in the Assignment Game: Extended Abstract

Please wait, while we are loading the content...

Econometrics for Learning Agents

Hidden Substitutes

Decentralized Dynamics and Fast Convergence in the Assignment Game: Extended Abstract

Online Reputation Management: Estimating the Impact of Management Responses on Consumer Reviews

Near-Optimum Online Ad Allocation for Targeted Advertising

Algorithms as Mechanisms: The Price of Anarchy of Relax-and-Round

A Non-asymptotic Approach to Analyzing Kidney Exchange Graphs

Designing Dynamic Contests

Information Asymmetries in Common-Value Auctions with Discrete Signals

Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries

Competitive Analysis via Benchmark Decomposition

Improved Efficiency Guarantees in Auctions with Budgets

Customer Referral Incentives and Social Media

At What Quality and What Price?: Eliciting Buyer Preferences as a Market Design Problem

Mechanisms for Fair Attribution

Integrating Market Makers, Limit Orders, and Continuous Trade in Prediction Markets

The Impact of the Sharing Economy on the Hotel Industry: Evidence from Airbnb's Entry Into the Texas Market

The Wisdom of Multiple Guesses

Dynamic Fair Division with Minimal Disruptions

Short Lists in Centralized Clearinghouses

Reverse Mechanism Design

Combining Traditional Marketing and Viral Marketing with Amphibious Influence Maximization

Finding Any Nontrivial Coarse Correlated Equilibrium Is Hard

Why Prices Need Algorithms

Full Substitutability in Trading Networks

Making the Most of Your Samples

Canary in the e-Commerce Coal Mine: Detecting and Predicting Poor Experiences Using Buyer-to-Seller Messages

Core-competitive Auctions

Smooth Online Mechanisms: A Game-Theoretic Problem in Renewable Energy Markets

Designing Matching Mechanisms under General Distributional Constraints

Managing Innovation in a Crowd

Simple Auctions with Simple Strategies

Matching with Stochastic Arrival

Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity

Truthful Mechanism Design via Correlated Tree Rounding

Estimating the Causal Impact of Recommendation Systems from Observational Data

Procurement Mechanisms for Differentiated Products

Sound Auction Specification and Implementation

Learning What's Going on: Reconstructing Preferences and Priorities from Opaque Transactions

Pricing in Ride-Sharing Platforms: A Queueing-Theoretic Approach

Generalized Decision Scoring Rules: Statistical, Computational, and Axiomatic Properties

Truthful Online Scheduling with Commitments

Redesigning the Israeli Medical Internship Match

Price Competition, Fluctuations and Welfare Guarantees

Approximability of Adaptive Seeding under Knapsack Constraints

Faster First-Order Methods for Extensive-Form Game Solving

Near Feasible Stable Matchings

Commitment Without Regrets: Online Learning in Stackelberg Security Games

Coalition Games on Interaction Graphs: A Horticultural Perspective

Adverse Selection and Auction Design for Internet Display Advertising

Greedy Algorithms Make Efficient Mechanisms

Private Pareto Optimal Exchange

Incentive-Compatible Experimental Design

Randomization Beats Second Price as a Prior-Independent Auction

Leximin Allocations in the Real World

Public Projects, Boolean Functions, and the Borders of Border's Theorem

Revenue Maximization and Ex-Post Budget Constraints

Inducing Approximately Optimal Flow Using Truthful Mediators

Team Performance with Test Scores

Bayesian Incentive-Compatible Bandit Exploration

Low-Cost Learning via Active Data Procurement

Bias and Reciprocity in Online Reviews: Evidence From Field Experiments on Airbnb

Behavioral Mechanism Design: Optimal Crowdsourcing Contracts and Prospect Theory

Markets with Production: A Polynomial Time Algorithm and a Reduction to Pure Exchange

Assigning More Students to their Top Choices: A Tiebreaking Rule Comparison

Robust Dynamic Pricing With Strategic Customers

Bidding Games and Efficient Allocations

Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models

Algorithms against Anarchy: Understanding Non-Truthful Mechanisms

An Approximate Law of One Price in Random Assignment Games

Strong Duality for a Multiple-Good Monopolist

The Burden of Risk Aversion in Mean-Risk Selfish Routing

Decentralized Dynamics and Fast Convergence in the Assignment Game: Extended Abstract

Content Provider	ACM Digital Library
Author	Pradelski, Bary S.R.
Abstract	We study decentralized learning dynamics for the classic assignment game with transferable utility [Shapley and Shubik 1972]. In our model agents follow an aspiration adjustment process based on their experienced payoffs (see [Sauermann and Selten 1962], [Nax and Pradelski 2014]). At random points in time firms and workers match, break up, and re-match in the search for better opportunities. Agents have aspiration levels that they adjust based on their experienced payoffs. When matched an agent occasionally tries to succeed with a higher bid than his current aspiration level. When single an agent lowers his aspiration level in the hope of attracting a partner. In particular agents have no knowledge about other players' payoffs or actions and they update their behavior in a myopic fashion. Behavior fluctuates according to a random variable that reflects current market sentiment: sometimes the firms exhibit greater price stickiness than the workers, and at other times the reverse holds. We show that this stochastic learning process converges in polynomial time to the core. While convergence to the core is known for some types of decentralized dynamics this paper is the first to prove {polynomial time convergence}, a crucial feature from an explanatory and market design standpoint. We also show that without market sentiment the dynamic exhibits exponential time convergence. The proof relies on novel results for random walks on graphs, and more generally suggests a fruitful connection between the theory of random walks and matching theory.
Starting Page	43
Ending Page	43
Page Count	1
File Format	PDF
ISBN	9781450334105
DOI	10.1145/2764468.2764470
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-06-15
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Convergence time Random walks Assignment games Matching markets Core Evolutionary game theory
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in