NDLI: On the efficiency of the walrasian mechanism

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

Centrality, gossip, and diffusion of information in networks

Strategic trading in informationally complex environments

Generalized second price auction with probabilistic broad match

A dynamic network game for the adoption of new technologies

Clinching auctions beyond hard budget constraints

Individual security and network design

Optimal mechanisms with simple menus

Efficient voting via the top-k elicitation scheme: a probabilistic approach

Optimal allocation without money: an engineering approach

Adaptive contract design for crowdsourcing markets: bandit algorithms for repeated principal-agent problems

Reasoning about optimal stable matchings under partial information

The wisdom of smaller, smarter crowds

Incentivized optimal advert assignment via utility decomposition

Towards a better measure of business proximity: topic modeling for analyzing M As

Local computation mechanism design

Extensive-form game abstraction with bounds

Fair enough: guaranteeing approximate maximin shares

Routing and staffing when servers are strategic

Network formation games with heterogeneous players and the internet structure

On the efficiency of the walrasian mechanism

Long-run learning in games of cooperation

Pragmatic algorithmic game theory

Mechanism with unique learnable equilibria

Buying private data without verification

Recency, records and recaps: learning and non-equilibrium behavior in a simple decision problem

Incentivizing exploration

Expressiveness and robustness of first-price position auctions

Characterizing strategic cascades on networks

Deferred-acceptance auctions and radio spectrum reallocation

Cryptographically blinded games: leveraging players' limitations for equilibria and profit

Modularity and greed in double auctions

A local-dominance theory of voting equilibria

Two-sided matching with one-sided preferences

Removing arbitrage from wagering mechanisms

Manipulation of stable matchings using minimal blacklists

Revealing and incorporating implicit communities to improve recommender systems

Strategyproof allocation of discrete jobs on multiple machines

Why marketplace experimentation is harder than it seems: the role of test-control interference

Reallocation mechanisms

Bounds for the query complexity of approximate equilibria

Price of anarchy for auction revenue

Multiplicative bidding in online advertising

Simple approximate equilibria in large games

Strategy-proofness, investment efficiency, and marginal returns: an equivalence

Strategic information platforms: selective disclosure and the price of "free"

Simultaneous bayesian auctions and computational complexity

Differentially private and incentive compatible recommendation system for the adoption of network goods

Dynamically eliciting unobservable information

Optimal auctions for correlated buyers with sampling

Optimising trade-offs among stakeholders in ad auctions

The polarizing effect of network influences

The performance of deferred-acceptance auctions

The complexity of fairness through equilibrium

Duality and optimality of auctions for uniform distributions

Universal pareto dominance and welfare for plausible utility functions

Dynamic matching market design

Information aggregation in exponential family markets

Managing congestion in decentralized matching markets

Trick or treat: putting peer prediction to the test

Time-inconsistent planning: a computational problem in behavioral economics

Whole page optimization: how page elements interact with the position auction

Knightian self uncertainty in the vcg mechanism for unrestricted combinatorial auctions

Finding approximate nash equilibria of bimatrix games via payoff queries

Mechanism design for data science

Cournot competition in networked markets

Asymptotically truthful equilibrium selection in large congestion games

Optimal impartial selection

Level-0 meta-models for predicting human behavior in games

Contract complexity

A dynamic model of certification and reputation

Bandits with concave rewards and convex knapsacks

An axiomatic approach to characterizing and relaxing strategyproofness of one-sided matching mechanisms

Optimizing prices in descending clock auctions

Re-incentivizing discovery: mechanisms for partial-progress sharing in research

Approximate revenue maximization in interdependent value settings

Neutrality and geometry of mean voting

Misdirected search effort in a matching market: causes, consequences and a partial solution

A general volume-parameterized market making framework

Size versus truthfulness in the house allocation problem

Corporate prediction markets: evidence from google, ford, and firm X

Optimal contest design for simple agents

The empirical implications of privacy-aware choice

On the efficiency of the walrasian mechanism

Content Provider	ACM Digital Library
Author	Paes Leme, Renato Babaioff, Moshe Nisan, Noam Lucier, Brendan
Abstract	Central results in economics guarantee the existence of efficient equilibria for various classes of markets. An underlying assumption in early work is that agents are price-takers, i.e., agents honestly report their true demand in response to prices. A line of research in economics, initiated by Hurwicz (1972), is devoted to understanding how such markets perform when agents are strategic about their demands. This is captured by the Walrasian Mechanism that proceeds by collecting reported demands, finding clearing prices in the reported market via an ascending price tatonnement procedure, and returns the resulting allocation. Similar mechanisms are used, for example, in the daily opening of the New York Stock Exchange and the call market for copper and gold in London. In practice, it is commonly observed that agents in such markets reduce their demand leading to behaviors resembling bargaining and to inefficient outcomes. We ask how inefficient the equilibria can be. Our main result is that the welfare of every pure Nash equilibrium of the Walrasian mechanism is at least one quarter of the optimal welfare, when players have gross substitute valuations and do not overbid. Previous analysis of the Walrasian mechanism have resorted to large market assumptions to show convergence to efficiency in the limit. Our result shows that approximate efficiency is guaranteed regardless of the size of the market. We extend our results in several directions. First, our results extend to Bayes-Nash equilibria and outcomes of no regret learning via the smooth mechanism framework. We also extend our bounds to any mechanism that maximizes welfare with respect to the declared valuations and never charges agents more than their bids. Additionally, we consider other classes of valuations and bid spaces beyond those satisfying the gross substitutes conditions. Finally, we relax the no-overbidding assumption, and present bounds that are parameterized by the extent to which agents are willing to overbid.
Ending Page	800
Page Count	18
Starting Page	783
File Format	PDF
ISBN	9781450325653
DOI	10.1145/2600057.2602850
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-06-01
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Combinatorial auctions Walrasian equilibrium Price of anarchy
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