Timezone: »

 
Poster
Online Allocation and Learning in the Presence of Strategic Agents
Steven Yin · Shipra Agrawal · Assaf Zeevi

Wed Nov 30 09:00 AM -- 11:00 AM (PST) @ Hall J #812
in Poster Session 3 »
We study the problem of allocating $T$ sequentially arriving items among $n$ homogenous agents under the constraint that each agent must receive a prespecified fraction of all items, with the objective of maximizing the agents' total valuation of items allocated to them. The agents' valuations for the item in each round are assumed to be i.i.d. but their distribution is apriori unknown to the central planner.vTherefore, the central planner needs to implicitly learn these distributions from the observed values in order to pick a good allocation policy. However, an added challenge here is that the agents are strategic with incentives to misreport their valuations in order to receive better allocations. This sets our work apart both from the online auction mechanism design settings which typically assume known valuation distributions and/or involve payments, and from the online learning settings that do not consider strategic agents. To that end, our main contribution is an online learning based allocation mechanism that is approximately Bayesian incentive compatible, and when all agents are truthful, guarantees a sublinear regret for individual agents' utility compared to that under the optimal offline allocation policy.
Keywords: Online Learning · Resource Allocation · Incentive Compatibility
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Steven Yin (Scriptus.app)
Shipra Agrawal (Columbia University)
Assaf Zeevi (Columbia University)

More from the Same Authors