NDLI: Combinatorial Auctions Do Need Modest Interaction

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

Fair Algorithms for Machine Learning

Dominant-Strategy versus Bayesian Multi-item Auctions: Maximum Revenue Determination and Comparison

The Double Clinching Auction for Wagering

The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm

A "Quantal Regret" Method for Structural Econometrics in Repeated Games

The Scope of Sequential Screening with Ex Post Participation Constraints

Accounting for Strategic Response in an Agent-Based Model of Financial Regulation

Stable Secretaries

Making Right Decisions Based on Wrong Opinions

A Simple and Approximately Optimal Mechanism for a Buyer with Complements: Abstract

Optimal Signaling Mechanisms in Unobservable Queues with Strategic Customers

Combinatorial Cost Sharing

Makespan Minimization via Posted Prices

Convex Program Duality, Fisher Markets, and Nash Social Welfare

Online Auctions and Multi-scale Online Learning

The Tragedy of your Upstairs Neighbors: Is the Negative Externality of Airbnb Internalized?

Truthful Allocation Mechanisms Without Payments: Characterization and Implications on Fairness

Planning with Multiple Biases

Approximating Gains from Trade in Two-sided Markets via Simple Mechanisms

Nash Social Welfare Approximation for Strategic Agents

Graphons: A Nonparametric Method to Model, Estimate, and Design Algorithms for Massive Networks

Stability, Strategy-Proofness, and Cumulative Offer Mechanisms

Simple Approximate Equilibria in Games with Many Players

Deferred-Acceptance Auctions for Multiple Levels of Service

Forecast Aggregation

Facilitating the Search for Partners on Matching Platforms: Restricting Agent Actions

The Theory is Predictive, but is it Complete?: An Application to Human Perception of Randomness

Dynamic Mechanisms with Martingale Utilities

Empirical Mechanism Design for Optimizing Clearing Interval in Frequent Call Markets

Computing Equilibrium in Matching Markets

Voting in the Limelight

Price Doubling and Item Halving: Robust Revenue Guarantees for Item Pricing

Information Sharing and Privacy in Networks

Truth and Regret in Online Scheduling

Controlled Dynamic Fair Division

Joint Pricing and Inventory Management with Strategic Customers

Interacting User Generated Content Technologies: How Q&As Affect Ratings & Reviews

From Monetary to Non-Monetary Mechanism Design via Artificial Currencies

Multidimensional Binary Search for Contextual Decision-Making

Approximately Efficient Two-Sided Combinatorial Auctions

Fair Public Decision Making

Stable Matching with Proportionality Constraints

Theoretical and Practical Advances on Smoothing for Extensive-Form Games

The Optimal Mechanism for Selling to a Budget Constrained Buyer: The General Case

Machine-Learning Aided Peer Prediction

Matching while Learning

Comparison-based Choices

Repeated Sales with Multiple Strategic Buyers

Potential Function Minimizers of Combinatorial Congestion Games: Efficiency and Computation

Communication Requirements and Informative Signaling in Matching Markets

Metric Distortion of Social Choice Rules: Lower Bounds and Fairness Properties

The Competition Complexity of Auctions: A Bulow-Klemperer Result for Multi-Dimensional Bidders

Algorithmic Persuasion with No Externalities

Cost-Sharing Methods for Scheduling Games under Uncertainty

A Lower Bound for Equitable Cake Cutting

Pricing and Optimization in Shared Vehicle Systems: An Approximation Framework

Learning in the Repeated Secretary Problem

Gibbard-Satterthwaite Success Stories and Obvious Strategyproofness

Bifurcation Mechanism Design - from Optimal Flat Taxes to Improved Cancer Treatments

Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium

Approximation Algorithms for Maximin Fair Division

Making it Safe to Use Centralized Markets: Epsilon - Dominant Individual Rationality and Applications to Market Design

A Network Game of Dynamic Traffic

Optimal Multi-Unit Mechanisms with Private Demands

Peer Prediction with Heterogeneous Users

Redesigning the Israeli Psychology Master's Match

Combinatorial Auctions Do Need Modest Interaction

Posted Price Mechanisms for a Random Stream of Customers

Surge Pricing Solves the Wild Goose Chase

Complementary Inputs and the Existence of Stable Outcomes in Large Trading Networks

Of the People: Voting Is More Effective with Representative Candidates

Assortment Optimisation under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments

Fairness Incentives for Myopic Agents

Multidimensional Dynamic Pricing for Welfare Maximization

Diffusion in Networks and the Unexpected Virtue of Burstiness

How (Not) to Allocate Affordable Housing

A Polynomial Time Algorithm for Spatio-Temporal Security Games

Combinatorial Auctions Do Need Modest Interaction

Content Provider	ACM Digital Library
Author	Assadi, Sepehr
Abstract	We study the necessity of interaction for obtaining efficient allocations in combinatorial auctions with subadditive bidders. This problem was originally introduced by Dobzinski, Nisan, and Oren (STOC'14) as the following simple market scenario: m items are to be allocated among n bidders in a distributed setting where bidders valuations are private and hence communication is needed to obtain an efficient allocation. The communication happens in rounds: in each round, each bidder, simultaneously with others, broadcasts a message to all parties involved. At the end, the central planner computes an allocation solely based on the communicated messages. Dobzinski et al. showed that (at least some) interaction is necessary for obtaining any efficient allocation: no non-interactive (1-round) protocol with polynomial communication (in the number of items and bidders) can achieve approximation ratio better than $Ω(m^{1/4}),$ while for any r ≥ 1, there exists r-round protocols that achieve Ō(r. $m1/^{r+1})$ approximation with polynomial communication; in particular, O(log m) rounds of interaction suffice to obtain an (almost) efficient allocation, i.e., a polylog(m)-approximation. A natural question at this point is to identify the "right" level of interaction (i.e., number of rounds) necessary to obtain an efficient allocation. In this paper, we resolve this question by providing an almost tight round-approximation tradeoff for this problem: we show that for any r ≥ 1, any r-round protocol that uses poly(m,n) bits of communication can only approximate the social welfare up to a factor of Ω(1 over r. m1/2 r+1). This in particular implies that Ω(log m over log log m) rounds of interaction are necessary for obtaining any efficient allocation (i.e., a constant or even a polylog(m)-approximation) in these markets. Our work builds on the recent multi-party round-elimination technique of Alon, Nisan, Raz, and Weinstein (FOCS'15) -- used to prove similar-in-spirit lower bounds for round-approximation tradeoff in unit-demand (matching) markets -- and settles an open question posed initially by Dobzinski et al., and subsequently by Alon et al.
Starting Page	145
Ending Page	162
Page Count	18
File Format	PDF
ISBN	9781450345279
DOI	10.1145/3033274.3085121
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2017-06-20
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Combinatorial auctions Round-approximation tradeoff Multi-party communication complexity
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