Invited Session Tue.1.H 3010

Tuesday, 10:30 - 12:00 h, Room: H 3010

Cluster 1: Approximation & online algorithms [...]

Approximation in algorithmic game theory

 

Chair: Chaitanya Swamy

 

 

Tuesday, 10:30 - 10:55 h, Room: H 3010, Talk 1

Konstantinos Georgiou
Black-box reductions for cost-sharing mechanism design

Coauthor: Chaitanya Swamy

 

Abstract:
We consider the design of strategyproof cost-sharing mechanisms, focusing mainly on the single-dimensional setting. We give two simple, but extremely versatile, black-box reductions, that in combination reduce the cost-sharing mechanism-design problem to the algorithmic problem of finding a minimum-cost solution for a set of players. Our first reduction shows that any α-approximation, truthful mechanism for the social-cost-minimization (SCM) problem that satisfies a technical no-bossiness condition can be morphed into a truthful mechanism that achieves an αlog n-approximation where the prices recover the cost incurred. This disconnects the task of truthfully computing an outcome with near-optimal social cost from the cost-sharing problem. Complementing this, our second reduction shows that any LP-based ρ-approximation for the problem of finding a min-cost solution for a set of players can be used to obtain a truthful, no-bossy, (ρ+1)-approximation for the SCM problem (and hence, a truthful (ρ + 1)log n-approximation cost-sharing mechanism).

 

 

Tuesday, 11:00 - 11:25 h, Room: H 3010, Talk 2

Berthold Vöcking
A universally-truthful approximation scheme for multi-unit auctions

 

Abstract:
We present a randomized, polynomial-time approximation scheme for multi-unit auctions. Our mechanism is truthful in the universal sense, i.e., a distribution over deterministically truthful mechanisms. Previously known approximation schemes were truthful in expectation which is a weaker notion of truthfulness assuming risk neutral bidders. The existence of a universally truthful approximation scheme was questioned by previous work showing that multi-unit auctions with certain technical restrictions on their output do not admit a polynomial-time, universally truthful mechanism with approximation factor better than two.
Our new mechanism employs VCG payments in a non-standard way: The deterministic mechanisms underlying our universally truthful approximation scheme are not maximal in range and do not belong to the class of affine maximizers which, on a first view, seems to contradict previous characterizations of VCG-based mechanisms. Instead, each of these deterministic mechanisms is composed of a collection of affine maximizers, one for each bidder which yields a subjective variant of VCG.

 

 

Tuesday, 11:30 - 11:55 h, Room: H 3010, Talk 3

Deeparnab Chakrabarty
Matching markets with ordinal preferences

Coauthors: Anand Bhalgat, Sanjeev Khanna, Chaitanya Swamy

 

Abstract:
In this talk we will consider the following basic economic problem: given n agents and n items with agents having a preference over these items, how should we allocate items to agents? The answer will depend on what we hope to achieve - we will see this goal is not very clear always. Furthermore, we would like our mechanisms which achieve these goals to be strategyproof - we will see that the definition of the same also is also arguable. After covering some groundwork, we'll describe some new analysis of old mechanisms, and (also new) analysis of some new algorithms.

 

  Today, Payday Loans Ohio are legitimate, but there are illegal transactions that are still on the rise. Since its introduction in the market buying Generic Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.