path: root/wasserstein/include/auction_oracle_kdtree_restricted.hpp

/*

Copyright (c) 2015, M. Kerber, D. Morozov, A. Nigmetov
All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

You are under no obligation whatsoever to provide any bug fixes, patches, or
upgrades to the features, functionality or performance of the source code
(Enhancements) to anyone; however, if you choose to make your Enhancements
available either publicly, or directly to copyright holder,
without imposing a separate written license agreement for such Enhancements,
then you hereby grant the following license: a  non-exclusive, royalty-free
perpetual license to install, use, modify, prepare derivative works, incorporate
into other computer software, distribute, and sublicense such enhancements or
derivative works thereof, in binary and source code form.

  */
#ifndef AUCTION_ORACLE_KDTREE_RESTRICTED_HPP
#define AUCTION_ORACLE_KDTREE_RESTRICTED_HPP

#include <assert.h>
#include <algorithm>
#include <functional>
#include <iterator>

#include "def_debug_ws.h"
#include "auction_oracle_kdtree_restricted.h"


#ifdef FOR_R_TDA
#undef DEBUG_AUCTION
#endif

namespace hera {
namespace ws {


// *****************************
// AuctionOracleKDTreeRestricted
// *****************************



template <class Real_, class PointContainer_>
std::ostream& operator<<(std::ostream& output, const AuctionOracleKDTreeRestricted<Real_, PointContainer_>& oracle)
{
    output << "Oracle " << &oracle << std::endl;
    output << "max_val_ = " << oracle.max_val_ << ", ";
    output << "best_diagonal_items_computed_ = " << oracle.best_diagonal_items_computed_ << ", ";
    output << "best_diagonal_item_value_ = " << oracle.best_diagonal_item_value_ << ", ";
    output << "second_best_diagonal_item_idx_ = " << oracle.second_best_diagonal_item_idx_ << ", ";
    output << "second_best_diagonal_item_value_ = " << oracle.second_best_diagonal_item_value_ << ", ";
    output << "prices = " << format_container_to_log(oracle.prices) << "\n";
    output << "diag_items_heap_ = " << losses_heap_to_string(oracle.diag_items_heap_) << "\n";
    output << "top_diag_indices_ = " << format_container_to_log(oracle.top_diag_indices_) << "\n";
    output << "top_diag_counter_ = " << oracle.top_diag_counter_ << "\n";
    output << "top_diag_lookup_ = " << format_container_to_log(oracle.top_diag_lookup_) << "\n";
    output << "end of oracle " << &oracle << std::endl;
    return output;
}


template<class Real_, class PointContainer_>
AuctionOracleKDTreeRestricted<Real_, PointContainer_>::AuctionOracleKDTreeRestricted(const PointContainer_& _bidders,
                                                                   const PointContainer_& _items,
                                                                   const AuctionParams<Real>& params) :
    AuctionOracleBase<Real>(_bidders, _items, params),
    heap_handles_indices_(_items.size(), k_invalid_index),
    kdtree_items_(_items.size(), k_invalid_index),
    top_diag_lookup_(_items.size(), k_invalid_index)
{
    size_t dnn_item_idx { 0 };
    size_t true_idx { 0 };
    dnn_points_.clear();
    dnn_points_.reserve(this->items.size());
    // store normal items in kd-tree
    for(const auto& g : this->items) {
        if (g.is_normal() ) {
            kdtree_items_[true_idx] = dnn_item_idx;
            // index of items is id of dnn-point
            DnnPoint p(true_idx);
            p[0] = g.getRealX();
            p[1] = g.getRealY();
            dnn_points_.push_back(p);
            assert(dnn_item_idx == dnn_points_.size() - 1);
            dnn_item_idx++;
        }
        true_idx++;
    }

    assert(dnn_points_.size() < _items.size() );
    for(size_t i = 0; i < dnn_points_.size(); ++i) {
        dnn_point_handles_.push_back(&dnn_points_[i]);
    }
    DnnTraits traits;
    traits.internal_p = params.internal_p;
    kdtree_ = new dnn::KDTree<DnnTraits>(traits, dnn_point_handles_, params.wasserstein_power);

    size_t handle_idx {0};
    for(size_t item_idx = 0; item_idx < _items.size(); ++item_idx) {
        if (this->items[item_idx].is_diagonal()) {
            heap_handles_indices_[item_idx] = handle_idx++;
            diag_heap_handles_.push_back(diag_items_heap_.push(std::make_pair(item_idx, 0.0)));
        }
    }
    max_val_ = 3*getFurthestDistance3Approx<>(_bidders, _items, params.internal_p);
    max_val_ = std::pow(max_val_, params.wasserstein_power);
    weight_adj_const_ = max_val_;
}


template<class Real_, class PointContainer_>
bool AuctionOracleKDTreeRestricted<Real_, PointContainer_>::is_in_top_diag_indices(const size_t item_idx) const
{
    return top_diag_lookup_[item_idx] != k_invalid_index;
}


template<class Real_, class PointContainer_>
void AuctionOracleKDTreeRestricted<Real_, PointContainer_>::add_top_diag_index(const size_t item_idx)
{
    assert(find(top_diag_indices_.begin(), top_diag_indices_.end(), item_idx) == top_diag_indices_.end());
    assert(this->items[item_idx].is_diagonal());

    top_diag_indices_.push_back(item_idx);
    top_diag_lookup_[item_idx] = top_diag_indices_.size() - 1;
}

template<class Real_, class PointContainer_>
void AuctionOracleKDTreeRestricted<Real_, PointContainer_>::remove_top_diag_index(const size_t item_idx)
{
    if (top_diag_indices_.size() > 1) {
        // remove item_idx from top_diag_indices after swapping
        // it with the last element, update index lookup appropriately
        auto old_index = top_diag_lookup_[item_idx];
        auto end_element = top_diag_indices_.back();
        std::swap(top_diag_indices_[old_index], top_diag_indices_.back());
        top_diag_lookup_[end_element] = old_index;
    }

    top_diag_indices_.pop_back();
    top_diag_lookup_[item_idx] = k_invalid_index;
    if (top_diag_indices_.size() < 2) {
        recompute_second_best_diag();
    }
    best_diagonal_items_computed_ = not top_diag_indices_.empty();
    reset_top_diag_counter();
}


template<class Real_, class PointContainer_>
void AuctionOracleKDTreeRestricted<Real_, PointContainer_>::increment_top_diag_counter()
{
    assert(top_diag_counter_ >= 0 and top_diag_counter_ < top_diag_indices_.size());

    ++top_diag_counter_;
    if (top_diag_counter_ >= top_diag_indices_.size()) {
        top_diag_counter_ -= top_diag_indices_.size();
    }

    assert(top_diag_counter_ >= 0 and top_diag_counter_ < top_diag_indices_.size());
}


template<class Real_, class PointContainer_>
void AuctionOracleKDTreeRestricted<Real_, PointContainer_>::reset_top_diag_counter()
{
    top_diag_counter_ = 0;
}

template<class Real_, class PointContainer_>
void AuctionOracleKDTreeRestricted<Real_, PointContainer_>::recompute_top_diag_items(bool hard)
{
    assert(hard or top_diag_indices_.empty());

    if (hard) {
        std::fill(top_diag_lookup_.begin(), top_diag_lookup_.end(), k_invalid_index);
        top_diag_indices_.clear();
    }

    auto top_diag_iter = diag_items_heap_.ordered_begin();
    best_diagonal_item_value_ = top_diag_iter->second;
    add_top_diag_index(top_diag_iter->first);

    ++top_diag_iter;

    // traverse the heap while we see the same value
    while(top_diag_iter != diag_items_heap_.ordered_end()) {
        if ( top_diag_iter->second != best_diagonal_item_value_) {
            break;
        } else {
            add_top_diag_index(top_diag_iter->first);
        }
        ++top_diag_iter;
    }

    recompute_second_best_diag();

    best_diagonal_items_computed_ = true;
    reset_top_diag_counter();
}

template<class Real_, class PointContainer_>
typename AuctionOracleKDTreeRestricted<Real_, PointContainer_>::DebugOptimalBidR
AuctionOracleKDTreeRestricted<Real_, PointContainer_>::get_optimal_bid_debug(IdxType bidder_idx) const
{
    auto bidder = this->bidders[bidder_idx];

    size_t best_item_idx = k_invalid_index;
    size_t second_best_item_idx = k_invalid_index;
    Real best_item_value = std::numeric_limits<Real>::max();
    Real second_best_item_value = std::numeric_limits<Real>::max();

    for(IdxType item_idx = 0; item_idx < static_cast<IdxType>(this->items.size()); ++item_idx) {
        auto item = this->items[item_idx];
        if (item.type != bidder.type and item_idx != bidder_idx)
            continue;
        auto item_value = std::pow(dist_lp(bidder, item, this->internal_p, 2), this->wasserstein_power) + this->prices[item_idx];
        if (item_value < best_item_value) {
            best_item_value = item_value;
            best_item_idx = item_idx;
        }
    }

    assert(best_item_idx != k_invalid_index);

    for(size_t item_idx = 0; item_idx < this->items.size(); ++item_idx) {
        auto item = this->items[item_idx];
        if (item.type != bidder.type and static_cast<IdxType>(item_idx) != bidder_idx)
            continue;
        if (item_idx == best_item_idx)
            continue;
        auto item_value = std::pow(dist_lp(bidder, item, this->internal_p, 2), this->wasserstein_power) + this->prices[item_idx];
        if (item_value < second_best_item_value) {
            second_best_item_value = item_value;
            second_best_item_idx = item_idx;
        }
    }

    assert(second_best_item_idx != k_invalid_index);
    assert(second_best_item_value >= best_item_value);

    DebugOptimalBidR result;

    result.best_item_idx = best_item_idx;
    result.best_item_value = best_item_value;
    result.second_best_item_idx = second_best_item_idx;
    result.second_best_item_value = second_best_item_value;

    return result;
}


template<class Real_, class PointContainer_>
IdxValPair<Real_> AuctionOracleKDTreeRestricted<Real_, PointContainer_>::get_optimal_bid(IdxType bidder_idx)
{
    auto bidder = this->bidders[bidder_idx];

    // corresponding point is always considered as a candidate
    // if bidder is a diagonal point, proj_item is a normal point,
    // and vice versa.

    size_t best_item_idx { k_invalid_index };
    size_t second_best_item_idx { k_invalid_index };
    size_t best_diagonal_item_idx { k_invalid_index };
    Real best_item_value;
    Real second_best_item_value;


    size_t proj_item_idx = bidder_idx;
    assert( 0 <= proj_item_idx and proj_item_idx < this->items.size() );
    assert(this->items[proj_item_idx].type != bidder.type);
    Real proj_item_value = this->get_value_for_bidder(bidder_idx, proj_item_idx);

    if (bidder.is_diagonal()) {
        // for diagonal bidder the only normal point has already been added
        // the other 2 candidates are diagonal items only, get from the heap
        // with prices

        if (not best_diagonal_items_computed_) {
            recompute_top_diag_items();
        }

        best_diagonal_item_idx = top_diag_indices_[top_diag_counter_];
        increment_top_diag_counter();

        if ( proj_item_value < best_diagonal_item_value_) {
            best_item_idx = proj_item_idx;
            best_item_value = proj_item_value;
            second_best_item_value = best_diagonal_item_value_;
            second_best_item_idx = best_diagonal_item_idx;
        } else if (proj_item_value < second_best_diagonal_item_value_) {
            best_item_idx = best_diagonal_item_idx;
            best_item_value = best_diagonal_item_value_;
            second_best_item_value = proj_item_value;
            second_best_item_idx = proj_item_idx;
        } else {
            best_item_idx = best_diagonal_item_idx;
            best_item_value = best_diagonal_item_value_;
            second_best_item_value = second_best_diagonal_item_value_;
            second_best_item_idx = second_best_diagonal_item_idx_;
        }
    } else {
        // for normal bidder get 2 best items among non-diagonal points from
        // kdtree_
        DnnPoint bidder_dnn;
        bidder_dnn[0] = bidder.getRealX();
        bidder_dnn[1] = bidder.getRealY();
        auto two_best_items = kdtree_->findK(bidder_dnn, 2);
        size_t best_normal_item_idx { two_best_items[0].p->id() };
        Real best_normal_item_value { two_best_items[0].d };
        // if there is only one off-diagonal point in the second diagram,
        // kd-tree will not return the second candidate.
        // Set its value to inf, so it will always lose to the value of the projection
        Real second_best_normal_item_value { two_best_items.size() == 1 ? std::numeric_limits<Real>::max() : two_best_items[1].d };

        if ( proj_item_value < best_normal_item_value) {
            best_item_idx = proj_item_idx;
            best_item_value = proj_item_value;
            second_best_item_value = best_normal_item_value;
        } else if (proj_item_value < second_best_normal_item_value) {
            best_item_idx = best_normal_item_idx;
            best_item_value = best_normal_item_value;
            second_best_item_value = proj_item_value;
        } else {
            best_item_idx = best_normal_item_idx;
            best_item_value = best_normal_item_value;
            second_best_item_value = second_best_normal_item_value;
        }
    }

    IdxValPair<Real> result;

    assert( second_best_item_value >= best_item_value );

    result.first = best_item_idx;
    result.second = ( second_best_item_value - best_item_value ) + this->prices[best_item_idx] + this->epsilon;

#ifdef DEBUG_KDTREE_RESTR_ORACLE
    auto db = get_optimal_bid_debug(bidder_idx);
    assert(fabs(db.best_item_value - best_item_value) < 0.000001);
    assert(fabs(db.second_best_item_value - second_best_item_value) < 0.000001);
    //std::cout << "bid OK" << std::endl;
#endif

    return result;
}
/*
a_{ij} = d_{ij}
value_{ij} = a_{ij} + price_j
*/
template<class Real_, class PointContainer_>
void AuctionOracleKDTreeRestricted<Real_, PointContainer_>::recompute_second_best_diag()
{
    if (top_diag_indices_.size() > 1) {
        second_best_diagonal_item_value_ = best_diagonal_item_value_;
        second_best_diagonal_item_idx_ = top_diag_indices_[0];
    } else {
        if (diag_items_heap_.size() == 1) {
            second_best_diagonal_item_value_ = std::numeric_limits<Real>::max();
            second_best_diagonal_item_idx_ = k_invalid_index;
        } else {
            auto diag_iter = diag_items_heap_.ordered_begin();
            ++diag_iter;
            second_best_diagonal_item_value_ = diag_iter->second;
            second_best_diagonal_item_idx_ = diag_iter->first;
        }
    }
}


template<class Real_, class PointContainer_>
void AuctionOracleKDTreeRestricted<Real_, PointContainer_>::set_price(IdxType item_idx,
                                                    Real new_price,
                                                    const bool update_diag)
{
    assert(this->prices.size() == this->items.size());
    assert( 0 < diag_heap_handles_.size() and diag_heap_handles_.size() <= this->items.size());
	// adjust_prices decreases prices,
    // also this variable must be true in reverse phases of FR-auction
	bool item_goes_down = new_price > this->prices[item_idx];

    this->prices[item_idx] = new_price;
    if ( this->items[item_idx].is_normal() ) {
        assert(0 <= item_idx and item_idx < static_cast<IdxType>(kdtree_items_.size()));
        assert(0 <= kdtree_items_[item_idx] and kdtree_items_[item_idx] < dnn_point_handles_.size());
        kdtree_->change_weight( dnn_point_handles_[kdtree_items_[item_idx]], new_price);
    } else {
        assert(diag_heap_handles_.size() > heap_handles_indices_.at(item_idx));
		if (item_goes_down) {
			diag_items_heap_.decrease(diag_heap_handles_[heap_handles_indices_[item_idx]], std::make_pair(item_idx, new_price));
		} else {
			diag_items_heap_.increase(diag_heap_handles_[heap_handles_indices_[item_idx]], std::make_pair(item_idx, new_price));
		}
        if (update_diag) {
            // Update top_diag_indices_ only if necessary:
            // normal bidders take their projections, which might not be on top
            // also, set_price is called by adjust_prices, and we may have already
            // removed the item from top_diag
            if (is_in_top_diag_indices(item_idx)) {
                remove_top_diag_index(item_idx);
            }

            if (item_idx == (IdxType)second_best_diagonal_item_idx_) {
                recompute_second_best_diag();
            }
        }
    }
}


template<class Real_, class PointContainer_>
void AuctionOracleKDTreeRestricted<Real_, PointContainer_>::adjust_prices(Real delta)
{
    if (delta == 0.0)
        return;

    for(auto& p : this->prices) {
        p -= delta;
    }

    kdtree_->adjust_weights(delta);

    bool price_goes_up = delta < 0;

	for(size_t item_idx = 0; item_idx < this->items.size(); ++item_idx) {
        if (this->items[item_idx].is_diagonal()) {
            auto new_price = this->prices[item_idx];
            if (price_goes_up) {
                diag_items_heap_.decrease(diag_heap_handles_[heap_handles_indices_[item_idx]], std::make_pair(item_idx, new_price));
            } else {
                diag_items_heap_.increase(diag_heap_handles_[heap_handles_indices_[item_idx]], std::make_pair(item_idx, new_price));
            }
        }
	}
    best_diagonal_item_value_ -= delta;
    second_best_diagonal_item_value_ -= delta;
}

template<class Real_, class PointContainer_>
void AuctionOracleKDTreeRestricted<Real_, PointContainer_>::adjust_prices()
{
    auto pr_begin = this->prices.begin();
    auto pr_end = this->prices.end();
    Real min_price = *(std::min_element(pr_begin, pr_end));
    adjust_prices(min_price);
}

template<class Real_, class PointContainer_>
size_t AuctionOracleKDTreeRestricted<Real_, PointContainer_>::get_heap_top_size() const
{
    return top_diag_indices_.size();
}

template<class Real_, class PointContainer_>
std::pair<Real_, Real_> AuctionOracleKDTreeRestricted<Real_, PointContainer_>::get_minmax_price() const
{
    auto r = std::minmax_element(this->prices.begin(), this->prices.end());
    return std::make_pair(*r.first, *r.second);
}



template<class Real_, class PointContainer_>
AuctionOracleKDTreeRestricted<Real_, PointContainer_>::~AuctionOracleKDTreeRestricted()
{
    delete kdtree_;
}

template<class Real_, class PointContainer_>
void AuctionOracleKDTreeRestricted<Real_, PointContainer_>::sanity_check()
{
#ifdef DEBUG_KDTREE_RESTR_ORACLE
    if (best_diagonal_items_computed_) {
        std::vector<Real> diag_items_price_vec;
        diag_items_price_vec.reserve(this->items.size());

        for(size_t item_idx = 0; item_idx < this->items.size(); ++item_idx) {
            if (this->items.at(item_idx).is_diagonal()) {
                diag_items_price_vec.push_back(this->prices.at(item_idx));
            } else {
                diag_items_price_vec.push_back(std::numeric_limits<Real>::max());
            }
        }

        auto best_iter =  std::min_element(diag_items_price_vec.begin(), diag_items_price_vec.end());
        assert(best_iter != diag_items_price_vec.end());
        Real true_best_diag_value = *best_iter;
        size_t true_best_diag_idx = best_iter - diag_items_price_vec.begin();
        assert(true_best_diag_value != std::numeric_limits<Real>::max());

        Real true_second_best_diag_value = std::numeric_limits<Real>::max();
        size_t true_second_best_diag_idx = k_invalid_index;
        for(size_t item_idx = 0; item_idx < diag_items_price_vec.size(); ++item_idx) {
            if (this->items.at(item_idx).is_normal()) {
                assert(top_diag_lookup_.at(item_idx) == k_invalid_index);
                continue;
            }

            auto i_iter = std::find(top_diag_indices_.begin(), top_diag_indices_.end(), item_idx);
            if (diag_items_price_vec.at(item_idx) == true_best_diag_value) {
                assert(i_iter != top_diag_indices_.end());
                assert(top_diag_lookup_.at(item_idx) == i_iter - top_diag_indices_.begin());
            } else {
                assert(top_diag_lookup_.at(item_idx) == k_invalid_index);
                assert(i_iter == top_diag_indices_.end());
            }

            if (item_idx == true_best_diag_idx) {
                continue;
            }
            if (diag_items_price_vec.at(item_idx) < true_second_best_diag_value) {
                true_second_best_diag_value = diag_items_price_vec.at(item_idx);
                true_second_best_diag_idx = item_idx;
            }
        }

        assert(true_best_diag_value == best_diagonal_item_value_);
        assert(true_second_best_diag_idx != k_invalid_index);
        assert(true_second_best_diag_value == second_best_diagonal_item_value_);
    }
#endif
}


} // ws
} // hera

#endif