Disclaimer: This article is part of the Industry 4.0 Open Educational Resources (OER) Publication Initiatives jointly supported by Duke Learning Innovation Center and DKU Center for Teaching and Learning under the Carrying the Innovation Forward program. This article belongs to the OER Series No. 2 Computational Economics Spring 2022 collection. The Spring 2022 collection is partly supported by the Social Science Divisional Chair’s Discretionary Fund to encourage faculty engagement in undergraduate research and enhance student-faculty scholarly interactions outside of the classroom. The division chair is Prof. Keping Wu, Associate Professor of Anthropology at Duke Kunshan University. The co-author Xinshi Ma was the Teaching and Research Assistant for Prof. Luyao Zhang in the course: COMPSCI/ECON 206 Computational Microeconomics at Duke Kunshan University Spring 2022, when he completed the joint article. The co-authors are forever indebted to Prof. Vincent Conitzer, who presented “Computer Science Meets Economics” as a distinguished guest lecture for this course on Apr. 19, 2022.

Prof. Vincent Conitzer’s work impacts our world both directly through innovations that have substantial industry applications and policy insights that are crucial to responsible technological development. His innovations and policy impact follow two main veins: combinatorial exchanges and AI ethics. In this article, we are going to explore some of Prof. Conitzer’s contributions to resolving real-world problems and addressing policy challenges.

Part I: Combinatorial Exchanges

A combinatorial exchange is an exchange where buyers and sellers can bid on bundles (subsets) of goods (Kothari, Sandholm, and Suri 2002; Cramton, Steinberg, and Shoham 2006). It was first proposed by Rassenti, Smith, and Bulfin in 1982 to solve the problem of allocating airport time slots. A combinatorial exchange is essentially a two-sided combinatorial auction, where the exchange generalizes the auction mechanism to the setting with multiple buyers and sellers, whereas a one-sided combinatorial auction would only contain sellers or buyers that bid on a bundle of items. Unlike classic single-item auctions, combinatorial auctions facilitate bids on a subset of items. 

Combinatorial exchanges are widely applied in real-world scenarios such as commodity exchanges, stock exchanges, and resource allocation problems such as trading of airport spots (Pellegrini, Castelli, and Pesenti 2012), and fishing catch share allocation (Bichler, Fux, and Goeree 2018). Prof. Conitzer’s research designs effective combinatorial exchanges and resolves various challenging problems surrounding mechanism design. Although combinatorial exchanges maximize efficiency by optimizing allocation, there nonetheless exist questions in real-world situations about algorithmic fairness (Conitzer 2018) and ethical implications. This is very much analogous to a combinatorial exchange being able to solve positive economic problems but unable to account for normative economic problems. The problem surrounding efficiency and ethics are well encapsulated in, for example, organ exchanges. 

In Figure 2, we depict the organ exchange process and an example of organ exchange. The fundamental issue organ changes seek to overcome is the incompatibility of organs between donors and patients. For example, patient 1 needs a kidney transplant and brings in a family member, donor 1, who is willing to donate an organ to patient 1. However, donor 1’s kidney is incompatible with patient 1, so a kidney transplant cannot be directly executed. Therefore, patient 1 and donor 1 would proceed to a kidney exchange in search of a patient donor pair that they are cross-compatible with (donor 1 is compatible with patient 2, and donor 2 is compatible with patient 1). Then, the patient donor pairs would complete the exchange of organs. When multiple parties participate in such a kidney exchange, the exchange would seek to maximize the number of pairs matched by solving a combinatorial optimization problem. Although kidney exchanges can maximize efficiency in the realm of positive economics by maximizing the number of exchanges completed, a simple exchange mechanism does not take into account fairness and ethical issues in the realm of normative economics. Prof. Conitzer’s two main veins of work intersect here. In the next section, we will explore AI ethics and the “normative” side of algorithms and AI.

Part II: AI Ethics

AI ethics can be roughly defined as a system of moral principles and techniques converging around five ethical principles of transparency, justice, fairness, non-maleficence, responsibility, and privacy in the use of AI technology (Jobin, Ienca, and Vayena 2019). 

• Transparency: including the explainability, interpretability, or other acts of communication and disclosure that may enable understanding and oversight of AI systems. 

• Justice and fairness: the prevention of unwanted bias and discrimination along with the improvement in diversity, inclusion, and equality among AI agents, especially in the process of development and training.  

• Non-maleficence: describes the safety and security of AI where AI systems do not cause foreseeable or unintentional harm.  

• Responsibility: calls for acting with integrity, the attribution of responsibility, and the clarification of legal liability.

• Privacy: the protection of privacy among users in the development and implementation of AI systems, often related to data privacy and data security.

AI ethics and responsible AI are top priorities in today’s AI research as the application of AI expands into all spheres of our world. Morals and expectations of behavior need to be instilled into newly developed AI agents as they increase their interactions with human agents. There exists a need for established principles and guidelines surrounding the responsible development of AI. 

For example, in recent years, AI has substantially impacted organ exchanges (Purtil 2018). Although computer scientists and economists have developed successful algorithms that match donors with patients, saving thousands of lives, the fundamental question of who should get the organ still remains. Is it the patients who have been waiting for the longest? Or is it those that have the best chance of survival? Or is it those that need the organ the most in order to survive? Such problems are traditionally resolved by medical professionals through the lens of human ethics. AI is now involved in the process, not only to make matches, but also to make judgments. Problems like these are increasingly prevalent as the use of computational algorithms and AI expands into various spheres of our decision process. Established ethical guidelines for AI agents to operate within are crucial for their responsible use.

Part III: Vince’s Innovation in Combinatory Exchange and AI Ethics

Prof. Conitzer’s work and innovations are at the forefront of challenging and life-changing situations that intersect combinatorial exchanges and AI ethics in instances such as organ exchanges. Beyond various works in academic research around combinatorial auctions and exchanges (Conitzer and Sandholm, 2004; Conitzer, Sandholm, and Santi, 2005), Prof. Conitzer is also the co-inventor of 6 US patents that are related to the design and implementation of combinatorial exchanges (all are owned by CombineNet, Inc.). These innovations improve the implementation and efficiency of combinatorial exchanges. For example, the Method and Apparatus for Conducting a Dynamic Exchange and Dynamic Exchange Method and Apparatus innovation set up a computational framework that processes bids with a set of rules that allows participants to update bids after each allocation cycle. These dynamic combinatorial exchange designs are implemented in real-world situations. 

Below is the list of Prof. Conitzer’s Patents:

• Items Ratio Based Price/Discount Adjustment in a Combinatorial Auction. Tuomas Sandholm, David Levine, David Parkes, Subhash Suri, Vincent Conitzer, Robert Shields, Yuri Smirnov. (CombineNet, Inc.) United States Patent 8,195,524, June 5, 2012. [JUSTIA Patents]

• Overconstraint Detection, Rule Relaxation and Demand Reduction in Combinatorial Exchange. Tuomas Sandholm, David Levine, David Parkes, Subhash Suri, Vincent Conitzer, Robert Shields, Yuri Smirnov. [JUSTIA Patents](CombineNet, Inc.) United States Patent 8,190,490, May 29, 2012.

• Bid Modification Based on Logical Connections between Trigger Groups in a Combinatorial Exchange. Tuomas Sandholm, David Levine, David Parkes, Subhash Suri, Vincent Conitzer, Robert Shields, Yuri Smirnov. (CombineNet, Inc.) United States Patent 8,190,489, May 29, 2012. [JUSTIA Patents]

• Method of Determining an Exchange Allocation That Promotes Truthful Bidding and Improves the Obtainment of Exchange Objectives. Vincent Conitzer and Tuomas Sandholm. (Com- bineNet, Inc.) United States Patent 8,060,433, November 15, 2011. [JUSTIA Patents]

• Method and Apparatus for Conducting a Dynamic Exchange. Tuomas Sandholm, David Levine, David Parkes, Subhash Suri, Vincent Conitzer, Robert Shields, and Yuri Smirnov. (CombineNet, Inc.) United States Patent 7,577,589, August 18, 2009. [JUSTIA Patents]

• Dynamic Exchange Method and Apparatus. Tuomas Sandholm, Richard James McKenzie Jr., David Levine, David Parkes, Subhash Suri, Vincent Conitzer, Robert Shields, Benjamin Schmaus, and Christopher Cole. (CombineNet, Inc.) United States Patent 7,499,880, March 3, 2009. [JUSTIA Patents]

In the field of AI ethics, Prof. Conitzer has published various works in specific areas such as mechanism design and algorithmic fairness (Kramer et al. 2018) and bioethics (Skorburg, Sinnott-Armstrong, and Conitzer 2020; Afnan et al. 2021). He has spoken at numerous conferences about the ethics and fairness of algorithms and AI. Prof. Conitzer is also the Head of Technical AI Engagement at the Institute for Ethics in AI at Oxford University, an interdisciplinary initiative that seeks to promote AI ethics as a field globally, and will lead the Foundations of Cooperative AI Lab at Carnegie Mellon University starting this fall.

References:

Kothari, Anshul, Tuomas Sandholm, and Subhash Suri. 2002. “Solving Combinatorial Exchanges: Optimality via a Few Partial Bids.” American Association for Artificial Intelligence. https://www.cs.cmu.edu/~sandholm/partialBids.aaai02WS.pdf.

Bichler, Martin, Vladimir Fux, and Jacob K. Goeree. 2018. “Designing Combinatorial Exchanges for the Reallocation of Resource Rights.” Proceedings of the National Academy of Sciences 116 (3): 786–91. https://doi.org/10.1073/pnas.1802123116.

‌Pellegrini, Paola, Lorenzo Castelli, and Raffaele Pesenti. 2012. “Secondary Trading of Airport Slots as a Combinatorial Exchange.” Transportation Research Part E: Logistics and Transportation Review 48 (5): 1009–22. https://doi.org/10.1016/j.tre.2012.03.004.

Jobin, Anna, Marcello Ienca, and Effy Vayena. 2019. “The Global Landscape of AI Ethics Guidelines.” Nature Machine Intelligence 1 (9): 389–99. https://doi.org/10.1038/s42256-019-0088-2.

 Cramton, Peter C, Richard Steinberg, and Yoav Shoham, eds. 2006. Combinatorial Auctions. Cambridge, Mass.: Mit Press.

 Vincent Conitzer and Tuomas Sandholm. 2004. “Self-Interested Automated Mechanism Design and Implications for Optimal Combinatorial Auctions.” Proceedings of the fifth ACM Conference on Electronic Commerce. https://dl.acm.org/doi/pdf/10.1145/988772.988793

Vincent Conitzer, Tuomas Sandholm, and Paolo Santi. 2005. “Combinatorial Auctions with K-wise Dependent Valuation.” Proceedings of the Twentieth National Conference on Artificial Intelligence. https://users.cs.duke.edu/~conitzer/kwiseAAAI05.pdf

 Skorburg, Joshua August, Walter Sinnott-Armstrong, and Vincent Conitzer. 2020. “AI Methods in Bioethics.” AJOB Empirical Bioethics 11 (1): 37–39. https://doi.org/10.1080/23294515.2019.1706206.

Kramer, Max F., Jana Schaich Borg, Vincent Conitzer, and Walter Sinnott-Armstrong. 2018. “When Do People Want AI to Make Decisions?” Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, December. https://doi.org/10.1145/3278721.3278752.

‌Afnan, Michael Anis Mihdi, Cynthia Rudin, Vincent Conitzer, Julian Savulescu, Abhishek Mishra, Yanhe Liu, and Masoud Afnan. 2021. “Ethical Implementation of Artificial Intelligence to Select Embryos in in Vitro Fertilization.” Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, July, 316–26. https://doi.org/10.1145/3461702.3462589.

“Vincent Conitzer Inventions, Patents and Patent Applications - Justia Patents Search.” n.d. Patents.justia.com. Accessed May 2, 2022. https://patents.justia.com/inventor/vincent-conitzer.

‌Conitzer, Vincent. 2018. “Designing Algorithms and the Fairness Criteria They Should Satisfy.” Communications of the ACM 61 (2): 92–92. https://doi.org/10.1145/3166066.

Rassenti, S. J., V. L. Smith, and R. L. Bulfin. 1982. “A Combinatorial Auction Mechanism for Airport Time Slot Allocation.” The Bell Journal of Economics 13 (2): 402. https://doi.org/10.2307/3003463.

The Glossary Table