How bidders communicate bids to the auctioneer (the bidding language) is a central concern for any auction. It's pretty straightforward for unit good auctions (I'll pay $5 for A or I'll sell B for $4), but combinatorial auctions involve arbitrary packages of goods; the set of all possible bids is the powerset of the goods being auctioned. Having bidders attach a value to each package is both a computational impossibility for anything more than a few goods and a "UX" nightmare. For example, a bidder that wants to buy A for at most $5 in a market for goods A and B with free disposal (meaning you'll take something extra if it's free) needs to enter the bid ({A, $5}, {AB, $5}).
Information theory tells us that no universal bidding language (there's a representation of any package of interest) is uniformly more compact than the power set representation. Nonetheless, a good bidding language makes "common" bids compact and easy to communicate. We thought about this problem deeply and realized that functionally pure computer programs mapping proposals (packages of goods) to valuations (how much the bidder will pay or would want to receive) are about as natural as it gets. There's a direct analog in asking a human or a pricing algo for a price in a bilateral trade setting. However, our optimizer doesn't know what to do with an arbitrary computer algorithm, and exhaustively querying one to get the power set of prices out is computationally infeasible. However, using formal methods, we can (in the right setting) convert a computer program into an equivalent representation in a logic fragment called mixed integer real arithmetic. And that (via SMT solving) is something that an optimizer can work with.
You can see what Proxy Bidders (the pure functions that create expressive bids) look like here [1].
Comments
Can you elaborate on how it's challenging in a UX sense? I'm curious to know what the challenges are.
How bidders communicate bids to the auctioneer (the bidding language) is a central concern for any auction. It's pretty straightforward for unit good auctions (I'll pay $5 for A or I'll sell B for $4), but combinatorial auctions involve arbitrary packages of goods; the set of all possible bids is the powerset of the goods being auctioned. Having bidders attach a value to each package is both a computational impossibility for anything more than a few goods and a "UX" nightmare. For example, a bidder that wants to buy A for at most $5 in a market for goods A and B with free disposal (meaning you'll take something extra if it's free) needs to enter the bid ({A, $5}, {AB, $5}).
Information theory tells us that no universal bidding language (there's a representation of any package of interest) is uniformly more compact than the power set representation. Nonetheless, a good bidding language makes "common" bids compact and easy to communicate. We thought about this problem deeply and realized that functionally pure computer programs mapping proposals (packages of goods) to valuations (how much the bidder will pay or would want to receive) are about as natural as it gets. There's a direct analog in asking a human or a pricing algo for a price in a bilateral trade setting. However, our optimizer doesn't know what to do with an arbitrary computer algorithm, and exhaustively querying one to get the power set of prices out is computationally infeasible. However, using formal methods, we can (in the right setting) convert a computer program into an equivalent representation in a logic fragment called mixed integer real arithmetic. And that (via SMT solving) is something that an optimizer can work with.
You can see what Proxy Bidders (the pure functions that create expressive bids) look like here [1].
[1]: https://www.onechronos.com/docs/expressive/bidding-guide/#in...
Thanks for the answer!