(with Daniel Houser and Weiwei Zheng)
We present an efficient linear program that can be used to solve winner determination problem for combinatorial auction in a market with both private and public goods. The setting can be applied to voters bidding in an interpretive environment with a propositional logic bidding language. We allow for a wide set of constraints, complement and substitute relations, and discuss several Cumulative Utility Functions. Solving the winner determination problem as a linear program proves to have a large computational advantage over other methods, which is valuable due to problem being generally NP-complete. We confirm this result with in silico experiments.
The paper uses Thue-Morse sequence and knapsack problem to formally relate several problems of negotiations, fair division and tournament sequencing. All of the considered problems are shown to be reduced versions of partitioning problem, i.e. equally dividing items into two sets. An argument is made that it is often beneficial to set the partitioning problem as stochastic with item values drawn from a distribution, especially but not limited to the case of intangible items like skill level. Balanced alternation according to Thue-Morse sequence proves to be the better mechanic in this case for all sample sizes for common distributions. This is not true for all distributions and for settings with k>2 agents. A further improvement upon this mechanic is greedy approximation over the underlying subset-sum problem.
(with Mikhail Freer)