Search for: All records

We consider the following communication problem: Alice and Bob each have some valuation functions $$v_1(\cdot)$$ and $$v_2(\cdot)$$ over subsets of $$m$$ items, and their goal is to partition the items into $$S, \bar{S}$$ in a way that maximizes the welfare, $$v_1(S) + v_2(\bar{S})$$. We study both the allocation problem, which asks for a welfare-maximizing partition and the decision problem, which asks whether or not there exists a partition guaranteeing certain welfare, for binary XOS valuations. For interactive protocols with $poly(m)$ communication, a tight 3/4-approximation is known for both [Fei06,DS06]. For interactive protocols, the allocation problem is provably harder than the decision problem: any solution to the allocation problem implies a solution to the decision problem with one additional round and $$\log m$$ additional bits of communication via a trivial reduction. Surprisingly, the allocation problem is provably easier for simultaneous protocols. Specifically, we show: 1) There exists a simultaneous, randomized protocol with polynomial communication that selects a partition whose expected welfare is at least $3/4$ of the optimum. This matches the guarantee of the best interactive, randomized protocol with polynomial communication. 2) For all $$\varepsilon > 0$$, any simultaneous, randomized protocol that decides whether the welfare of the optimal partition is $$\geq 1$$ or $$\leq 3/4 - 1/108+\varepsilon$$ correctly with probability $> 1/2 + 1/ poly(m)$ requires exponential communication. This provides a separation between the attainable approximation guarantees via interactive ($3/4$) versus simultaneous ($$\leq 3/4-1/108$$) protocols with polynomial communication. In other words, this trivial reduction from decision to allocation problems provably requires the extra round of communication. We further discuss the implications of our results for the design of truthful combinatorial auctions in general, and extensions to general XOS valuations. In particular, our protocol for the allocation problem implies a new style of truthful mechanisms. 

We consider the problem of a single seller repeatedly selling a single item to a single buyer (specifically, the buyer has a value drawn fresh from known distribution $$D$$ in every round). Prior work assumes that the buyer is fully rational and will perfectly reason about how their bids today affect the seller's decisions tomorrow. In this work we initiate a different direction: the buyer simply runs a no-regret learning algorithm over possible bids. We provide a fairly complete characterization of optimal auctions for the seller in this domain. Specifically: 1) If the buyer bids according to EXP3 (or any ``mean-based'' learning algorithm), then the seller can extract expected revenue arbitrarily close to the expected welfare. This auction is independent of the buyer's valuation $$D$$, but somewhat unnatural as it is sometimes in the buyer's interest to overbid. 2) There exists a learning algorithm $$\mathcal{A}$$ such that if the buyer bids according to $$\mathcal{A}$$ then the optimal strategy for the seller is simply to post the Myerson reserve for $$D$$ every round. 3) If the buyer bids according to EXP3 (or any ``mean-based'' learning algorithm), but the seller is restricted to ``natural'' auction formats where overbidding is dominated (e.g. Generalized First-Price or Generalized Second-Price), then the optimal strategy for the seller is a pay-your-bid format with decreasing reserves over time. Moreover, the seller's optimal achievable revenue is characterized by a linear program, and can be unboundedly better than the best truthful auction yet simultaneously unboundedly worse than the expected welfare.