NDLI: Bayesian optimal auctions via multi- to single-agent reduction

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

On aggregation bias in sponsored search data: existence andimplications

Optimal bidding in multi-item multi-slot sponsored search auctions

Combinatorial auctions with restricted complements

Bayesian optimal auctions via multi- to single-agent reduction

Online prophet-inequality matching with applications to ad allocation

Sequential voting with externalities: herding in social networks

Finding overlapping communities in social networks: toward a rigorous approach

Strategyproofness in the large as a desideratum for market design

On bitcoin and red balloons

Dynamic pricing with limited supply

Optimal mechanisms for selling information

Optimization with demand oracles

Learning on a budget: posted price mechanisms for online procurement

Social influence in social advertising: evidence from field experiments

Multi-dimensional mechanism design with limited information

Mechanisms and allocations with positive network externalities

Optimal social choice functions: a utilitarian view

A bayesian market maker

Computing dominance-based solution concepts

Send mixed signals: earn more, work less

The groupon effect on yelp ratings: a root cause analysis

Mechanism design: from partial to probabilistic verification

Approximate pure nash equilibria in weighted congestion games: existence, efficient computation, and structure

Traffic shaping to optimize ad delivery

Ad serving using a compact allocation plan

Tatonnement in ongoing markets of complementary goods

How to schedule a cascade in an arbitrary graph

Efficiency of sequential english auctions with dynamic arrivals

Symmetries and optimal multi-dimensional mechanism design

Asymptotically optimal algorithm for stochastic adwords

The computational complexity of truthfulness in combinatorial auctions

Mechanism design on discrete lines and cycles

Simpler sybil-proof mechanisms for multi-level marketing

A tractable combinatorial market maker using constraint generation

Payment rules through discriminant-based classifiers

Finding a walrasian equilibrium is easy for a fixed number of agents

Clone structures in voters' preferences

Signaling schemes for revenue maximization

Revenue maximizing envy-free multi-unit auctions with budgets

Interviewing secretaries in parallel

Approximately optimal auctions for selling privacy when costs are correlated with data

Conditional equilibrium outcomes via ascending price processes with applications to combinatorial auctions with item bidding

Safe opponent exploitation

A truthful learning mechanism for contextual multi-slot sponsored search auctions with externalities

The structure of online diffusion networks

Improving the effectiveness of time-based display advertising

Mean field equilibria of multiarmed bandit games

Approximate revenue maximization with multiple items

Secondary spectrum auctions for symmetric and submodular bidders

Striving for social status

Information and the value of execution guarantees

Accuracy improvements for multi-criteria recommender systems

Behavioral experiments on a network formation game

Monotone branch-and-bound search for restricted combinatorial auctions

Matching models for preference-sensitive group purchasing

To match or not to match: economics of cookie matching in online advertising

Two-sided search with experts

Coalitional bargaining in networks

Local bargaining and endogenous fluctuations

Privacy-aware mechanism design

Profit-charging market makers with bounded loss, vanishing bid/ask spreads, and unlimited market depth

Beyond dominant resource fairness: extensions, limitations, and indivisibilities

Conducting truthful surveys, cheaply

Supply-limiting mechanisms

The price of anarchy in games of incomplete information

Lossy stochastic game abstraction with bounds

Market user interface design

Computing a proper equilibrium of a bimatrix game

Bayesian sequential auctions

Cooperation and assortativity with endogenous partner selection

Single-call mechanisms

Peer prediction without a common prior

Computing the margin of victory for various voting rules

Bayesian optimal auctions via multi- to single-agent reduction

Content Provider	ACM Digital Library
Author	Hartline, Jason Alaei, Saeed Fu, Hu Haghpanah, Nima Malekian, Azarakhsh
Abstract	We study an abstract optimal auction problem for selecting a subset of self-interested agents to whom to provide a service. A feasibility constraint governs which subsets can be simultaneously served; however, the mechanism may additionally choose to bundle unconstrained attributes such as payments or add-ons with the service. An agent's preference over service and attributes is given by her private type and may be multi-dimensional and non-linear. A single-agent problem is to optimizes a menu to offer an agent subject to constraints on the probabilities with which each of the agent's types is served. We give computationally tractable reductions from multi-agent auction problems to these single-agent problems. Our discussion focuses on maximizing revenue, but our results can be applied to other objectives (e.g., welfare). From each agent's perspective, any multi-agent mechanism and distribution on other agent types induces an interim allocation rule, i.e., a probability that the agent will be served as a function of the type she reports. The resulting profile of interim allocation rules (one for each agent) is feasible in the sense that there is a mechanism that induces it. An optimal mechanism can be solved for by inverting this process. Solve the single-agent problem of finding the optimal way to serve an agent subject to an interim allocation rule as a constraint (taking into account the agent's incentives). Optimize over interim feasible allocation profiles, i.e., ones that are induced by the type distribution and some mechanism, the cumulative revenue of the single-agent problems for the interim allocation profile. Find the mechanism that induces the optimal interim feasible allocation profile in the previous step. For a large class of auction problems and multi-dimensional and non-linear preferences each of the above steps is computationally tractable. We observe that the single-agent problems for (multi-dimensional) unit-demand and budgeted preferences can be solved in polynomial time in the size of the agent's type space via a simple linear program. For feasibility constraints induced by single-item auctions interim feasibility was characterized by Border (1991); we show that interim feasible allocation rules can be optimized over and implemented via a linear program that has quadratic complexity in the sum of the sizes of the individual agents' type spaces. We generalize Border's characterization to auctions where feasible outcomes are the independent sets of a matroid; here the characterization implies that the polytope of interim feasible allocation rules is a polymatroid. This connection implies that a concave objective, such as the revenue from the single-agent problems, can be maximized over the interim feasibility constraint in polynomial time. The resulting optimal mechanism can be viewed as a randomization over the vertices of the polymatroid which correspond to simple greedy mechanisms: given an ordering on a subset all agent types, serve the agents in this order subject to feasibility. Related work: Cai, Daskalakis, and Weinberg (2012) solve (independently) the single-item interim feasibility problem and use this solution to give tractable revenue-optimal multi-item auctions for agents with linear utilities.
Starting Page	17
Ending Page	17
Page Count	1
File Format	PDF
ISBN	9781450314152
DOI	10.1145/2229012.2229017
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-06-04
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Optimal mechanism design Border's constraints
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