ABSTRACT
When donating money to a (say, charitable) cause, it is possible touse the contemplated donation as negotiating material to induce other parties interested in the charity to donate more. Such negotiation is usually done in terms of matching offers, where one party promises to pay a certain amount if others pay a certain amount. However, in their current form, matching offers allow for only limited negotiation. For one, it is not immediately clear how multiple parties can make matching offers at the same time without creating circular dependencies. Also, it is not immediately clear how to make adonation conditional on other donations to multiple charities, when the donator has different levels of appreciation for the different charities. In both these cases, the limited expressiveness of matching offers causes economic loss: it may happen that an arrangement that would have made all parties (donators as well as charities) better off cannot be expressed in terms of matching offers and will therefore notoccur.In this paper, we introduce a bidding language for expressing very general types of matching offers over multiple charities. We formulate the corresponding clearing problem (deciding how much each bidder pays, and how much each charity receives), and show that it is NP-complete to approximate to any ratio even in very restricted settings. We givea mixed-integer program formulation of the clearing problem, and show that for concave bids, the program reduces to a linear program. We then show that the clearing problem for a subclass of concave bids is at least as hard as the decision variant of linear programming. Subsequently, we show that the clearing problem is much easier when bids are quasilinear---for surplus, the problem decomposes across charities, and for payment maximization, a greedy approach isoptimal if the bids are concave (although this latter problem is weakly NP-complete when the bids are not concave). For the quasilinear setting, we study the mechanism design question. We show that anex-post efficient mechanism is impossible even with only one charity and a very restricted class of bids. We also show that there may bebenefits to linking the charities from a mechanism design stand point.
- K. Arrow. The property rights doctrine and demand revelation under incomplete information. In M. Boskin, editor, Economics and human welfare. New York Academic Press, 1979.Google Scholar
- L. M. Ausubel and P. Milgrom. Ascending auctions with package bidding. Frontiers of Theoretical Economics, 1, 2002. No. 1, Article 1.Google Scholar
- Y. Bartal, R. Gonen, and N. Nisan. Incentive compatible multi-unit combinatorial auctions. In Theoretical Aspects of Rationality and Knowledge (TARK IX), Bloomington, Indiana, USA, 2003. Google ScholarDigital Library
- E. H. Clarke. Multipart pricing of public goods.Public Choice, 11:17--33,1971.Google ScholarCross Ref
- V. Conitzer and T. Sandholm. Complexity of mechanism design. In Proceedings of the 18th Annual Conference on Uncertainty in Artificial Intelligence (UAI-02), pages 103--110,Edmonton, Canada, 2002. Google ScholarDigital Library
- C. d 'Aspremont and L. A. Gérard-Varet. Incentives and incomplete information. Journal of Public Economics, 11:25--45, 1979.Google ScholarCross Ref
- M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1:237--267, 1976.Google ScholarCross Ref
- D. Goldburg and S. McElligott. Red cross statement on official donation locations. 2001. Press release, http://www.redcross.org/press/disaster/ds_pr/011017legitdonors.html.Google Scholar
- R. Gonen and D. Lehmann. Optimal solutions for multi-unit combinatorial auctions:Branch and bound heuristics. In Proceedings of the ACM Conference on Electronic Commerce (ACM-EC), pages 13--20, Minneapolis,MN,Oct.2000. Google ScholarDigital Library
- T. Groves. Incentives in teams. Econometrica, 41:617--631,1973.Google ScholarCross Ref
- L. Khachiyan. A polynomial algorithm in linear programming. Soviet Math.Doklady, 20:191--194, 1979.Google Scholar
- R. Lavi, A. Mu'Alem, and N. Nisan. Towards a characterization of truthful combinatorial auctions. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), 2003. Google ScholarDigital Library
- D. Lehmann, L. I. O 'Callaghan, and Y. Shoham. Truth revelation in rapid,approximately efficient combinatorial auctions. Journal of the ACM, 49(5):577--602, 2002. Early version appeared in ACMEC-99. Google ScholarDigital Library
- A. Mas-Colell, M. Whinston, and J. R. Green. Microeconomic Theory. Oxford University Press, 1995.Google Scholar
- R. Myerson and M. Satterthwaite. Efficient mechanisms for bilateral trading. Journal of Economic Theory, 28:265--281,1983.Google ScholarCross Ref
- G. L. Nemhauser and L. A. Wolsey.Integer and Combinatorial Optimization. John Wiley & Sons, 1999. Section 4, page 11. Google ScholarDigital Library
- N. Nisan. Bidding and allocation in combinatorial auctions.In Proceedings of the ACM Conference on Electronic Commerce (ACM-EC), pages 1--12, Minneapolis, MN, 2000. Google ScholarDigital Library
- N. Nisan and A. Ronen. Computationally feasible VCG mechanisms.In Proceedings of the ACM Conference on Electronic Commerce (ACM-EC), pages 242--252,Minneapolis,MN,2000. Google ScholarDigital Library
- D. C. Parkes. iBundle: An efficient ascending price bundle auction.In Proceedings of the ACM Conference on Electronic Commerce (ACM-EC),pages 148--157, Denver, CO, Nov. 1999. Google ScholarDigital Library
- M. H. Rothkopf, A. Pekeč, and R. M. Harstad. Computationally manageable combinatorial auctions. Management Science, 44(8):1131--1147,1998. Google ScholarDigital Library
- T. Sandholm. Algorithm for optimal winner determination in combinatorial auctions. Artificial Intelligence, 135:1-54, Jan. 2002. Conference version appeared at the International Joint Conference on Artificial Intelligence (IJCAI), pp.542--547, Stockholm, Sweden, 1999. Google ScholarDigital Library
- T. Sandholm, S. Suri, A. Gilpin, and D. Levine. CABOB: A fast optimal algorithm for combinatorial auctions.In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI),pages 1102--1108,Seattle,WA, 2001. Google ScholarDigital Library
- J. Tagliabue. Global AIDS Funds Is Given Attention, but Not Money. The New York Times, June 1, 2003. Reprinted on http://www.healthgap.org/press releases/a03/060103 NYT HGAP G8 fund.html.Google Scholar
- W. Vickrey. Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance, 16:837,1961.Google Scholar
- P. R. Wurman and M. P. Wellman. AkBA: A progressive,anonymous-price combinatorial auction. In Proceedings of the ACM Conference on Electronic Commerce (ACM-EC), pages 21--29,Minneapolis, MN, Oct.2000. Google ScholarDigital Library
- M.Yokoo.The characterization of strategy/false-name proof combinatorial auction protocols:Price-oriented, rationing-free protocol.In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI),Acapulco,Mexico,Aug. 2003. Google ScholarDigital Library
Index Terms
- Expressive negotiation over donations to charities
Recommendations
Expressive markets for donating to charities
When donating money to a (say, charitable) cause, it is possible to use the contemplated donation as a bargaining chip to induce other parties interested in the charity to donate more. Such negotiation is usually done in terms of matching offers, where ...
Correcting vindictive bidding behaviors in sponsored search auctions
In this study, we aim to develop a pricing mechanism that reduces the effects resulted by vindictive advertisers who bid on sponsored search auctions run by search engine providers. In particular, we aim to ensure payment fairness and price stability in ...
Competing sellers in online markets: reserve prices, shill bidding, and auction fees
AAMAS '06: Proceedings of the fifth international joint conference on Autonomous agents and multiagent systemsIn this paper, we consider competition between sellers offering similar items in concurrent online auctions, where each seller must set its individual auction parameters (such as the reserve price) in such a way as to attract buyers. We show that there ...
Comments