2026-07-21T18:41:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:183 2024-03-06T11:06:06Z ddc:004 open_access

Fair Payments for Efficient Allocations in Public Sector Combinatorial Auctions Day, Robert Raghavan, S. auctions core bidder-Pareto-optimal constraint generation VCG payments proxy auctions combinatorial auctions Motivated by the increasing use of auctions by government agencies, we consider the problem of fairly pricing public goods in a combinatorial auction. A well-known problem with the incentive-compatible Vickrey-Clarke-Groves (VCG) auction mechanism is that the resulting prices may not be in the core. Loosely speaking, this means the payments of the winners could be so low, that there are losing bidders who would have been willing to pay more than the payments of the winning bidders. Clearly, this ``unfair'' outcome is unacceptable for a public-sector auction. Proxy-based combinatorial auctions, in which each bidder submits several package bids to a proxy, result in efficient outcomes and bidder-Pareto-optimal core-payments by winners, thus offering a viable practical alternative to address this problem. This paper confronts two critical issues facing the proxy-auction. First, motivated to minimize a bidder's ability to benefit through strategic manipulation (through collusive agreement or unilateral action), we demonstrate the strength of a mechanism that minimizes total payments among all possible proxy auction outcomes, narrowing the previously broad solution concept. Secondly, we address the computational difficulties of achieving these outcomes with a constraint-generation approach, promising to broaden the range of applications for which the proxy-auction achieves a comfortably rapid solution. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Robert Day and S. Raghavan 2005 Is Part Of Dagstuhl Seminar Proceedings, Volume 5011, Computing and Markets (2005) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.05011.9 urn:nbn:de:0030-drops-1832 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.9 eng https://creativecommons.org/licenses/by/4.0/legalcode