Efficient Interdependent Value Combinatorial Auctions with Single Minded Bidders

Robu, Valentin; Parkes, David C.; Ito, Takayuki; Jennings, Nicholas R.

Efficient Interdependent Value Combinatorial Auctions with Single Minded Bidders

Valentin Robu, David C. Parkes, Takayuki Ito, Nicholas R. Jennings

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 339-344.

Abstract

We study the problem of designing efficient auctions where bidders have interdependent values; i.e., values that depend on the signals of other agents. We consider a contingent bid model in which agents can explicitly condition the value of their bids on the bids submitted by others. In particular, we adopt a linear contingent bidding model for single minded combinatorial auctions (CAs), in which submitted bids are linear combinations of bids received from others. We extend the existing state of the art, by identifying constraints on the interesting bundles and contingency weights reported by the agents which allow the efficient second priced, fixed point bids auction to be implemented in single minded CAs. Moreover, for domains in which the required single crossing condition fails (which characterizes when efficient, IC auctions are possible), we design a two-stage mechanism in which a subset of agents (''experts) are allocated first, using their reports to allocate the remaining items to the other agents.

Valentin Robu, David C. Parkes, Takayuki Ito, and Nicholas R. Jennings. 2013. Efficient Interdependent Value Combinatorial Auctions with Single Minded Bidders. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 339–344. https://ijcai.org/proceedings/2013/58

@inproceedings{ijcai2013p58,
  title     = {Efficient Interdependent Value Combinatorial Auctions with Single Minded Bidders},
  author    = {Robu, Valentin and Parkes, David C. and Ito, Takayuki and Jennings, Nicholas R.},
  booktitle = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {339--344},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/58},
}

TY  - CPAPER
TI  - Efficient Interdependent Value Combinatorial Auctions with Single Minded Bidders
AU  - Robu, Valentin
AU  - Parkes, David C.
AU  - Ito, Takayuki
AU  - Jennings, Nicholas R.
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 339
EP  - 344
UR  - https://ijcai.org/proceedings/2013/58
ER  -