  Serial dictatorship is a simple mechanism for coordinating agents in solving
combinatorial optimization problems according to their preferences. The most
representative such problem is one-sided matching, in which a set of n agents
have values for a set of n items, and the objective is to compute a matching of
the agents to the items of maximum total value (a.k.a., social welfare).
Following the recent framework of Caragiannis and Rathi [10], we consider a
model in which the agent-item values are not available upfront but become known
by querying agent sequences. In particular, when the agents are asked to act in
a sequence, they respond by picking their favorite item that has not been
picked by agents who acted before and reveal their value for it. Can we compute
an agent sequence that induces a social welfare-optimal matching?
  We answer this question affirmatively and present an algorithm that uses
polynomial number (n^5) of queries. This solves the main open problem stated by
Caragiannis and Rathi [CR23]. Our analysis uses a potential function argument
that measures progress towards learning the underlying edge-weight information.
Furthermore, the algorithm has a truthful implementation by adapting the
paradigm of VCG payments.
