All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Macros Pages
Namespaces | Classes | Typedefs | Functions
paal::auctions Namespace Reference

Auctions namespace. More...

Namespaces

 concepts
 Auctions Concepts namespace.
 
 detail
 concepts
 

Classes

struct  auction_traits
 Types associated with all auctions. More...
 
class  value_query_auction_traits
 Types associated with value query auction. More...
 
struct  demand_query_auction_traits
 Types associated with demand query auction. More...
 
class  gamma_oracle_auction_traits
 Types associated with gamma oracle auction. More...
 

Typedefs

using base_auction_components = data_structures::components< bidders, items, data_structures::NameWithDefault< get_copies_num, utils::return_one_functor > >
 concepts More...
 
using value_query_components = detail::add_to_base_auction< value_query >
 detail More...
 
template<typename... Args>
using value_query_auction_components = typename value_query_components::type< Args...>
 value query auction components template alias More...
 
using demand_query_components = detail::add_to_base_auction< demand_query >
 definition for the components class for a demand query auction
 
template<typename... Args>
using demand_query_auction_components = typename demand_query_components::type< Args...>
 demand query auction components template alias More...
 
using gamma_oracle_components = detail::add_to_base_auction< gamma_oracle, gamma >
 definition for the components class for a gamma oracle auction.
 
template<typename... Args>
using gamma_oracle_auction_components = typename gamma_oracle_components::type< Args...>
 gamma oracle auction components template alias More...
 

Functions

template<typename... Args>
auto make_value_query_auction_components (Args &&...args) -> decltype(value_query_components::make_components(std::forward< Args >(args)...))
 make function for value query components More...
 
template<typename... Args>
auto make_demand_query_auction_components (Args &&...args)
 make function for demand query components More...
 
template<typename... Args>
auto make_gamma_oracle_auction_components (Args &&...args) -> decltype(gamma_oracle_components::make_components(std::forward< Args >(args)...))
 make function for gamma oracle components More...
 
template<class Auction >
auto items_number (Auction &&auction)
 Returns the number of different kinds of items in an auction. More...
 
template<class Auction >
auto bidders_number (Auction &&auction)
 Returns the number of bidders in an auction. More...
 
template<class Auction >
paal::auctions::auction_traits
< Auction >::copies_num_t 
get_minimum_copies_num (Auction &&auction)
 Returns minimum number of copies of an item in an auction. More...
 
template<class DemandQueryAuction , class OutputIterator , class ItemToLpIdMap , class SeparationOracle = paal::lp::random_violated_separation_oracle>
void fractional_determine_winners_in_demand_query_auction (DemandQueryAuction &&auction, OutputIterator result, ItemToLpIdMap item_to_id, double epsilon, SeparationOracle separation_oracle=SeparationOracle{})
 detail More...
 
template<class DemandQueryAuction , class OutputIterator >
void fractional_determine_winners_in_demand_query_auction (DemandQueryAuction &&auction, OutputIterator result, double epsilon=1e-7)
 This is fractional determine winners in demand query auction and return assignment of fractional bundles to bidders. This is version with default ItemToLpIdMap using std::unordered_map and default epsilon. More...
 
template<class Bidders , class Items , class GetValue , class GetItems , class GetCopiesNum = utils::return_one_functor>
auto make_single_minded_to_value_query_auction (Bidders &&bidders, Items &&items, GetValue get_value, GetItems get_items, GetCopiesNum get_copies_num=GetCopiesNum{}) -> decltype(make_xor_bids_to_value_query_auction(std::forward< Bidders >(bidders), std::forward< Items >(items), detail::get_bids(), get_value, get_items, get_copies_num))
 detail More...
 
template<class Bidders , class Items , class GetValue , class GetItems , class GetCopiesNum = utils::return_one_functor>
auto make_single_minded_to_demand_query_auction (Bidders &&bidders, Items &&items, GetValue get_value, GetItems get_items, GetCopiesNum get_copies_num=GetCopiesNum{}) -> decltype(make_xor_bids_to_demand_query_auction(std::forward< Bidders >(bidders), std::forward< Items >(items), detail::get_bids(), get_value, get_items, get_copies_num))
 Create demand query auction from single minded valuations. More...
 
template<class Bidders , class Items , class GetValue , class GetItems , class GetCopiesNum = utils::return_one_functor>
auto make_single_minded_to_gamma_oracle_auction (Bidders &&bidders, Items &&items, GetValue get_value, GetItems get_items, GetCopiesNum get_copies_num=GetCopiesNum{}) -> decltype(make_xor_bids_to_gamma_oracle_auction(std::forward< Bidders >(bidders), std::forward< Items >(items), detail::get_bids(), get_value, get_items, get_copies_num))
 Create gamma oracle auction from single minded valuations. More...
 
template<class Bidders , class GetItems , class OutputIterator >
void extract_items_from_single_minded (Bidders &&bidders, GetItems get_items, OutputIterator output)
 Extract all items appearing in all bidders' bids. This function doesn't eliminate duplicates, this is left out to the caller. More...
 
template<class GammaOracleAuction , class OutputIterator , class PriceMap , class Epsilon >
void determine_winners_in_gamma_oracle_auction (GammaOracleAuction &&auction, OutputIterator result, PriceMap price, Epsilon epsilon)
 detail More...
 
template<class GammaOracleAuction , class OutputIterator , class Epsilon = double>
void determine_winners_in_gamma_oracle_auction (GammaOracleAuction &&auction, OutputIterator result, Epsilon epsilon=1e-8)
 This is determine winners in gamma oracle auction and return assignment of bidders to items. This is version with default PriceMap using std::unordered_map and default epsilon. More...
 
template<class Bidders , class Items , class GetBids , class GetValue , class GetItems , class GetCopiesNum = utils::return_one_functor>
auto make_xor_bids_to_value_query_auction (Bidders &&bidders, Items &&items, GetBids get_bids, GetValue get_value, GetItems get_items, GetCopiesNum get_copies_num=GetCopiesNum{}) -> decltype(make_value_query_auction_components(std::forward< Bidders >(bidders), std::forward< Items >(items), detail::xor_bids_value_query< GetBids, GetValue, GetItems >(get_bids, get_value, get_items), get_copies_num))
 detail More...
 
template<class Bidders , class Items , class GetBids , class GetValue , class GetItems , class GetCopiesNum = utils::return_one_functor>
auto make_xor_bids_to_demand_query_auction (Bidders &&bidders, Items &&items, GetBids get_bids, GetValue get_value, GetItems get_items, GetCopiesNum get_copies_num=GetCopiesNum{})
 detail More...
 
template<class Bidders , class Items , class GetBids , class GetValue , class GetItems , class GetCopiesNum = utils::return_one_functor>
auto make_xor_bids_to_gamma_oracle_auction (Bidders &&bidders, Items &&items, GetBids get_bids, GetValue get_value, GetItems get_items, GetCopiesNum get_copies_num=GetCopiesNum{}) -> decltype(make_gamma_oracle_auction_components(std::forward< Bidders >(bidders), std::forward< Items >(items), detail::xor_bids_gamma_oracle< GetBids, GetValue, GetItems >(get_bids, get_value, get_items), 1, get_copies_num))
 detail More...
 
template<class Bidders , class GetBids , class GetItems , class OutputIterator >
void extract_items_from_xor_bids (Bidders &&bidders, GetBids get_bids, GetItems get_items, OutputIterator output)
 extract all items appearing in all bids. This function doesn't eliminate duplicates, this is left out to the caller. More...
 

Detailed Description

Auctions namespace.

Typedef Documentation

concepts

Definition for the components class representing an auction. This class is not meant to be directly used, it is just a base for the more specialized components interfaces.

Definition at line 204 of file auction_components.hpp.

template<typename... Args>
using paal::auctions::demand_query_auction_components = typedef typename demand_query_components::type<Args...>

demand query auction components template alias

Template Parameters
Args

Definition at line 261 of file auction_components.hpp.

template<typename... Args>
using paal::auctions::gamma_oracle_auction_components = typedef typename gamma_oracle_components::type<Args...>

gamma oracle auction components template alias

Template Parameters
Args

Definition at line 292 of file auction_components.hpp.

template<typename... Args>
using paal::auctions::value_query_auction_components = typedef typename value_query_components::type<Args...>

value query auction components template alias

Template Parameters
Args

Definition at line 229 of file auction_components.hpp.

detail

definition for the components class for a value query auction.

Definition at line 221 of file auction_components.hpp.

Function Documentation

template<class Auction >
auto paal::auctions::bidders_number ( Auction &&  auction)

Returns the number of bidders in an auction.

Parameters
auction
Template Parameters
Auction

Definition at line 50 of file auction_utils.hpp.

template<class GammaOracleAuction , class OutputIterator , class PriceMap , class Epsilon >
void paal::auctions::determine_winners_in_gamma_oracle_auction ( GammaOracleAuction &&  auction,
OutputIterator  result,
PriceMap  price,
Epsilon  epsilon 
)

detail

This is determine winners in gamma oracle auction and return assignment of items to bidders.

Example:

int main()
{
using Bidder = std::string;
using Item = std::string;
using Items = std::unordered_set<Item>;
using Value = double;
using Bid = std::pair<Items, Value>;
using Bids = std::vector<Bid>;
// create auction
const std::unordered_map<Bidder, Bids> bids {
{"John", {
{{"ball", "kite"}, 2},
{{"umbrella"}, 3},
{{"orange"}, 1.75},
{{"ball", "kite", "umbrella"}, 5},
{{"ball", "kite", "orange", "umbrella"}, 6.75},
}},
{"Bob", {
{{"orange"}, 1.5},
{{"apple"}, 2.0},
{{"apple", "orange"}, 4},
}},
{"Steve", {
{{"apple"}, 1},
{{"umbrella"}, 4},
{{"apple", "umbrella"}, 5},
}},
};
const std::vector<Bidder> bidders {"John", "Bob", "Steve"};
const std::vector<Item> items {"apple", "ball", "orange", "kite", "umbrella"};
auto get_bids = [&](const Bidder& bidder) -> const Bids& { return bids.at(bidder); };
auto get_value = [](const Bid& bid) { return bid.second; };
auto get_items = [](const Bid& bid) -> const Items& { return bid.first; };
bidders, items, get_bids, get_value, get_items
);
// determine winners
Value social_welfare = 0;
bidders, items, get_bids, get_value, get_items
);
auction,
boost::make_function_output_iterator([&](std::pair<Bidder, Items> p)
{
auto bidder = p.first;
auto& cur_items = p.second;
social_welfare += valuation.call<paal::auctions::value_query>(bidder, cur_items);
std::cout << bidder << " got bundle: ";
boost::copy(cur_items, std::ostream_iterator<Item>(std::cout, ", "));
std::cout << std::endl;
})
);
std::cout << "social welfare: " << social_welfare << std::endl;
return 0;
}

Complete example is winner_determination_in_MUCA_example.cpp.

Template Parameters
GammaOracleAuction
OutputIterator
PriceMap
Epsilon
Parameters
auction
result
priceStores the current mapping of items to prices. These are prices just for the working purposes of the algorithm, not the prices to be paid by the bidders.
epsilonUsed for floating point comparison to ensure feasibility.

Definition at line 106 of file winner_determination_in_MUCA.hpp.

template<class GammaOracleAuction , class OutputIterator , class Epsilon = double>
void paal::auctions::determine_winners_in_gamma_oracle_auction ( GammaOracleAuction &&  auction,
OutputIterator  result,
Epsilon  epsilon = 1e-8 
)

This is determine winners in gamma oracle auction and return assignment of bidders to items. This is version with default PriceMap using std::unordered_map and default epsilon.

Template Parameters
GammaOracleAuction
OutputIterator
Epsilon
Parameters
auction
result
epsilonUsed for floating point comparison to ensure feasibility.

Definition at line 218 of file winner_determination_in_MUCA.hpp.

template<class Bidders , class GetItems , class OutputIterator >
void paal::auctions::extract_items_from_single_minded ( Bidders &&  bidders,
GetItems  get_items,
OutputIterator  output 
)

Extract all items appearing in all bidders' bids. This function doesn't eliminate duplicates, this is left out to the caller.

Parameters
bidders
get_items
output
Template Parameters
Bidders
GetItems
OutputIterator

Definition at line 233 of file single_minded_auctions.hpp.

template<class Bidders , class GetBids , class GetItems , class OutputIterator >
void paal::auctions::extract_items_from_xor_bids ( Bidders &&  bidders,
GetBids  get_bids,
GetItems  get_items,
OutputIterator  output 
)

extract all items appearing in all bids. This function doesn't eliminate duplicates, this is left out to the caller.

Template Parameters
Bidders
GetBids
GetItems
OutputIterator
Parameters
bidders
get_bids
get_items
output

Definition at line 458 of file xor_bids.hpp.

template<class DemandQueryAuction , class OutputIterator , class ItemToLpIdMap , class SeparationOracle = paal::lp::random_violated_separation_oracle>
void paal::auctions::fractional_determine_winners_in_demand_query_auction ( DemandQueryAuction &&  auction,
OutputIterator  result,
ItemToLpIdMap  item_to_id,
double  epsilon,
SeparationOracle  separation_oracle = SeparationOracle{} 
)

detail

This is fractional determine winners in demand query auction and return assignment of fractional bundles to bidders.

Example:

Complete example is fractional_winner_determination_in_MUCA_example.cpp

Template Parameters
DemandQueryAuction
OutputIterator
ItemToLpIdMap
SeparationOracle
Parameters
auction
result
item_to_idStores the current mapping of items to LP column ids.
epsilonUsed for floating point comparison.
separation_oracleSeparation Oracle Strategy for searching the bidder with violated inequality.

Definition at line 113 of file fractional_winner_determination_in_MUCA.hpp.

template<class DemandQueryAuction , class OutputIterator >
void paal::auctions::fractional_determine_winners_in_demand_query_auction ( DemandQueryAuction &&  auction,
OutputIterator  result,
double  epsilon = 1e-7 
)

This is fractional determine winners in demand query auction and return assignment of fractional bundles to bidders. This is version with default ItemToLpIdMap using std::unordered_map and default epsilon.

Template Parameters
DemandQueryAuction
OutputIterator
Parameters
auction
result
epsilonUsed for floating point comparison.

Definition at line 224 of file fractional_winner_determination_in_MUCA.hpp.

template<class Auction >
paal::auctions::auction_traits<Auction>::copies_num_t paal::auctions::get_minimum_copies_num ( Auction &&  auction)

Returns minimum number of copies of an item in an auction.

Parameters
auction
Template Parameters
Auction

Definition at line 62 of file auction_utils.hpp.

template<class Auction >
auto paal::auctions::items_number ( Auction &&  auction)

Returns the number of different kinds of items in an auction.

Parameters
auction
Template Parameters
Auction

Definition at line 39 of file auction_utils.hpp.

template<typename... Args>
auto paal::auctions::make_demand_query_auction_components ( Args &&...  args)

make function for demand query components

Template Parameters
Args
Parameters
args
Returns
demand query components

Definition at line 272 of file auction_components.hpp.

template<typename... Args>
auto paal::auctions::make_gamma_oracle_auction_components ( Args &&...  args) -> decltype(gamma_oracle_components::make_components(std::forward<Args>(args)...))

make function for gamma oracle components

Template Parameters
Args
Parameters
args
Returns
gamma oracle components

Definition at line 303 of file auction_components.hpp.

template<class Bidders , class Items , class GetValue , class GetItems , class GetCopiesNum = utils::return_one_functor>
auto paal::auctions::make_single_minded_to_demand_query_auction ( Bidders &&  bidders,
Items &&  items,
GetValue  get_value,
GetItems  get_items,
GetCopiesNum  get_copies_num = GetCopiesNum{} 
) -> decltype(make_xor_bids_to_demand_query_auction( std::forward<Bidders>(bidders), std::forward<Items>(items), detail::get_bids(), get_value, get_items, get_copies_num ))

Create demand query auction from single minded valuations.

Parameters
bidders
items
get_value
get_items
get_copies_num
Template Parameters
Bidders
Items
GetValue
GetItems
GetCopiesNum

Definition at line 148 of file single_minded_auctions.hpp.

template<class Bidders , class Items , class GetValue , class GetItems , class GetCopiesNum = utils::return_one_functor>
auto paal::auctions::make_single_minded_to_gamma_oracle_auction ( Bidders &&  bidders,
Items &&  items,
GetValue  get_value,
GetItems  get_items,
GetCopiesNum  get_copies_num = GetCopiesNum{} 
) -> decltype(make_xor_bids_to_gamma_oracle_auction( std::forward<Bidders>(bidders), std::forward<Items>(items), detail::get_bids(), get_value, get_items, get_copies_num ))

Create gamma oracle auction from single minded valuations.

Parameters
bidders
items
get_value
get_items,@paramget_copies_num
Template Parameters
Bidders
Items
GetValue
GetItems
GetCopiesNum

Definition at line 195 of file single_minded_auctions.hpp.

template<class Bidders , class Items , class GetValue , class GetItems , class GetCopiesNum = utils::return_one_functor>
auto paal::auctions::make_single_minded_to_value_query_auction ( Bidders &&  bidders,
Items &&  items,
GetValue  get_value,
GetItems  get_items,
GetCopiesNum  get_copies_num = GetCopiesNum{} 
) -> decltype(make_xor_bids_to_value_query_auction( std::forward<Bidders>(bidders), std::forward<Items>(items), detail::get_bids(), get_value, get_items, get_copies_num ))

detail

Create value query auction from single minded valuations.

Parameters
bidders
items
get_value
get_items
get_copies_num
Template Parameters
Bidders
Items
GetValue
GetItems
GetCopiesNum

Definition at line 98 of file single_minded_auctions.hpp.

template<typename... Args>
auto paal::auctions::make_value_query_auction_components ( Args &&...  args) -> decltype(value_query_components::make_components(std::forward<Args>(args)...))

make function for value query components

Template Parameters
Args
Parameters
args
Returns
value query components

Definition at line 240 of file auction_components.hpp.

template<class Bidders , class Items , class GetBids , class GetValue , class GetItems , class GetCopiesNum = utils::return_one_functor>
auto paal::auctions::make_xor_bids_to_demand_query_auction ( Bidders &&  bidders,
Items &&  items,
GetBids  get_bids,
GetValue  get_value,
GetItems  get_items,
GetCopiesNum  get_copies_num = GetCopiesNum{} 
)

detail

Create demand query auction from xor bids valuations.

Parameters
bidders
items
get_bids
get_value
get_items
get_copies_num
Template Parameters
Bidders
Items
GetBids
GetValue
GetItems
GetCopiesNum

Definition at line 264 of file xor_bids.hpp.

template<class Bidders , class Items , class GetBids , class GetValue , class GetItems , class GetCopiesNum = utils::return_one_functor>
auto paal::auctions::make_xor_bids_to_gamma_oracle_auction ( Bidders &&  bidders,
Items &&  items,
GetBids  get_bids,
GetValue  get_value,
GetItems  get_items,
GetCopiesNum  get_copies_num = GetCopiesNum{} 
) -> decltype(make_gamma_oracle_auction_components( std::forward<Bidders>(bidders), std::forward<Items>(items), detail::xor_bids_gamma_oracle<GetBids, GetValue, GetItems>(get_bids, get_value, get_items), 1, get_copies_num ))

detail

Create gamma oracle auction from xor bids valuations.

Parameters
bidders
items
get_bids
get_value
get_items
get_copies_num
Template Parameters
Bidders
Items
GetBids
GetValue
GetItems
GetCopiesNum

Definition at line 418 of file xor_bids.hpp.

template<class Bidders , class Items , class GetBids , class GetValue , class GetItems , class GetCopiesNum = utils::return_one_functor>
auto paal::auctions::make_xor_bids_to_value_query_auction ( Bidders &&  bidders,
Items &&  items,
GetBids  get_bids,
GetValue  get_value,
GetItems  get_items,
GetCopiesNum  get_copies_num = GetCopiesNum{} 
) -> decltype(make_value_query_auction_components( std::forward<Bidders>(bidders), std::forward<Items>(items), detail::xor_bids_value_query<GetBids, GetValue, GetItems>(get_bids, get_value, get_items), get_copies_num ))

detail

Create value query auction from xor bids valuations.

Parameters
bidders
items
get_bids
get_value
get_items
get_copies_num
Template Parameters
Bidders
Items
GetBids
GetValue
GetItems
GetCopiesNum

Definition at line 170 of file xor_bids.hpp.